《人工智能與專家系統(tǒng)（第二版）》課件第3章 搜索方法

人工智能與專家系統(tǒng)第3章搜索方法

3.1問題求解過程的形式表示3.2狀態(tài)空間的搜索方法3.3與∕或圖的搜索方法第3章搜索方法根據(jù)領(lǐng)域知識的多寡，分為知識貧乏系統(tǒng)和知識豐富系統(tǒng)。

知識貧乏系統(tǒng)的求解問題如果能設(shè)計(jì)一個(gè)操作算子（算符）集,則可使用搜索技術(shù)求解。

知識豐富系統(tǒng)的求解問題依靠推理技術(shù)求解。3.1問題求解過程的形式表示3.1.1狀態(tài)空間表示法3.1.2與/或圖表示法3.1.1狀態(tài)空間表示法

狀態(tài)空間表示法用“狀態(tài)”和“算符”來表示問題及求解問題可使用的知識。

狀態(tài)：是求解過程中用以描述問題在任一時(shí)刻狀況的數(shù)據(jù)結(jié)構(gòu)。

算符：表示對狀態(tài)的操作，算符的一次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)。

問題的解：當(dāng)?shù)竭_(dá)目標(biāo)狀態(tài)時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就是問題的一個(gè)解。由問題的全部狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間，一般用一個(gè)三元組表示：（S，F(xiàn)，G）其中S是問題的所有初始狀態(tài)構(gòu)成的集合；F是算符的集合；G是目標(biāo)狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。其中，節(jié)點(diǎn)表示狀態(tài)；有向邊（?。┍硎舅惴?。例3.1

二階梵塔問題設(shè)有三根柱子，在1號柱子上穿有A、B兩個(gè)盤片，盤A小于盤B，盤A位于盤B的上面。要求把這兩個(gè)盤片全部移到另一根柱子上，而且規(guī)定每次只能移動(dòng)一片，任何時(shí)刻都不能使盤B位于盤A的上面。畫出二階梵塔問題的狀態(tài)空間有向圖，并給出問題的解。解：設(shè)用S=（xA,xB）表示問題的狀態(tài)，xA表示盤A所在的柱號，xB表示盤B所在的柱號。全部可能的狀態(tài)有以下9種：S0=（1,1）S1=（1,2）S2=（1,3）S3=（2,1）S4=（2,2）S5=（2,3）S6=（3,1）S7=（3,2）S8=（3,3）問題的初始狀態(tài)集合為S={S0}，目標(biāo)狀態(tài)集合為G={S4,S8}。算符：A(i,j)表示把盤A從柱i移到柱j上；B(i,j)表示把盤B從柱i移到柱j上。共有12個(gè)算符，它們分別是：A(1,2)，A(1,3)，A(2,1)，A(2,3)，A(3,1)，A(3,2)B(1,2)，B(1,3)，B(2,1)，B(2,3)，B(3,1)，B(3,2)圖3.1二階梵塔的狀態(tài)空間1,12,12,33,31,22,23,23,11,3B(1,2)A(1,3)A(3,2)3.1.2與/或圖表示法問題歸約方法:把初始問題通過一系列變換最終變?yōu)橛扇舾勺訂栴}組成的集合，而這些子問題的解可以直接得到，從而解答了初始問題。問題歸約方法表示問題及其求解過程用與/或圖表示。1分解變換

問題的分解過程可用一個(gè)“與樹”表示。把問題P分解為三個(gè)子問題P1、P2、P3，只有當(dāng)P1、P2、P3三個(gè)子問題都可解時(shí)，問題P才可解，稱P1、P2、P3之間存在“與關(guān)系”；稱節(jié)點(diǎn)P為“與節(jié)點(diǎn)”。圖3.2與樹

等價(jià)變換問題的等價(jià)變換過程可用一個(gè)“或樹”表示。問題P被等價(jià)變換為新問題P1、P2、P3，其中，新問題P1、P2、P3中只要有一個(gè)可解，則原問題就可解，稱P1、P2、P3之間存在“或關(guān)系”；節(jié)點(diǎn)P稱為“或節(jié)點(diǎn)”。PP1P2P3圖3.2或樹與/或樹:其中既有“與”節(jié)點(diǎn)，也有“或”節(jié)點(diǎn)。PP2P3P1P11P12P31P32P33圖3.4與/或樹3本原問題直接可解的子問題稱為本原問題。4端節(jié)點(diǎn)與終葉節(jié)點(diǎn)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)；本原問題所對應(yīng)的端節(jié)點(diǎn)稱為終葉節(jié)點(diǎn)。5可解節(jié)點(diǎn)①它是一個(gè)終葉節(jié)點(diǎn)。②它是一個(gè)“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)至少有一個(gè)是可解節(jié)點(diǎn)。③它是一個(gè)“與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。6不可解節(jié)點(diǎn)①它是一個(gè)非終葉節(jié)點(diǎn)的端節(jié)點(diǎn)，即無法變換的非終葉節(jié)點(diǎn)。②它是一個(gè)“或”節(jié)點(diǎn)，且其子節(jié)點(diǎn)全部是不可解節(jié)點(diǎn)。③它是一個(gè)“與”節(jié)點(diǎn)，且其子節(jié)點(diǎn)至少有一個(gè)是不可解節(jié)點(diǎn)。7解樹由可解節(jié)點(diǎn)構(gòu)成的、且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)（它對應(yīng)于原始問題）為可解節(jié)點(diǎn)的與/或樹稱為解樹。例3.2

