prolog - 为什么prolog统一是深度优先搜索而不是广度优先搜索？

Question

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

ISO prolog 强制这样做吗？

Answer 1

首先，它相当容易更改。大多数 Prolog 文本都解释了如何编写执行 BFS 的谓词以及如何创建使用任意术语执行此操作的元解释器。事实是，在大学里尝试过 Prolog 的学生(基本上)都能度过使用 Prolog 的头一两周。做到这一点并不完全是一个基本 Prolog 任务，但它也不是高级 Prolog 技术。如果您在 Prolog 上花费了两个月的时间，那么这并不是一件令人生畏的事情。这听起来像是很多 Prolog，但与(例如)Java 相比，它确实不多。出于某种原因，我们希望使用 Prolog 比我们使用实际上不那么有趣的系统更快地到达终点线。

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

我不知道特别强制使用 DFS 的原因。使用 Prolog 一段时间后，非 DFS 的想法对我来说显然效率低下。例如，如果我添加一些代码来处理边缘情况，我每次都会使用 BFS 付费，但仅限于需要使用 DFS 的情况。我觉得 DFS 的内存效率会更高；例如，我不必跟踪一堆可能无用的代码路径。我觉得 DFS 可能更容易控制，因为我可以轻松修剪搜索树。但这些只是感觉；也许我对自然的感觉完全是我所使用的结果。缺乏基于 BFS 的 Prolog 竞争对 watch 明这可能不是一个好主意。另一方面，1980 年的低效之处仍然影响着今天的 Prolog 实现，尽管现在情况已大不相同。