为什么Prolog统一使用深度优先搜索而不是广度优先搜索？

Question

我刚开始学习prolog，想知道为什么它使用dfs而不是bfs，以及为什么没有简单的方法可以更改它。

ISO prolog是否要求这样做？

- nosefouratyou

---

当你在搜索一棵树时，只要找到你要找的东西，就可以停止搜索。这意味着“深度优先搜索”和“广度优先搜索”之间存在差异。但Prolog不是在进行搜索，而是在进行计算。对于“深度优先计算”和“广度优先计算”，没有任何区别，因为你必须进行完整的计算才能得到结果。 - Enigmativity

你真的在谈论统一中的深度优先吗？这是你的意思吗？ - false

你能给一个“unification depth-first-search”这个术语的例子吗？或者你是指一般的深度优先搜索，例如在树结构中搜索？ - lurker

在典型的BFS任务中，您可以处理当前节点而无需处理其所有子节点。在Prolog中，要处理节点，您应该处理其所有子节点，就像您不能在找到“x”之前找到“x + 5”的结果一样。 - Stanislav Ivanov

Answer 1

首先，它相当容易改变。大多数Prolog文本都解释了如何编写执行BFS的谓词以及如何创建可以使用任意术语执行BFS的元解释器。事实上，在大学里尝试Prolog的学生基本上只需要一两周就能掌握。虽然这不是一个基本的Prolog任务，但也不是一种高级的Prolog技术。如果你花两个月时间学习Prolog，这并不是什么令人畏惧的事情。听起来像是很多Prolog，但与（比如）Java相比，这真的不算什么。由于某种原因，我们希望能够更快地掌握Prolog，而对于实际上不那么有趣的系统，我们却不会这样期望。

我相信ISO规定的搜索策略被称为SLD Resolution，深度优先搜索源于此解析机制。我没有阅读ISO标准，所以也许有比我更了解的人会发表评论。如果解析方法（因此，深度优先或广度优先）不是强制性的，那么管理Prolog标准化将会很困难，因为以一种方式成功的计算可能会以另一种方式进入无限循环。一个不指定正常程序行为的语言标准将是一个相当糟糕的标准。尽管如此，完全可以内置一个用于指定替代搜索策略的方法。

我不知道为什么特别要求使用深度优先搜索。使用Prolog一段时间后，不使用DFS的想法似乎显然是低效的。例如，如果我添加一些代码来处理一个边缘情况，在BFS中每次都要付出代价，但只有在DFS中必要时才需要。我觉得DFS会更加节省内存; 我不必跟踪一堆可能无用的代码路径。我觉得DFS可能更容易控制，因为我可以轻松修剪搜索树。但这些只是感觉而已；也许我的自然感觉完全是由我使用过的东西所决定的。没有以BFS为基础的Prolog竞争对手的存在，暗示着这可能不是一个好主意。另一方面，1980年的低效仍然影响着Prolog实现，即使现在情况已经大不相同。

- Daniel Lyons