三階梵塔問題：如圖3.5所示。應(yīng)用分解變換求解三階梵塔問題。（a）初始狀態(tài) （b）目標(biāo)狀態(tài)

圖3.5三階梵塔問題解：定義問題的狀態(tài)表示：S=（xC，xB，xA）其中xC表示盤片C所在的柱號；xB表示盤片B所在的柱號；xA表示盤片A所在的柱號。算符集：F={A(i,j),B(i,j),C(i,j)},分別表示把盤A，B，C從柱I移到柱j上。初始問題：(（1,1,1）,F,（3,3,3）)可用與/或樹把分解過程表示出來，如圖3.6所示。圖3.6三階梵塔問題的與/或樹7個(gè)終葉節(jié)點(diǎn)對應(yīng)于7個(gè)本原問題：(（1,1,1）,（1,1,3）)，(（1,1,3）,（1,2,3）)，(（1,2,3）,（1,2,2）),(（1,2,2）,（3,2,2）)，

(（3,2,2）,（3,2,1）)，(（3,2,1）,（3,3,1）),(（3,3,1）,（3,3,3）)初始問題的解：A（1,3），B（1,2），A（3,2），C（1,3），A（2,1），B（2,3），A（1,3）3.2狀態(tài)空間的搜索方法3.2.1盲目搜索算法3.2.2啟發(fā)式搜索算法3.2.3狀態(tài)空間搜索算法的應(yīng)用3.2.4Ａ*算法及其特性3.2狀態(tài)空間的搜索方法搜索的結(jié)果將獲得一棵搜索樹。搜索樹是由稱為open表和closed表的兩個(gè)表共同記載的。①open表記載搜索過程中尚未考查的節(jié)點(diǎn)和新生成的節(jié)點(diǎn)；②open表支持按指定要求對表中節(jié)點(diǎn)排序；③搜索算法每次循環(huán)時(shí)都將open表中的第一個(gè)節(jié)點(diǎn)移送到closed表的表尾；④closed表記載搜索過程中已被考查過的節(jié)點(diǎn)。3.2.1盲目搜索算法1無代價(jià)的寬度優(yōu)先搜索寬度優(yōu)先搜索：在搜索樹的生成過程中，只有對搜索樹中同一層的所有節(jié)點(diǎn)都考查完之后，才會(huì)對下一層的節(jié)點(diǎn)進(jìn)行考查。open表和closed表的節(jié)點(diǎn)域的定義：無代價(jià)寬度優(yōu)先搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。（2）若open=（），則算法失敗終止；否則轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止，否則轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成I的所有子節(jié)點(diǎn)。若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中也不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將所有的新子節(jié)點(diǎn)放入open表的表尾并記載子節(jié)點(diǎn)各個(gè)域的值，轉(zhuǎn)步驟（2）；否則，不把新生成的節(jié)點(diǎn)j放入open中(放棄節(jié)點(diǎn)j），轉(zhuǎn)步驟（2）。2無代價(jià)的深度優(yōu)先搜索深度優(yōu)先搜索：在搜索樹的生成過程中，對open表中同一層的節(jié)點(diǎn)只選擇表中一個(gè)節(jié)點(diǎn)進(jìn)行考查和擴(kuò)展，只有當(dāng)這個(gè)節(jié)點(diǎn)是不可擴(kuò)展的。才選擇同層的兄弟節(jié)點(diǎn)進(jìn)行考查和擴(kuò)展。open表和closed表的節(jié)點(diǎn)的域定義：無代價(jià)深度優(yōu)先搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。設(shè)置搜索最大深度dmax的值.（2）若open=（），則算法失敗終止；否則轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止；否則轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成i的所有子節(jié)點(diǎn)。若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中又不在closed表中且dj≤dmax，則節(jié)點(diǎn)j是一個(gè)允許的新節(jié)點(diǎn)。將所有的新子節(jié)點(diǎn)按節(jié)點(diǎn)序號從小到大依序放入open表的表首，并記載子節(jié)點(diǎn)各域的值。否則，不把新生成的節(jié)點(diǎn)j放入open表中（放棄節(jié)點(diǎn)j），轉(zhuǎn)步驟（2）。3有代價(jià)的寬度優(yōu)先搜索定義節(jié)點(diǎn)j的代價(jià)函數(shù)為：

gj

=gi

+c（i,j）open表和closed表的節(jié)點(diǎn)域定義：有代價(jià)寬度優(yōu)先搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。且令g1=0（2）若open=（），則算法失敗終止；否則轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止，否則轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成i

的所有子節(jié)點(diǎn)，并計(jì)算所有子節(jié)點(diǎn)的代價(jià)值。①若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中，也不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將所有新子節(jié)點(diǎn)放入open表中，記載子節(jié)點(diǎn)各域的值，轉(zhuǎn)步驟（7）。②若子節(jié)點(diǎn)j的狀態(tài)Sj已在open表中，即節(jié)點(diǎn)j與open表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較gj與gj’。若gj≥gj’，則放棄新節(jié)點(diǎn)j；若gj<gj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除open中的老節(jié)點(diǎn)j’；轉(zhuǎn)步驟（7）。③若子節(jié)點(diǎn)j的狀態(tài)Sj已在closed表中，即節(jié)點(diǎn)j與closed表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較gj與gj’。若gj≥gj’，則放棄新節(jié)點(diǎn)j；若gj<gj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除closed中的老節(jié)點(diǎn)j’以及節(jié)點(diǎn)j’在open表和closed表中的所有后裔節(jié)點(diǎn)。轉(zhuǎn)步驟（7）。

（7）對open表中的所有節(jié)點(diǎn)按g值從小到大的順序重新排序，若有2個(gè)或2個(gè)以上的節(jié)點(diǎn)有相同的g值，則對這些節(jié)點(diǎn)再按節(jié)點(diǎn)序號排序。轉(zhuǎn)步驟（2）。4有代價(jià)的深度優(yōu)先搜索open表和closed表的節(jié)點(diǎn)域定義：jSjFkgji有代價(jià)深度優(yōu)先搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。且令g1=0（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i

的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止，否則，轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)I不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則，轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成i

