2

我遇到了将学生分组到最近的考试中心的问题。以下是条件/约束：

  1. 有X个学生和Y个考试中心。每个中心将容纳不同数量的学生。
  2. 考点总数的最大容量可以大于学生人数，但不能更小。
  3. 一个学生可以到多个考试中心的最短距离。
  4. 考试将在所有考试中心同时举行。

例如，有11500名学生和15个考试中心。5 个中心（1 至 5 个）可容纳 1500 名学生，3 个可容纳 600 名学生（6 至 8 名），另外 7 个（9 至 15 名）可容纳 350 名学生。

我开发了以下内容：

  1. 每个考试中心的学生位置（注册地址）的数据库表。像下面的东西

    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

  2. 我可以为每个学生添加一列存储最近的考试中心，并创建如下表：

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

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

提前非常感谢！

4

3 回答 3

1

我知道您正在寻找最佳解决方案- （所有学生都被分配到离他们最近的考试中心）。为此，我们将问题简化为最大流量问题

将问题简化为二分1图G=(V,E)，这样V = {students} U {examination centers} U {S,T}（所有学生、所有考试中心和两个额外的顶点 S 和 T）。
E = CLOSESTS U {S} X {examination centers} U {students} X {T}（S 连接到所有中心，所有学生都连接到 T，以及 CLOSETS - 我们现在将讨论）。
在哪里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

生成的图表应类似于此示例：

在此处输入图像描述 现在，运行一个最大流量算法，比如edmonds-karp。如果“进入”的最大流量 T 是#num_studets，则存在一个最优解，并由算法2实现的流量网络表示。max-flow 算法会在不突破容量限制的情况下，找出每条边放多少流量，相当于如何将一个学生分配到一个中心。

证明：

  • 如果有 #students 的最大流量，则使用所有边 (student,T)，并且所有学生都有一个传入流量，因此被分配。另外，每个考点最多capcity分配一个学生，这个解决方案是有效的。
  • 如果最大流量小于#students，那么有一个学生没有从考试中心获得流量，因此没有被分配，并且没有最优解。

(1) 不完全是二分图，因为我们添加了 S 和 T，没有它 - 它是。
(2)根据积分流定理，并且由于所有权重都是整数 - 存在积分解。

于 2012-09-20T07:20:21.073 回答
0

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

以学生群体和他们的作业为例，您的适应度函数可以为重叠较少的学生提供更大的价值。

我在大学期间以这种方式实现了学生/调度问题，效果非常好。

所以我相信遗传算法是一种方法

祝你好运！

于 2012-09-20T07:08:09.563 回答
0

（我知道这是 2 年前问过的，但也许它会对某人有所帮助）

可以使用匈牙利算法 ( https://en.wikipedia.org/wiki/Hungarian_algorithm ) 创建一个二分图，如下所示：

  • 左边的节点代表学生
  • 右侧节点代表15 个中心的席位
  • 将每个学生的边缘插入每个座位，重量 = 到中心的距离
  • 然后计算最小权重匹配

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

解决方案：可以使用以下算法在不将中心“扩展”到其座位的情况下对问题进行建模（我不会详细说明）：

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

于 2015-07-06T20:19:00.637 回答