我应该使用什么样的算法来对学生进行排序？

2014-5-6 22:27:48
收藏：0
阅读：111
评论：1

在一个生成随机学生组的程序中，我给用户提供了强制指定学生组合在一起以及禁止学生组合在一起的选项。我已经尝试了两天自己编写算法来完成这个任务，但我在所有递归中都迷失了方向。我正在使用Lua编写这个程序，但我能够理解任何伪代码。以下是学生如何排序的示例：

students = {
    Student1 = {name=Student1, force={"Student2"}, deny={}};
    Student2 = {name=Student2, force={"Student1","Student3"}, deny={}};
    Student3 = {name=Student3, force={"Student2"}, deny={}};
}--在需要通过students[num]检索名称来访问学生表的情况下，会给出第二个名称属性

然后我创建临时表：

forced = {}--将强制表中至少有一个条目的每个学生放入此表中，即使他们在拒绝表中有1个或更多条目也是如此
denied = {}--将为拒绝表中有1个条目且强制表中没有任何条目的每个学生放入此表中
leftovers = {}--将没有任何数据在强制表和拒绝表中的每个学生放入此表中
unsortable = {}--现在还没有放置任何学生 - 这是为了存储按照设定的规则无法放置的学生（即被强制与组合中的某人配对，而该组合又包含了他们不能配对的学生）

SortStudentsIntoGroups()--预定义; 将学生分配到上述组中

在每个学生都被放置在这些组中之后（注意它们仍然在学生表中），我开始通过在组中插入被强制配对的学生（好吧，我已经尝试过了），将具有一个或多个拒绝表条目的学生插入到他们可以被放置的组中，并将剩余的学生填入其余组中。

有一些会有所帮助的东西：

numGroups--预定义的组数
maxGroupSize--自动计算，是最大允许在一个组中出现的学生数量的快速参考值
groups = {}--项数等于numGroups（如在三个组的情况下，groups = {{},{},{}}）。这是为了存储学生而设计的，以便在算法完成后可以向最终用户显示组。

sortGroups()--预定义函数，按大小将组排序;如果以true布尔值作为参数提供，则会将它们按从大到小排序）

正如我之前所说，我不知道如何为此设置递归算法。每次我尝试强制把学生放在一起时，我最终会在多个组中得到同一个学生，被强制成对的学生没有组合在一起，等等。请注意格式。在每个学生的force/deny表中，给出了目标学生的名称 - 而不是对该学生的直接引用。我应该使用什么样的算法（如果一个算法适用于这种情况的话）？非常感谢您的所有帮助。

点赞
用户572670
用户572670

看起来你在面临一个 NP-Hard 问题。

这相当于用 k 种颜色进行图着色，其中边缘是拒绝列表。

图着色：

给定图G=(V,E)和整数 `k`，创建颜色函数f:V->{1,2,..,k}，使得：
f(v)=f(u)->(v,u)不在E中

从图着色到你的问题的简化：

给定图着色问题 (G,k) 其中 G=(V,E)，则创建你的问题的一个实例：

students = V
for each student: student.denial = { student' | for each edge (student,student')}
#groups = k

直观地，每个顶点都由一个学生表示，并且一个学生否认所有的学生，这些学生之间存在边。组数是给定的颜色数。

现在，给定你的问题的一个解 - 我们得到了k组，如果学生 u 否认学生 v - 它们不在同一组，但这等同于用不同的颜色着色 u 和 v，所以对于原始图中的每条边 (u,v)，u 和 v 在不同的颜色中。

反之亦然。

因此，我们通过多项式归约从图着色问题中得到了一个答案，从而发现找到你的问题的最优解是 NP-Hard, 目前没有已知有效的解决方案，大多数人认为不存在一个有效的解决方案。

一些替代方案是使用诸如不提供最优解的 遗传算法 这样的启发式算法，或使用耗时的 暴力 方法（对于大量学生而言不可行）。

暴力方法只会生成所有可能的 k 组分割，并检查其是否是可行解，最后选择找到的最佳解。

2014-05-06 22:55:15

作者:

用户2938986

用户2938986
推荐文章