的所有子節(jié)點(diǎn)，并計(jì)算所有子節(jié)點(diǎn)的代價(jià)值。①若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中，也不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將所有新子節(jié)點(diǎn)放入open表中，記載子節(jié)點(diǎn)各域的值，轉(zhuǎn)步驟（7）。②若子節(jié)點(diǎn)j的狀態(tài)Sj已在open表中的一個(gè)，即節(jié)點(diǎn)j與open表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較gj與gj’。若gj≥gj’，則放棄新節(jié)點(diǎn)j；若gj<gj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除open表中的老節(jié)點(diǎn)j’；轉(zhuǎn)步驟（7）。③若子節(jié)點(diǎn)j的狀態(tài)Sj已在closed表中的一個(gè)，即節(jié)點(diǎn)j與closed表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較gj與gj’。若gj≥gj’，則放棄新節(jié)點(diǎn)j；若gj<gj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除closed表中的老節(jié)點(diǎn)j’以及節(jié)點(diǎn)j’在open表和closed表中的所有后裔節(jié)點(diǎn)。轉(zhuǎn)步驟（7）。（7）對open表中的新子節(jié)點(diǎn)按g值從小到大排序后放入open表中的表首，若有2個(gè)或2個(gè)以上的節(jié)點(diǎn)有相同的g值，則按這些節(jié)點(diǎn)再按節(jié)點(diǎn)序號排序。轉(zhuǎn)步驟（2）。例3.3應(yīng)用狀態(tài)空間的搜索策略求解最短路徑問題：求從城市A經(jīng)過每個(gè)城市最多一次到達(dá)城市E的最小交通費(fèi)用的解。（1）給出問題求解的狀態(tài)定義（2）給出問題求解的算符定義（3）應(yīng)用有代價(jià)寬度優(yōu)先搜索求解（4）應(yīng)用有代價(jià)深度優(yōu)先搜索求解圖3.7例3.3的城市交通路線圖解：（1）狀態(tài)定義狀態(tài)S定義為當(dāng)前走過的城市名字符串，剛走過的城市名在串尾。初態(tài)：S0=A

終態(tài)：Sg=A$E其中$為城市名子串，$∈{B，C，D}（2）算符定義

