2023學(xué)年完整公開(kāi)課版Prolog的工作機(jī)理

Prolog的工作機(jī)理1匹配與回溯方法

1.實(shí)例化Prolog中稱(chēng)無(wú)值的變量為自由變量，有值的變量為約束變量。一個(gè)變量取了某值就說(shuō)該變量約束于某值，或者說(shuō)該變量被某值實(shí)例化了。例：mother(Who1,xiaoming).在Who1有值以前，它是自由變量，如果(Who1=xiaozhang)，那么我們就說(shuō)變量Who1約束于xiaozhang，或說(shuō)Who1被xiaozhang實(shí)例化了。2.匹配如果兩個(gè)謂詞的名相同，參數(shù)的個(gè)數(shù)和類(lèi)型對(duì)應(yīng)相同，并且對(duì)應(yīng)參數(shù)滿(mǎn)足下面的條件之一，那么這兩個(gè)謂詞可以匹配(match)。

（1）如果兩者都是常量，則必須完全相同。

（2）如果兩者都是約束變量，則兩個(gè)約束值必須相同。（3）如果其中一個(gè)是常量，一個(gè)是約束變量則約束值與常量必須相同。

（4）當(dāng)兩者至少有一個(gè)是自由變量。其實(shí)匹配是一種操作，這種操作為參加匹配的自由變量和常量，或者兩個(gè)自由變量建立一種對(duì)應(yīng)關(guān)系，將常量作為對(duì)應(yīng)變量的約束值，使兩個(gè)對(duì)應(yīng)的自由變量始終保持一致。如果其中一個(gè)被某值實(shí)例化，那么另一個(gè)也被同一值實(shí)例化；反過(guò)來(lái)說(shuō)，如果其中一個(gè)被解除約束，則另一個(gè)值的約束也被解除。上面例子中每對(duì)謂詞均可以匹配。對(duì)于含有自由變量的謂詞表示，如Bame(X)，它與game(xijizhengba).匹配的結(jié)果是自由變量X被常量xijizhengba實(shí)例化。再如color(Y)與color(Z)，匹配的結(jié)果是，當(dāng)自由變量Y和Z中的一個(gè)被某值約束，如Y被apple實(shí)例化，則Z也被apple實(shí)例化。

3.回溯大家可能玩過(guò)走迷宮的游戲，在走迷官的過(guò)程中，我們就經(jīng)常用到回溯。讓我們通過(guò)個(gè)走迷官的例子來(lái)解釋回溯這個(gè)概念。

迷宮如圖所示，迷宮的左下角有一只的猴子，它想吃到迷宮右上角的香蕉。下面的圖記錄了猴子找到香蕉的過(guò)程。在這里畫(huà)的幾幅圖是搜索與回溯過(guò)程的示例。由這組示意圖可以看出，猴子通過(guò)搜索（例如按左手法則，沿左邊的阻擋墻前進(jìn)）和回溯（在碰壁時(shí)往回退）來(lái)完成尋找香蕉的過(guò)程。圖中帶有箭頭的黑線(xiàn)是搜索路線(xiàn)，紅色帶箭頭的線(xiàn)是回溯路線(xiàn)。在Prolog中，回溯是在程序目標(biāo)確定后，Prolog就會(huì)從上到下，從左到右地在程序中搜索能匹配的事實(shí)和規(guī)則。在搜索過(guò)程中，當(dāng)某條事實(shí)或規(guī)則無(wú)法滿(mǎn)足目標(biāo)時(shí)，Prolog會(huì)繼續(xù)搜索其他能滿(mǎn)足目標(biāo)的事實(shí)或規(guī)則，進(jìn)行掃描實(shí)例化和匹配等操作，目的是努力找到程序的一個(gè)或多個(gè)解。2Prolog程序的運(yùn)行過(guò)程

Prolog程序的運(yùn)行過(guò)程是從詢(xún)問(wèn)語(yǔ)句出發(fā)，不斷的進(jìn)行實(shí)例化、匹配、有時(shí)還需要回溯，直到目標(biāo)被完全滿(mǎn)足成最終不能滿(mǎn)足時(shí)為止。

以家庭關(guān)系程序?yàn)槔疾焖倪\(yùn)行過(guò)程，目的是了解Prolog是怎樣分清家庭成員間關(guān)系的。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運(yùn)行過(guò)程：首先從目標(biāo)出發(fā)，即先執(zhí)行第8條語(yǔ)句?-mother(Who1,xiaoming).（誰(shuí)是小明的母親？）求解目標(biāo)為Mother(Who1,xiaoming).系統(tǒng)對(duì)程序進(jìn)行掃描，尋找能與目標(biāo)謂詞匹配的事實(shí)或規(guī)則頭部。顯然，程序中前面的四條事實(shí)均不能與目標(biāo)匹配，而第5個(gè)語(yǔ)句的左端，即規(guī)則。mother(X,Z):-father(Y,Z)husband(Y,X).的頭部可與目標(biāo)謂詞匹配。又因?yàn)檫@個(gè)語(yǔ)句是一個(gè)規(guī)則，所以，要使其結(jié)論（頭部）成立，其前提（體部）必須全部為真。于是，對(duì)原目標(biāo)的求解轉(zhuǎn)化為對(duì)新目標(biāo)。father(Y,Z),husband(Y,X).的求解。由于規(guī)則頭部與目標(biāo)謂詞匹配的結(jié)果是Z被xiaoming實(shí)例化，即Z=xiaoming。因此程序運(yùn)行到此處是對(duì)子目標(biāo)father(Y,xiaoming)和husband(Y,X)求解。子目標(biāo)的求解過(guò)程與主目標(biāo)完全一樣，也是從頭對(duì)程序進(jìn)行掃描，不斷進(jìn)行匹配，直到匹配成功或掃描完整個(gè)程序?yàn)橹?。?duì)于第一個(gè)子目標(biāo)father(Y,xiaoming)的求解，子目標(biāo)與程序中的第1句事實(shí)匹配成功，Y被實(shí)例化為xiaowang。于是Prolog接著求解第二個(gè)子目標(biāo)husbnd(Z,X)。由于變量Y被實(shí)例化為xiaowang，則第二個(gè)子目標(biāo)實(shí)際上已變成了husband(xiaowang,X)，這樣，第二個(gè)子目標(biāo)與第三條語(yǔ)句匹配成功，同時(shí)X被實(shí)例化為xiaozhang.由于兩個(gè)子目標(biāo)都求解成功，所以原目標(biāo)mother(Whe1,xiaoming)也匹配成動(dòng)，自由變量Who1被實(shí)例化為xiaozhang。于是Prolog回答：Who1=xiaozhang.3問(wèn)題與練習(xí)

1.根據(jù)求解第一個(gè)目標(biāo)的過(guò)程來(lái)分析第二和第三個(gè)詢(xún)問(wèn)的求解過(guò)程。2.假設(shè)一個(gè)Prolog程序包括以下語(yǔ)句thriftier(carol,john).thriftier(bill,sue).thriftier(sue,carol).thriftier(X,Z):