1、1李偉生李偉生信科大廈信科大廈19樓樓Tel：2內(nèi)容提要內(nèi)容提要: : 8.1 8.1 狀態(tài)圖搜索策略狀態(tài)圖搜索策略 8.2 8.2 啟發(fā)式搜索啟發(fā)式搜索 8.3 8.3 與或圖搜索與或圖搜索 8.4 8.4 博弈樹搜索博弈樹搜索3l迷宮問題：把迷宮每一個(gè)位置以及入口和出口都作為節(jié)點(diǎn)，把通道作為邊，則迷宮可由一個(gè)有向圖表示。走迷宮實(shí)際就是從該有向圖的初始節(jié)點(diǎn)（入口）出發(fā)，尋找目標(biāo)節(jié)點(diǎn)（出口）的問題，或者是尋找通向目標(biāo)節(jié)點(diǎn)（出口）的路徑的問題。l8數(shù)碼問題：在一個(gè)3*3的方格棋盤上放置著1，2，3，4，5，6，7，8八個(gè)數(shù)碼，每個(gè)數(shù)碼占一格，且有一個(gè)空格。這些數(shù)碼可在棋盤上移動(dòng)，其移動(dòng)規(guī)則是：與

2、空格相鄰的數(shù)碼才可以移入空格。問題：對(duì)于指定的初始棋局和目標(biāo)棋局，給出數(shù)碼的移動(dòng)序列。 如果把一個(gè)棋局作為一個(gè)節(jié)點(diǎn)，相鄰的節(jié)點(diǎn)就可以通過(guò)移動(dòng)數(shù)碼，一個(gè)一個(gè)地產(chǎn)生出來(lái)。這樣，所有節(jié)點(diǎn)就可由它們相鄰的關(guān)系連成一個(gè)有向圖，圖中的一條邊就對(duì)應(yīng)一次數(shù)碼移動(dòng)，反之，一次數(shù)碼移動(dòng)就對(duì)應(yīng)著圖中的一條邊，邊也就代表著一個(gè)移動(dòng)規(guī)則或者移動(dòng)規(guī)則的一次執(zhí)行。該問題也就是要在該有向圖中尋找目標(biāo)節(jié)點(diǎn)，或找一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑問題。4l上述兩個(gè)問題雖然內(nèi)容不同，但抽象地看，它們都是在某個(gè)有向圖中尋找目標(biāo)或路徑的問題。我們把這種描述問題的有向圖稱為狀態(tài)空間圖，簡(jiǎn)稱狀態(tài)圖。58.1.1 圖搜索策略的定義 8.1.2

3、圖搜索算法中的幾個(gè)重要名詞術(shù)語(yǔ) 8.1.3 圖搜索(GRAPH SEARCH)的一般過(guò)程 8.1.4 圖搜索方法分析 6l圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。l研究圖搜索的一般策略，能夠給出圖搜索過(guò)程的一般步驟。 7l（1）OPEN表與CLOSED表l（2）搜索(狀態(tài))圖與搜索樹 登記當(dāng)前登記當(dāng)前待考查的待考查的節(jié)點(diǎn)節(jié)點(diǎn)記錄考查記錄考查過(guò)的節(jié)點(diǎn)過(guò)的節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)節(jié)點(diǎn)編號(hào)父節(jié)點(diǎn)編號(hào)節(jié)點(diǎn)OPENCLOSED8(1) 建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S

4、放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。(2) 建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。(3) LOOP：若OPEN表是空表，則失敗退出。(4) 選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n。(5) 若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。(6) 擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。9(7) 對(duì)那些未曾在G中出現(xiàn)過(guò)的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過(guò)的)M成員設(shè)置一個(gè)通向n的指針。把M的這些成員

5、加進(jìn)OPEN表。對(duì)已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針方向。對(duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針方向。(8) 按某一或按某個(gè)探試值，重排OPEN表。(9) GO LOOP。 10開始開始把S放入OPEN表把S放入OPEN表把第一個(gè)節(jié)點(diǎn)(n)從OPEN移至CLOSE表把第一個(gè)節(jié)點(diǎn)(n)從OPEN移至CLOSE表OPEN為空表OPEN為空表n為目標(biāo)節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)把n的后繼節(jié)點(diǎn)放入OPEN表的末端，把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)的指針提供返回節(jié)點(diǎn)的指針修改指針方向修改指針方向重排OPEN表重排

