改进的 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。

但是，您的标准 2 应该位于路径成本 g 中，而不是 h 中。我不确定“从相同的 y 坐标接近目的地”到底是什么意思，但是您可以通过为所有其他方法提供无限或非常高的路径成本来禁止/惩罚进入目标节点。完全没有必要修改启发式h。

到目前为止所经过的圈数也应该包含在部分路径成本g中。如果您可以廉价地计算出这样的数字，您可能希望在 h 中包含对还需要转多少圈的（乐观）估计。

Answer 2

用某种 HACK 的方式回答我自己的问题。如果您知道解决此问题的更好方法，仍然对其他答案、想法、评论感兴趣。

Hacked 曼哈顿距离是向 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();