depth-first-search - DFS“可以返回任何路径”

Question

这是来自加州伯克利大学的AI 练习考试。

问题提出

考虑上面显示的状态空间图。A 是起始状态，G 是目标状态。每条边的成本都显示在图表上。每条边都可以双向遍历。请注意，启发式 h1 是一致的，但启发式 h2 是不一致的。

对于以下每个图搜索策略（不要回答树搜索），标记它可以返回的列出的路径中的哪一个（如果有）。请注意，对于某些搜索策略，返回的特定路径可能取决于平局行为。

搜索算法是深度优先、广度优先、统一成本、A* 与 h1 和 A* 与 h2。“列出的路径”是 ABDG、ACDG 和 ABCDFG

这是我从图中构建的搜索树（具有各种启发式方法和操作成本）： 该解决方案表明 DFS 将返回 ABDG、ACDG 和 ABCDFG，因为“DFS 可以返回任何路径”

我可以理解，如果决胜局是字母表中较早的字母，DFS 将返回 ABCDE G。如果决胜局是字母表中较晚的字母，DFS 将返回 ACD G。但我不明白在什么情况下情况 DFS 将返回 ABDG 或 ABCDF G。

我还认为 DFS 扩展了最深的节点并以这种方式返回解决方案。它可以返回任何路径解决方案是真的吗？如果是这样，怎么做？

标签： depth-first-searchstate-spacetree-search

Answer 1

DFS（深度优先搜索）不评估路径成本。因此，没有决胜局。DFS 仅返回它遇到的第一个成功路径。特定路径完全取决于在每个节点对连续路径进行排序的顺序。因此，该图上的 DFS 可以返回九种可能的解中的任何一种。

例如，假设该图与此顺序相连：

Node   edges to ...
 A       B C
 B       C D
 C       D A B
 D       F B C G E
 F       G D
 G       E F
 E       D G

然后遍历很简单 ABCDFG（每个节点的第一个引用）。其他边缘排序将导致返回其他解决方案。

同样，BFS 可能会导致返回 4 节点解决方案中的任何一个。

这样就清楚了吗？