6、OPEN表失敗失敗成功成功11 圖搜索過(guò)程的第8步（按某一方式重排OPEN表）對(duì)OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第4步擴(kuò)展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù)(屬于啟發(fā)式搜索)。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過(guò)程就宣告成功結(jié)束。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向S返回追溯。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過(guò)程就以失敗告終(某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。 1.

7、 寬度優(yōu)先搜索2. 深度優(yōu)先搜索121)定義如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。 (breadth-first search) 2)特點(diǎn)這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 13 (1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。(2) 如果OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(4) 擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。(5) 把n的所有后繼節(jié)點(diǎn)放到OPEN表的末

8、端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。(6) 如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。 14(1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。(2) 如果OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(4) 擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。(5) 把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。(6) 如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。 15

9、 寬度優(yōu)先搜索是圖搜索一般過(guò)程的特殊情況，將圖搜索一般過(guò)程中的第8步具體化為本算法中的第6步，這實(shí)際是將OPEN表作為“先進(jìn)先出”的隊(duì)列進(jìn)行操作。 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對(duì)有限圖來(lái)說(shuō)，我們就說(shuō)該法失敗退出；對(duì)于無(wú)限圖來(lái)說(shuō)，則永遠(yuǎn)不會(huì)終止)。 16把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題：2 8 32 8 31 1 4 47 6 57 6 51 2 31 2 38 8 4 47 6 57 6 5172 8 3417 6 51 2 38 47 6

10、52 8 3 1 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 6 4 7 52 8 31 6 47 52 81 4 37 6 52 8 31 4 57 68 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 8 7 6 52 8 3 6 41 7 52 8 31 67 5 42 81 4 37 6 52 8 31 4 57 68 32 1 47 6 58 1 3427 6 52 8 37

11、 46 1 52 8 37 1 46 51 2 37 8 4 6 5181)定義在此搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。這種盲目(無(wú)信息)搜索叫做深度優(yōu)先搜索(depth-first search)。2)特點(diǎn)首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。 193)深度界限為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度棗深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點(diǎn)處理。4)含有深度界限的深度優(yōu)

12、先搜索算法請(qǐng)課后自學(xué)。201.為什么需要啟發(fā)式搜索 盲目搜索效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間，這是組合爆炸的一種表現(xiàn)形式。2.定義 進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。 213.啟發(fā)式搜索策略有關(guān)具體問題領(lǐng)域的信息常?？梢杂脕?lái)簡(jiǎn)化搜索。一個(gè)比較靈活(但代價(jià)也較大)的利用啟發(fā)信息的方法是應(yīng)用某些準(zhǔn)則來(lái)重新排列每一步OPEN表中所有節(jié)點(diǎn)的順序。然后，搜索就可能沿著某個(gè)被認(rèn)為是最有希望的邊緣區(qū)段向外擴(kuò)展。應(yīng)用這種排序過(guò)程，需要某些估算節(jié)點(diǎn)“希望”的量度，這種量度叫做估價(jià)函數(shù)(evalution function)。

13、224.估價(jià)函數(shù)為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值建立估價(jià)函數(shù)的一般方法：試圖確定一個(gè)處在最佳路徑上的節(jié)點(diǎn)的概率；提出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來(lái)決定棋局的得分?jǐn)?shù)。這些特點(diǎn)被認(rèn)為與向目標(biāo)節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。 231、定義、定義用估價(jià)函數(shù)f來(lái)排列GRAPHSEARCH第8步中OPEN表上的節(jié)點(diǎn)。應(yīng)用某個(gè)算法選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索(ordered search)

14、或最佳優(yōu)先搜索 best-first search)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。尼爾遜(Nilsson)曾提出一個(gè)有序搜索的基本算法。估價(jià)函數(shù)f是這樣確定的：一個(gè)節(jié)點(diǎn)的希望程序越大，其f值就越小。被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。 24l選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，即總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。 25 (1) 把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來(lái)。 (2) 如果OPEN是個(gè)空表，則失敗退出，無(wú)解。 (3) 從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選

