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

在上一章節(jié)里面，我給大家演示了一個(gè)Prolog特有的神奇的功能：它能夠回答你提出的問題！在這一章里面，我將簡單的解釋一下Prolog是如何能夠回答你的問題的。 首先，還是自己試著把下面的程序?qū)懸幌拢缓蠹虞d到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)會(huì)試圖證明這個(gè)查詢，很顯然，程序會(huì)返回”true.”那么，Prolog系統(tǒng)是如何找到答案的呢？當(dāng)我們向Prolog提問”ancestor(keyuan,yuqing)”的時(shí)候，Prolog首先會(huì)在它的知識(shí)庫里面尋找”ancestor”的定義，當(dāng)然，它找到了兩個(gè)”ancestor”的定義：

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

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

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

很顯然，X=keyuan,Y=yuqing。之后，Prolog會(huì)把a(bǔ)ncestor換成后面的條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

加分習(xí)題

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.

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

2. (這道題有點(diǎn)難度哦)請(qǐng)看下圖：

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

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).

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

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