改进的a-star寻路启发式设计

Question

首先，理想的路径是(按重要性排序)：

1. shortest

我的启发式(f)是：

manhattan distance (h) + path length (g)

这是错误的，因为它倾向于转向目标然后蛇形返回的路径。

其次，理想的路径是：

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)

我的启发式保持不变。在达到目标后，我在最后检查了第二个标准。启发式的效率稍低(以解决转向问题)，这也导致必须的相邻坐标总是被搜索。

第三，理想路径：

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)
3. takes the least number of turns

现在我试着做启发式(f)：

manhattan distance (h) + path length (g) * number of turns (t)

这当然适用于标准#1和#3，并从本质上解决了转向问题。不幸的是，现在它的效率如此之高，以至于最终对标准#2的测试不起作用，因为所探索的节点集不够大，不足以重建最优解。

有谁能建议我如何将标准#2放入我的启发式(f)中，或者如何解决这个问题？

条件2示例:如果目标是(4,6)，并且通向(3,6)和(4,5)的路径长度相同，那么理想的解决方案应该经过(3,6)，因为它是从Y平面接近的，而不是来自X平面的(4,5)。然而，如果长度不相同，那么无论最短路径在哪个平面上接近，都必须优先选择最短路径。

Answer 1

您似乎混淆了A*启发式( Russell & Norvig称之为h )和部分路径成本g。这些一起构成了优先级f=g+ h。

启发式应该是对从当前点达到目标所需成本的乐观估计。如果台阶向上、向下、向左和向右，并且至少采用单位成本，则曼哈顿距离对于h是合适的。

严格来说，没有必要修改启发式h。

到目前为止的圈数也应该计入部分路径成本g中。如果你能以较低的成本计算出这样的数字，你可能想在h中包含一个(乐观的)估计还有多少个圈数。

Answer 2

在回答我自己的问题时，我有点像个黑客。如果你知道解决这个问题的更好的方法，仍然对其他答案，想法，评论感兴趣。

被黑的曼哈顿距离是向Y平面上最近的正方形计算的，而不是目的地本身：

dy = min(absolute_value(dy), absolute_value(dy-1));

然后在构造启发式(F)时：

h = hacked_manhattan_distance();
if (h < 2)
   // we are beside close to the goal
   // switch back to real distance
    h = real_manhattan_distance();