go(x,y)表示從城市x走到城市y。使用條件：當(dāng)前狀態(tài)Si城市名字符串串尾城市名是x且Si不含城市名y算符操作：將城市名y添加到當(dāng)前狀態(tài)Si

的串尾。表3.1例3.3的算符集FK算符算符代價(jià)FK算符算符代價(jià)F1go(A,B)4F7go(C,D)2F2go(A,C)3F8go(D,B)4F3go(B,A)4F9go(D,C)2F4go(B,D)4F10go(D,E)3F5go(B,E)5F11go(E,B)5F6go(C,A)3F12go(E,D)3（3）應(yīng)用有代價(jià)寬度優(yōu)先搜索求解open=(1(0))Loop1:closed=(1(0))open=(3(3),2(4))Loop2:closed=(1(0),3(3))open=(2(4),4(5))Loop3:closed=(1(0),3(3),2(4))open=(4(5),5(8),6(9))Loop4:closed=(1(0),3(3),2(4),4(5))open=(5(8),8(8),6(9),7(9))Loop5:closed=(1(0),3(3),2(4),4(5),5(8))open=(8(8),6(9),7(9),9(10),10(11))Loop6:closed=(1(0),3(3),2(4),4(5),5(8),8(8))S8=ACDE是目標(biāo)狀態(tài)，故算法成功終止。

open=(6(9),7(9),9(10),10(11))圖3.8例3.3的有代價(jià)寬度優(yōu)先搜索生成的搜索樹（4）應(yīng)用有代價(jià)深度優(yōu)先搜索求解

open=(1(0))Loop1:closed=(1(0))open=(3(3),2(4))Loop2:closed=(1(0),3(3))open=(4(5),2(4))Loop3:closed=(1(0),3(3),4(5))open=(6(8),5(9),2(4))Loop4:closed=(1(0),3(3),4(5),6(8))S6=ACDE是目標(biāo)狀態(tài)，故算法成功終止。

open=(5(9),2(4))圖3.9例3.3的有代價(jià)深度優(yōu)先搜索生成的搜索樹3.2.2啟發(fā)式搜索算法

估價(jià)函數(shù)：f(x)=g(x)+h(x)

代價(jià)函數(shù)g(x)為從初始節(jié)點(diǎn)到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià)

啟發(fā)函數(shù)h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的估計(jì)代價(jià)。open表和closed表的節(jié)點(diǎn)的域可如下定義：jSjFkgjhjfji局部擇優(yōu)搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。且令g1

=0，計(jì)算h1和f1

=

g1+h1（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止，否則，轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則，轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成i的所有子節(jié)點(diǎn)，并計(jì)算所有子節(jié)點(diǎn)的估價(jià)值f。①若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中，也不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將所有新子節(jié)點(diǎn)放入open表中，記載子節(jié)點(diǎn)各域的值，轉(zhuǎn)步驟（7）。②若子節(jié)點(diǎn)j的狀態(tài)Sj已在open表中，即節(jié)點(diǎn)j與open表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較fj與fj’。若fj≥fj’，則放棄新節(jié)點(diǎn)j；若fj<fj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除open表中的老節(jié)點(diǎn)j’；轉(zhuǎn)步驟（7）。③若子節(jié)點(diǎn)j的狀態(tài)Sj已在closed表中，即節(jié)點(diǎn)j與closed表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較fj與fj’。若fj≥fj’，則放棄新節(jié)點(diǎn)j；若fj<fj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除closed表中的老節(jié)點(diǎn)j’以及節(jié)點(diǎn)j’在open表和closed表中的所有后裔節(jié)點(diǎn)。轉(zhuǎn)步驟（7）.（7）對open表中的新子節(jié)點(diǎn)按f值從小到大排序后放入open表中的表首，若有2個(gè)或2個(gè)以上的節(jié)點(diǎn)有相同的f值，則對這些節(jié)點(diǎn)再按節(jié)點(diǎn)序號排序。轉(zhuǎn)步驟（2）。全局擇優(yōu)搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。且令g1=0，并計(jì)算h1和f1=

