私は現在、大学の学生が受講したいコースに基づいて有効なスケジュールを自動的に生成できるようにする Web サイトに取り組んでいます。
サイト自体に取り組む前に、コースを効率的にスケジュールする方法の問題に取り組むことにしました。
いくつかの説明:
私たちの大学の各コース (他のすべての大学もそうだと思います) は、1 つまたは複数のセクションで構成されています。たとえば、微積分 I には現在 4 つのセクションがあります。これは、セクションの量、およびコースにラボがあるかどうかに応じて、スケジュール プロセスに大きな影響を与えることを意味します。
本学の科目は、科目略称と科目コードの組み合わせで表されます。微積分 I の場合: MATH 1110.
CRN はセクション固有のコードです。
私が勉強している大学は混合ではありません。つまり、男性と女性は (ほぼ) 別々のキャンパスで勉強しています。ほとんどというのは、キャンパスが二つに分かれているということです。
datetimes および timeranges dict は、実際のボトルネックであった datetime.datetime.strptime() の呼び出しを減らすことを目的としています。
私の最初の試みは、30 個のスケジュールが見つかるまで継続的にループするアルゴリズムで構成されていました。スケジュールは、入力されたコースの 1 つからランダムにセクションを選択し、残りのコースからセクションを配置して有効なスケジュールを構築しようとすることによって作成されました。すべてのコースがスケジュールに収まらない場合、つまり競合があった場合、スケジュールは破棄され、ループが続きました。
明らかに、上記の解決策には欠陥があります。アルゴリズムの実行に時間がかかりすぎ、ランダム性に依存しすぎていました。
2 番目のアルゴリズムは、古いアルゴリズムとは正反対のことを行います。まず、itertools.product() を使用して、可能なすべてのスケジュールの組み合わせのコレクションを生成します。次に、スケジュールを繰り返し処理し、無効なスケジュールを除外します。さまざまなセクションを確保するために、スケジュールの組み合わせは検証前にシャッフル (random.shuffle()) されます。ここでも、多少のランダム性が含まれます。
少し最適化した後、5 つのコースで構成される平均的なスケジュールでスケジューラを 1 秒未満で実行することができました。それは素晴らしいことですが、コースを追加し始めると問題が始まります。
参考までに、特定の入力セットを提供すると、可能な組み合わせの量が非常に多くなり、 itertools.product()が妥当な時間内に終了せず、その過程で 1GB の RAM を消費します。
明らかに、これをサービスにするには、より高速で効率的なアルゴリズムが必要になります。オンラインと IRC で登場した 2 つは、動的プログラミングと遺伝的アルゴリズムです。
概念を正しく理解していれば、動的計画法をこの問題に適用することはできません。なぜなら、問題をより小さな部分に分割し、これらの部分を個別に解決し、これらの部分の解決策をまとめて完全な解決策を形成する必要があるからです。私が見る限り、これはここには当てはまりません。
遺伝的アルゴリズムに関しては、私はそれらをあまり理解しておらず、そのような状況でどのように適用するかを理解することさえできません. また、非常に大きな問題空間では GA の方が効率的であることも理解していますが、これはそれほど大きくはありません。
どのような代替手段がありますか? この問題を解決するために私が取ることができる比較的わかりやすいアプローチはありますか? それとも、今持っているものに固執して、多くの人が次の学期に 8 つのコースを受講することを決定しないことを願うべきですか?
私は優れたライターではないので、質問が曖昧で申し訳ありません。ご不明な点がございましたら、お気軽にお問い合わせください。できる限りお手伝いさせていただきます。
これがコード全体です。
http://bpaste.net/show/ZY36uvAgcb1ujjUGKA1d/
注：誤解を招くタグ（スケジュール）を使用して申し訳ありません。