第3章：Prolog是如何回答問題的

在上一章節(jié)里面，我給大家演示了一個Prolog特有的神奇的功能：它能夠回答你提出的問題！在這一章里面，我將簡單的解釋一下Prolog是如何能夠回答你的問題的。 首先，還是自己試著把下面的程序?qū)懸幌?，然后加載到SWI-Prolog里面。

parent(di,yuqing).
parent(keyuan,jianbo).
parent(jianbo,di).

ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).

然后我們問Prolog:

?- ancestor(keyuan,yuqing).

Prolog系統(tǒng)會試圖證明這個查詢，很顯然，程序會返回”true.”那么，Prolog系統(tǒng)是如何找到答案的呢？當我們向Prolog提問”ancestor(keyuan,yuqing)”的時候，Prolog首先會在它的知識庫里面尋找”ancestor”的定義，當然，它找到了兩個”ancestor”的定義：

ancestor(X,Y):-parent(X,Y).
ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).

按照默認的規(guī)定，它會首先取第一個規(guī)則：“ancestor(X,Y):-parent（X,Y).”由于這個規(guī)則里面的X,Y是變量，Prolog會給這兩個變量賦值，使得：

ancestor(keyuan,yuqing) = ancestor(X,Y)

很顯然，X=keyuan,Y=yuqing。之后，Prolog會把ancestor換成后面的條件：

ancestor(keyuan,yuqing) ==> parent(keyuan,yuqing).

之后，Prolog試圖證明”parent(keyuan,yuqing)”,根據(jù)上面的程序，很顯然，這是錯的，會返回：”false”。那么，之后Prolog會怎么辦呢？記得上面說過，ancestor有兩個規(guī)則吧，我們之前根據(jù)慣例選擇了第一個規(guī)則，現(xiàn)在我們可以試一下第二個規(guī)則：”ancestor(X,Y):-parent(X,Z),ancestor(Z,Y).”根據(jù)這個規(guī)則，Prolog會把”ancestor(keyuan,yuqing).”換成了：

parent(keyuan,Z),ancestor(Z,yuqing).

之前Prolog需要證明一個式子(ancestor(keyuan,yuqing).)，現(xiàn)在Prolog需要證明兩個式子了。因為這兩個式子中間是一個逗號，逗號的意思是”且“，所以只有當這兩個式子都是”true”時候，整個的查詢才是”true”。首先，Prolog會嘗試第一個”parent(keyuan,Z).“它會在知識庫里面找到：”parent(keyuan,jianbo)”。于是，Z=jianbo。這時候，我們之前的那兩個式子變成了：

parent(keyuan,jianbo),ancestor(jianbo,yuqing).

然后，Prolog嘗試證明第二個式子：”ancestor(jianbo,yuqing)”。同樣的道理，Prolog首先找到的是：”ancestor(X,Y):-parent(X,Y)”，于是想證明”ancestor(jianbo,yuqing)”就變成了要證明”parent(jianbo,yuqing)”。很顯然”parent(jianbo,yuqing)”會返回”false”。這時候，程序會試著把”ancestor(jianbo,yuqing)”替換成”parent(jianbo,Z1),ancestor(Z1,yuqing)”。要注意的是，此處我們不用Z作為變量了，而是用Z1作為變量，這叫做變量的重命名。原因是我們之前已經(jīng)用過Z做變量了，為了把現(xiàn)在這個Z變量和之前的Z變量區(qū)別開來，我們把現(xiàn)在的Z變量重命名為Z1。很顯然，無論變量的名字如何，它都是一個變量，理論上我們可以把它賦值成任何值，所以修改名字不會改變變量的含義。根據(jù)我們的知識庫，此時Z1應該等于di。于是我們得到了兩個式子：

parent(jianbo,di),ancestor(di,yuqing).

把”ancestor(di,yuqing).”換成”parent(di,yuqing)”，我們得到一個事實(fact),所以”parent(di,yuqing)”是真。 綜上所述，我們其實是用回溯的方式把”ancestor(keyuan,yuqing).”換成了：

parent(keyuan,jianbo),parent(jianbo,di),parent(di,yuqing).

由于上面的三個式子都是真的，所以”ancestor(keyuan,yuqing).”是真的。

下面這個圖顯示了Prolog是如何證明你的查詢的：

通過這個簡單的例子，我們可以得出，Prolog通過三個方面來嘗試著證明你給的查詢(query)：

• 匹配(unifing/matching)。例如上面的”ancestor(keyuan,yuqing) = ancestor(X,Y)”，Prolog試圖從它的知識庫里面找出最符合你的查詢的規(guī)則或者是事實。
• 變量重命名(variable renaming)。例如上面的”parent(jianbo,Z1),ancestor(Z1,yuqing)”，因為在同一個查詢(query)里面已經(jīng)有了”Z”，所以Prolog系統(tǒng)將重復的Z命名為Z1。(事實上，在Prolog內(nèi)部，變量根本不會用”Z”,”Z1”這樣的名字，Prolog的編譯程序的時候就已經(jīng)將”Z”換成了”G132329392049”這類名字以保證名字不會重復)。
• 回溯(back-tracking)。這是Prolog最最重要的一個特性。Prolog是用深度優(yōu)先(depth-first search)的算法來尋找答案的。當一個規(guī)則或者是事實不符合時，Prolog會通過回溯的方式回到之前的狀態(tài)，然后去嘗試另外的規(guī)則或者是事實，知道你的查詢(query)被證明為止。如果所有的可能性都搜索過了，你的查詢?nèi)匀徊荒艿玫阶C實，那么Prolog會認為你的查詢證實不了，返回”false”。有關(guān)回溯算法的詳細介紹你可以去網(wǎng)絡(luò)上搜索一下。

到這里，這一章就結(jié)束了，希望你對Prolog程序的執(zhí)行順序有了一個初步的了解。說實話，Prolog的程序回溯執(zhí)行方式有時候我自己都想不明白，特別是遇到特別復雜的問題的時候。這個時候，最好的辦法就是拿一張紙一支筆，親自畫一下程序的回溯圖，就想上面的那個圖一樣，這樣就能幫助你理解程序了～

加分習題

1. 我們有如下代碼：

   parent(tom,bob). parent(pam,bob). parent(pam,liz). parent(pam,bob). male(tom). male(bob). female(liz). female(pam). sister(X,Y):-

    parent(Z,X),
    parent(Z,Y),
    female(X),
    X\=Y.

   請比照著上面的教程里面”ancestor(keyuan,yuqing)”的執(zhí)行順序圖畫一個 ?-sister(liz,bob). 的執(zhí)行圖。(注：程序中的”X\=Y”是X不等于Y的意思)

2. (這道題有點難度哦)請看下圖：

我們的目的是要在上面表格中白色的方格(帶有LXX標識的方格)里面填上英文單詞，可供選擇的單詞有：

word(d,o,g).    word(r,u,n).    word(t,o,p).    word(f,i,v,e).
word(f,o,u,r).  word(l,o,s,t).  word(m,e,s,s).  word(u,n,i,t).
word(b,a,k,e,r).    word(f,o,r,u,m).    word(g,r,e,e,n).
word(s,u,p,e,r).    word(p,r,o,l,o,g).  word(v,a,n,i,s,h).
word(w,o,n,d,e,r).  word(y,e,l,l,o,w).

試著寫出一個規(guī)則solution.

solution(L1,L2,L3,L4,L5,L6,L7,L8,L9,L10,L11,L12,L13,L14,L15,L16).