1、人工智能Artificial Intelligence,主講：楊利英 西安電子科技大學計算機學院 E_mail：,第五章搜索策略,5.1 基本概念 5.2 狀態(tài)空間的搜索策略 5.3 與/或樹的搜索策略 5.4 搜索的完備性與效率,5.1 基本概念,采用某種策略，在知識庫中尋找可利用的知識，從而構(gòu)造一條代價較小的推理路線，使問題得到解決的過程稱為搜索。,5.1.1 什么是搜索,5.1.1 什么是搜索,搜索分為盲目搜索和啟發(fā)式搜索。,盲目搜索是按照預(yù)定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。,啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導搜索朝著最有希望的方

2、向前進，加速問題的求解過程并找到最優(yōu)解。,5.1.2 狀態(tài)空間表示法,狀態(tài)空間用“狀態(tài)”和“算符”來表示問題。 狀態(tài) 狀態(tài)用以描述問題在求解過程中不同時刻的狀態(tài)，一般用向量表示 算符 使問題從一個狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。 狀態(tài)空間 由所有可能出現(xiàn)的狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間。,回顧,狀態(tài)空間示例：十五數(shù)碼難題,回顧,5.1.3 與/或樹表示法,對于一個復(fù)雜問題，直接求解往往比較困難。此時可通過下述方法進行簡化： （1）分解 （2）等價變換,回顧,5.1.3 與/或樹表示法,（1）分解 把一個復(fù)雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解。重復(fù)此過

3、程，直到不需要再分解或者不能再分解為止。如此形成“與”樹。 （2）等價變換 利用同構(gòu)或同態(tài)的等價變換，把原問題變換為若干個較為容易求解的新問題。如此形成“或”樹。,回顧,與/或樹,分解與等價變換可以結(jié)合起來使用，這樣形成的圖稱為“與/或樹”,回顧,由可解節(jié)點所構(gòu)成，并且由這些可解節(jié)點可推出初始節(jié)點為可解節(jié)點的子樹稱為解樹(t表示終止節(jié)點)。解樹中一定包含初始節(jié)點。（它對應(yīng)于原始問題）,解樹,回顧,5.2 狀態(tài)空間的搜索策略,5.2 狀態(tài)空間的搜索策略,盲目搜索 搜索按規(guī)定的路線進行，不使用與問題有關(guān)的啟發(fā)性信息； 適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問題。 啟發(fā)式搜索 使用與問題有關(guān)的啟發(fā)性信息

4、，并以這些啟發(fā)性信息指導搜索過程，可以高效地求解結(jié)構(gòu)復(fù)雜的問題。,5.2.1 狀態(tài)空間的一般搜索過程,一個復(fù)雜問題的狀態(tài)空間一般都是十分龐大的。如64階梵塔問題共有3的64次方個不同的狀態(tài)。 把問題的所有狀態(tài)空間都進行存儲有時候是不可能的。 把問題的所有狀態(tài)空間都進行存儲也是不必要的。因為與解題有關(guān)的狀態(tài)空間往往只是整個狀態(tài)空間的一部分，只要能生產(chǎn)并存儲這部分狀態(tài)空間就可以求出問題的解。,5.2.1 狀態(tài)空間的一般搜索過程,如何產(chǎn)生問題需要的狀態(tài)空間從而實現(xiàn)對問題的求解呢？答案就是搜索技術(shù)。 搜索技術(shù)基本思想：把問題的初始狀態(tài)作為當前狀態(tài)，選擇適用的算符對其操作，生產(chǎn)一組子狀態(tài)，然后檢查目標狀

5、態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解，否則按某種搜索策略從已生成的狀態(tài)中再選擇一個作為當前狀態(tài)。重復(fù)上述過程，直到目標狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符為止。,5.2.1 狀態(tài)空間的一般搜索過程,OPEN表和CLOSE表 OPEN表用于存放剛生成的節(jié)點。對于不同的搜索策略，節(jié)點在OPEN表中的排列順序是不同的。 CLOSE表用于存放將要擴展的節(jié)點。對一個節(jié)點的擴展是指：用所有可適用的算符對該節(jié)點進行操作，生成一組子節(jié)點 OPEN表,CLOSE表,搜索的一般過程,把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G； 檢查OPEN表是否為空，若為空則問題無解，退出；

