algorithm - 求解多源多目的 map 博弈

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

我可以将它减少到 min-cost-max-flow问题。

让我们建立一个网络。为每个单元和每个点分配一个顶点。对于每一对(单位，点)添加容量为 1 且成本等于相应曼哈顿距离的定向边。添加一个水槽，将其连接到所有单元。添加陷阱并将所有点连接到它。

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

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