第五章搜索策略

1、第五章 搜索策略 5.1 概述 5.2 狀態(tài)空間搜索 5.3 與或樹(shù)搜索w2 搜索分為盲目搜索和啟發(fā)式搜索。 盲目搜索是按照預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。 啟發(fā)式搜索是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。w3w問(wèn)題求解過(guò)程可以看作一個(gè)搜索過(guò)程。狀態(tài)空間表示法是用來(lái)表示問(wèn)題及其搜索過(guò)程的一種方法。它是人工智能中最基本的一種形式化方法。w狀態(tài)空間用“狀態(tài)”和“算符”來(lái)表示問(wèn)題。狀態(tài)狀態(tài)用以描述問(wèn)題求解過(guò)程中不同時(shí)刻的狀況，是一個(gè)數(shù)據(jù)結(jié)構(gòu)，一般用一組變量的有序組合表示：SK=(Sk0,Sk1

2、,)當(dāng)每一個(gè)分量的值確定時(shí)，就得到了一個(gè)具體的狀態(tài)。算符引起狀態(tài)中某些分量發(fā)生變化，從而使問(wèn)題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作稱(chēng)為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)則就是一個(gè)算符。狀態(tài)空間由問(wèn)題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱(chēng)為問(wèn)題的狀態(tài)空間，一般用一個(gè)三元組表示：(S,F,G)其中S是問(wèn)題所有初始狀態(tài)的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。狀態(tài)空間的圖示形式稱(chēng)為狀態(tài)空間圖。w4設(shè)用SK=(Sk0,Sk1)表示問(wèn)題的狀態(tài)，SK0表示金片A所在的柱號(hào)，Sk1表示金片B所在的柱號(hào)，全部可能的狀態(tài)有九種：S0=(1,1), S1=(1,2) , S2=(1,3)S3=(2,1), S4=(2

3、,2) , S5=(2,3)S6=(3,1), S7=(3,2) , S8=(3,3)問(wèn)題的初始狀態(tài)集合為S=S0,目標(biāo)狀態(tài)集合為G=S4,S8。算符分別用A(i,j)及B(i,j)。A(i,j)表示把A金片從第i號(hào)柱移到第j號(hào)柱。B(i,j)與之同理。算符共有12個(gè)。在狀態(tài)空間圖中，從初始節(jié)點(diǎn)(1,1)到目標(biāo)節(jié)點(diǎn)(2,2)或(3,3)的任何一條通路都是問(wèn)題的一個(gè)解。其中最短的路徑長(zhǎng)度是3，它由3個(gè)算符組成。例如:A(1,3),B(1,2),A(3,2)w51,12,13,12,33,23,31,31,22,2A(1,3)B(1,2)A(3,2) 用狀態(tài)空間方法表示問(wèn)題，首先必須定義狀態(tài)的描述

4、形式，把問(wèn)題的一切狀態(tài)都表示出來(lái)。其次要定義一組算符。 問(wèn)題的求解過(guò)程是一個(gè)不斷把算符作用于狀態(tài)的過(guò)程。如果在使用某個(gè)算符后得到的新?tīng)顟B(tài)是目標(biāo)狀態(tài)，就得到了問(wèn)題的一個(gè)解。這個(gè)解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。 算符的一次使用，就使問(wèn)題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。使用算符最少的解或者總代價(jià)最少的解稱(chēng)為最優(yōu)解。 對(duì)任何一個(gè)狀態(tài)，可使用的算符可能不止一個(gè)。這樣由一個(gè)狀態(tài)所生成的后繼狀態(tài)就可能有多個(gè)。此時(shí)首先對(duì)哪一個(gè)狀態(tài)進(jìn)行操作，就取決于搜索策略。w6 與或樹(shù)是用于表示問(wèn)題及其求解過(guò)程的又一種形式化方法，通常用于表示比較復(fù)雜問(wèn)題的求解。 對(duì)于一個(gè)復(fù)雜問(wèn)題，直接求解往往比較困難。此時(shí)可通過(guò)下述

5、方法進(jìn)行簡(jiǎn)化： 分解把一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)較為簡(jiǎn)單的子問(wèn)題，每個(gè)子問(wèn)題又可繼續(xù)分解。重復(fù)此過(guò)程，直到不需要或者不能再分解為止。如此形成“與”樹(shù)。 等價(jià)變換利用同構(gòu)或同態(tài)的等價(jià)變換，把原問(wèn)題變換為若干個(gè)較為容易求解的新問(wèn)題。如此形成“或”樹(shù)。w7PP1P2P3與樹(shù)PP1P2P3或樹(shù)w8 本原問(wèn)題 不能再分解或變換，而且直接可解的子問(wèn)題。 端節(jié)點(diǎn)與終止節(jié)點(diǎn) 在與/或樹(shù)中，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)統(tǒng)稱(chēng)為端節(jié)點(diǎn)；本原問(wèn)題所對(duì)應(yīng)的節(jié)點(diǎn)稱(chēng)為終止節(jié)點(diǎn)。 可解節(jié)點(diǎn) 在與/或樹(shù)中，滿足下列條件之一者，稱(chēng)為可解節(jié)點(diǎn)： 它是一個(gè)終止節(jié)點(diǎn)； 它是一個(gè)“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)； 它是一個(gè)“與”節(jié)點(diǎn)，且其

