2023学年完整公开课版Prolog的工作机理

Prolog的工作机理1匹配与回溯方法

1.实例化Prolog中称无值的变量为自由变量，有值的变量为约束变量。一个变量取了某值就说该变量约束于某值，或者说该变量被某值实例化了。例：mother(Who1,xiaoming).在Who1有值以前，它是自由变量，如果(Who1=xiaozhang)，那么我们就说变量Who1约束于xiaozhang，或说Who1被xiaozhang实例化了。2.匹配如果两个谓词的名相同，参数的个数和类型对应相同，并且对应参数满足下面的条件之一，那么这两个谓词可以匹配(match)。

（1）如果两者都是常量，则必须完全相同。

（2）如果两者都是约束变量，则两个约束值必须相同。（3）如果其中一个是常量，一个是约束变量则约束值与常量必须相同。

（4）当两者至少有一个是自由变量。其实匹配是一种操作，这种操作为参加匹配的自由变量和常量，或者两个自由变量建立一种对应关系，将常量作为对应变量的约束值，使两个对应的自由变量始终保持一致。如果其中一个被某值实例化，那么另一个也被同一值实例化；反过来说，如果其中一个被解除约束，则另一个值的约束也被解除。上面例子中每对谓词均可以匹配。对于含有自由变量的谓词表示，如Bame(X)，它与game(xijizhengba).匹配的结果是自由变量X被常量xijizhengba实例化。再如color(Y)与color(Z)，匹配的结果是，当自由变量Y和Z中的一个被某值约束，如Y被apple实例化，则Z也被apple实例化。

3.回溯大家可能玩过走迷宫的游戏，在走迷官的过程中，我们就经常用到回溯。让我们通过个走迷官的例子来解释回溯这个概念。

迷宫如图所示，迷宫的左下角有一只的猴子，它想吃到迷宫右上角的香蕉。下面的图记录了猴子找到香蕉的过程。在这里画的几幅图是搜索与回溯过程的示例。由这组示意图可以看出，猴子通过搜索（例如按左手法则，沿左边的阻挡墙前进）和回溯（在碰壁时往回退）来完成寻找香蕉的过程。图中带有箭头的黑线是搜索路线，红色带箭头的线是回溯路线。在Prolog中，回溯是在程序目标确定后，Prolog就会从上到下，从左到右地在程序中搜索能匹配的事实和规则。在搜索过程中，当某条事实或规则无法满足目标时，Prolog会继续搜索其他能满足目标的事实或规则，进行扫描实例化和匹配等操作，目的是努力找到程序的一个或多个解。2Prolog程序的运行过程

Prolog程序的运行过程是从询问语句出发，不断的进行实例化、匹配、有时还需要回溯，直到目标被完全满足成最终不能满足时为止。

以家庭关系程序为例，考察它的运行过程，目的是了解Prolog是怎样分清家庭成员间关系的。father(xiaowang,xiaoming).father(laowang,xiaoming).husband(xiaowang,xiaozhang).husband(laowang,laoli).mother(X,Z):-father(Y,Z),husband(Y,X)grandfather(X,Z):-father(Y,Z),father(X,Y).grandmother(X,Z):-grandfather(Y,Z),husband(Y,X).?mother(Who1,xiaoming).?grandfather(Who2,xiaoming).?grandmother(Who3,xiaoming).

Prolog运行过程：首先从目标出发，即先执行第8条语句?-mother(Who1,xiaoming).（谁是小明的母亲？）求解目标为Mother(Who1,xiaoming).系统对程序进行扫描，寻找能与目标谓词匹配的事实或规则头部。显然，程序中前面的四条事实均不能与目标匹配，而第5个语句的左端，即规则。mother(X,Z):-father(Y,Z)husband(Y,X).的头部可与目标谓词匹配。又因为这个语句是一个规则，所以，要使其结论（头部）成立，其前提（体部）必须全部为真。于是，对原目标的求解转化为对新目标。father(Y,Z),husband(Y,X).的求解。由于规则头部与目标谓词匹配的结果是Z被xiaoming实例化，即Z=xiaoming。因此程序运行到此处是对子目标father(Y,xiaoming)和husband(Y,X)求解。子目标的求解过程与主目标完全一样，也是从头对程序进行扫描，不断进行匹配，直到匹配成功或扫描完整个程序为止。对于第一个子目标father(Y,xiaoming)的求解，子目标与程序中的第1句事实匹配成功，Y被实例化为xiaowang。于是Prolog接着求解第二个子目标husbnd(Z,X)。由于变量Y被实例化为xiaowang，则第二个子目标实际上已变成了husband(xiaowang,X)，这样，第二个子目标与第三条语句匹配成功，同时X被实例化为xiaozhang.由于两个子目标都求解成功，所以原目标mother(Whe1,xiaoming)也匹配成动，自由变量Who1被实例化为xiaozhang。于是Prolog回答：Who1=xiaozhang.3问题与练习

1.根据求解第一个目标的过程来分析第二和第三个询问的求解过程。2.假设一个Prolog程序包括以下语句thriftier(carol,john).thriftier(bill,sue).thriftier(sue,carol).thriftier(X,Z):