2

誰もがコンピュータサイエンスのスケジュールの問題に精通しています。
私はこの問題のアルゴリズムを求めていません。

学校での学期の個人的なスケジュールを作成したいだけです

。これがあなたが想定できることです。

  • 私の大学の誰かがすでにクラスを作成し、教師、部屋などを割り当てました。したがって、クラスはすでにそこにあり、選択する準備ができています。
  • クラスの比較的小さな部分だけが私に利用可能です。25クラスと言います。
  • 私は学期ごとに5つのクラスを受講する必要があります（多かれ少なかれこれを単純にしましょう）

    私が欲しいのは、有効なスケジュール、さらに重要なことに、最適なスケジュールを作成する方法に関するいくつかのヒント/手がかりです。
    そういえば、最適なスケジュールは？
    私の個人的なケースでは、これらのクラスは2つの異なる学部からのものですが、次のような情報を含むcsvファイルを作成することができました。

    M               
16:35:00 17:25:00PHIL375実存主義。
14:35:00 15:55:00COMP350数値計算。
14:35:00 15:55:00COMP208エンジニアリングのコンピュータ。
14:35:00 15:25:00PHIL306心の哲学。
14:35:00 15:25:00PHIL200哲学入門
..等

    ご覧のとおり、すべてが開始時間（反転）でソートされていますが、競合があります。他のすべての曜日についても同じです。
    有効/最適なスケジュールを作成するにはどうすればよいですか？何を考えればいいですか？

    詳細情報：

    これは、私が考慮すべきことについて最初に考えたものです。

  • 私にとっての優先事項の1つは、できるだけ遅くクラスを開くことです。したがって、月曜日、水曜日、金曜日に可能な最新の3つのクラスと、火曜日、木曜日に2つのクラスを選択します。[これを実装する方法については、コメントを参照してください]
  • 別の解決策は、クラス間（またはその逆）の「ブレーク」を最小限に抑えることです。
  • もう1つは、可能な限り早いクラスです。
  • もう1つの優先事項は、同じ日に1つの学部のすべてのクラスを取得し、さらに別の1つのクラスをA学部の1クラス、次にB学部の1クラスにすることです。
    何かが足りない？

    • 4

    1 に答える 1

    2

    この規模の場合-単純なプログラムの力ずくの解決策を避けようとはしません。

    25のリストから5つのコースを選択するさまざまな可能性があります25!/(20!*5!)=53130。それらすべてをチェックし、最良のものを取得するだけで、最適なソリューションが保証されます。このスケールの実行時間も、最新のマシンでは問題になりません。

    バックトラッキングソリューションは非常に単純です。追加するコースを「推測」し、リストがいっぱいになるまで再帰的に呼び出し、ソリューションを評価します。再帰から戻ったら、コースを選択する別の可能性を確認してください。

    擬似コード：

    best = 0
bestSol = nil
findCalendar(courses,candidate,i):
  if (take.size() == 5):
      t = evaluate(candidate)
      if (t > best):
          best = t
          bestSol = copy(candidate)
      return
  else if (i == courses.size()):
      //another stop clause, for non-feasible solutions (less then 5 were selected)
      return 
  for each j in range(i,courses.size()):
      candidate.add(courses[j]) //add this course to the candidate
      fidnCalendar(courses,candidate,j+1) //recurse to find the next courses for this candidate
      candidate.removeLast() //cklean up environment before next candidates

    findCalendar(myCourses,[],0)アルゴリズムが完了すると、で呼び出す-bestSol最高のカレンダーを保持し、その値は次のようになりますbest

    于 2012-08-30T06:11:20.930 に答える