g1+h1。（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）把open表的第1個(gè)節(jié)點(diǎn)i移出，放入closed表的表尾。（4）若節(jié)點(diǎn)i的狀態(tài)Si是目標(biāo)狀態(tài)，則算法成功終止，否則，轉(zhuǎn)步驟（5）。（5）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則轉(zhuǎn)步驟（2）；否則，轉(zhuǎn)步驟（6）。（6）用可用算符逐一擴(kuò)展節(jié)點(diǎn)i，生成i的所有子節(jié)點(diǎn)，并計(jì)算所有子節(jié)點(diǎn)的估價(jià)值。①若子節(jié)點(diǎn)j的狀態(tài)Sj既不在open表中，也不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將所有新子節(jié)點(diǎn)放入open表中，記載子節(jié)點(diǎn)各域的值，轉(zhuǎn)步驟（7）。②若子節(jié)點(diǎn)j的狀態(tài)Sj已在open表中，即節(jié)點(diǎn)j與open表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較fj與fj’。若fj≥fj’，則放棄新節(jié)點(diǎn)j；若fj<fj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除open表中的老節(jié)點(diǎn)j’；轉(zhuǎn)步驟（7）。

③若子節(jié)點(diǎn)j的狀態(tài)Sj已在closed表中，即節(jié)點(diǎn)j與closed表中的一個(gè)老節(jié)點(diǎn)j’的狀態(tài)相同，則比較fj與fj’。若fj≥fj’，則放棄新節(jié)點(diǎn)j；若fj<fj’，則將新節(jié)點(diǎn)j放入到open表中，記載節(jié)點(diǎn)各域的值，并刪除closed表中的老節(jié)點(diǎn)j’以及節(jié)點(diǎn)j’在open表和closed表中的所有后裔節(jié)點(diǎn)。轉(zhuǎn)步驟（7）。（7）對open表中的所有節(jié)點(diǎn)按f值從小到大的順序重新排序，若有2個(gè)或2個(gè)以上的節(jié)點(diǎn)有相同的f值，則對這些節(jié)點(diǎn)再按節(jié)點(diǎn)序號排序。轉(zhuǎn)步驟（2）。例3.4

應(yīng)用狀態(tài)空間的全局擇優(yōu)搜索求解例3.3的最短路徑問題。解：（1）狀態(tài)定義同例3.3（2）算符定義同例3.3（3）應(yīng)用全局擇優(yōu)搜索策略求解估計(jì)函數(shù)：fj

=gj

+hj

代價(jià)函數(shù)gj

=gi+c(i,j)，啟發(fā)函數(shù)hj=a(b-dj)其中，參數(shù)a為兩個(gè)城市之間的平均費(fèi)用（代價(jià)）

a=（3+4+4+2+3+5）/6=21/6=3.5可取整數(shù)a=3參數(shù)b為從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)需要到達(dá)的城市數(shù)的估計(jì)?？梢匀=2,或取b=3,或取b=4。取b=2，則hj=3（2-dj）

open=(1(6))Loop1:closed=(1(6))open=(3(5),2(7))Loop2:closed=(1(6),3(6))open=(4(5),2(7))Loop3:closed=(1(6),3(6),4(5))open=(6(5),5(6),2(7))Loop4:closed=(1(6),3(6),4(5),6(5))S6=ACDE是目標(biāo)狀態(tài)，故算法成功終止。

open=(5(6),2(7))圖3.10例3.4生成的搜索樹（1）取b=3，則hj=3(3-dj)open=(1(9))Loop1:closed=(1(9))open=(3(9),2(10))Loop2:closed=(1(9),3(9))open=(4(8),2(10))Loop3:closed=(1(9),3(9),4(8))open=(6(8),5(9),2(10))Loop4:closed=(1(9),3(9),4(8),6(8))S6=ACDE是目標(biāo)狀態(tài)，故算法成功終止。

open=(5(9),2(10))圖3.11例3.4生成的搜索樹（2）取b=4,則hj=3（4–dj）

open=(1(12))Loop1:closed=(1(12))open=(3(12),2(13))Loop2:closed=(1(12),3(12))open=(4(11),2(13))Loop3:closed=(1(12),3(12),4(11))open=(6(11),5(12),2(13))Loop4:closed=(1(12),3(12),4(11),6(11))S6=ACDE是目標(biāo)狀態(tài)，故算法成功終止。

open=(5(12),2(13))圖3.12例3.4生成的搜索樹（3）

例3.5

五個(gè)城市之間的交通路線圖如圖3.13所示，從城市A出發(fā)到城市E，且經(jīng)過每個(gè)城市最多一次，求從A到E的最小費(fèi)用的解。（1）應(yīng)用有代價(jià)寬度優(yōu)先搜索求解，算法循環(huán)多少次終止？畫出搜索樹，給出問題的解。（2）應(yīng)用全局擇優(yōu)搜索策略求解，算法循環(huán)多少次終止？畫出搜索樹，給出問題的解。

圖3.13例3.5的城市交通路線圖解：(1)有代價(jià)寬度優(yōu)先搜索求解圖3.14例3.5的代價(jià)樹寬度優(yōu)先搜索的搜索樹