15、擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i. (4) 把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (5) 如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。 (6) 擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j： 26(6) 擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j： (a)計(jì)算f(j)。 (b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。 (c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對(duì)j計(jì)算過(guò)的f值和前面計(jì)算過(guò)的該節(jié)

16、點(diǎn)在表中的f值。如果新的f值較小，則 (i) 以此新值取代舊值。 (ii) 從j指向i，而不是指向它的父輩節(jié)點(diǎn)。 (iii) 如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表(7) 轉(zhuǎn)向(2)，即GO TO(2)。 27寬度優(yōu)先搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。 有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。如果沒有適用的準(zhǔn)確的希望量度，那么f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。 28采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=d(n)+W(n)其中：d(n)是搜索樹中節(jié)點(diǎn)

17、n的深度；W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局2 8 31 6 47 5的f值等于0+4=4。 1 2 31 2 38 8 4 47 6 57 6 5292 8 31 6 47 51 2 38 47 6 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 51 2 37 8 4 6 51 2 3 8 47 6 530lA*算法是一種有序搜索算法

18、，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 31令k(ni，nj)表示任意兩個(gè)節(jié)點(diǎn)ni和nj之間最小代價(jià)路徑的實(shí)際代價(jià)(對(duì)于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn)，函數(shù)k沒有定義)。 于是，從節(jié)點(diǎn)n到某個(gè)具體的目標(biāo)節(jié)點(diǎn)ti，某一條最小代價(jià)路徑的代價(jià)可由k(n,ti)給出。 令h*(n)表示整個(gè)目標(biāo)節(jié)點(diǎn)集合ti上所有k(n,ti)中最小的一個(gè)，因此，h*(n)就是從n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從n到目標(biāo)節(jié)點(diǎn)能夠獲得h*(n)的任一路徑就是一條從n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑(對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù)h*沒有定義)。 32定義g*為 g*(n)=k(S,n)定義函數(shù)f*，使得在任一節(jié)點(diǎn)n上其函數(shù)值f*(n

19、)就是從節(jié)點(diǎn)S到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，即f*(n)=g*(n)+h*(n) 33希望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出：f(n)=g(n)+h(n)其中：g是g*的估計(jì)；h是h*的估計(jì)。對(duì)于g(n)來(lái)說(shuō)，一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價(jià)路徑)。這個(gè)定義包含了g(n)g*(n)。h*(n)的估計(jì)h(n)依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信

20、息相似。把h叫做啟發(fā)函數(shù)。 34定義1 在GRAPHSEARCH過(guò)程中，如果第8步的重排OPEN表是依據(jù) f(x)=g(x)+h(x)進(jìn)行的，則稱該過(guò)程為A算法。定義2 在A算法中，如果對(duì)所有的x存在h(x)h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?35樹式搜索樹式搜索窮舉式窮舉式盲目搜索盲目搜索啟發(fā)式搜索啟發(fā)式搜索寬度優(yōu)先寬度優(yōu)先深度優(yōu)先深度優(yōu)先A算法A算法A*算法A*算法線式搜索線式搜索36 為了便于分析，我們僅考慮二階梵塔(即只有兩個(gè)金盤)問題。 設(shè)

21、有三根寶石桿，在1號(hào)桿上穿有A、B兩個(gè)金盤，A小于B，A位于B的上面. 要求把這兩個(gè)金盤全部移到另一根桿上，而且規(guī)定每次只能移動(dòng)一個(gè)盤子，任何時(shí)刻都不能使B位于A的上面。37 設(shè)用二元組(SA，SB)表示問題的狀態(tài)， SA表示金盤A所在的桿號(hào)， SB表示金盤B所在的桿號(hào)。這樣，全部可能的狀態(tài)有9種，可表示如下：這里的狀態(tài)轉(zhuǎn)換規(guī)則就是金盤的搬動(dòng)規(guī)則，分別用A(i，J)及B(i，J)表示：A(i，J)表示把A從第i號(hào)桿移到第J號(hào)桿上；共有l(wèi) 2個(gè)操作，它們分別是: A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，4(3，2)，B(1，2)，B(1，3)，B(2，1)，B(2，

22、3)，B(3，1)，B3，2)3839在現(xiàn)實(shí)世界中，經(jīng)常會(huì)遇到這樣的問題：一個(gè)問題可以有幾種求解方法，只要其中一種方法可以求解問題，則該問題被求解。也就是說(shuō)，對(duì)求解該問題來(lái)說(shuō)，方法之間是“或”的關(guān)系。但在用每一種方法求解時(shí)，又可能需要求解幾個(gè)子問題，這些子問題必須全部求解，才可能用該方法求解原始問題。也就是說(shuō)，這些子問題之間是“與”的關(guān)系。此類問題可以用與或圖來(lái)表示。 40它表示，如果要求解n0，可以求解n1，或者求解n4、n5，也就是說(shuō)，對(duì)于n0來(lái)說(shuō)，n4和n5是與的關(guān)系，而n1和n4、n5的與之間是或的關(guān)系。其他節(jié)點(diǎn)之間也具有類似的關(guān)系。一個(gè)節(jié)點(diǎn)與它的k個(gè)與子節(jié)點(diǎn)間用下圖的形式連接，稱為k