6、子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。 不可解節(jié)點(diǎn) 關(guān)于可解節(jié)點(diǎn)的三個(gè)條件全部不滿足的節(jié)點(diǎn)w9解樹(shù)由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹(shù)稱(chēng)為解樹(shù)。w10(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)w11狀態(tài)空間搜索策略盲目搜索啟發(fā)式搜索廣度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索代價(jià)樹(shù)的廣度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索局部擇優(yōu)搜索全局

7、擇優(yōu)搜索A*算法w12盲目搜索的特點(diǎn)：搜索按規(guī)定的路線進(jìn)行，不使用與問(wèn)題有關(guān)的啟發(fā)性信息；適用于其狀態(tài)空間圖是樹(shù)狀結(jié)構(gòu)的一類(lèi)問(wèn)題。啟發(fā)式搜索要使用與問(wèn)題有關(guān)的啟發(fā)性信息，并以這些啟發(fā)性信息指導(dǎo)搜索過(guò)程，可以高效地求解結(jié)構(gòu)復(fù)雜的問(wèn)題。廣度優(yōu)先搜索按照“先擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索；深度優(yōu)先搜索按照“后擴(kuò)展出的節(jié)點(diǎn)先被考察”的原則進(jìn)行搜索；有界深度優(yōu)先搜索的原則與深度優(yōu)先搜索相同，但是它規(guī)定了深度限界，使搜索不得無(wú)限制地向縱深方向發(fā)展；代價(jià)樹(shù)的廣度優(yōu)先搜索按照“哪個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的代價(jià)小就先考察哪個(gè)節(jié)點(diǎn)”的原則進(jìn)行搜索；代價(jià)樹(shù)的深度優(yōu)先搜索按照“當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)到其父節(jié)點(diǎn)的代價(jià)小就先考

8、察哪個(gè)子節(jié)點(diǎn)”的原則進(jìn)行搜索；局部擇優(yōu)搜索按照“當(dāng)前節(jié)點(diǎn)的哪個(gè)子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)小就先考察哪個(gè)子節(jié)點(diǎn)”的原則進(jìn)行搜索；全局擇優(yōu)搜索按照“哪個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)小就先考察哪個(gè)節(jié)點(diǎn)”的原則進(jìn)行搜索；w13OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點(diǎn)。對(duì)于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴(kuò)展或者已經(jīng)擴(kuò)展的節(jié)點(diǎn)。 OPEN表CLOSE表w14狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào) 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問(wèn)題無(wú)解，退出；把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入CLOSE表，

9、并計(jì)該節(jié)點(diǎn)為n；考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出；擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中；針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理： 對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表； 對(duì)于那些先前已經(jīng)在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針； 對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；按某種搜索策略對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序；轉(zhuǎn)第2步。w15上述是一個(gè)通用過(guò)程，各種搜索策略的主要區(qū)別是

10、對(duì)OPEN表中節(jié)點(diǎn)排序的準(zhǔn)則不同。一個(gè)節(jié)點(diǎn)經(jīng)一個(gè)算符操作后一般只生成一個(gè)子節(jié)點(diǎn)。但適用于一個(gè)節(jié)點(diǎn)的算符可能有多個(gè)，此時(shí)就會(huì)生成一組子節(jié)點(diǎn)。這些子節(jié)點(diǎn)中可能有些是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等，此時(shí)不能把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)。一個(gè)新生成的節(jié)點(diǎn)，它可能是第一次被生成的節(jié)點(diǎn)，也可能是先前已作為其它節(jié)點(diǎn)的后繼節(jié)點(diǎn)被生成過(guò)，當(dāng)前又作為另一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)被再次生成。此時(shí)，它究竟應(yīng)作為哪個(gè)節(jié)點(diǎn)的不后繼節(jié)點(diǎn)？一般由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價(jià)來(lái)決定，代價(jià)小的相應(yīng)節(jié)點(diǎn)就作為父節(jié)點(diǎn)。在搜索過(guò)程中，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就得到了一個(gè)解。該解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成。如果在搜索

11、中一直找不到目標(biāo)節(jié)點(diǎn)，而且OPEN表中不再有可供擴(kuò)展的節(jié)點(diǎn)，則搜索失敗。w16 基本思想：從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)。在第n層的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察之前，不對(duì)第n1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 OPEN表中節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。w17把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)

12、的指針，然后轉(zhuǎn)第2步。w18w19 優(yōu)點(diǎn)：只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。 缺點(diǎn)：廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。w20 基本思想：從初始節(jié)點(diǎn)S0開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察。若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)達(dá)到某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。 深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到OPEN表的首部。w21

