为什么深度优先搜索不是最优的，而广度优先搜索是最优的？

Question

我一直有一个问题，但从来没有得到合理的答案：

通常，在人工智能课程中，当涉及到搜索时，总是说BFS（广度优先搜索）是最优的，但DFS（深度优先搜索）不是，但我可以举出许多例子证明DFS甚至可以更快地得到答案。所以，有人能解释一下吗？我可能漏掉了什么吗？

- HMdeveloper

---

在时间复杂度（执行性能）或空间复杂度（内存使用）方面哪个更优？还是在输出的实际质量方面，当最佳解决方案非常难以计算时（例如在贪心算法的情况下）？ - barak manos

@barakmanos 通常，在AI的背景下，最优性是指解决方案，而不是策略。我猜这就是OP的意思。 - Stefano Sanfilippo

Answer 1

“Optimal”在这里指的是“产生最佳路径”，而不是“是可能的最快算法”。当搜索状态空间以找到目标路径时，深度优先搜索（DFS）可能会产生比广度优先搜索（BFS）更长的路径。需要注意的是，只有当操作未加权时，BFS才是最优的；如果不同的操作具有不同的权重，则需要像A*这样的算法。

- user2357112

---

谢谢你的出色回答。那么针对这种情况呢：目标位于树的最左侧分支。在这种情况下哪个是最优的？ - HMdeveloper

如果您知道目标在树的最左侧分支中，您就不需要搜索算法。 每次只需采取列表中的第一个操作即可。 这并不是一个特别常见的情况，因此优化针对该情况并没有多大用处。 - user2357112

你需要一个特定的启发式来使用A*算法。如果找不到这样的启发式，那么可以考虑使用统一代价搜索（一种修改版的广度优先搜索）。 - Stefano Sanfilippo

@StefanoSanfilippo：嗯，通常至少可以得到一些用作启发式的东西。如果您已经编写了A*算法，但是无法想出启发式函数，那么“我们到了吗？”函数将使用一些额外开销使您得到UCS算法。 - user2357112

Answer 2

这是因为他们通过 最优策略 指的是返回的解决方案最大化效用。

关于这一点，没有任何保证DFS找到的第一个解决方案是最优的。此外，从一般意义上讲，BFS也不是最优的，所以您的陈述是错误的。

这里的主要问题在于保证某种搜索策略将始终返回最优结果。任何策略都可能是特定情况下的最佳选择，但通常情况下（特别是在人工智能领域），您并不知道具体情况是什么，最多只有一些假设。

然而，当搜索树是有限的，所有操作成本相同，并且所有解决方案长度相同时， DFS是最优的。虽然这听起来很受限制，但有一个重要的问题类满足这些条件：CSPs（约束满足问题）。也许您考虑的所有示例都属于这个（相当常见的）类别。

- Stefano Sanfilippo

Answer 3

您可以参考我的回答this问题，其中我解释了为什么深度优先搜索不是最优的选择，以及为什么广度优先搜索不是解决无信息状态空间搜索问题的最佳选择。

- Net_Raider

Answer 4

您可以参考下面的链接，它考虑了一棵树的例子，并使用两种方法进行解决。 link

- Shashwat Jha

---

虽然这理论上回答了问题，但最好在此处包含答案的基本部分，并提供参考链接。 - Anton Menshov