23、連接符。 41從圖可以看出，節(jié)點(diǎn)n0有兩個(gè)連接符：1-連接符指向節(jié)點(diǎn)n1；2-連接符指向節(jié)點(diǎn)集n4，n5。該2-連接符還用一小段圓弧括起來(lái)（對(duì)k1的k-連接符都應(yīng)有小圓弧標(biāo)記），以表示子節(jié)點(diǎn)間與的關(guān)系。可以看出這種標(biāo)記法在節(jié)點(diǎn)間具有明確的關(guān)系。顯然若用原先的術(shù)語(yǔ)，則對(duì)父節(jié)點(diǎn)n0來(lái)說(shuō)，n4、n5是兩個(gè)與節(jié)點(diǎn)，而n1可稱為或節(jié)點(diǎn)；而n8既是n5的一個(gè)與節(jié)點(diǎn)，又是n4的一個(gè)或節(jié)點(diǎn)，混淆難于避免。另外也把圖中沒有任何父節(jié)點(diǎn)的節(jié)點(diǎn)叫根節(jié)點(diǎn)，沒有任何后繼節(jié)點(diǎn)的節(jié)點(diǎn)叫端節(jié)點(diǎn)或葉節(jié)點(diǎn)。42在普通圖中，目標(biāo)用一個(gè)節(jié)點(diǎn)表達(dá)，而在與或圖中，目標(biāo)則表現(xiàn)為一個(gè)節(jié)點(diǎn)的集合，該集合中由一些子目標(biāo)節(jié)點(diǎn)組成。值得指出的是，解圖

24、不一定要求到達(dá)目標(biāo)集中的每一個(gè)子目標(biāo)節(jié)點(diǎn)，而只要求解圖的端節(jié)點(diǎn)是目標(biāo)集中的節(jié)點(diǎn)即可。也就是說(shuō)，解圖中的端節(jié)點(diǎn)是目標(biāo)集的子集即可。 43與或圖中某一個(gè)節(jié)點(diǎn)n到節(jié)點(diǎn)集N的一個(gè)解圖類似于普通圖中的一條解路徑。解圖的求法是：從節(jié)點(diǎn)n開始，正確選擇一個(gè)外向連接符，再?gòu)脑撨B接符所指的每一個(gè)后繼節(jié)點(diǎn)出發(fā)，繼續(xù)選一個(gè)外向連接符，如此進(jìn)行下去直到由此產(chǎn)生的每一個(gè)后繼節(jié)點(diǎn)成為集合N中的一個(gè)元素為止。44在與或圖是無(wú)環(huán)（即不存在這樣的節(jié)點(diǎn)-其后繼節(jié)后同時(shí)又是它的祖先）的假定下，解圖可遞歸定義如下：定義：一個(gè)與或圖G中，從節(jié)點(diǎn)n到節(jié)點(diǎn)集N的解圖記為G， G是G的子圖。若n是N的一個(gè)元素，則G由單一節(jié)點(diǎn)組成；若n有一個(gè)

25、指向節(jié)點(diǎn)n1，nk的外向連接符K，使得從每一個(gè)ni到N有一個(gè)解圖（i=1，k），則G由節(jié)點(diǎn)n，連接符K，及n1，nk中的每一個(gè)節(jié)點(diǎn)到N的解圖所組成；否則n到N不存在解圖。 45遞歸定義局部圖：定義：?jiǎn)我还?jié)點(diǎn)是一個(gè)局部圖；對(duì)于一個(gè)局部圖的任意葉節(jié)點(diǎn)n，選擇一個(gè)n的外向連接符K，則該局部圖、外向連接符K，以及K所連接的n的后繼節(jié)點(diǎn)一起組成的圖，仍然組成一個(gè)局部圖。 46與或圖一般表示問題的變換過(guò)程（而不是狀態(tài)變換）。具體講，它是從原問題出發(fā)，通過(guò)運(yùn)用某些規(guī)則不斷進(jìn)行問題分解（得到與分支）和變換（得到或分支），而得到一個(gè)與或圖。換句話說(shuō)，與或圖的節(jié)點(diǎn)一般代表問題。那么，整個(gè)圖就表示問題空間。與或圖中