13、把初始節(jié)點(diǎn)S0放入OPEN表。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。w222 8 31 47 6 52 8 3 1 47 6 52 8 31 67 5 42 31 8 47 6 5 2 8 31 4 7 6 52 8 1 6 3 7 5 42 81 6 37 5 42 8 31 6 47 5 2 8 3 1 6 47 6 2 8 3 1 6 47 5 2

14、 8 31 6 7 5 4S01234.5w23 在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問(wèn)題有解，它也不一定能求得解。 用深度優(yōu)先求得的解，不一定是路徑最短的解。w24w基本思想：對(duì)深度優(yōu)先搜索引入搜索深度的界限（設(shè)為dm），當(dāng)搜索深度達(dá)到了深度界限，而尚未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。w搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN

15、表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n的深度d(節(jié)點(diǎn)n)=dm，則轉(zhuǎn)第2步。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。w25 如果問(wèn)題有解，且其路徑長(zhǎng)度dm，則上述搜索過(guò)程一定能求得解。但是，若解的路徑長(zhǎng)度dm,則上述搜索過(guò)程就得不到解。這說(shuō)明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。 要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。w26先任意設(shè)定一個(gè)較小的數(shù)作為dm，然后進(jìn)行上述的有界深度優(yōu)先搜索，當(dāng)搜索

16、達(dá)到了指定的深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，并且CLOSE表中仍有待擴(kuò)展節(jié)點(diǎn)時(shí)，就將這些節(jié)點(diǎn)送回OPEN表，同時(shí)增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問(wèn)題有解，就一定可以找到它。但此時(shí)找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設(shè)一個(gè)表R，每找到遠(yuǎn)程目標(biāo)節(jié)點(diǎn)Sg后，就把它放入到R的前面，并令dm等于該目標(biāo)節(jié)點(diǎn)所對(duì)應(yīng)的路徑長(zhǎng)度，然后繼續(xù)搜索。由于后求得的解的路徑長(zhǎng)度不會(huì)超過(guò)先求得的解的路徑長(zhǎng)度，所以后求得的解一定是最優(yōu)解。w27設(shè)深度界限dm4w282 3 1 8 4 7 6 5 2 3 41 8 7 6 5221 2 38 47 6 51 2 37 8 46 5 2 31 8

17、47 6 51 2 3 8 47 6 52 3 41 87 6 52 3 41 8 57 62 8 3 1 47 6 52 31 8 47 6 52 81 4 37 6 52 4 81 37 6 52 8 31 4 57 62 8 31 57 4 68 32 6 41 7 52 8 36 41 7 52 8 31 67 5 42 81 6 37 5 62 81 4 37 6 52 8 1 4 3 7 6 52 8 31 4 57 6 2 8 3 1 4 57 6 2 8 36 4 1 7 5 2 8 31 6 7 5 4 2 8 3 1 6 47 6 2 8 3 1 6 47 5 2 8 31

18、 4 7 6 52 8 31 6 47 52 8 31 47 6 5S0123Sg789141516232425264561011121317181920212728 盲目搜索具有較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)較多，搜索空間較大，效率不高。 啟發(fā)式搜索要用到問(wèn)題自身的某些特性信息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。由于這種搜索針對(duì)性較強(qiáng)，因而原則上只需要搜索問(wèn)題的部分狀態(tài)空間，效率較高。w29 可用于指導(dǎo)搜索過(guò)程，且與具體問(wèn)題求解有關(guān)的控制性信息稱(chēng)為啟發(fā)性信息。 用于估價(jià)節(jié)點(diǎn)重要性的函數(shù)稱(chēng)為估價(jià)函數(shù)。其一般形式為：f(x) = g(x)+h(x) 其中g(shù)(x)為從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出

19、的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)，它體現(xiàn)了問(wèn)題的啟發(fā)性信息，其形式要根據(jù)問(wèn)題的特性確定。例如它可以是節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的距離，或者節(jié)點(diǎn)x處于最優(yōu)路徑上的概率等等。h(x)稱(chēng)為啟發(fā)函數(shù)。 g(x)指出了搜索的橫向趨勢(shì)。它有利于搜索的完備性，但影響搜索的效率。如果我們只關(guān)心到達(dá)目標(biāo)節(jié)點(diǎn)的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時(shí)會(huì)影響搜索的完備性。w30設(shè)有如下結(jié)構(gòu)的移動(dòng)牌游戲：該游戲規(guī)則：當(dāng)一個(gè)牌移入相鄰的空位置時(shí)，費(fèi)用為一個(gè)單位。一個(gè)牌至多可跳過(guò)兩個(gè)牌進(jìn)入空位置，其費(fèi)用等于跳過(guò)的牌數(shù)加1。要求把所有的B都移至W的右邊，請(qǐng)?jiān)O(shè)計(jì)估價(jià)函數(shù)中的h(x)。解：根

20、據(jù)要求可知，W左邊的B越少越接近目標(biāo)，因此可用W左邊B的個(gè)數(shù)作為h(x),即h(x)=3(每個(gè)W左邊B個(gè)數(shù)的總和)這里乘以系數(shù)3是為了擴(kuò)大h(x)在f(x)中的比重。w31BBBWWWE基本思想：當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展以后，按f(x)對(duì)每一個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并按估價(jià)值從小