(2)全局擇優(yōu)搜索求解:hj=a(3-dj)圖3.16例3.5的全局擇優(yōu)搜索的搜索樹3.2.3狀態(tài)空間搜索算法的應(yīng)用

例3.6

應(yīng)用狀態(tài)空間的搜索策略求解最短路徑問題：求從城市A經(jīng)過每個(gè)城市最多一次到達(dá)城市F的最小交通費(fèi)用的解。(1)應(yīng)用有代價(jià)寬度優(yōu)先搜索求解。(2)應(yīng)用有代價(jià)深度優(yōu)先搜索求解。(3)應(yīng)用全局擇優(yōu)搜索求解。圖3.16例3.6的交通路線圖解：

（1）狀態(tài)定義(略)（2）算符定義(略)（3）應(yīng)用代價(jià)樹寬度優(yōu)先搜索求解圖3.17例3.6的有代價(jià)寬度優(yōu)先搜索生成的搜索樹（4）應(yīng)用有代價(jià)深度優(yōu)先搜索求解圖3.18例3.6的有代價(jià)深度優(yōu)先搜索的搜索樹（5）應(yīng)用全局擇優(yōu)搜索策略求解啟發(fā)函數(shù)hj=a(b-dj)，參數(shù)a≈6，參數(shù)b可取b=2～5。取b=3，則hj

=6（3-dj）圖3.19例3.6的全局擇優(yōu)搜索的搜索樹例3.7

應(yīng)用全局擇優(yōu)搜索求解推銷員旅行問題：推銷員從城市A出發(fā)經(jīng)過圖中每個(gè)城市一次且一次，回到城市A。求最小交通費(fèi)用的解。圖3.20例3.7的交通路線圖解：（1）狀態(tài)定義(略)（2）算符定義(略)

由20個(gè)算符組成算符集。（3）應(yīng)用全局擇優(yōu)搜索策略求解啟發(fā)函數(shù)

hj=a(b-dj)，參數(shù)a

≈8，參數(shù)b由題意可知，b=5。

hj

=8（5-dj）。圖3.21例3.7的全局擇優(yōu)搜索生成的搜索樹例3.8

應(yīng)用全局擇優(yōu)搜索求解九宮重排問題。

（a）初始棋局 （b）目標(biāo)棋局圖3.22例3.8的初始棋局與目標(biāo)棋局解：（1）狀態(tài)定義S=[aij]3×3 aij∈A=[1,8]初態(tài)：S0=

終態(tài)：Sg=（2）算符定義空格左移F1：（aij=””）∧（ai,j-1∈A）→（aij=ai,j-1）∧（ai,j-1=””）空格上移F2：（aij=””）∧（ai-1,j∈A）→（aij=ai-1,j）∧（ai-1,j=””）空格右移F3：（aij=””）∧（ai,j+1∈A）→（aij=ai,j+1）∧（ai,j+1=””）空格下移F4：（aij=””）∧（ai+1,j∈A）→（aij=ai+1,j）∧（ai+1,j=””）（3）應(yīng)用全局擇優(yōu)搜索求解估計(jì)函數(shù)：fj

=gj

+hj代價(jià)函數(shù):gj

=gi+c(i,j)=gi

+1=dj。啟發(fā)函數(shù):hj定義為節(jié)點(diǎn)j的狀態(tài)Sj與目標(biāo)節(jié)點(diǎn)狀態(tài)Sg比較錯(cuò)位棋子的個(gè)數(shù)。圖3.23例3.8的全局擇優(yōu)搜索生成的搜索樹圖3.24例3.9的初始狀態(tài)與目標(biāo)狀態(tài)例3.9

應(yīng)用全局擇優(yōu)搜索求解三階梵塔問題。解：（1）狀態(tài)定義S=(x1,x2,x3)其中xn為柱?上的盤名序列。盤名序列遵守C>B>A。初態(tài)：S0=（CBA,Φ,Φ），終態(tài)：Sg=（Φ,Φ,CBA）（2）算符定義算符M（k，ń，m）表示盤k從柱n移至柱m。FK算符FK算符FK算符F1M(A,1,2)F7M(B,1,2)F13M(C,1,2)F2M(A,1,3)F8M(B,1,2)F14M(C,1,3)F3M(A,2,1)F9M(B,2,1)F15M(C,2,1)F4M(A,2,3)F10M(A,2,3)F16M(C,2,3)F5M(A,3,1)F11M(A,3,1)F17M(C,3,1)F6M(A,3,2)F12M(A,3,2)F18M(C,3,2)表3.2例3.9的算符集（3）應(yīng)用全局擇優(yōu)搜索求解代價(jià)函數(shù):gj=gi+c(i,j)=gi+1=dj。啟發(fā)函數(shù):hj