6、 把OPEN表的第一個節(jié)點取出放入CLOSE表，并計該節(jié)點為n； 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出； 擴展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中；,針對M中子節(jié)點的不同情況，分別進行如下處理： 對于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表；（不在OPEN表） 對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點的指針；（在OPEN表中） 對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針；（在CLOSE

7、表中） 按某種搜索策略對OPEN表中的節(jié)點進行排序； 轉(zhuǎn)第2步。,搜索的一般過程,對一般搜索過程的一些說明,一個節(jié)點經(jīng)一個算符操作后一般只生成一個子節(jié)點。但適用于一個節(jié)點的算符可能有多個，此時就會生成一組子節(jié)點。這些子節(jié)點中可能有些是當前擴展節(jié)點的父節(jié)點、祖父節(jié)點等，此時不能把這些先輩節(jié)點作為當前擴展節(jié)點的子節(jié)點。,對一般搜索過程的一些說明,一個新生成的節(jié)點，它可能是第一次被生成的節(jié)點，也可能是先前已作為其它節(jié)點的子節(jié)點被生成過，當前又作為另一個節(jié)點的子節(jié)點被再次生成。此時，它究竟應(yīng)選擇哪個節(jié)點作為父節(jié)點？一般由原始節(jié)點到該節(jié)點的代價來決定，處于代價小的路途上的那個節(jié)點就作為該節(jié)點的父節(jié)點。,

8、對一般搜索過程的一些說明,在搜索過程中，一旦某個被考察的節(jié)點是目標節(jié)點就得到了一個解。該解是由從初始節(jié)點到該目標節(jié)點路徑上的算符構(gòu)成。 如果在搜索中一直找不到目標節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。,對一般搜索過程的一些說明,通過搜索得到的圖稱為搜索圖，搜索圖是狀態(tài)空間圖的一個子集。由搜索圖中的所有節(jié)點及反向指針所構(gòu)成的集合是一棵樹，稱為搜索樹。根據(jù)搜索樹可給出問題的解。,5.2.2 廣度（寬度）優(yōu)先搜索,基本思想： 從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考察它是否為目標節(jié)點。在第n層的節(jié)點沒有全部擴展并考察之前，不對第n1層的節(jié)點進行擴展。 OPEN表中節(jié)點總是按進入

9、的先后順序排列，先進入的節(jié)點排在前面，后進入的排在后面。,廣度優(yōu)先搜索過程,把初始節(jié)點S0放入OPEN表。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。,重排九宮的廣度優(yōu)先搜索操作符：空格左移、上移、右移、下移,小插曲關(guān)于九宮問題,射雕英雄傳 瑛姑的問題：將一至九這九個數(shù)字排成三列，不論縱橫斜角，每三字相加都是十五，如何排法？ 黃蓉的回答：九宮之義，法

10、以靈龜，二四為肩，六八為足，左三右七，戴九履一，五居中央。,幻方問題,中國人首先發(fā)現(xiàn)了幻方 洛水神龜獻奇圖,關(guān)于三階幻方的奧秘,南宋楊輝 研究幻方第一人,幻方問題在我國古代稱為“縱橫圖”，又叫“九宮算圖”。南宋大數(shù)學家楊輝在1275年所著的續(xù)古摘奇算法兩卷中，除了給出洛書中3階幻方的構(gòu)造方法外，還給出了4階至10階的幻方。,楊輝對3階幻方的解釋,三階幻方(15),四階幻方(34),歐美的幻方熱,德國畫家和文藝理論家丟勒在1514年創(chuàng)作的一幅銅版雕刻畫憂傷中就有一個4階幻方。 名畫憂傷現(xiàn)在珍藏于大英博物館。 富蘭克林也投入了很大精力研究幻方。,名畫憂傷,廣度優(yōu)先算法中需要注意的問題,1、對于任意

