算法 - 匹配学生考试中心

Question

我在将学生分组到最近的考试中心时遇到了问题。以下是条件/限制条件:

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
   

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

提前致谢!

Answer 1

我了解到您正在寻找最佳解决方案 -(所有学生都被分配到离他们最近的考试中心)。为此，我们将问题简化为 max-flow problem

将问题简化为二分图¹ 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，而 CLOSESTS - 即我们现在将讨论)。
哪里 CLOSESTS = { (exam,stud) | exam 是离学生最近的考试中心 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，则存在最优解，并由算法² 实现的流量网络表示。 max-flow 算法会找到每条边放多少流量，这相当于如何在不突破容量限制的情况下将学生分配到一个中心。

证明:

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

---

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