在一个迷宫中,给定初始状态和单个终止状态,是否可能设计一个迷宫,使得广度优先搜索比使用曼哈顿距离作为启发式函数的A*算法扩展更少的节点?所有节点的扩展成本为1。
在一个迷宫中,给定初始状态和单个终止状态,是否可能设计一个迷宫,使得广度优先搜索比使用曼哈顿距离作为启发式函数的A*算法扩展更少的节点?所有节点的扩展成本为1。
这是不可能的。 直觉是启发式算法比BFS更加明智。 这也是证明它的基础。
正式地:
h'(n)= 0
也是一种可接受的启发式函数。
BFS基本上是使用h'
作为其启发式函数的A *(因为它总是根据f'=g(n) + h'(n) = g(n)
扩展)
h
支配h'
,因为对于所有n
:h'(n) <= h(n)
。h
支配h'
并且是单调的,则使用h
的算法扩展的节点是使用h'
的算法扩展的节点的子集。 this thread中有更多信息和证明,以及original articleQED
一般来说,这可以通过以下三种方式实现:
当A*算法使用不一致的启发式函数时,它可以对N个状态进行最多2^N次扩展。对于无向图,即使启发式函数是可接受的(h(a,g) <= c(a,g)
),但存在某些状态满足|h(a, g)-h(b, g)| > c(a, b)
。曼哈顿距离是一个一致的启发式函数,所以在你的例子中这种情况不起作用。
在广度优先搜索中,假定所有代价都为1。因此,当生成目标状态时,它可以立即终止,知道它已经得到了到达目标的最佳代价。而A*算法通常在选择目标状态进行扩展之前不会终止。请注意,如果A*可以保证所有边缘具有统一的代价(或者具有某个最小代价),那么A*可以采取相同的策略。
A*算法仅最优地扩展必要的节点——那些满足f(n) < C*
的节点,其中C*
是最优解决方案的代价。如果一个问题实例有多个状态满足f(n) = C*
,那么如果A*做出错误的决策,而BFS却能够幸运地进行正确的决策,则A*算法可能会表现得更差。
现在,考虑这个例子:
....._.
SXXXXG.
.......
这里,.
代表空格,_
代表可达/扩展的单元格。 S
是起点,G
是终点。 X
状态是不可通过的,而_
单元格可以被到达/扩展,但您不能从该状态向下到达目标。
如果A*算法运气不佳,它将首先扩展顶部路径(假设它按最大g-cost优先扩展,但这也适用于其他决策规则)。该路径看起来很有前途,直到它到达终点后,A*将不得不扩展完整的备选路径。
假设广度优先搜索(BFS)在扩展_
状态之前扩展了G
下面的状态,则BFS将能够在不扩展_
状态的情况下终止,并且比A*少进行一些扩展。
为了清楚起见,请按以下方式标记上一个示例中的状态:
abcdefg
SXXXXG.
hijklmn
A*算法中,使用不幸的决策函数将扩展a,b,c,d,e,f并生成g(但不会扩展它)。然后它会继续并扩展h,i,j,k,l和m,之后就能以解决方案结束。
幸运拆分的BFS将扩展h,a,i,b,j,c,k,d,l,e和m,然后以最优解结束。BFS比A*少进行一次扩展,因为它不会扩展f。
是的,如果幸运拆分有利于BFS,BFS有可能击败A*。
除非A*和BFS总是按照相同顺序扩展状态,或者在迷宫上加强进一步的限制,使得启发式函数始终完美地靠近目标,否则此类情况始终存在。
请参阅this paper,了解关于A*搜索的常见误解。其中之一涉及更好的启发式将做更少的工作的误解,另一个涉及到具有0启发式的A*与BFS相同的误解。
--
注意1:评论中有一些关于_
状态是否会扩展的讨论,如果它没有任何后继节点。原始的A*论文指出:
从节点s开始,通过重复应用后继算子R生成子图G的某个部分。在算法的过程中,如果将R应用于一个节点,则我们称该算法已扩展该节点。
因此,如果我们应用R运算符并找不到后继节点,我们仍然已经扩展了该节点。(他们使用了一个希腊字母,我已经替换为R。)但是,通过对上面的地图进行小修改,_
状态确实有一个后继节点,因此A*会扩展_
并生成一个后继节点(而不是目标)。
注意2:
评论中有一个关于A*论文中定理3的问题。该定理指出,总是存在某种打破平局的方案,使得A*算法至少与其他不太了解的算法一样好。这个定理有两个问题。首先,它只说明A*在正确的打破平局的情况下能够击败另一个算法,而不是它将始终击败其他所有算法。第二个问题是BFS比A*更了解。BFS知道所有边缘的成本都是单位成本,而A*不知道。因此,该定理不适用于BFS,因为BFS具有更多信息。
注3:
问题只问“这可能吗。”我在这里提供的答案显示了它可能发生的确切条件。其他答案(其中一个现已被删除)断言它永远不可能发生,因此是不正确的。
_
状态,而 BFS 不会。在这个例子中,BFS 比 A* 更好(考虑到我指定的决策规则)。 - Nathan S.