21、到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。1.深度優(yōu)先搜索、代價(jià)樹(shù)的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。w32基本思想：在代價(jià)樹(shù)的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察。而代價(jià)樹(shù)的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點(diǎn)中選一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSE表進(jìn)行考察。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)

22、。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按代價(jià)從小到大的順序放到OPEN表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。1.代價(jià)樹(shù)的深度有限搜索是不完備的。w33w34基本思想：每當(dāng)要選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察時(shí)，局部擇優(yōu)搜索只是從剛生成的子節(jié)點(diǎn)中進(jìn)行選擇，選擇的范圍比較狹窄。全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點(diǎn)中選擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。搜索過(guò)程：把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)

23、題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子節(jié)點(diǎn)都送入OPEN表中，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第2步。w廣度優(yōu)先搜索、代價(jià)樹(shù)的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當(dāng)前所有節(jié)點(diǎn)作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。設(shè)估價(jià)函數(shù)為f(x)=d(x)+h(x)其中，d(x)表示節(jié)點(diǎn)x的深度，h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。w351 2 38 47 6 51 2 37 8 46 5 2 31 8 47 6 51 2 3 8 47

24、6 52 8 3 1 47 6 52 31 8 47 6 5 2 8 31 4 7 6 52 8 31 6 47 52 8 31 47 6 5S035Sg556748 3 2 1 4 7 6 5 2 8 3 7 1 46 5672 3 1 8 4 7 6 5765 邊上標(biāo)有代價(jià)(或費(fèi)用)的樹(shù)稱(chēng)為代價(jià)樹(shù)。 用g(x)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)x2的代價(jià)則有：g(x2)=g(x1)+c(x1,x2) 基本思想：每次從OPEN表中選擇節(jié)點(diǎn)往CLOSE表傳送時(shí)，總是選擇其代價(jià)最小的節(jié)點(diǎn)。也就是說(shuō)，OPEN表中的節(jié)點(diǎn)在任一時(shí)刻都是按其代價(jià)從小到大排序的。

25、代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)排在后面，而不管節(jié)點(diǎn)在代價(jià)樹(shù)中處于什么位置。 如果問(wèn)題有解，代價(jià)樹(shù)的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。w36把初始節(jié)點(diǎn)S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問(wèn)題無(wú)解，退出。把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSE表?？疾旃?jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第2步。擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入OPEN表中，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。計(jì)算各子節(jié)點(diǎn)的代價(jià)，并按各節(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的全部節(jié)點(diǎn)進(jìn)行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。w37ABCDE432345

26、交通圖w38AC1B1D1E2B2E4D2E1C2E33423454523交通圖的代價(jià)樹(shù)如果使一般搜索過(guò)程滿足如下限制，則它就稱(chēng)為A*算法：1、把OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)f(x)=g(x)+h(x)的值從小至大進(jìn)行排序（一般搜索過(guò)程的第7步）。2、g(x)是對(duì)g*(x)的估計(jì)，g(x)0。3、h(x)是h*(x)的下界，即對(duì)所有的x均有：h(x)h*(x)其中，g*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)；h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，若有多個(gè)目標(biāo)節(jié)點(diǎn)，則為其中最小的一個(gè)。w39 在A*算法中，g(x)實(shí)際上就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的路徑代價(jià)，恒有g(shù)(x)g*(x)。而且在算

27、法執(zhí)行過(guò)程中隨著更多搜索信息的獲得，g(x)的值呈下降的趨勢(shì)。例如： H(x)的確定依賴于具體問(wèn)題領(lǐng)域的啟發(fā)性信息，其中h(x)h*(x)的限制十分重要，它保證A*算法能找到最優(yōu)解。w40S0X1X2X33732可納性對(duì)于可解狀態(tài)空間圖(即從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在)來(lái)說(shuō)，如果一個(gè)搜索算法能在有限步那終止，并且能找到最優(yōu)解，則稱(chēng)該搜索算法是可納的。A*算法是可納的。A*算法的最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x)，在滿足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它攜帶的啟發(fā)性信息越多，搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少，搜索的效率越高。h(x)的單調(diào)性限制在A

