1

問題は次のようなものです。

学校にはさまざまなクラスがあります。各クラスには週ごとのスケジュールがあります (英語 8 時間、数学 6 時間、アート 2 時間など)。各教師は、クラスのサブセットで一定の時間を持っています。（学校はほとんどどこでもそうだと思います）。

追加の制約を追加できます。たとえば、次のようになります。

  1. 先生 X は月曜日に出勤しません
  2. 教師 Y は、特定のクラスで連続 2 時間を必要とします。

目標は、制約に対してコスト関数を最適化するスケジュールを見つけることです。

最後に、これは私が推測する古典的な NP 問題です。これは、空間状態検索を使用して解決できます (スマートな検索方法を使用して、考えられるすべての組み合わせを試し、可能な限り最良の解決策を選択します)。

  • これは実現可能ですか？(組み合わせは膨大です。10 クラス、クラスあたり 30 時間、7 つの科目の場合、実質的な剪定が可能であっても、約 10^253 です。SA​​T ソルバーはそのようなものを処理できると思います)。

  • 概算であっても、検索を完了するための代替手段はありますか?

4

1 に答える 1

1

これは制約充足問題です。リンクで述べたように、これらを解決する方法の 1 つは、 min-conflictsやforwardchingなどのローカル検索方法を使用することです。最適なソリューションが保証されているわけではありませんが、通常、比較的短い時間で「適切な」ソリューションが得られます。

たまたま Prolog を使用している場合、clpfd ライブラリ (Constraint Logic Programming over Finite Domains) は非常に強力です。

于 2012-06-22T15:55:04.217 に答える