5

多くの学生がクラスのセクションに入りたいと思っています。一部の学生はすでに1つのセクションにサインアップしていますが、セクションを変更したいので、全員が順番待ちリストに載っています。学生は、誰かがそのセクションからドロップした場合にのみ、新しいセクションに入ることができます。それが彼らが待っているセクションに確実に入ることができない限り、学生は彼らがすでに入っているセクションを落とすことをいとわない。各セクションの順番待ちリストは先着順です。

できるだけ多くの生徒を希望のセクションに入れます。

述べられた問題は、すぐに交通渋滞のシナリオに発展する可能性があります。私の質問は; この問題に対する既知の解決策はありますか？

簡単な解決策の1つは、各セクションを順番に取得し、待機リストの最初の生徒をセクションに強制的に入れ、問題が解決したときに誰かが中退するかどうかを確認することです（セクション数でO（n）以上）。これは場合によっては機能しますが、複数の学生をセクションに強制する（学生数でO（n）以上）、および/または一度に複数のセクションで操作する（O （悪い） ：-）

4

3 に答える 3

2

わかりました、試してみましょう。8 人の生徒 (1..8) と 4 つのセクションがあります。各学生はセクションに分かれており、各セクションには 2 人の学生用の部屋があります。ほとんどの学生は切り替えを望んでいますが、全員ではありません。

下の表では、学生の現在のセクション、必要なセクション、キューの位置 (ある場合) を確認できます。

+------+-----+-----+-----+
| stud | now | req | que |
+------+-----+-----+-----+
|    1 |   A |   D |   2 |
|    2 |   A |   D |   1 |
|    3 |   B |   B |   - |
|    4 |   B |   A |   2 |
|    5 |   C |   A |   1 |
|    6 |   C |   C |   - |
|    7 |   D |   C |   1 |
|    8 |   D |   B |   1 |
+------+-----+-----+-----+

この情報をグラフで表示できます。

+-----+           +-----+           +-----+
|  C  |---[5]--->1|  A  |2<---[4]---|  B  |
+-----+           +-----+           +-----+
   1               |   |               1
   ^               |   |               ^
   |              [1] [2]              |
   |               |   |               |
  [7]              |   |              [8]
   |               V   V               |
   |               2   1               |
   |              +-----+              |
   \--------------|  D  |--------------/
                  +-----+

空室のある区画を探しますが、空室がありません。すべてのセクションがいっぱいなので、裏技が必要です。それでは、空でないキューを持つランダムなセクションを見てみましょう。この場合、セクション A と仮定すると、余分な位置があります。これは、学生 5 がセクション A に入ることができることを意味し、学生 7 が占有するセクション C に空席が残ります。これにより、学生 2 が占有するセクション D に空席が残ります。現在、セクション A に空席があります。 A には追加の位置があるため、この仮定を削除して、より単純なグラフを得ることができます。

パスがセクション A に戻らない場合は、移動を元に戻し、A を無効な開始点としてマークします。別のセクションで再試行してください。有効なセクションが残っていない場合は終了です。

現在、次のような状況があります。

+-----+           +-----+           +-----+
|  C  |           |  A  |1<---[4]---|  B  |
+-----+           +-----+           +-----+
                   |                   1
                   |                   ^
                  [1]                  |
                   |                   |
                   |                  [8]
                   V                   |
                   1                   |
                  +-----+              |
                  |  D  |--------------/
                  +-----+

別のランダムなセクションでトリックを繰り返すと、グラフが解決されます。

現在割り当てられていない複数の学生から始める場合は、開始点として追加のダミー セクションを追加します。もちろん、これはいずれかのセクションに欠員がなければ問題が解決できないことを意味します。

キュー内の順序が原因で、解決策がない可能性があることに注意してください。

于 2009-01-09T22:26:13.070 に答える
2

ええと、これはクラスの有向グラフでサイクルを見つけることに帰着しますよね? 各リンクは、あるノードから別のノードに移動したい学生です。サイクルが見つかったら、いつでも削除します。これらの学生は、お互いのニーズを解決できるからです。サイクルがなくなったら終了です。

于 2009-01-09T21:48:50.447 に答える
1

これは実際にはグラフの問題です。これらの順番待ちリストの依存関係はそれぞれ、有向グラフのエッジと考えることができます。このグラフにサイクルがある場合は、説明した状況の 1 つがあります。サイクルを特定したら、いずれかのクラスを「埋め尽くす」ことでサイクルを「中断」する任意のポイントを選択できます。グラフにサイクルがあったため、物事が正しく解決されることがわかります。

于 2009-01-09T21:49:04.720 に答える