冗余推理和无限循环

9.4.4 冗余推理和无限循环

现在，我们转向Prolog的阿基里斯之踵（唯一致命弱点——译者注）：深度优先搜索与包含了重复状态和无限路径的搜索树之间的不匹配。考虑如下判定有向图中的两点之间的是否存在路径的逻辑程序：

path(X,Z) :- link(X,Z)

path(X,Z) :- path(X,Y), link(Y,Z)

由事实link(a,b)和link(b,c)所描述的一个简单的三节点图如图9.9（a）所示。利用该程序，查询path(a,c)生成如图9.10（a）所示的证明树。另一方面，如果我们把两个子句按下列次序排列：

path(X,Z) :- path(X,Y), link(Y,Z)

path(X,Z) :- link(X,Z)

图9.9 （a）寻找从A到C的路径，将导致Prolog进入一个无限循环。（b）每个节点都连接到下一层的两个随机后继节点的图。寻找从A1到J4的一条路径需要877步推理

图9.10 （a）证明存在从A到C的路径。（b）当子句处于“错误的”次序时生成的无限证明树

那么Prolog会沿着如图9.10（b）所示的无限路径前进。因此作为确定子句的定理证明机——甚至对数据日志程序而言，如同本例所显示——Prolog是不完备的，因为对某些知识库，它无法证明被蕴涵的语句。注意，前向链接不会遇到这个问题：一旦推理出path(a,b)、path(b,c)和path(a,c)，前向链接就停止了。

深度优先反向链接也存在冗余计算的问题。例如，在图9.9（b）中寻找从A1到J4的路径，Prolog需要执行 877 步推理，大部分推理涉及到寻找那些途经无法到达目标的节点的所有可能路径。这和第三章讨论的重复状态问题类似。推理的总量可能是生成的基本事实数量的指数级。如果我们替代地采用前向链接，至多会生成n2path(x,y)个事实，链接n个节点。对于图9.9（b）中的问题，只需要62步推理。

图搜索问题的前向链接是动态规划的一个例子，其中子问题的解是由那些更小的子问题的解递增构造的，并被缓存起来以避免重复计算。我们可以在使用备忘法的反向链接系统中获得类似的效果——这就是，当发现子目标的解时将它们缓存起来，当子目标再次出现时重新使用这些解，而不是重复以前的计算。这就是制表逻辑程序设计系统采用的方法，它们利用有效的存储和检索机制实现备忘法。制表逻辑程序设计将反向链接的目标指导和前向链接的动态规划的效率结合起来。对数据日志程序而言，它还是完备的，这意味着程序员可以更少地担心无限循环。