28、*算法中，每當(dāng)要擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)都要先檢查其子節(jié)點(diǎn)是否已在OPEN表或CLOSE表中，有時(shí)還要調(diào)整指向父節(jié)點(diǎn)的指針，這就增加了搜索的代價(jià)。如果對(duì)啟發(fā)函數(shù)h(x)加上單調(diào)性限制，就可減少檢查及調(diào)整的工作量，從而減少搜索代價(jià)。w41所謂單調(diào)性限制是指h(x)滿足如下兩個(gè)條件：1、h(Sg)=0;2、設(shè)xj是節(jié)點(diǎn)xi的任意子節(jié)點(diǎn)，則有h(xi)-h(xj)c(xi,xj)，即h(xi)h(xj)+c(xi,xj)其中，Sg是目標(biāo)節(jié)點(diǎn)；c(xi,xj)是節(jié)點(diǎn)xi到其子節(jié)點(diǎn)xj的代價(jià)?？梢宰C明，當(dāng)A*算法的啟發(fā)函數(shù)h(x)滿足單調(diào)性限制時(shí)，可得到如下兩個(gè)結(jié)論：1、若A*算法選擇節(jié)點(diǎn)xn進(jìn)行擴(kuò)展，則g(xn

29、)=g*(xn)2、由A*算法所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。這兩個(gè)結(jié)論都是在h(x)滿足單調(diào)性限制時(shí)才成立的。否則，它們不一定成立。w425.3.1 與或樹(shù)的一般搜索過(guò)程5.3.2 與或樹(shù)的廣度優(yōu)先搜索5.3.3 與或樹(shù)的深度優(yōu)先搜索5.3.4 與或樹(shù)的有序搜索5.3.5 博弈樹(shù)的啟發(fā)式搜索5.3.6 剪枝技術(shù)w43 完備性 對(duì)于一類(lèi)可解的問(wèn)題和一個(gè)搜索過(guò)程，如果運(yùn)用該搜索過(guò)程一定能求得該類(lèi)問(wèn)題的解，則稱(chēng)該搜索過(guò)程為完備的，否則為不完備的。 廣度優(yōu)先搜索、代價(jià)樹(shù)的廣度優(yōu)先搜索、改進(jìn)后的有界深度優(yōu)先搜索以及A*算法都是完備的搜索過(guò)程，其它搜索過(guò)程都是不完備的。w44一個(gè)搜索過(guò)程的搜索效率不僅

30、取決于過(guò)程自身的啟發(fā)能力，而且還與被解問(wèn)題的有關(guān)屬性等多種因素有關(guān)。目前雖已有多種定義和計(jì)算搜索效率的方法，但都有一定的局限性。外顯率外顯率定義為P=L/T其中，L為從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑長(zhǎng)度；T為整個(gè)搜索過(guò)程中所生成的節(jié)點(diǎn)總數(shù)。外顯率反映了搜索過(guò)程中從初始節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)前進(jìn)時(shí)搜索區(qū)域的寬度。當(dāng)L=T時(shí)，P=1，表示搜索過(guò)程中每次只生成一個(gè)節(jié)點(diǎn)，它恰好是解路徑上的節(jié)點(diǎn)，搜索效率最高。P越小表示搜索時(shí)產(chǎn)生的無(wú)用節(jié)點(diǎn)愈多，搜索效率愈低。w45 有效分枝因數(shù)B定義為B+B2+BL=T其中，B是有效分枝因數(shù)，它表示在整個(gè)搜索過(guò)程中每個(gè)有效節(jié)點(diǎn)平均生成的子節(jié)點(diǎn)數(shù)目；L為路徑長(zhǎng)度；T為節(jié)點(diǎn)總數(shù)。 當(dāng)B

31、1時(shí)，L=T，此時(shí)所生成的節(jié)點(diǎn)數(shù)最少，搜索效率最高。 不難證明，有效分枝因數(shù)與外顯率之間由如下關(guān)系：P=(L(B-1)/(B(BL-1)T=B(BL-1)/(B-1)由此可以看出，當(dāng)B一定時(shí)，L愈大則P愈??；當(dāng)L一定時(shí)，B愈大則P愈??；對(duì)同一個(gè)L而言，B愈大則T愈大。w4647 與與/ /或樹(shù)的搜索策略就是確定節(jié)點(diǎn)是否為可解或不可解節(jié)點(diǎn)?；驑?shù)的搜索策略就是確定節(jié)點(diǎn)是否為可解或不可解節(jié)點(diǎn)。在整個(gè)確定過(guò)程中，會(huì)循環(huán)用到兩個(gè)過(guò)程，分別為：在整個(gè)確定過(guò)程中，會(huì)循環(huán)用到兩個(gè)過(guò)程，分別為：可解標(biāo)示過(guò)程：可解標(biāo)示過(guò)程： 由可解子節(jié)點(diǎn)來(lái)確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)由可解子節(jié)點(diǎn)來(lái)確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解

32、節(jié)點(diǎn)的回溯向上過(guò)程的回溯向上過(guò)程不可解標(biāo)示過(guò)程：不可解標(biāo)示過(guò)程： 由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的回溯向上過(guò)程解節(jié)點(diǎn)的回溯向上過(guò)程這兩個(gè)過(guò)程都是自下而上進(jìn)行的，即由子節(jié)點(diǎn)的可解性這兩個(gè)過(guò)程都是自下而上進(jìn)行的，即由子節(jié)點(diǎn)的可解性確定父確定父( (或祖先或祖先) )節(jié)點(diǎn)的可解性節(jié)點(diǎn)的可解性5.3.1 5.3.1 與與/ /或樹(shù)的搜索策略或樹(shù)的搜索策略48與與/ /或樹(shù)的搜索策略或樹(shù)的搜索策略把原始問(wèn)題作為初始節(jié)點(diǎn)把原始問(wèn)題作為初始節(jié)點(diǎn)S S0 0，并把它作為當(dāng)前節(jié)點(diǎn)，并把它作為當(dāng)前節(jié)點(diǎn)應(yīng)用分解或等價(jià)變換算符對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。應(yīng)用

