0

私は、教師が週に 1 回 (音楽のレッスンなどで) 個別に教える生徒数を設定する、教育の時間割を作成しようとしています。生徒はローテーションする必要があります。つまり、週ごとに同じ時間に教えてはいけません (私が「ローテーション期間」と呼んでいる、同時にレッスン間に許容される最小のギャップ)。最も単純な形式を考え出すのは簡単です:

        Week 1  Week 2  Week 3  Week 4  Week 5  Week 6
10.00   Alice   Edgar   David   Charles Bertha  Alice
10.30   Bertha  Alice   Edgar   David   Charles Bertha
11.00   Charles Bertha  Alice   Edgar   David   Charles
11.30   David   Charles Bertha  Alice   Edgar   David
12.00   Edgar   David   Charles Bertha  Alice   Edgar

しかし、ユーザーがルールを追加できるようにしたいと考えています。たとえば、Alice は 3 週目に 10.30 または 11.00 を作ることはできません。単純なバックトラック ループから始めましたが、可能性の数が多すぎるため、これが実現不可能であることにすぐに気付きました。私はあまり経験豊富なプログラマーではありませんが、これが私を高度なプログラミング手法に導く可能性があることを認識していますか. しかし、誰かが問題にアプローチする方法についていくつかのアイデアを私に与えることができれば、私はとても感謝しています. もちろん、私は助けを求めて周りを見回しましたが、議論のほとんどは、学校全体の時間割を作成するというより複雑なタスクに関するものであるようです. 遺伝的プログラミングはこれを調べるものですか？PHPを使用してプログラムをWebページとして構築しています。

4

3 に答える 3

0

これをアルゴリズムで解決すると、計算コストが非常に高くなる可能性がありますが、例の6人のような少数の学生の場合は可能です。

（より一般的な時間割の問題と比較して）あなたに有利に働くことの1つは、学生が毎週異なる時間にレッスンを受けなければならないという制約です. これにより、検索スペースが大幅に削減されます。可能な順列の数は次のとおりです。

n! * (n - 1)!

はn生徒数であり、時間割が生成された週数でもあります。

この問題を解決するには、すべての有効なタイムテーブルのセットを生成し、生成された各タイムテーブルを学生が指定した制約のセットと照合します。

おそらく、これらのタイムテーブルを保存する必要はありません。どの制約にも違反しないタイムテーブルを生成する場合は、それを公開します。そうであれば、次の時刻表にスキップしてください。

多くの制約がない場合、このメソッドは有効な timetable をすばやく生成する必要があります。一方、時間割を不可能にするのに十分な制約がある場合、時間割が有効でないことを確認するために膨大な数のチェックが必要になります (6 人の学生の場合、86,400 のチェックがありますが、これは学生の数とともに急速に増加します)。

この問題を解決するために遺伝的計算を使用するというあなたの考えは、あなたの要件を考えるとおそらくうまくいかないでしょう。GC は、問題の適切な解決策をすばやく見つけるのに優れています (時間割の問題でうまく使用されています) が、解決策が存在しないことを証明するのには役に立ちません。

于 2013-11-14T12:20:59.040 に答える
0

各生徒が毎週来る必要があり、毎週同じ時間に来ることはないと想定している場合、数独と非常によく似たルールセットを持つことになります。この場合、その問題を解決するために使用されたアルゴリズムのいくつかを調べることを検討することをお勧めします。これは、ソリューションの探索とルールに関する限り、これらのアルゴリズムがほぼ同じであるためです。

数独ソルバーが9 x 9で機能し、数分の一で解決できることを私は知っています。クラス/週の規模によっては、ヒューリスティック ソルバー(または遺伝的アルゴリズムなど)を使用しなくても、そこにある手法を適用できる場合があります。私はwikiを提案し、 backtracking、正確なカバー、または (彼らが呼ぶもの)ブルートフォースを調べます。

それでも解決しない場合。最終的なスケジュールに期待するルールを明確にできますか? 「デフォルト」スケジュールからスワップの数を最小限に抑えるなど、またはそのようなものはありますか? また、それを数週間の問題として見ている理由はありますか? 問題を週ごとの問題に減らして、週の間にリンク/接続をなくすことはできますか? 最後に、例外をどのように表現していますか? どの生徒にとってどの時間が悪いかをどのように示していますか?

于 2013-11-12T20:35:04.460 に答える