11、一個可擴展的節(jié)點，總是按照固定的操作符的順序?qū)ζ溥M行擴展（如前面重排九宮例子中的空格左移、上移、右移、下移）。 2、在對任一節(jié)點進行擴展的時候，如果所得的某個子節(jié)點（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復(fù)畫出（不送入OPEN表）。 因此，廣度優(yōu)先搜索的本質(zhì)是：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。,廣度優(yōu)先搜索的特點,優(yōu)點： 只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。 缺點： 廣度優(yōu)先搜索盲目性較大，當目標節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。,5.2.3 深度優(yōu)先搜索,基本思想：從初始節(jié)點開始，在其子節(jié)點中選擇

12、一個節(jié)點進行考察，若不是目標節(jié)點，則再在該子節(jié)點的子節(jié)點中選擇一個節(jié)點進行考察，一直如此向下搜索。當?shù)竭_某個子節(jié)點，且該子節(jié)點既不是目標節(jié)點又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。 深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。,深度優(yōu)先搜索過程,把初始節(jié)點S0放入OPEN表。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，將其子節(jié)點

13、放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。,重排九宮的深度優(yōu)先搜索,操作符：空格左移、上移、右移、下移,深度優(yōu)先搜索的特點,在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。 用深度優(yōu)先求得的解，不一定是路徑最短的解。 本質(zhì)：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。,5.2.4 有界深度優(yōu)先搜索,基本思想： 對深度優(yōu)先搜索引入搜索深

14、度界限（設(shè)為dm），當搜索深度達到了深度界限，而仍未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。 “有界”是為了解決深度優(yōu)先搜索不完備的問題，避免陷入無窮分支的死循環(huán)。,有界深度優(yōu)先搜索過程,把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n的深度d(n)=dm，則轉(zhuǎn)第2步（此時節(jié)點n位于CLOSE表，但并未進行擴展）。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，為每一個子節(jié)點都配置指向父

15、節(jié)點的指針，將每一個子節(jié)點的深度設(shè)置為d(n)+1，然后轉(zhuǎn)第2步。,對有界深度優(yōu)先搜索的說明,如果問題有解，且其路徑長度dm，則上述搜索過程一定能求得解。但是，若解的路徑長度dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。 要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。,有界深度優(yōu)先搜索的改進,先任意設(shè)定一個較小的數(shù)作為dm，然后進行上述的有界深度優(yōu)先搜索，當搜索達到了指定的深度界限dm仍未發(fā)現(xiàn)目標節(jié)點，并且CLOSE表中仍有待擴展節(jié)點時，就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解

16、，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。,有界深度優(yōu)先搜索的改進,2. 為了找到最優(yōu)解，可增設(shè)一個表R，每找到目標節(jié)點Sg后，就把它放入到R的前面，并令dm等于該目標節(jié)點所對應(yīng)的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以最后求得的解一定是最優(yōu)解。,重排九宮的有界深度優(yōu)先搜索,設(shè)深度界限dm4,5.2.5 代價樹的廣度優(yōu)先搜索,邊上標有代價(或費用)的樹稱為代價樹。 用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有： g(x2)=g(x1)+c(x1,x2),5.2.5 代價樹的廣度優(yōu)先搜索,

17、每次從OPEN表中選擇節(jié)點往CLOSE表傳送時，總是選擇其中代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面。 如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。 該算法應(yīng)用的條件:該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉(zhuǎn)換為代價樹。,代價樹廣度優(yōu)先搜索過程,把初始節(jié)點S0放入OPEN表，令g(S0)=0。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n