33、分解或等價(jià)變換算符對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第2 2）步和第步和第3 3）步，在此期間要多次調(diào)用）步，在此期間要多次調(diào)用可解標(biāo)示過(guò)程可解標(biāo)示過(guò)程和和不不可解標(biāo)示過(guò)程可解標(biāo)示過(guò)程，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不，直到初始節(jié)點(diǎn)被標(biāo)示為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止?？山夤?jié)點(diǎn)為止。49與與/ /或樹(shù)搜索的兩個(gè)特性：或樹(shù)搜索的兩個(gè)特性：(1)(1)如果已確定某個(gè)節(jié)點(diǎn)是可解節(jié)點(diǎn)，則刪去其不可如果已確定某個(gè)節(jié)點(diǎn)是可解節(jié)點(diǎn)，則刪去其不可解的后裔節(jié)點(diǎn)解的后裔節(jié)點(diǎn)(2)(2)如

34、果已確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn)，刪去其全部如果已確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn)，刪去其全部后裔節(jié)點(diǎn)，保留該結(jié)點(diǎn)后裔節(jié)點(diǎn)，保留該結(jié)點(diǎn)505.3.2 5.3.2 與與/ /或樹(shù)的寬度優(yōu)先搜索或樹(shù)的寬度優(yōu)先搜索搜索過(guò)程：搜索過(guò)程： 與狀態(tài)空間的寬度優(yōu)先搜索類(lèi)似，按照與狀態(tài)空間的寬度優(yōu)先搜索類(lèi)似，按照“先產(chǎn)生先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展的節(jié)點(diǎn)先擴(kuò)展”的原則進(jìn)行搜索，在整個(gè)搜索過(guò)程的原則進(jìn)行搜索，在整個(gè)搜索過(guò)程中多次調(diào)用可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程。中多次調(diào)用可解標(biāo)示過(guò)程和不可解標(biāo)示過(guò)程。51例例設(shè)有如圖所示的與設(shè)有如圖所示的與/ /或樹(shù)，節(jié)點(diǎn)按圖中所標(biāo)注的順或樹(shù)，節(jié)點(diǎn)按圖中所標(biāo)注的順序號(hào)進(jìn)行擴(kuò)展。其中標(biāo)有序號(hào)進(jìn)行擴(kuò)展。

35、其中標(biāo)有t t1 1、 t t2 2、 t t3 3、 t t4 4的節(jié)點(diǎn)均為的節(jié)點(diǎn)均為終止節(jié)點(diǎn)終止節(jié)點(diǎn)，A A和和B B為不可解的為不可解的端節(jié)點(diǎn)端節(jié)點(diǎn)。1 12 23 34 4t1t15 5B BA At2t2t4t4t5t5525.3.3 5.3.3 與與/ /或樹(shù)的有界深度優(yōu)先搜索或樹(shù)的有界深度優(yōu)先搜索其搜索過(guò)程：其搜索過(guò)程： 與與/ /或樹(shù)的深度優(yōu)先搜索過(guò)程和與或樹(shù)的深度優(yōu)先搜索過(guò)程和與/ /或樹(shù)的寬度優(yōu)或樹(shù)的寬度優(yōu)先搜索過(guò)程基本相同，只是將擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)放入先搜索過(guò)程基本相同，只是將擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)放入OPENOPEN表的表的首部首部，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的，并為每個(gè)子節(jié)

36、點(diǎn)配置指向父節(jié)點(diǎn)的指針。指針。 與與/ /或樹(shù)的有界深度優(yōu)先搜索同樣也規(guī)定一個(gè)深度或樹(shù)的有界深度優(yōu)先搜索同樣也規(guī)定一個(gè)深度界限，使搜索在規(guī)定的范圍內(nèi)進(jìn)行界限，使搜索在規(guī)定的范圍內(nèi)進(jìn)行535.3.4 5.3.4 與與/ /或樹(shù)的有序搜索或樹(shù)的有序搜索 與與/ /或樹(shù)的有序搜索可用來(lái)求取代價(jià)最小的解樹(shù)，是一種啟或樹(shù)的有序搜索可用來(lái)求取代價(jià)最小的解樹(shù)，是一種啟發(fā)式搜索策略發(fā)式搜索策略 1. 1. 解樹(shù)的代價(jià)解樹(shù)的代價(jià) 可通過(guò)計(jì)算樹(shù)中節(jié)點(diǎn)的代價(jià)得到?？赏ㄟ^(guò)計(jì)算樹(shù)中節(jié)點(diǎn)的代價(jià)得到。 設(shè)設(shè)c(x,y)c(x,y)表示節(jié)點(diǎn)表示節(jié)點(diǎn)x x到其子節(jié)點(diǎn)到其子節(jié)點(diǎn)y y的代價(jià)，計(jì)算節(jié)點(diǎn)的代價(jià)，計(jì)算節(jié)點(diǎn)x x代價(jià)的方

