对 A* 中的启发式函数进行加权

Question

三个AI新手问题：

1. 为什么 A* 应该允许启发式方法来找到最佳路径？
2. 如果有障碍物，系带制动技术有什么用呢？
3. 什么算法适合在有障碍物的网格上寻找路径？（如吃豆人）

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

我读过这篇文章，他们在那里谈到了乘以一个小系数来进行制动制动，这在某种程度上符合我的理论，但他们坚持认为该系数应该很小。所以我不知道该怎么想。

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

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

Answer 1

问题3：

如果您实际上正在制作吃豆人游戏，您必须找到每个“幽灵”的路径，您也可以使用Dijkstra 算法，以吃豆人的位置为目标，一次性计算每个幽灵的最佳路径。由于每个“边”（从一个单元格到下一个单元格）的成本始终相同，因此您也可以使用简单的广度优先搜索。最后，您还可以看看协作扩散，以不同的方式发送每个幽灵。