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

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

地形没有具体的意义。

单位有一个位置（由矩阵定义的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*（使用简单的启发式方法）来解决这个问题，但即使对于矩阵的较小尺寸，我也得到了非常多的状态并耗尽了内存。

回答：

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

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

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

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