有 n 个人和 k 个目的地的图表

Question

4

在一个连通的图中，有n个饥饿的人站在不同的位置。每个饥饿的人想去位于图中的k个餐厅之一。行驶距离应该在每个人1公里以内。一个餐厅最多可以容纳CEILING [n/k]名客人。

假设已经有这些饥饿的人和区域内的餐厅的位置，请问是否有一种高效的算法，在多项式时间内告诉我们是否可以容纳每一位客人（即True或False）？

这有点像旅行推销员问题，因此它只是对其进行了修改的版本吗？

- HikeTakerByRequest

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

这是一个二分图匹配问题的示例。相比于旅行商问题，这要容易得多，并且可以在O((n+k)^3)时间内解决。

有两个子问题：

1.找出哪些人能到达每个餐厅

2.找到如何将人与餐厅匹配以避免超出限制

到达餐厅

可以通过使用例如Floyd-Warshall算法在O(n^3)中计算任意一对点之间的最短路径来实现。

然后，允许的匹配是距离小于1公里的连接。

将人与餐厅匹配

这个匹配问题可以通过构建图，然后解决最大流问题来解决。

一个适当的图是具有源节点、汇节点和每个人和每个餐厅的节点。

1.将源节点与每个人连接，容量为1

2.将每个人与1公里内的每个餐厅连接，容量为1

3.将每个餐厅与汇节点连接，容量为Ceil(n/k)。

然后计算通过该图的最大流量。当且仅当最大流量为n时，每个客人都可以被接待。

有许多算法可以计算最大流量。一个例子是推-重贴标签算法，其复杂度为O(V^3)，其中V是顶点数（在此问题中，V=n+k+2）。