37、代價(jià)的方法如下：法如下：1 1）如果）如果x x是終止節(jié)點(diǎn)，則定義節(jié)點(diǎn)是終止節(jié)點(diǎn)，則定義節(jié)點(diǎn)x x的代價(jià)的代價(jià)h(x)=0;h(x)=0;2 2）如果）如果x x是是“或或”節(jié)點(diǎn)，節(jié)點(diǎn)，y y1 1, y, y2 2, , y, yn n是它的子節(jié)點(diǎn)，則節(jié)點(diǎn)是它的子節(jié)點(diǎn)，則節(jié)點(diǎn)x x的代價(jià)為的代價(jià)為 h(x)=minc(x, yh(x)=minc(x, yi i)+h(y)+h(yi i) ) 1in1in541. 1. 解樹(shù)的代價(jià)解樹(shù)的代價(jià)3 3）如果）如果x x是是“與與”節(jié)點(diǎn)，則節(jié)點(diǎn)節(jié)點(diǎn)，則節(jié)點(diǎn)x x的代價(jià)有兩種計(jì)算的代價(jià)有兩種計(jì)算方法：和代價(jià)法與最大代價(jià)法。方法：和代價(jià)法與最大代價(jià)法。

38、若按和代價(jià)法計(jì)算，則有：若按和代價(jià)法計(jì)算，則有： n n h(x)= h(x)= ( (c(x, yc(x, yi i)+h(y)+h(yi i) ) i=1i=1若按最大代價(jià)法計(jì)算，則有：若按最大代價(jià)法計(jì)算，則有： h(x)=maxc(x, yh(x)=maxc(x, yi i)+h(y)+h(yi i) ) 1in1in4 4）如果）如果x x是不可擴(kuò)展，且又不是終止節(jié)點(diǎn)，則定義是不可擴(kuò)展，且又不是終止節(jié)點(diǎn)，則定義h(x)=h(x)= 。55例例 圖為一棵與圖為一棵與/ /或樹(shù)，其中包括兩棵解樹(shù)，一棵解或樹(shù)，其中包括兩棵解樹(shù)，一棵解樹(shù)由樹(shù)由S S0 0，A A，t t1 1和和t t2 2

39、組成；另一棵解樹(shù)由組成；另一棵解樹(shù)由S S0 0，B B，D D，G G，t t4 4和和t t5 5組成。在此與組成。在此與/ /或樹(shù)中或樹(shù)中, t, t1 1、t t2 2 、t t3 3 、t t4 4 、t t5 5 為終止節(jié)點(diǎn)；為終止節(jié)點(diǎn)；E E、F F是端節(jié)點(diǎn)，其代價(jià)為是端節(jié)點(diǎn)，其代價(jià)為 ；邊上的；邊上的數(shù)字是邊的代價(jià)。數(shù)字是邊的代價(jià)。56S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0左邊的解樹(shù)左邊的解樹(shù)右邊的解樹(shù)右邊的解樹(shù)57 1) 1)若按和代價(jià)計(jì)算，右解樹(shù)是最優(yōu)解樹(shù)，若按和代價(jià)計(jì)算，右解樹(shù)是最優(yōu)

40、解樹(shù)，其代價(jià)為其代價(jià)為8 8； 2)2)若按最大代價(jià)計(jì)算，右解樹(shù)仍然是最優(yōu)解樹(shù)，若按最大代價(jià)計(jì)算，右解樹(shù)仍然是最優(yōu)解樹(shù)，其代價(jià)為其代價(jià)為7 7。 有時(shí)用不同的計(jì)算代價(jià)方法得到的最優(yōu)解樹(shù)不相同。有時(shí)用不同的計(jì)算代價(jià)方法得到的最優(yōu)解樹(shù)不相同。S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0由左邊的解樹(shù)可得：由左邊的解樹(shù)可得： 按和代價(jià)：按和代價(jià)： h(A)=11, h(Sh(A)=11, h(S0 0)=13)=13 按最大代價(jià)：按最大代價(jià)： h(A)=6, h(Sh(A)=6, h(S0 0)=8)=8由右邊的解樹(shù)可

41、得：由右邊的解樹(shù)可得： 按和代價(jià)：按和代價(jià)： h(G)=3, h(D)=4, h(B)=6, h(Sh(G)=3, h(D)=4, h(B)=6, h(S0 0)=8)=8按最大代價(jià)：按最大代價(jià)： h(G)=2, h(D)=3, h(B)=5, h(Sh(G)=2, h(D)=3, h(B)=5, h(S0 0)=7)=7582. 2. 希望樹(shù)希望樹(shù)定義：定義： 每次選擇欲擴(kuò)展的節(jié)點(diǎn)時(shí)希望成為最優(yōu)解樹(shù)一部分的節(jié)點(diǎn)每次選擇欲擴(kuò)展的節(jié)點(diǎn)時(shí)希望成為最優(yōu)解樹(shù)一部分的節(jié)點(diǎn)進(jìn)行擴(kuò)展。由這些節(jié)點(diǎn)及其先輩節(jié)點(diǎn)所構(gòu)成的與進(jìn)行擴(kuò)展。由這些節(jié)點(diǎn)及其先輩節(jié)點(diǎn)所構(gòu)成的與/ /或樹(shù)或樹(shù) ，稱(chēng)為，稱(chēng)為希望樹(shù)希望樹(shù)1 1）初

