algorithm - 包含 n 个人和 k 个目的地的图表

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

提供这些饥饿的人和该地区的餐馆的分数，是否有一种有效的算法可以在多项式时间内运行，以判断是否可以容纳每个客人(如 True 或 False)？

这让我想起了旅行商问题，所以它只是它的一个修改版本吗？

最佳答案

这是二部图上匹配问题的一个例子。这比旅行商问题更容易解决，并且可以在 O((n+k)^3) 中完成。

有两个子问题:

查找哪些人可以到达每个餐厅

查找如何将人与餐厅匹配以避免溢出约束

到达餐厅

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

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

将人与餐厅相匹配

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

一个合适的图是为每个人和每个餐厅都有一个源节点、一个汇节点和一个节点。

将源连接到每个容量为 1 的人

将每个人连接到 1km 内的每个餐厅，容量为 1

将每个餐厅连接到容量为 Ceil(n/k) 的汇节点。

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

有很多 algorithms 来计算最大流量。一个例子是复杂度为 O(V^3) 的 push-relabel，其中 V 是顶点数(在这个问题中 V=n+k+2)。

关于algorithm - 包含 n 个人和 k 个目的地的图表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17424434/