算法 - 匹配学生考试中心

我有一个将学生分组到最近的考试中心的问题。这里是条件/约束：算法 - 匹配学生考试中心

有X学生和Y考试中心。每个中心将有不同数量的学生。
考试中心总数的最大容量可以大于学生人数，但不能小于。
学生可以有一个距离超过1个考试中心的最小距离。
考试将同时在所有考试中心举行。

例如，有11500名学生和15个考试中心。 5个中心（1至5个）将招收1500名学生，其中3名为600名（6至8名），另外7名（9至15名）将招收350名学生。

我已经开发出了如下：

与学生的位置（注册地址）给每个考试中心的数据库表。类似下面

Student ID Dist-Ex1 Dist-Ex2 ... Dist-Ex14 Dist-Ex15 
1   10   70   20   50 
2   25   43   5   105 
... 
11499  35   12    35   55 
11500  5   23    5   5

我可以添加存储最近的考试中心到每个学生的一列，并创建一个表像下面：

Ex centers   Nearest for no. of students 
1      2000 
2      500 
... 
14      150 
15      500

但我不知道如何进一步进行。我相信这是一种算法问题。如果有人会给我一些想法，我将不胜感激。

非常感谢！

来源

2012-09-20 kwytse

这似乎是一个实例广义分配问题，这是NP难。维基百科有一个很好的解释，以及一个贪婪的算法，不保证是最佳的。 HTTP：//en.wikipedia。org/wiki/Generalized_assignment_problem如果“代理商”是地点，“任务”是学生，则代理商/任务公式对应于您的问题。成本是从地点到学生的距离，每个学生的利润为1。 – dsg

也许最大流量算法可以适合这里 – amit

我明白你正在寻找一个最佳解决方案 - （所有的学生被分配到他们最近的考试中心）。为此，我们将这个问题降低到max-flow problem

问题缩小到二分图G=(V,E)这样V = {students} U {examination centers} U {S,T}（所有学生，各考试中心和两个额外的顶点S和T）。（S与所有中心相连，所有学生都与T和CLOSESTS相连 - 我们现在将讨论）。
凡CLOSESTS = { (exam,stud) | exam is the closest examination center to the student sutd}

我们还需要一个权重函数f:E->N这样的：

f(u,v) = capcity if u=S, v=examination center 
f(u,v) = 1 if u is examination center and v is student 
f(u,v) = 1 if u is student and v is T

最终图表应该是这个样子的样品：

enter image description here 现在，运行最大流算法，像edmonds-karp。如果最大流量“进入”T是#num_studets，则存在最优解，并且由算法实现的流程网络表示。最大流算法会查找每条边放置多少流量，这相当于如何将学生分配到中心，而不会打破容量限制。

证明：

如果有#students的最大流量，所有边缘（学生，T）时，和所有学生具有进入流，并且因此被分配。此外，每个考试中心最多只有capcity名学生，解决方案有效。
如果最大流量小于#students，那么有一个学生没有从考试中心获得流量，因此未分配，因此没有最佳解决方案。

（1）不完全二部图，因为我们加入S和T，没有它 - 它是。
（2）根据Integral Flow Theorem，由于所有权重都是整数，所以有一个完整的解决方案。

来源

2012-09-20 07:20:21 amit

非常感谢您的帮助。我会看看最大流量以及遗传算法 – kwytse

@kwytse：不客气。请注意，遗传算法（GA）是启发式的 - 并且找不到最优解。如果您真的想找到最佳解决方案，并将每个学生分配到最近的中心 - 最大流量是最佳选择。另请参阅编辑 - 我添加了一张照片，用来展示图形的外观。 – amit

我建议你在这里看看遗传算法。

以学生人数和他们的任务您的健身功能可以为重叠较少的学生提供更大的价值。

我在这样的大学里实施了学生/排班问题，它工作得很好。

所以我相信遗传算法是一种方式去这里

好运！

来源

2012-09-20 07:08:09

（我知道这是2年前问过，但也许这将帮助别人）

它是可以解决的最佳与匈牙利算法（https://en.wikipedia.org/wiki/Hungarian_algorithm）创造了二分图如下：

左节点表示学生
正确的节点代表席位15个中心的
插入一个边缘从每个学生每个座椅具有重量=距离中心
然后计算最小重量匹配

问题：您的矩阵具有大小11500²。

解决方法：这是可能的，但无模式的问题“扩展”的中心，以自己的座位上使用以下算法（我就不细讲）：

https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

来源

2015-07-06 20:19:00 Benjamin

算法 - 匹配学生考试中心

回答

相关问题