18、不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，為每一個子節(jié)點都配置指向父節(jié)點的指針，并將各子節(jié)點放入OPEN表中；計算各子節(jié)點的代價，按各節(jié)點的代價對OPEN表中的全部節(jié)點進行排序(按從小到大的順序)，然后轉(zhuǎn)第2步。,代價樹示例,圖到代價樹的轉(zhuǎn)換,求A到E的最小費用交通路線,代價樹的廣度優(yōu)先搜索,5.2.6 代價樹的深度優(yōu)先搜索,在代價樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點中選擇一個代價最小的節(jié)點送入CLOSE表進行考察 在代價樹的深度優(yōu)先搜索中，是從剛擴展出的子節(jié)點中選擇一個代價最小的節(jié)點送入CLOSE表進行考察,代價樹的深度優(yōu)先搜索過程,把初始節(jié)點S0放入OPEN表，令g(S0)=0。

19、如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，將其子節(jié)點按“邊”代價從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。 代價樹的深度優(yōu)先搜索是不完備的。,總 結(jié) 1、上述各種搜索方法的本質(zhì)是，以初始節(jié)點為根節(jié)點，按照既定的策略對狀態(tài)空間圖進行遍歷，并希望能夠盡早發(fā)現(xiàn)目標節(jié)點。 2、由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。,5.2.7 啟發(fā)式搜索,盲目搜索具有較大的盲目性

20、，產(chǎn)生的無用節(jié)點較多，效率不高。 啟發(fā)式搜索采用問題自身的特性信息，以指導搜索朝著最有希望的方向前進。這種搜索針對性較強，因而效率較高。,1.啟發(fā)性信息與估價函數(shù),可用于指導搜索過程，且與具體問題有關(guān)的信息稱為啟發(fā)性信息。 用于評估節(jié)點重要性的函數(shù)稱為估價函數(shù)。其一般形式為： f(x) = g(x)+h(x) 其中g(shù)(x)表示從初始節(jié)點S0到節(jié)點x的代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的代價的估計，它體現(xiàn)了問題的啟發(fā)性信息，稱為啟發(fā)函數(shù)。 f(x) 決定節(jié)點在OPEN表中的次序。,1.啟發(fā)性信息與估價函數(shù),g(x) 指出了搜索的橫向趨勢，有利于搜索的完備性，但影響搜索的效率。 h(

21、x)指出了搜索的縱向趨勢，有利于提高搜索的效率，但影響搜索的完備性。 確定f(x) 時要使g(x)+h(x)各占適當比重。,啟發(fā)函數(shù)示例,設(shè)有如下結(jié)構(gòu)的移動將牌游戲： 游戲規(guī)則： 當一個牌移入相鄰的空位置時，費用為一個單位。 一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數(shù)加1。 要求：把所有的B都移至W的右邊，請設(shè)計啟發(fā)函數(shù)h(x)。 解：根據(jù)要求可知，W左邊的B越少越接近目標，因此可用W左邊B的個數(shù)作為h(x),即 h(x)=3(每個W左邊B的個數(shù)的總和) 這里乘以系數(shù)3是為了擴大h(x)在f(x)中的比重。,例如下面這一狀態(tài)：h(x)=3(2+2+3)=21,2.局部擇優(yōu)搜索,局部

22、擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對深度優(yōu)先搜索方法的一種改進。 基本思想：當一個節(jié)點被擴展以后，按f(x)對每一個子節(jié)點計算估價值，并選擇最小者作為下一個要考察的節(jié)點。,局部擇優(yōu)搜索過程,把初始節(jié)點S0放入OPEN表，計算f(S0)。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第2步。,2.局部擇優(yōu)搜

23、索,在局部擇優(yōu)搜索中，若令f(x) = g(x)，則局部擇優(yōu)搜索就成為代價樹的深度優(yōu)先搜索。 在局部擇優(yōu)搜索中，若令f(x) =d(x)，這里d(x) 表示節(jié)點x的深度，則局部擇優(yōu)搜索就成為深度優(yōu)先搜索。 因此：深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索均為局部擇優(yōu)搜索的特例。,3.全局擇優(yōu)搜索,每當要選擇下一個節(jié)點進行考察時，局部擇優(yōu)搜索只是從剛生成的子節(jié)點中選擇一個估價值最小的節(jié)點。其選擇范圍比較窄。 每當要選擇下一個節(jié)點進行考察時，全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點中選擇一個估價值最小的節(jié)點。,全局擇優(yōu)搜索過程,把初始節(jié)點S0放入OPEN表，計算f(S0)。 如果OPEN表為空，則問題無