=aA+aB+aC=∑aK其中ak

為在當(dāng)前狀態(tài)Sj中，盤k移動(dòng)到目標(biāo)狀態(tài)Sg指定位置上至少需要移動(dòng)次數(shù)的估計(jì)。

0 若盤k在Sg指定的位置上，即

k∈x3，且在x3=CBA指定位置上ak=1若盤k在柱1或柱2上，即k∈x1或k∈x22若盤k在柱3上，且不在Sg指定位置上圖3.25例3.9的全局擇優(yōu)搜索生成的搜索樹3.2.4Ａ*算法及其特性1Ａ*算法A*算法:如果全局擇優(yōu)搜索算法的估價(jià)函數(shù)f滿足如下限制，則成為A*算法:f(x)=g(x)+h(x)①代價(jià)函數(shù)g(x)是對g*(x)的估計(jì)，g(x)＞0。g*(x)是從初始節(jié)點(diǎn)到節(jié)點(diǎn)x的最小代價(jià)。②啟發(fā)函數(shù)h(x)是h*(x)的下界，即對所有的x均有h(x)≤h*(x)。h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，若有多個(gè)目標(biāo)節(jié)點(diǎn)，則為其中最小的代價(jià)。h(x)≤h*(x)的限制保證A*算法能找到最優(yōu)解。2Ａ*算法的特性

(1)A*算法可納性對于可解狀態(tài)空間圖（即從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在）來說，如果一個(gè)搜索算法能在有限步內(nèi)終止，并且能找到最優(yōu)解，則稱該搜索算法是可納的。（2）A*算法的最優(yōu)性在滿足h(x)≤h*(x)的前提下，h(x)的值越大越好，搜索的效率越高。（3）h(x)的單調(diào)性限制單調(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).節(jié)點(diǎn)xi到目標(biāo)節(jié)點(diǎn)最優(yōu)費(fèi)用的估價(jià)不會(huì)超過從xi到其子節(jié)點(diǎn)xj的邊代價(jià)加上從xj到目標(biāo)節(jié)點(diǎn)最優(yōu)費(fèi)用的估價(jià)。3.3與∕或圖的搜索方法3.3.1與∕或圖的盲目搜索算法3.3.2與／或圖的啟發(fā)式搜索算法3.3.3博弈算法及應(yīng)用3.3.1與∕或圖的盲目搜索算法1可解標(biāo)示過程與不可解標(biāo)示過程由可解子節(jié)點(diǎn)來確定父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的回溯向上過程稱為可解標(biāo)示過程；由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的回溯向上過程稱為不可解標(biāo)示過程。2與∕或圖的寬度優(yōu)先搜索open表和closed表的節(jié)點(diǎn)域的定義：jSjFkand/ory/ni與∕或圖寬度優(yōu)先搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中。（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）把open表中尚未標(biāo)示的可解/不可解標(biāo)志的第一個(gè)節(jié)點(diǎn)i移出，放入closed表表尾。（4）若節(jié)點(diǎn)i可擴(kuò)展（即在算符集中找到可用算符），則用可用算符作用于節(jié)點(diǎn)i的問題表示Si，生成其子問題節(jié)點(diǎn)；否則，轉(zhuǎn)步驟（6）。若子節(jié)點(diǎn)j的問題表示Sj，既不在open表中又不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將節(jié)點(diǎn)j

放入open表的表尾，并記載節(jié)點(diǎn)j各域的值，轉(zhuǎn)步驟(5);否則，放棄節(jié)點(diǎn)j，轉(zhuǎn)步驟（2）。（5）若子節(jié)點(diǎn)j是終葉節(jié)點(diǎn)（即Sj是本原問題），則標(biāo)示節(jié)點(diǎn)j可解，并調(diào)用可解標(biāo)示過程。若可解標(biāo)示過程將初始節(jié)點(diǎn)標(biāo)示為可解，則算法成功終止；否則轉(zhuǎn)步驟（2）。（6）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則標(biāo)示節(jié)點(diǎn)i不可解，并調(diào)用不可解標(biāo)示過程。若不可解標(biāo)示過程將初始節(jié)點(diǎn)標(biāo)示為不可解，則問題無解，算法終止；否則，刪除節(jié)點(diǎn)i在open表和closed表中的所有后裔節(jié)點(diǎn)，轉(zhuǎn)步驟（2）。與∕或圖的深度優(yōu)先搜索open表和cloesd表的節(jié)點(diǎn)的域定義：jSjFkdjand/ory/ni

