1

这是情况。假设我们有 x 个学生，编号为 1,2...x，住在一个城市的固定地点。有 y 个考试中心，编号为 1 、 2 、 3 ...y，每个考试中心的容量分别为“i-can-hold[y]”。学生 i 到考试中心 j 的距离是 'i-have-to-walk[i][j]'

你能推荐一种算法来确保总行驶距离最小吗？（即每个学生到考试中心的距离总和）

显然 i-can-hold[1]+i-can-hold[2]+...+i-can-hold[y]>x

我正在考虑创建这样一个程序，以减少进行考试的麻烦。在 googlemap 的帮助下，实际实施是可能的。

4

1 回答 1

5

一般来说，在距离和容量没有任何限制的情况下，这是一个最小成本最大流量问题。

  • 每个学生和城市都是一个顶点。
  • 每个学生都连接到一个容量为 1、成本为 0 的源。
  • 每个城市都连接到容量为i-can-hold，成本为 0 的接收器。
  • 每个学生都连接到一个容量为 1 的城市，成本从i-have-to-walk.

Ford-Fulkerson 算法可用于找到最大流量，但不考虑成本。尽管通过更简单的示例了解流网络，但学习它可能会有所帮助。

有许多不同的算法可以最小化成本。一是“连续最短路径”。这个想法是在残差网络中反复找到一条从源到汇的最小成本路径，并沿着这条路径添加一个流，直到找不到更多路径。

例如：

流网络

a) 一个流网络，其中每个顶点都被标记（成本、容量）。包含一列 3 名学生连接到一列 2 个中心。

b) 在残差网络中沿最短路径添加的流（可以使用 Bellman-Ford 找到）。残差网络是从可用容量（容量减去每个方向的流量）创建的图。

c) 沿另一条路径添加更多流量。

d) 最优流量。已沿更改已添加流的路径添加流。这是允许的，因为残差网络在流的相反方向上具有容量。

也可以看看：

于 2012-11-24T14:47:06.657 回答