A *和曼哈顿距离成本

Question

您好这个学期我们开始了一个AI课程，我们有一个项目，计算在NxN董事会达到目标的最佳路线。这块木板也可以随机包含我们不能穿过的障碍物，而且我们也只能垂直和水平移动。每次垂直移动的成本为1.0，水平移动的成本为0.5。我们被要求用曼哈顿启发式方法用A *算法进行计算。我的问题是：当我们计算曼哈顿距离（我知道你必须添加水平和垂直“方块”直到你达到目标），我们必须增加成本到每个“平方”（0.5或1.0）？。或曼哈顿距离只是计算你需要达到目标的“方块”？

Answer 1

您需要使用问题的距离，即1和0.5。

当使用A *时，从开始到当前节点的距离将是沿着到该点的实际路径的1秒和0.5秒的总和，并且估计到结束的剩余距离将是1和沿着“完美路径”0.5s，即没有障碍物。

我希望能回答你的问题。

Answer 2

由于曼哈顿不计算平方，因为它计算的最简单的成本与在相同重量的垂直和水平移动情况下计数平方相同，因此您应该将成本添加到每个平方。