與∕或圖深度優(yōu)先搜索算法:

（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中，設(shè)置搜索最大深度dmax的值。（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）把open表中尚未標(biāo)示的可解/不可解標(biāo)志不可解的第一個(gè)節(jié)點(diǎn)i移出，放入closed表表尾。（4）若節(jié)點(diǎn)i的深度di

<dmax且可擴(kuò)展（即在算符集中找到可用算符），則用可用算符作用于節(jié)點(diǎn)i的問題表示Si，生成其子問題節(jié)點(diǎn)；否則，轉(zhuǎn)步驟（6）。若子節(jié)點(diǎn)j的問題表示Sj，既不在open表中，又不在closed表中，則節(jié)點(diǎn)j是一個(gè)新節(jié)點(diǎn)。將節(jié)點(diǎn)j放入open表的表尾，并記載節(jié)點(diǎn)j各域的值，轉(zhuǎn)步驟（5）；否則，放棄節(jié)點(diǎn)j，轉(zhuǎn)步驟（2）。（5）若子節(jié)點(diǎn)j是終葉節(jié)點(diǎn)（即Sj是本原問題），則標(biāo)示節(jié)點(diǎn)j可解，并調(diào)用可解標(biāo)示過程。若可解標(biāo)示過程將初始節(jié)點(diǎn)標(biāo)示為可解，則算法成功終止；否則轉(zhuǎn)步驟（2）。（6）若節(jié)點(diǎn)i不可擴(kuò)展（即在算符集中找不到可用算符），則標(biāo)示節(jié)點(diǎn)i不可解，并調(diào)用不可解標(biāo)示過程。若不可解標(biāo)示過程將初始節(jié)點(diǎn)標(biāo)示為不可解，則問題無解，算法終止；否則，刪除節(jié)點(diǎn)i在open表和closed表中的所有后裔節(jié)點(diǎn)，轉(zhuǎn)步驟（2）。3.3.2與／或圖的啟發(fā)式搜索算法１解樹的代價(jià)計(jì)算節(jié)點(diǎn)x代價(jià)的方法：

設(shè)c(x,y)表示節(jié)點(diǎn)x到其子節(jié)點(diǎn)y的算符代價(jià)，g(x)表示節(jié)點(diǎn)x的代價(jià)，

(1)如果x是終葉節(jié)點(diǎn)，則定義節(jié)點(diǎn)x的代價(jià)g(x)=0;

(2)如果x是“或”節(jié)點(diǎn)，y1,y2,…,yn是它的子節(jié)點(diǎn)，則節(jié)點(diǎn)x的代價(jià)為

(3)如果x是“與”節(jié)點(diǎn)，則節(jié)點(diǎn)x的代價(jià)有兩種計(jì)算方法。若按和代價(jià)法計(jì)算，則有h(x)=若按最大代價(jià)法計(jì)算，則有h(x)=

(4)如果x不可擴(kuò)展，且又不是終止節(jié)點(diǎn)，則定義

g(x)=∝。希望樹的定義(1)初始節(jié)點(diǎn)S0在希望樹T中。(2)如果節(jié)點(diǎn)x在希望樹T中，則一定有：1）如果x是具有子節(jié)點(diǎn)y1,y2,…,yn的“或”節(jié)點(diǎn)，則具有{c(x,yi)+h(yi)}值的那個(gè)子節(jié)點(diǎn)yi也應(yīng)在T中。2）如果x是“與”節(jié)點(diǎn)，則它的全部子節(jié)點(diǎn)都應(yīng)在T中。3與/或圖的啟發(fā)式搜索open表和cloesd表的節(jié)點(diǎn)的域定義：jSjFkand/ory/nhjPji

與∕或圖啟發(fā)式搜索算法:（1）初始化open表與closed表，把初始節(jié)點(diǎn)（序號1）放入open表中，并設(shè)初始節(jié)點(diǎn)的希望標(biāo)志P=1。（2）若open=（），則算法失敗終止；否則，轉(zhuǎn)步驟（3）。（3）修改以初始節(jié)點(diǎn)為根的希望樹，置希望樹上的節(jié)點(diǎn)的P=1；其他節(jié)點(diǎn)的P=0。（4）把open表中尚未標(biāo)示可解/不可解標(biāo)志且希望標(biāo)志P=1的第一個(gè)節(jié)點(diǎn)i移出，放入closed表表尾。（5）若節(jié)點(diǎn)i可擴(kuò)展（即在算符集中找到可用算符），則用可用算符作用于節(jié)點(diǎn)I的問題表示Si，生成其子問題節(jié)點(diǎn)；否則轉(zhuǎn)步驟（7）。