考场座位处理的算法

use*_*666 1 algorithm graph

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

您能提出一种确保总行驶距离最小的算法吗?(即每个学生到考试中心的距离之和)

显然,我可以持有[1] +我可以持有[2] + ... +我可以持有[y]> x

我正在考虑创建这样一个程序,以使进行检查的麻烦最少。借助googlemap,可以实现实际的实现。

fgb*_*fgb 5

通常,这对距离和容量没有任何限制,这是最小成本的最大流量问题。

  • 每个学生和城市都是一个顶点。
  • 每个学生都连接到容量为1(成本为0)的边的源。
  • 每个城市都连接到容量为的i-can-hold成本为0的接收器。
  • 每个学生都连接到容量为1的城市,费用为i-have-to-walk

可以使用Ford–Fulkerson算法来找到最大流量,但不考虑成本。尽管可以通过更简单的示例了解流网络,但可能有助于学习。

有许多不同的算法可将成本降至最低。一种是“连续最短路径”。这个想法是反复寻找一条从源到剩余网络中汇入的最小成本路径,并沿着该路径添加流量,直到找不到更多路径为止。

例如:

流网络

a)标记每个顶点(成本,容量)的流网络。包含一列3个学生的列,这些列与2个中心的列相连。

b)在剩余网络中沿最短路径(可以在Bellman-Ford中找到)添加的流量。剩余网络是根据可用容量(容量减去各个方向的流量)创建的图形。

c)沿着另一条路径增加了更多的流量。

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

也可以看看: