計画ツールのアルゴリズム

Question

私は、地元の学校の簡単な計画ツールとして機能する必要がある小さなソフトウェア アプリケーションを作成しています。解決する必要がある「問題」はかなり基本的なものです。つまり、教師はすべての子供たちの保護者と話をする必要があります。ただし、もちろん、異なるグループに兄弟姉妹がいる子供もいます。そのため、両親が午後 6 時に話し、午後 10 時に別の話をするという状況を避けるために、これらの話しは隣同士でスケジュールする必要があります。したがって、要するに、次のコレクションが与えられると、 n 一部の子供には 1 人以上の兄弟または姉妹がおり、これらの子供たちのすべての話が互いに隣り合って計画されるスケジュールが作成されます。

さて、この問題は非常に簡単に解決できるかもしれませんが、一方で、これはかなり複雑な問題になる可能性があり、ある種のアルゴリズムが必要であり、それを使用して解決できるのではないかと感じています。エレガントに。しかし、私は正しいでしょうか？ありますか？見てきました ハンガリー語 しかし、それはこの特定の問題にはまったく当てはまりません。

編集：言い忘れていましたが、すべての交渉には同じ時間がかかります。

ありがとう！

Answer 1

私はそれが非常に簡単だと思います。

まずグループ彼らは両親を共有するため一緒に属している子供たち。ランダムとして残りをスケジュールし、連続してグループ内の子供のスケジュールを設定します。

それとは問題を容易に抽象化する別の方法は、親の視点から見て、「子」として兄弟や姉妹を見ると、彼らに多くの時間を与えることです。次に、あなただけランダムに両親をスケジュールすることができますが、（彼らは複数のchilderenを持っているので）いくつかのより多くの時間を必要とします。

Answer 2

1 つのアプローチは、宣言型制約言語で問題を定義し、それによって問題を解決させることです。最後にこれを行ったときに使用したのは、 ECLiPSe, これは、制約によって問題空間を定義し、それらの制約を満たす許容値を見つけさせる気の利いた小さな言語です。

たとえば、次の 2 つのクラスの制約があると思います。

1. 教師は一度に1つの会議しか持たないかもしれません
2. 同じ家族のすべての学生は、 連続したスロットがある

ECLiPSe でこれらを定義すると、要件を満たす各生徒の値が計算されます。この方法を使用すると、必要に応じて制約を簡単に追加することもできます。たとえば、スロット Y には教師が不在である、または教師が交代で管理業務を行う必要がある、などと言うのは簡単です。

Answer 3

この種類は、問題の「バックパックのアルゴリズム」タイプのように感じています。あなたは家族が一緒にそして適切にスロットを満たすグループにする必要があります。

あなたは、「バックパックのアルゴリズムを」Googleの場合は、

、あなたの頭の回転を行うのに十分な書き込みアップし、また、いくつかの良いコード化されたソリューションが表示されます。

Answer 4

私は、各話はそれぞれの活動は、あなたがコンピュータサイエンスの研究活動選択アルゴリズムを使用することができ、開始時間と終了時間を持っている「活動」に減らすことができればと思います。それは貪欲なアプローチに基づいており（nは活動の数である）O（N）で解決することができます。あなたはより多くの情報ここに見つけることができます。私はあなたが同じタイプの活動として兄弟/姉妹の問題を軽減することができるようにここに前処理を行うために持っている必要があります確信しています。