タイムテーブルの制約を計算するためのアルゴリズム

Question

私は仮説的な問題を考えており、アルゴリズム的な観点から問題の解決方法を指導しています。

問題：

は大学を考えてみましょう。次のオブジェクトがあります。

• 教員。各職員は1つ以上の論文を教える。
• 学生。各学生は1つ以上の論文を取ります。
• お部屋。部屋には特定の数の学生がいて、特定の種類の機器が含まれています。
• 論文。特定の種類の機器を必要とし、毎週一定の時間が必要です。
  ：（各論文に登録され、そしてどのようなスタッフが、それぞれの紙を教えるために割り当てられているどのように多くの学生IE-）入学に関する情報、どのように私は、以下の制限に従う時刻表を計算することができますを考えると

スタッフはすぐに1つのことを教えることができます。

学生は一度に1枚の用紙にしか出席できません。

部屋には特定の数の学生しか収容できません。

特定の種類の装置を必要とする用紙は、その種類の装置を提供する部屋でのみ保持することができます。

営業時間は、月曜日〜金曜日、8-12、1-5です。

ディスカッション：現実に

私は先に概説状況にあまり関心がないんだ - それは私が好奇心だ問題の一般的なクラスです。一見、私は遺伝的アルゴリズムに適しているように思えますが、そのようなアルゴリズムのための適合関数は信じられないほど複雑になります。

このような制約条件を満たす問題を解決しようとするとよいアプローチはありますか？

私はおそらく生徒の数が生徒の数が増えるにつれて、不可能な状況につながる論文の組み合わせを取るかもしれないので、これを完全に解決する方法はないと思います。

Answer 1

遺伝的アルゴリズムにとどまっているにもかかわらず、私はこのためのフィットネス機能は非常に複雑ではないと考えています。

基本的には、それぞれの制約（5つしかない）の候補解（エンコーディングに関係なく）をチェックし、制約が満たされていないときに重みが合計スコアに加算されるように重みを割り当てますフィットネスを表す可能性があります。

このようなシナリオでは、フィットネス機能を最小限に抑えることができます（可能な限り最良のフィットネスが0であるため、すべての制約が満たされるため）。

はエンコードが考え出すのビットがかかりますが、それを行うの後、私はもちろん:)私はNP-ハードの問題を好きではない一部の人を推測

Answer 2

この問題の非常に制限されたバージョンは、NP-Completeです。

正確に1人の学生が紙を取ることができる場合を考えてみましょう。

ここで、指定された時間帯（1日中紙を教えている）では、部屋と論文と生徒が3つの部分グラフに構成され、紙と学生の間にエッジがありますそれを取る。紙とその可能性のある部屋の間にもエッジを追加します。

ここで、3 Dimensional matching problemが問題のインスタンスであることがわかります。その特定のタイムスロットに重ならない（学生、紙、部屋）組み合わせを選択する必要があります。

一般的な問題については、ヒューリスティックのほうがよいでしょう。申し訳ありませんが、私はそこにお手伝いできません。

希望に役立ちます。