5

一些学生想进入一个班级的部分,有些学生已经注册了一个部分但想改变部分,所以他们都进入了候补名单。只有当有人从该部分掉线时,学生才能进入新部分。没有学生愿意放弃他们已经在的部分,除非可以确保进入他们正在等待的部分。每个部分的等候名单是先到先得。

让尽可能多的学生进入他们想要的部分。

上述问题可能很快演变为僵局。我的问题是;这个问题有已知的解决方案吗?


一个简单的解决方案是依次选择每个部分并强制等待列表中的第一个学生进入该部分,然后检查当事情解决时是否有人最终退出(部分数量为 O(n) 或更多)。这在某些情况下可行,但我认为可能有更好的选择,包括强制一个以上的学生进入一个部分(O(n) 或更多学生数量)和/或一次操作多个部分(O (坏的) :-)

4

3 回答 3

2

好吧,这只是归结为在类的有向图中找到循环,对吗?每个链接都是一个想要从一个节点到另一个节点的学生,任何时候你找到一个循环,你就删除它,因为这些学生可以相互解决他们的需求。当你没有周期时,你就完成了。

于 2009-01-09T21:48:50.447 回答
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 部分,在 C 部分留下一个空缺,由学生 7 占据。这在 D 部分留下一个空缺,由学生 2 占据。我们现在在 A 部分有一个空缺。但我们假设该部分A有一个额外的位置,所以我们可以去掉这个假设,得到一个更简单的图。

如果路径从未返回到 A 部分,则撤消移动并将 A 标记为无效起点。用另一个部分重试。如果没有剩余的有效部分,我们就完成了。

现在我们有以下情况:

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

我们用另一个随机部分重复这个技巧,这解决了图形。

如果您从几个当前未分配的学生开始,则添加一个额外的虚拟部分作为他们的起点。当然,这意味着任何部分都必须有空缺,否则问题无法解决。

请注意,由于队列中的顺序,可能没有解决方案。

于 2009-01-09T22:26:13.070 回答
1

这实际上是一个 Graph 问题。您可以将这些等待列表依赖项中的每一个视为有向图上的边。如果这个图有一个循环,那么你有你描述的情况之一。一旦您确定了一个循环,您可以通过“过度填充”其中一个类来选择任何点来“打破”循环,并且您将知道事情会正确解决,因为图中存在一个循环。

于 2009-01-09T21:49:04.720 回答