algorithm - 解决多源多目的图游戏

Question

我正在尝试对下面的图形问题进行分类或找到其解决方案的提示。

有一个（邻接）矩阵可以包含 3 种类型的元素：单位、点和简单地形。

地形没有特定的含义。

单位有一个位置（x,y 由矩阵定义）和它们可以获取的点数。
点有一个位置（x,y 由矩阵定义）。
获取一个点的成本是一个点和一个单位之间的曼哈顿距离。
每个点只能由一个单位获得。

问题是：如何找到单位获取点的最小成本配置，使得单位的所有资源都被耗尽？

示例：
u1 可以获得 3 分
u2 可以获得 2 分

p1 n n p2  
n u1 n p3  
p4 n n n  
n n u2 p5

最佳解决方案之一是：

u1 = p1, p2, p4  
cost(u1)=2+3+2=7  
u2 = p3, p5  
cost(u2)=3+1=4  
Total cost = 11  

（此配置的最低要求）

注意：我已经尝试使用统一成本搜索和 A*（使用简单的启发式算法）来解决这个问题，但即使对于小尺寸的矩阵，我也会得到非常多的状态并且内存不足。

Answer 1

我可以将其简化为最小成本最大流量问题。

让我们做一个网络。为每个单元和每个点分配一个顶点。对于每一对（单位、点），添加一条容量为 1 且成本等于相应曼哈顿距离的有向边。添加一个接收器，将其连接到所有单元。添加一个陷阱并将所有点连接到它。

分配以下成本和容量值：
cap( u, v ) = 1，如果从 u 到 v
cost( u, v ) = 0，如果 u = sink 或 v = trap；否则它等于从单元 u 到点 v 的曼哈顿距离。

现在，如果我们在这个网络中找到 min-cost-max-flow，它将成为您问题的解决方案。为什么 ？因为我们找到了将一个单元流从每个“单元”顶点移动到某个“点”顶点的最小成本方式，这相当于原始问题。