广度优先搜索与A*算法在迷宫中使用曼哈顿距离的比较

Question

在一个迷宫中，给定初始状态和单个终止状态，是否可能设计一个迷宫，使得广度优先搜索比使用曼哈顿距离作为启发式函数的A*算法扩展更少的节点？所有节点的扩展成本为1。

- RotDot20

Answer 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 article

QED

- amit

---

抱歉，这个证明是错误的。请看我的答案，其中有BFS击败A*的例子。 - Nathan S.

@NathanS。请指出证明中的错误步骤，因为它是基于原始论文中引入A*的定理，并且只显示所有条件都适用于该定理。您认为该定理在这里不适用吗？如果是这样，为什么？还是您认为该定理是错误的？原始介绍A*的论文在定理3中展示了这一点，并且后来明确使用BFS示例作为总是扩展更多节点的算法（请参见第IV节，讨论和结论）。 - amit

答案在我提供的误解论文中。BFS不是带有0启发式的A算法。当目标生成时，BFS总是可以终止，因此它可以有更好的打破平局的能力。请参见我的回答中的示例。Dechter和Pearl于1985年发表的论文比原始的A论文更详细地处理了A*算法的最优性问题。 - Nathan S.

本文与手头的启发式函数无关。它主要涉及不一致的启发式方法，而当它涉及一致的启发式方法时，它假定“任意大的状态集”。这些都不适用于问题中所要求的曼哈顿距离。 - amit

要明确一点，我在解释为什么适用条件的证明中加入了单调性限制。 - amit

这个案例与不一致无关，而是BFS在生成目标时终止。明确一点，问题是“可能吗？”如果你给我任何A的实现，我总能找到一个问题，在这个问题中我的BFS会像我的例子一样击败它。简而言之，A只是最优的打破平局。Dechter和Pearl在1985年证明了这一点-但理论比你想象的要复杂得多。我只声称BFS在非常特定的情况下以非常小的数量击败A*，仅此而已。 - Nathan S.

Answer 2

一般来说，这可以通过以下三种方式实现：

1. 当A*算法使用不一致的启发式函数时，它可以对N个状态进行最多2^N次扩展。对于无向图，即使启发式函数是可接受的（h(a,g) <= c(a,g)），但存在某些状态满足|h(a, g)-h(b, g)| > c(a, b)。曼哈顿距离是一个一致的启发式函数，所以在你的例子中这种情况不起作用。

2. 在广度优先搜索中，假定所有代价都为1。因此，当生成目标状态时，它可以立即终止，知道它已经得到了到达目标的最佳代价。而A*算法通常在选择目标状态进行扩展之前不会终止。请注意，如果A*可以保证所有边缘具有统一的代价（或者具有某个最小代价），那么A*可以采取相同的策略。

3. 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：

问题只问“这可能吗。”我在这里提供的答案显示了它可能发生的确切条件。其他答案（其中一个现已被删除）断言它永远不可能发生，因此是不正确的。

- Nathan S.

---

"但是，我可以在我的示例中添加另一个状态": 请添加。 - trincot

A* 仍会扩展 _ 状态，而 BFS 不会。在这个例子中，BFS 比 A* 更好（考虑到我指定的决策规则）。 - Nathan S.

在你的编辑之后：这篇论文使用了“扩展”的奇怪定义。他们可以这样做，但要看OP是否分享该定义。他们似乎暗示扩展是有代价的，在这种情况下，扩展是“真正的扩展”，即某些东西被扩展，变得更长。我认为说某物扩张而不变长，是在玩弄语言。 - trincot

@trincot 这是来自原始的A*论文的定义。如果您认为这很奇怪，那我也无能为力。这就是他们给出的定义。 - Nathan S.

这个问题问的是“是否可能”。我的例子证实了它是可能的。请阅读我提供链接的论文以获取更多讨论。 - Nathan S.