26、的父節(jié)點(diǎn)與其子節(jié)點(diǎn)服從邏輯上的與、或運(yùn)算關(guān)系。所以，與或圖表示的問題是否有解，要進(jìn)行邏輯判斷，與或圖的搜索也受邏輯的制約。47與或圖也是一個(gè)三元組(Q0,F,Qn)Q0,表示初始問題，F(xiàn)表示問題變換規(guī)則集， Qn表示本原問題集。例如：積分公式，就是一些典型的問題分解和變換問題。所以，一般求不定積分就可用與或圖來(lái)描述。48123三階 Hanoi塔可分解為下面三個(gè)子問題：1） 把A、B盤從1號(hào)桿移到2號(hào)桿。2） 把C盤從1號(hào)桿移到3號(hào)桿。3） 把A、B盤從2號(hào)桿移到3號(hào)桿。其中，子問題1）、3）又可分解為三個(gè)子問題。49(i,j,k) i: C盤所在桿號(hào)， j: B盤所在桿號(hào)， k: A盤所在桿號(hào)

27、。(1,1,1)(3,3,3)(1,1,1)(1,2,2)(1,2,2)(3,2,2)(3,2,2)(3,3,3)(1,1,1)(1,1,3)(1,1,3)(1,2,3)(1,2,3)(1,2,2)(3,2,2)(3,2,1)(3,2,1)(3,3,1)(3,3,1)(3,3,3)50這里所講的博弈，指的是類似于象棋這樣的游戲問題。這類問題有以下一些特點(diǎn)：（1）雙人對(duì)弈，對(duì)壘的雙方輪流走步。（2）信息完備，對(duì)壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。（3）零和。即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利、或均無(wú)利的棋。對(duì)弈的結(jié)果是一方贏，而另一方輸，或

28、者雙方和棋。51博弈問題為什么可以用與或圖表示呢？可以這樣來(lái)看待這個(gè)問題：當(dāng)輪到我方走棋時(shí)，只需從若干個(gè)可以走的棋中，選擇一個(gè)棋走就可以了。從這個(gè)意義上說(shuō)，若干個(gè)可以走的棋是“或”的關(guān)系。而對(duì)于輪到對(duì)方走棋時(shí)，對(duì)于我方來(lái)說(shuō)，必須能夠應(yīng)付對(duì)手的每一種走棋。這就相當(dāng)于這些棋是“與”的關(guān)系。因此，博弈問題可以看成是一個(gè)與或圖，但是與一般的與或圖并不一樣，是一種特殊的與或圖。52博弈一向被認(rèn)為是富有智能行為的游戲，因而很早就受到人工智能界的重視，早在60年代就已經(jīng)出現(xiàn)若干博弈程序，并達(dá)到一定水平。博弈問題的研究還不斷提出一些新的研究課題，從而也推動(dòng)了人工智能研究的發(fā)展。對(duì)于單人博弈的一些問題，可用一般

29、的搜索技術(shù)進(jìn)行求解，本節(jié)著重討論雙人完備信息這一類博弈問題的搜索策略。由于雙人博弈可用與或樹（或圖）來(lái)描述，因而搜索就是尋找最佳解樹（圖）的問題。53所謂雙人完備信息，就是兩位選手對(duì)壘，輪流走步，這時(shí)每一方不僅都知道對(duì)方過(guò)去已經(jīng)走過(guò)的棋步，而且還能估計(jì)出對(duì)方未來(lái)可能的走步。對(duì)弈的結(jié)果是一方贏（另一方則輸），或者雙方和局。這類博弈的實(shí)例有：一字棋、余一棋、西洋跳棋、國(guó)際象棋、中國(guó)象棋、圍棋等。對(duì)于帶機(jī)遇性的任何博弈，因不具有完備信息，不屬這里討論范圍，但有些論述可推廣到某些機(jī)遇博弈中應(yīng)用。54博弈問題可以用產(chǎn)生式系統(tǒng)的形式來(lái)描述，例如中國(guó)象棋，綜合數(shù)據(jù)庫(kù)可規(guī)定為棋盤上棋子各種位置布局的一種描述，

