解决图形问题需要简单建议

Question

我的同事向我介绍了一个在线评测网站上的练习题，基本上是一个小镇疏散计划的图形解决问题。

我不需要答案（也不想要），只需要一个建议，关于如何解决这个问题，因为我对这类问题还比较陌生。

问题包括城镇建筑物、工人和防核避难所。我必须构建一个算法，将每个建筑物的工人分配到一个或多个防核避难所，但不能使某些避难所过度拥挤而其他避难所几乎没有人（否则我会让工人去最近的避难所）。

问题在此处：http://acm.timus.ru/problem.aspx?space=1&num=1237。

如果它已经下线，请使用Google缓存版本：http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt。

到目前为止，我为每个建筑物获取最近的避难所，并将该建筑物中的工人数量移动到该避难所的容量。然后移到下一个建筑物。但是有时候工人数量大于避难所的容量，在这种情况下，当我遍历完每个建筑物后，我会再次遍历它们并应用相同的算法，直到每个建筑物都没有工人，问题是这几乎不是解决它的最佳方法。

欢迎任何提示，请不要觉得我在寻求答案，我只想得到正确解决方向的建议。

提前感谢。

- sap

Answer 1

这看起来与转运问题非常相似，可以使用线性规划来解决（显然这是整数线性规划的一个实例）。根据该网站上的描述，运输问题产生的标准情景是在连接给定城市集合的公路网络上发送产品单位。每个城市被认为是“源”，因为单位需要从那里发货，或者是“汇”，因为单位需要在那里提供。每个源都有给定的供应量，每个汇都有给定的需求量，连接源-汇对的每条公路都有给定的运输成本。这可以以网络的形式可视化，如下图所示。给定这样一个网络，感兴趣的问题是确定一种最优的运输方案，以最小化总运输成本，同时满足供应和需求约束。希望这可以帮到你。

- Aryabhatta

---

非常感谢您的帮助，我最终使用了运输问题而不是中转问题（它还考虑了中间商供应商而不仅仅是供应商和消费者），但它们都是相关的，因此解决一个需要知道如何解决另一个。至于算法，我使用了最小成本分配算法来找到可行解，然后使用了步进石法来找到最优解。再次感谢您的建议，真的非常有帮助。 - sap

Answer 2

这看起来像是一个标准的最小费用最大流问题。一个包含约200个顶点的二分图应该会很容易地在时间上运行。

为了创建顶点约束（每个节点只能处理k个人），您只需要创建另一个图G_1，其中为每个v_i都添加了一个额外的顶点u_i，并使得从v_i到u_i的流量满足您的约束条件，例如，在这种情况下，为k+1，成本为0。因此，如果原始图G中有边（a，b），则在G_1中，对于每个这些边，都将有一条边（u_a，v_b）。实际上，您正在创建第二层顶点，以限制每个顶点的流量为k。

- Larry

---

这个和线性规划是等效的。查看此维基文章，了解解决这些问题的简单算法。 - BlueRaja - Danny Pflughoeft

@BlueRaja：你的意思是每个线性规划都可以被建模成某个图上的最大流问题吗？（我知道最大流问题有线性规划的解法。） - Aryabhatta

@Moron：我曾经认为每个线性规划问题都可以被建模成网络流问题（我知道每个网络流问题都可以被建模成最小-最大流问题，每个最小-最大流问题都可以被建模成线性规划），但我找不到任何支持这种想法的参考资料。我可能是错了。 - BlueRaja - Danny Pflughoeft

@BlueRaja：我怀疑情况不会是这样的（LP <= max-flow）。如果我没记错的话，即使在多项式时间LP算法出现之前，网络流问题的解决方案也已经存在了。 - Aryabhatta

这是相反的情况 - 你可以将最大流问题描述为LP问题。虽然我认为，虽然已经有一段时间了，但反之则不成立。至于@Moron的详细说明，我认为你的图基本上就是它，除了它是一个最大流（强调最小成本）。图形设置完全相同。不确定为什么你特定的链接没有提到它。 - Larry