我有分组学生就近考试中心的问题。这里的条件/限制：

I have a problem of grouping the students to the nearest examination center. Here are the conditions/constraints:

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

例如，有11500名学生和15考试中心。 5个研究中心（1-5）将举行1500学生，3 600（6〜8），另7（9〜15）将容纳350名学生。

For example, there are 11500 students and 15 examination centers. 5 centers (1 to 5) will hold 1500 students, 3 for 600 (6 to 8) and the other 7 (9 to 15) will hold 350 students.

我已经开发了以下几个方面：

I have developed the followings:

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

A database table with the student's location (register address) to each of the examination centers. Something like below

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

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

I can add a column of storing the nearest examination center to each of the student, and create a table like below:

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

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

But I don't know how to further proceed. I believe it is some kind of algorithm problem. I would be grateful if anyone would give me some idea.

感谢很多提前！

推荐答案

我明白你正在寻找一个最优解 - （所有学生被分配到与其最接近的考试中心）。为此，我们将问题缩小到一个 最大流问题

I understood you are looking for an optimal solution - (all students are assigned to their closest examination center). For this, we will reduce the problem to a max-flow problem

问题缩小到两分 1 图 G =（V，E），使得 V = {学生} U {考试中心} U {S，T} （所有学生，各考试中心和两个额外的顶点S和T）。 E = CLOSESTSü{S}×{考试中心} U {学生}×【T】（S连接到所有的中心，所有的学生都连接至T和CLOSESTS - 我们现在讨论）。 其中 CLOSESTS = {（考试，螺栓）|考试是最接近考试中心对学生SUTD}

Reduce the problem to a bipartite1 graph G=(V,E) such that V = {students} U {examination centers} U {S,T} (all students, all examination centers, and two extra vertices S and T). E = CLOSESTS U {S} X {examination centers} U {students} X {T} (S is connected to all centers, all students are connected to T, and CLOSESTS - that we will now discuss). Where CLOSESTS = { (exam,stud) | exam is the closest examination center to the student sutd}

我们还需要一个权重函数 F：E-＆GT; N 这样：

We also need a weight function f:E->N such that:

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

最终图表应该类似于此示例：

The resulting graph should look something like this sample:

现在，运行最大流算法，如埃德蒙兹 - 卡普。如果最大流时，变为T是#num_studets，存在一个最佳的解决方案，它表示通过由算法 2 取得的流网络。的最大流算法将找到多少流把在每个边缘，这相当于如何学生分配给中心，而不会破坏容量限制

Now, run a max flow algorithm, like edmonds-karp. If the max flow "enters" T is #num_studets, there is an optimal solution and it is denoted by the flow network achieved by the algorithm2. The max-flow algorithm will find how much flow to put in each edge, which is equivalent to how to assign a student to a center, without breaking the capacity limit.

证明：

如果有#students的最大流量，所有边缘（学生，T）时， 和所有的学生有一个流入流量，并且因此被分配。此外，每个考点最多有 capcity 学生分配，以及 解决方案是有效的。 如果最大流量越小则#students，然后有一个 学生未得到考试中心的流动，是 因而没有被分配，并且没有最优解。 If there is max flow of #students, all edges (student,T) are used, and all student has an incoming flow, and thus is assigned. Also, each examination center has at most capcity students assigned, and the solution is valid. If the max flow is smaller then #students, then there is a student that did not get a flow from an examination center, and is thus not assigned, and there is no optimal solution.

（1）不完全是一个二分图，因为我们添加了S和T，没有它 - 它是。 （2）根据积分流量定理以及因​​为所有的权重都是整数 - 有一个组成溶液

(1) Not exactly a bipartite graph because we added S and T, without it - it was. (2)According to Integral Flow Theorem, and since all weights are integers - there is an integral solution.