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

Question

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

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

这让我想起了旅行推销员问题，所以它只是它的修改版本吗？

Answer 1

这是二分图上的匹配问题的示例。这比旅行商问题更容易解决，并且可以在 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) 的push-relabel，其中 V 是顶点数（在这个问题中 V=n+k+2）。