algorithm - 有 n 个人和 k 个目的地的图

Question

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

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

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

Answer 1

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

有两个子问题:

1. 找出哪些人可以到达每家餐厅
2. 找到如何将人们与餐馆相匹配以避免溢出限制

到达餐厅

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

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

将人们与餐厅相匹配

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

一个合适的图应该有一个源节点，一个汇节点，每个人和每个餐厅都有一个节点。

1. 将源连接到容量为 1 的每个人
2. 将每个人连接到 1 公里内的每家餐厅，容量为 1
3. 将每个餐厅连接到容量为 Ceil(n/k) 的汇聚节点。

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

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