artificial-intelligence - 加权 A* 中的启发式函数

Question

三个AI新手问题:

为什么 A* 可以采用启发式算法来找到最佳路径？

如果障碍物挡住了道路，系带制动技术有什么用？

什么算法适合在有障碍物的网格上找到路径？ (像吃 bean 一样)

第一个问题让我们以 Manhattan distance 为基础启发式，调用是 h(x)。现在为什么 A* 应该使用 8*h(x) + 5 的新启发式找到非最优路径？ (随机数)。据我了解在 A* 算法中，将根据函数 f(x) = g(x) + h(x) 做出决定。所以如果我按比例增加 h，为什么最大\最小要改变？

我已阅读 this article ，在那里他们谈到乘以一个小系数以用于系带制动，这在某种程度上符合我的理论，但他们坚持认为该系数应该很小。所以我不知道该怎么想。

第二个问题我尝试了解决吃 bean 游戏链接中的技术。曼哈顿距离启发式的任何变化都会导致更多的节点扩展。我什至“发明”了一个新的加权方案，我更喜欢 shell 上的路径——同样的事情。后来我尝试取所有函数的最大值(这也应该是可以接受的)，但性能仍然很差。我错过了什么？

第三个问题没什么好补充的。如前所述 - 我找不到比曼哈顿距离更好的东西了。

Answer 1

1) 简洁的答案是，如果您的启发式方法 Not Acceptable ，您将(可能)得到非最佳结果。我想你知道这一点。对于直觉，请回想可接受的启发式的定义:它是一种永远不会比现实更悲观的启发式方法。 (我们通常说，“它总是乐观的”，因为如果你有一个既不乐观也不悲观的启发式，你基本上已经有了答案。)如果你的启发式在某些地方是悲观的，那么它最终会避免最好的选择。

至于根据您的问题扩大和缩小启发式，请记住，您只是扩大了公式的启发式部分，而不是公式的沉没成本部分。如果您可以完全相同地按比例放大它们，您就看不到差异，但您不能总是那样做。即使在您的示例中，您添加的附加位也会破坏它。

2-3)我不清楚你所说的“解决”吃 bean 是什么意思。如果有什么比找到一条最短路径来吃掉空网格中的所有点更复杂的话，我认为你已经远远超出了 A* 的范围。即便如此，A* 也不会是我的首选工具。