42、始節(jié)點(diǎn)）初始節(jié)點(diǎn)S S0 0在希望樹(shù)在希望樹(shù)T T中。中。2 2）如果節(jié)點(diǎn)）如果節(jié)點(diǎn)x x在希望樹(shù)在希望樹(shù)T T中，則一定有：中，則一定有：如果如果x x是具有子節(jié)點(diǎn)是具有子節(jié)點(diǎn)y y1 1,y,y2 2, ,y,yn n的的“或或”節(jié)點(diǎn)節(jié)點(diǎn), ,則具有則具有: : minc(x, y minc(x, yi i)+h(y)+h(yi i) 1in) 1in值的那個(gè)子節(jié)點(diǎn)值的那個(gè)子節(jié)點(diǎn)y yi i也應(yīng)在也應(yīng)在T T中。中。如果如果x x是是“與與”節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在T T中。中。59 博弈問(wèn)題（或?qū)剐运阉鳎槭裁纯梢杂门c博弈問(wèn)題（或?qū)剐运阉鳎槭裁纯梢杂?/p>

43、與/ /或圖表示呢？或圖表示呢？ 可以這樣來(lái)看待這個(gè)問(wèn)題：可以這樣來(lái)看待這個(gè)問(wèn)題： 當(dāng)輪到我方走棋時(shí)，只需從若干個(gè)可以走的棋中，選擇當(dāng)輪到我方走棋時(shí)，只需從若干個(gè)可以走的棋中，選擇一個(gè)棋走就可以了。從這個(gè)意義上說(shuō)，若干個(gè)可以走的棋一個(gè)棋走就可以了。從這個(gè)意義上說(shuō)，若干個(gè)可以走的棋是是“或或”的關(guān)系。而對(duì)于輪到對(duì)方走棋時(shí)，對(duì)于我方來(lái)說(shuō)，的關(guān)系。而對(duì)于輪到對(duì)方走棋時(shí)，對(duì)于我方來(lái)說(shuō)，必須能夠應(yīng)付對(duì)手的每一種走棋。這就相當(dāng)于這些棋與必須能夠應(yīng)付對(duì)手的每一種走棋。這就相當(dāng)于這些棋與/ /或或的關(guān)系。因此，博弈問(wèn)題可以看成是一個(gè)與的關(guān)系。因此，博弈問(wèn)題可以看成是一個(gè)與/ /或圖，但是與或圖，但是與一般的與

44、一般的與/ /或圖并不一樣，是一種特殊的與或圖并不一樣，是一種特殊的與/ /或圖或圖5.3.5 5.3.5 博弈樹(shù)的啟發(fā)式搜索博弈樹(shù)的啟發(fā)式搜索60 描述博弈過(guò)程的與描述博弈過(guò)程的與/ /或樹(shù)或樹(shù)1 1）博弈的初始格局是初始節(jié)點(diǎn)）博弈的初始格局是初始節(jié)點(diǎn)2 2）在博弈樹(shù)中，）在博弈樹(shù)中，“或或”節(jié)點(diǎn)和節(jié)點(diǎn)和“與與”節(jié)點(diǎn)是逐層交節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或或”關(guān)系，關(guān)系，對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與與”關(guān)系。雙方輪流地?cái)U(kuò)展關(guān)系。雙方輪流地?cái)U(kuò)展節(jié)點(diǎn)節(jié)點(diǎn)3 3）所有能使自己一方獲勝的終局都是本原問(wèn)題，相）所有能使自己一方獲勝的終

45、局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)，所有使對(duì)方獲勝的終局都是不應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)，所有使對(duì)方獲勝的終局都是不可解節(jié)點(diǎn)可解節(jié)點(diǎn)612. 2. 極大極小分析法極大極小分析法621 1）設(shè)博弈的雙方中一方為）設(shè)博弈的雙方中一方為A A，另一方為，另一方為B B。極大極小分析法是為其中的一。極大極小分析法是為其中的一方（例如方（例如A A）尋找一個(gè)最優(yōu)行動(dòng)方案的方法。）尋找一個(gè)最優(yōu)行動(dòng)方案的方法。2 2）為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行）為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)方案可能產(chǎn)生的后果進(jìn)行比較。具體地說(shuō)，就是要考慮每一個(gè)方案實(shí)施后對(duì)方可能采取的所有行動(dòng)比較。具體地說(shuō)，就是要考慮每一個(gè)方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并計(jì)算可能的得分，并計(jì)算可能的得分3）為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估）為了計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹(shù)端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱(chēng)為靜態(tài)