30、產(chǎn)生式規(guī)則是各類棋子合法走步的描述，目標(biāo)則可規(guī)定為將（帥）被吃掉，規(guī)則作用于數(shù)據(jù)庫(kù)的結(jié)果便生成出博弈圖或博弈樹。55極小極大搜索方法是博弈樹搜索的基本方法，現(xiàn)在博弈樹搜索中最常用的-剪枝搜索方法，就是從這一方法發(fā)展而來(lái)的。首先假定，有一個(gè)評(píng)價(jià)函數(shù)可以對(duì)所有的棋局進(jìn)行評(píng)估。當(dāng)評(píng)價(jià)函數(shù)值大于0時(shí)，表示棋局對(duì)我方有利，對(duì)對(duì)方不利。當(dāng)評(píng)價(jià)函數(shù)小于0時(shí)，表示棋局對(duì)我方不利，對(duì)對(duì)方有利。而評(píng)價(jià)函數(shù)值越大，表示對(duì)我方越有利。當(dāng)評(píng)價(jià)函數(shù)值等于正無(wú)窮大時(shí)，表示我方必勝。評(píng)價(jià)函數(shù)值越小，表示對(duì)我方越不利。當(dāng)評(píng)價(jià)函數(shù)值等于負(fù)無(wú)窮大時(shí)，表示對(duì)方必勝。假設(shè)雙方都是對(duì)弈高手，在只看一步棋的情況下，我方一定走評(píng)價(jià)函數(shù)值最大

31、的一步棋，而對(duì)方一定走評(píng)價(jià)函數(shù)值最小的一步棋。會(huì)下棋的都知道，在只看一步的情況下最好的棋，從全局來(lái)說(shuō)不一定就好，還可能很不好。因此為了走出好棋，必須多看幾步，從多種可能狀態(tài)中選擇一步好棋。56想一想人是如何下棋的呢？人實(shí)際上采用的是一種試探性的方法。首先假定走了一步棋，看對(duì)方會(huì)有那些應(yīng)法，然后再根據(jù)對(duì)方的每一種應(yīng)法，看我方是否有好的回應(yīng).這一過(guò)程一直進(jìn)行下去，直到若干步以后，找到了一個(gè)滿意的走法為止。初學(xué)者可能只能看一、兩個(gè)輪次，而高手則可以看幾個(gè)，甚至十幾個(gè)輪次。極小極大搜索方法，模擬的就是人的這樣一種思維過(guò)程當(dāng)輪到我方走棋時(shí)，首先按照一定的搜索深度生成出給定深度d以內(nèi)的所有狀態(tài)，計(jì)算所有葉

32、節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值。然后從d-1層節(jié)點(diǎn)開始逆向計(jì)算：對(duì)于我方要走的節(jié)點(diǎn)（用MAX標(biāo)記，稱為極大節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最大值為該節(jié)點(diǎn)的值（因?yàn)槲曳娇偸沁x擇對(duì)我方有利的棋）；對(duì)于對(duì)方要走的節(jié)點(diǎn)（用MIN標(biāo)記，稱為極小節(jié)點(diǎn)）取其子節(jié)點(diǎn)中的最小值為該節(jié)點(diǎn)的值（對(duì)方總是選擇對(duì)我方不利的棋）。一直到計(jì)算出根節(jié)點(diǎn)的值為止。獲得根節(jié)點(diǎn)取值的那一分枝，即為所選擇的最佳走步。57在博弈問題中，每一個(gè)棋局可供選擇的行動(dòng)方案都有很多，因此會(huì)生成十分龐大的博弈樹。據(jù)統(tǒng)計(jì)，西洋跳棋完整的博弈樹約有1040個(gè)節(jié)點(diǎn)。試圖利用完整的博弈樹來(lái)進(jìn)行極小極大分析是困難的?？尚械霓k法是只生成一定深度的博弈樹，然后進(jìn)行極小極大分析，找出當(dāng)前最好的行動(dòng)方案。在此之后，再在已選定的分支上擴(kuò)展一定深度，再選最好的行動(dòng)方案。如此進(jìn)行下去，直到取得勝敗的結(jié)果為止。至于每次生成博弈樹的深度，當(dāng)然是越大越好，但由于受到存儲(chǔ)空間的限制，只好根據(jù)實(shí)際情況而定。58在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰(shuí)先取得三子一線的結(jié)果