24、解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉(zhuǎn)第2步。 擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉(zhuǎn)第2步。,3.全局擇優(yōu)搜索,在全局擇優(yōu)搜索中，若令f(x) = g(x)，則它就成為代價樹的廣度優(yōu)先搜索。 在全局擇優(yōu)搜索中，若令f(x) =d(x)，這里d(x) 表示節(jié)點x的深度，則它就成為廣度優(yōu)先搜索。 因此：廣度優(yōu)先搜索、代價樹的廣度優(yōu)

25、先搜索是全局擇優(yōu)搜索的兩個特例。,重排九宮問題的全局擇優(yōu)搜索樹,設(shè)估價函數(shù)為 f(x)=d(x)+h(x)，其中，d(x)表示節(jié)點x的深度，h(x)表示節(jié)點x的格局與目標節(jié)點格局不相同的牌數(shù)。,5.3 與/或樹的搜索策略,5.3.1 與/或樹的一般搜索過程 5.3.2 博弈樹的啟發(fā)式搜索 5.3.3 剪枝技術(shù),5.3 與/或樹的搜索策略,5.3 與/或樹的搜索策略,用與/或樹方法求解問題時，首先要定義問題的描述方法及分解和變換問題的算符，然后就可以用它們通過搜索生成與/或樹，從而求得原始問題的解。 在與/或樹中，由可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為可解節(jié)點的過程稱為可解標示過程；由不可解子

26、節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可解節(jié)點的過程稱為不可解標示過程； 在與/或樹搜索過程中，將反復(fù)使用可解和不可解標示過程，直到初始節(jié)點被標示為可解或不可解節(jié)點為止。,5.3.1 與/或樹的一般搜索過程,把原始問題作為初始節(jié)點S0，并把S0作為當前節(jié)點； 應(yīng)用分解或等價算法對當前節(jié)點進行擴展； 為每個子節(jié)點設(shè)置指向父節(jié)點的指針； 選擇合適的子節(jié)點作為當前節(jié)點，反復(fù)執(zhí)行第2和第3步，期間將反復(fù)使用可解和不可解標示過程，直到初始節(jié)點被標示為可解或不可解節(jié)點為止。 由這個搜索過程形成的節(jié)點和指針結(jié)構(gòu)稱為搜索樹。,與/或樹的廣度優(yōu)先搜索,把初始節(jié)點S0放入OPEN表。 把OPEN表的第一個節(jié)點（記為節(jié)

27、點n）取出放入CLOSE表。 若節(jié)點n可擴展，則做如下工作。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標示過程使用。 考察這些子節(jié)點中是否有終止節(jié)點。如有，則標示這些終止節(jié)點為可解節(jié)點，并用可解標示過程對其先輩節(jié)點中的可解節(jié)點進行標示。如果初始節(jié)點S0也被標示為可解節(jié)點，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。 轉(zhuǎn)第2步。 若節(jié)點n不可擴展，則做如下工作。 標示節(jié)點n為不可解節(jié)點。 用不可解標示過程對n的先輩節(jié)點中的不可解節(jié)點進行標示。如果初始節(jié)點S0也被標示為不可解節(jié)點，則搜索失敗，退出；如

28、果不能確定S0為不可解節(jié)點，則從OPEN表中刪去具有不可解先輩的節(jié)點。 轉(zhuǎn)第2步。,與/或樹的（有界）深度優(yōu)先搜索,把初始節(jié)點S0放入OPEN表。 把OPEN表的第個節(jié)一點（記為節(jié)點n）取出放入CLOSE表。 若節(jié)點n的深度大于等于深度界限，則轉(zhuǎn)第5步中的第。 若節(jié)點n可擴展，則做如下工作。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標示過程使用。 考察這些子節(jié)點中是否有終止節(jié)點。如有，則標示這些終止節(jié)點為可解節(jié)點，并用可解標示過程對其先輩節(jié)點中的可解節(jié)點進行標示。如果初始節(jié)點S0也被標示為可解節(jié)點，則得到了解樹，搜索成功，退出；如果不能確定S0為可解

