好的,让我们试试。我们有 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 部分,在 C 部分留下一个空缺,由学生 7 占据。这在 D 部分留下一个空缺,由学生 2 占据。我们现在在 A 部分有一个空缺。但我们假设该部分A有一个额外的位置,所以我们可以去掉这个假设,得到一个更简单的图。
如果路径从未返回到 A 部分,则撤消移动并将 A 标记为无效起点。用另一个部分重试。如果没有剩余的有效部分,我们就完成了。
现在我们有以下情况:
+-----+ +-----+ +-----+
| C | | A |1<---[4]---| B |
+-----+ +-----+ +-----+
| 1
| ^
[1] |
| |
| [8]
V |
1 |
+-----+ |
| D |--------------/
+-----+
我们用另一个随机部分重复这个技巧,这解决了图形。
如果您从几个当前未分配的学生开始,则添加一个额外的虚拟部分作为他们的起点。当然,这意味着任何部分都必须有空缺,否则问题无法解决。
请注意,由于队列中的顺序,可能没有解决方案。