私は現在、学生をコースにマッピングするプログラムを書いています。現在、私はSATソルバーを使用していますが、次のサブ問題を解決する多項式時間/貪欲でないアルゴリズムを実装しようとしています:
- 学生あり（50～150人）
- 「数学」、「生物学」、「芸術」などの科目 (10 ～ 20) があります。
- 科目ごとにコースがあります (少なくとも 1 つ)。たとえば、「数学 1」、「数学 2」、「生物学 1」、「芸術 1」、「芸術 2」、「芸術 3」などです。
- 学生はいくつかの (固定された) 科目 (10 ～ 12) を選択し、各科目について、既存のコースの 1 つに学生を割り当てる必要があります (可能な場合)。「数学1」「数学2」どちらの科目を選択しても問題ありません。
- コースには許可された最大数の学生（20-34）があります
- 各コースは固定ブロック（＝タイムスロット1～13）
- 学生は、同じブロックにあるコースに割り当てられない場合があります
今までやってきたことを紹介しています。
(1) 受講者制限の無視
ハンガリーのアルゴリズム/二部マッチングでこれを解決できました。各生徒は、次のようにモデル化することで個別に計算できます。
- 左のノードは、科目「数学」、「生物学」、「芸術」 (生徒の) を表します
- 右側のノードは、ブロック '1'、'2'、.... '13' を表します
- 「科目」から「ブロック」までのコースごとにエッジが挿入されます
このようにして、学生は同じブロックにあるコースに参加していなくても、コースのすべての科目に割り当てられます。ただし、コース制限は無視されます。
(2) 学生の選択科目無視
max-flow-algorithm でこれを解決できました。各学生について、以下がモデル化されます。
- レイヤー 1: 13 の流れでソースから各生徒へ
- レイヤー 2: 各生徒から個人ブロックまで、フロー 1
- レイヤー 3: 各学生ブロックからそのブロック内の各コースへのフロー 1
- レイヤ 4: 各コースから「max-student-limit」を使用してシンクまで
このようにして、学生は任意のコースを選択し、コース制限が満たされます。しかし、運が悪く、科目「生物学」と「芸術」を無視して「数学 1」「数学 2」「数学 3」に割り当てられるかもしれません。
(3)貪欲なハンガリー人
私が持っていた別のアイデアは、一度に 1 人の学生をハンガリーのアルゴリズムと一致させ、「より空のコース」が優先されるように重みを調整することでした。たとえば、次のモデルを作成できます。
- 左のノードは生徒の科目です
- 右のノードはブロック
- コースごとに、重み = 自由席の数で、コースのブロックにサブジェクトからエッジを挿入します
次に、Maximum-Weight-Matching を計算します。
提案/ヘルプをいただければ幸いです。
ありがとうございました！