29、節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。 轉(zhuǎn)第2步。 若節(jié)點n不可擴展，則做如下工作。 標示節(jié)點n為不可解節(jié)點。 用不可解標示過程對n的先輩節(jié)點中的不可解節(jié)點進行標示。如果初始節(jié)點S0也被標示為不可解節(jié)點，則搜索失敗，退出；如果不能確定S0為不可解節(jié)點，則從OPEN表中刪去具有不可解先輩的節(jié)點。 轉(zhuǎn)第2步。,與/或樹的廣度和深度優(yōu)先搜索舉例,A,廣度優(yōu)先的擴展順序：1.2.3.4.5,深度優(yōu)先的擴展順序（規(guī)定深度界限為4）：1.3.B.5.2.4,A,B為不可解的端節(jié)點 t1,t2,t3,t4為終止節(jié)點,5.3.2 博弈樹的啟發(fā)式搜索,1.博弈樹的基本概念 博弈：諸如下棋、打牌、戰(zhàn)爭等一

30、類競爭性智能活動。 “二人零和、全信息、非偶然”博弈 （1）對壘的雙方A、B輪流采取行動，博弈的結(jié)果只有三種情況：A勝B敗，A敗B勝，平局。 （2）對壘過程中，任何一方都了解當前的格局及過去的歷史。 （3）雙方都是理智的決定自己的行動的。,博弈樹,描述博弈過程的與/或樹稱為博弈樹，它具有如下特點： （1）博弈的初始格局是初始節(jié)點。 （2）在博弈樹中，或節(jié)點和與節(jié)點是交替出現(xiàn)的。己方擴展的節(jié)點之間是或關(guān)系，對方擴展的節(jié)點之間是與關(guān)系。雙方輪流擴展。 （3）所有能使己方獲勝的終局都是可解節(jié)點，使對方獲勝的終局是不可解節(jié)點。 博弈樹是始終站在一方的立場上得出的。,2. 極大極小分析法,極大極小分析法

31、是在二人博弈中，為了使己方獲勝而采用的分析方法?；舅枷肴缦拢?（1）為博弈雙方中的一方尋找一個最優(yōu)行動方案。 （2）要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。 （3）為計算得分，需要定義一個估價函數(shù)，用來估算當前博弈樹端節(jié)點的得分（靜態(tài)估算值）。 （4）由端節(jié)點的得分估算父節(jié)點的得分（倒推值）：對或節(jié)點，選子節(jié)點中最大的得分給父節(jié)點；對與節(jié)點，選子節(jié)點中最小的得分給父節(jié)點。 （5）如果一個行動方案能獲得較大的倒推值，則它就是當前最好的方案。,極大極小分析法面臨的問題,試圖用完整的博弈樹來進行極大極小分析是困難的。 可行的方法：生成一定深度的博弈樹，而后進行極大極小分析法，找出當前最好的方案。此后再在已經(jīng)選定的分支上擴展一定深度，再選最好的方案。如此進行下去，直到取得勝敗的結(jié)果為止。,5.3.3 剪枝技術(shù),在極大極小分析法中，總是先生成一定深度的博弈樹，對端節(jié)點進行估值，然后計算上層節(jié)點的倒推值。這樣做效率并不高。 鑒于博弈樹具有或節(jié)點和與節(jié)點交替出現(xiàn)的特點，如果能夠邊生成節(jié)點邊估值，就有可能刪去一些不必要的節(jié)點。剪枝技術(shù)就是基于此提出的。,通過邊生成節(jié)點邊計算估值，從而刪去某些分枝的技術(shù)稱為剪枝技術(shù)。 與節(jié)點