gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:09:21 26 4
gpt4 key购买 nike

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

有一个(邻接)矩阵可以包含 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*(使用简单的启发式算法)来解决这个问题,但即使对于小尺寸的矩阵,我也会得到非常多的状态并耗尽内存。

最佳答案

我可以将它减少到 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,这将是您问题的解决方案。为什么 ?因为我们找到了将单位流量从每个“单位”顶点移动到某个“点”顶点的最小成本方式,这等同于原始问题。

关于algorithm - 求解多源多目的 map 博弈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14800788/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com