2

私は、親と教師の会議をスケジュールするためのプログラムを書くことを志願しました。校長は、保護者に、英語と数学の先生を (同時に)訪問できる日時を 3 つ選択するよう求めています。

すべての保護者が 3 つの日時を選択したら、できるだけ多くの保護者が両方の教師と会うことができるように、保護者と教師の会議をスケジュールする最適な方法を見つけなければなりません。

(時間の都合で数学の先生が会議に出席できない場合、保護者は英語の先生とのみ会うことになります)

NP型の問題はよくわからないのですが、「最適」と「スケジュール」という言葉を一緒に聞くと不思議に思うのですが…

校長先生にはそれはできないと言いましたが、NPコンプリートなのか知りたかったのです。もしそうなら、以下があると仮定します：

  • 500人の親
  • 15名の英語教師
  • 数学教師5人
  • 25 の日時から選択

おばあちゃんのコンピューターで、これを数秒、数分、または数時間で正しく解決できますか?

4

1 に答える 1

0

あなたの質問に対する部分的な回答と、さまざまなシナリオを試すことができるシミュレーションがあります。これが私の作業中の（ただし変更可能な）仮定です。

  • パラメータはあなたがリストしたとおりです
  • 親によるセッション時間の選択は、べき乗則 (ベンフォード分布) に従います。これは、好みの予想される不均一性をモデル化するためです。
  • 実行にもよりますが、「非妥協的」で 1 回のセッションしか参加できなかった保護者が 20 人ほどいました。
  • 相関関係が高いと推定されるため、各英語教師には対応する数学教師が 1 人だけいますが、どれくらい高いかはわかりません。このコードは、0 から 1 までの任意の相関係数を処理できます。
  • もっともらしいシミュレートされた親 ('smith' .. 'atkins')、教師、時間の選択、および満足のいく結果の生成からのシバン全体は、midling マシン (5300 BogoMIPS ) で 300 ミリ秒かかりました。

最初のパスでは、すべての親の最初の選択が 1 つのセッションで最大 11 人の親に対応できるため、私の 2 次最適化は効果を発揮しませんでした。この結果は、平均親グループが 3 人以下の時間枠の約半分に出席しなければならなかった教師にとって、最適ではありませんでした。

コードは約 125 行なので、関心があれば公開できます。

于 2010-08-20T04:57:28.380 に答える