基于Prolog二元关系闭包运算的研究与实现

STEP3 用目标

transitive_closure(X,Y)

进行提问。

STEP4 完整的程序运行界面及结果分别参见图2（a）和（b）：

（a）

（b）

图2 求传递闭包的运行界面及结果

STEP5 分析结果：在这里求出的所有关系序对（A，B）的并集即为传递闭包R +的解。

即t(R)=R + = R*=R∪R2∪R3

={（a, a）, （a ,b）,（b ,a）,（c ,b）,（a, a）, （a, b）,（a ,a）,（b, b）, （ b ,a）,（c, a）,（a, b）, （a, a）,（a ,a）,（b, a）（a, a）, （b, a）,（b ,b）,（b ,a）, （c ,b）,（c ,a）}

={（a, a）, （a ,b）,（b ,a）,（b ,b）（c, a）,（c, b）}

3重复解的出现与消除

3.1 问题的提出

在Visual Prolog求解过程中，系统内部用到了很多控制策略，比如，匹配、回溯、递归等，回溯机制是其主要的运行机制。所谓回溯(backtrack)，是指Visual　Prolog采用“回退再试”的方式寻找给定问题的所有可能解的一种方法。这种机制使得Visual Prolog具有了通过所有已知事实和规则进行搜索求解的能力。即在求解的过程中，当Visual Prolog开始为求解一个问题(或目标)寻找答案时，往往要在多种可能情况中做出抉择，首先在分支点(即回溯点)设置好标志，然后选择要追踪的第一个子目标，如果该子目标失败，Visual Prolog将回退到上一个回溯点尝试另一个目标[4]。

回溯本身是一种获得目标所有可能解的良好方法，但也有副作用，在问题的求解过程中可能导致Visual Prolog给出多余重复的答案，而Visual Prolog自己不能区分实质上相同的两个解。最简单的原因就是这个问题可以与多个事实相匹配，而且在寻找下一个解答的过程中，Prolog并不留心它前面给出的解，它只是按照不同的规则分别对其进行匹配。如例1中，若按照给定的顺序找出所有有关transitive_closure的事实和规则，最后的结果可以通过不同的路径得到，Prolog将其相同的结果作为不同的解答，使得运行结果中出现了很多重复的序偶，需要人工进行分析，删去重复元素，才能得到最后的解。为了增强传递闭包求解的实用性，不需要人工进行计算，可以考虑消除运行结果中重复的关系序对，直接得到最后所要的结果。这也是下面将要解决重复解消除问题。

3.2 设计思想及方案

Prolog中，not是带有一个目标X作为变元的谓词。它的含义是：如果X成功，则not(X)失败，否则，not(X)成功[5]。如例1中

not(r(A, B))

表示A，B不属于序对集合r这样的条件。

在消除重复解的过程中，正是运用此思想，在产生新解之前，首先判断此解是否已经存在，若不存在，进行输出，若已经存在，继续寻找新的解，避免重复解的出现。例如，针对上述传递闭包求解规则

②transitive_closure(A,B):-r(A,B). /*求R，Rt(R) */

③transitive_closure(A,B):-r(A,C),r(C,B). /* 求R2 ，R2t(R)*/

④transitive_closure(A,B):- r(A,D),r(D,E),r(E,B). /* 求R3 ，R3t(R)*/

新的求解步骤如下：

STEP1首先，根据知识库对规则②进行匹配，求出相应的解。

STEP2对规则②进行完全匹配后，紧接着对规则③进行匹配，求解过程中，为了避免产生重复解，应该先判断此解是否已在由规则②满足的结果中，即增加一个not语句，not(transitive_closure(A,B)).

形成新的规则

transitive_closure1(A,B):-r(A,C),r(C, B),not(transitive_closure(A,B).

STEP3同理，在对规则④匹配过程中，为了判断所求结果是否已经包含于前面两个子目标所产生的结果，同时增加两条not语句，即

not(transitive_closure(A,B)),not(transitive_closure1(A,B)).

形成新的规则

transitive_closure2(A,B):-r(A,C),r(C,D),r(D,B),

not(transitive_closure(A,B)), not(transitive_closure1(A,B)).

3.3 程序实现与结果分析

根据上面提出的求解思路，求解例1的完整程序为：

predicates/*谓词说明 */

nondeterm r(string,string)

nondeterm transitive_closure(string,string)

nondeterm transitive_closure1(string,string)

nondeterm transitive_closure2(string,string)

clauses/*子句说明 */

r('a','a'). /*（a, a）∈R */

r('a','b'). /*（a, b）∈R */

r('b','a'). /*（b, a）∈R */

r('c','b'). /*（c, b）∈R */

transitive_closure(A,B):-r(A,B).

transitive_closure1(A,B):-r(A,C),r(C, B),not(transitive_closure(A,B).

transitive_closure2(A,B):-r(A,C),r(C,D),r(D,B),not(transitive_closure(A,B)), not(transitive_closure1(A,B)).

GOAL /*目标 */

transitive_closure(A,B);

transitive_closure1(A,B);

transitive_closure2(A,B).

运行界面和结果分别如图3(a)和(b)所示。

（a）

（b）

图3消除重复解的运行界面及结果图

由运行结果图可以看到，求解的最终结果中，没有出现重复解，使得求解传递闭包的过程完全自动化，当然这只是其中的一种设计方法。

4结语

关系作为一种抽象工具，它在计算机科学中的形式语言与自动机理论等方面又重要作用。特别是几种特殊关系，其求解方法更应该被掌握。本文所介绍的基于Prolog实现二元关系闭包运算有着一定的典型研究意义及价值。根据同样的设计步骤和思想，可并对其做以扩展，对二元关系上组合关系的性质进行判断，例如，自反、对称、传递、等价和偏序关系等。

参考文献
[1] 苏畅,蔡经球. 新一代智能语言VISUAL PROLOG[J].计算机应用研究,1999.
[2] 马光思. 离散数学.西安：西安电子科技大学出版社[M],2004.7.
[3] Kenneth H.Rosen. Discrete Mathematics and its Applications(Fifth Edition).（China Machine Press）北京：机械工业出版社[M],2003.3.
[4] 雷英杰,华继学,徐彤,狄博. Visual Prolog截断机制对回溯的作用机理[J]. 计算机工程,2005.31(18).
[5] 刘凤. 基于Visual Prolog 的牵引变电所故障分析专家系统研究[D].西南交通大学2005.

 2/2   首页 上一页 1 2