宽度优先搜索与A *迷宫中的曼哈顿距离

Question

考虑到迷宫中的初始状态和单个最终状态，是否可以设计这样一种迷宫，其中以曼哈顿距离作为启发函数，广度优先搜索扩展的节点数少于A *？扩展到所有节点的成本为1。

Answer 1

没有那不可能。

假设最短路径具有n个节点，并且在搜索结束时存在一个A *已访问但BFS尚未访问的节点p。

然后该节点p具有以下属性：

• 由于BFS未访问p，这意味着到p的最短路径具有n个或更多节点。这是因为通过<< n-1个（或更少）节点的路径可以到达的任何节点，在找到解决方案之前，BFS都已经对其进行了访问。

• 达到

  p

的A *成本必须为n：它为最少 n，因为该成本包括行进的节点数加上启发式。它不能大于n，因为获胜路径的总成本为n，因此在A *考虑访问p之前就已经找到了解决方案。 >因此，总而言之，

p从确切的n

个节点到起始节点的路径最短，并且A *启发式将为零。换句话说，这个节点就是目标节点！但是BFS算法访问了目标节点has。这是一个矛盾，因此存在这样的

p

的前提是错误的。

结论：

BFS算法也保证A *访问过的所有节点。因此，BFS已访问的节点数至少是A *已访问的节点数。请注意，算法可能会找到一条不同的路径，这仅仅是因为不确定的顺序决定了扩展路径的选择（导致相等的成本）。但这并不会改变以上结论。