理解不一致的启发式方法

Question

4

假设我有一个网格，其中一些正方形被指定为“目标”正方形。我正在使用A*来导航这个网格，尝试使用非对角移动至少一次访问每个目标正方形。一旦访问过目标正方形，它就不再被视为目标正方形。想象一下吃豆人(Pac Man)，四处移动并尝试吃下所有点。

我正在寻找一种一致的启发式方法来帮助A*进行导航。我决定尝试一种“返回到最近未访问目标的曼哈顿距离”的启发式，适用于任何给定位置。有人告诉我这不是一种一致的启发式，但我不明白为什么。

向最近的目标正方形移动一个方格的代价为1，而曼哈顿距离也应该减少1.着陆在目标正方形上，将增加启发式的值(因为现在它将寻找下一个最近的未访问目标)或结束搜索(如果目标是最后一个未访问目标)。

似乎H(N) < c(N,P) + h(P)总是成立的，那么是什么使得这个算法不一致，还是我的教练错了？

- Dan Brenner

你读过这篇文章吗？http://cs.stackexchange.com/questions/6208/heuristic-for-finding-multiple-goals-in-graph-e-g-using-kruskals-algorithm? - Grzegorz Sławecki

1

是的，虽然它并没有真正解决我的问题。 - Dan Brenner

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueRaja - Danny Pflughoeft · Accepted Answer

如果您想知道如何使用A*算法找到穿过所有目标的最短路径，答案是：您无法完成（只用一次迭代）。这是旅行商问题，一个NP完全问题。要使用A*算法解决此问题，您需要尝试每个目标顺序的排列组合。然后，可以使用A*算法解决从单个起点到单个目标的每条路径（因此，您需要为每个排列运行多次算法）。

但是，如果您想知道如何使用A*算法找到从单个起点到任何一个目标的最短路径，则您的解决方案很好，并且您的启发式函数确实是一致的。多个一致的启发式函数的最小值仍然是一致的启发式函数，这是易于证明的。