algorithm - 改进的 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)，因为它(4,5) 是从 Y 平面接近，而 (4,5) 是从 X 平面接近。但是，如果长度不相同，则无论接近哪个平面，都必须优先考虑最短路径。

Answer 1

您似乎混淆了 A* 启发式，什么 Russell & Norvig调用h，部分路径成本g。这些共同构成了优先级 f = g + h。

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

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

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