私は、地元の学校の簡単な計画ツールとして機能する必要がある小さなソフトウェア アプリケーションを作成しています。解決する必要がある「問題」はかなり基本的なものです。つまり、教師はすべての子供の親と話をする必要があります。ただし、もちろん、兄弟姉妹が別のグループにいる子供もいます。そのため、両親が午後 6 時に話し、午後 10 時に別の話しをするという状況を避けるために、これらの話し合いを隣り合わせにスケジュールする必要があります。つまり、 1 人以上の兄弟または姉妹がいるn人の子供のコレクションが与えられた場合、これらの子供のすべての話が隣り合って計画されるスケジュールを生成します。
さて、問題は非常に簡単に解決できるかもしれませんが、一方で、これはかなり複雑な問題になる可能性があり、何らかのアルゴリズムが必要であり、解決できると感じています。エレガントに。しかし、私は正しいですか？ある？ハンガリーのアルゴリズムを見てきましたが、この特定の問題にはまったく当てはまりません。
編集: 言い忘れていましたが、すべてのトークには同じ時間がかかります。
ありがとう！
1 つのアプローチは、宣言型の制約言語で問題を定義し、それによって問題を解決させることです。前回これを行ったとき、私はECLiPSeを使用しました。これは、制約によって問題空間を定義し、それらの制約を満たす許容値を見つけさせる気の利いた小さな言語です。
たとえば、次の 2 つのクラスの制約があると思います。
ECLiPSe でこれらを定義すると、要件を満たす生徒ごとに値が計算されます。このようにすれば、必要に応じて制約を簡単に追加することもできます。たとえば、スロット Y では教えることができない、または教師が交代で管理作業を行う必要があるなどと簡単に言えます。
とても簡単だと思います。
最初に、親が同じであるために一緒に属する子供をグループ化します。グループ内の子を連続してスケジュールし、残りをランダムにスケジュールします。
それを抽象化して問題を簡単にするもう1つの方法は、親の視点から見て、兄弟姉妹を「子供」として見て、より多くの時間を与えることです. 次に、親を無作為にスケジュールすることができますが、一部にはもっと時間が必要です (子供が複数いるため)。
それぞれの話が、開始時刻と終了時刻を持つ「活動」に還元できれば、コンピューター サイエンスで研究されている活動選択アルゴリズムを使用できると思います。これは貪欲なアプローチに基づいており、O(n) (n はアクティビティの数) で解決できます。詳細については、こちらをご覧ください。兄弟/姉妹の問題を同じタイプの活動として減らすことができるようにするには、ここで前処理を行う必要があると確信しています.
これは、「バックパック アルゴリズム」タイプの問題のように感じます。家族のメンバーをまとめてグループ化し、スロットを適切に埋める必要があります。
「バックパックアルゴリズム」をグーグルで検索すると、頭が回転するのに十分な記事と、いくつかの優れたコード化されたソリューションが表示されます。