第3章 圖搜索及問題求解

主講：李輝Email：lihui@第3章

圖搜索與問題求解第3章圖搜索與問題求解3.5博弈樹搜索3.1狀態(tài)圖搜索3.2狀態(tài)圖搜索問題求解3.3與或圖搜索3.4與或圖搜索問題求解主要內(nèi)容3.1狀態(tài)圖搜索-搜索與求解搜索是人工智能技術(shù)中進(jìn)行問題求解的基本技術(shù)，不管是符號智能還是計算智能，最終往往都?xì)w結(jié)為某種搜索，用某種搜索算法去實現(xiàn)。圖搜索模擬的是人腦分析問題、解決問題的過程，是基于領(lǐng)域知識的問題求解技術(shù)。計算智能是借鑒或模擬某些自然現(xiàn)象或生命現(xiàn)象而實現(xiàn)的搜索和問題求解技術(shù)。圖搜索技術(shù)是人工智能中的核心技術(shù)之一。

3.1.1狀態(tài)圖例3.1走迷宮走迷宮問題就是從該有向圖的初始節(jié)點出發(fā)，尋找目標(biāo)節(jié)點的問題，或者是尋找通向目標(biāo)節(jié)點的路徑問題。3.1.1狀態(tài)圖例3.2八數(shù)碼難題(重排九宮問題)

2831476512384765初始棋局目標(biāo)棋局以上兩個問題抽象來看，都是某個有向圖中尋找目標(biāo)或路徑的問題，在人工智能技術(shù)中，把這種描述問題的有向圖稱為狀態(tài)空間圖，簡稱狀態(tài)圖。棋局作為節(jié)點，相鄰節(jié)點通過移動數(shù)碼一個一個產(chǎn)生出來，所有節(jié)點由它們的相鄰關(guān)系連成一個有向圖。3.1.2狀態(tài)圖搜索搜索：從初始節(jié)點出發(fā)，沿著與之相連的邊試探地前進(jìn)，尋找目標(biāo)節(jié)點的過程。搜索過程中經(jīng)過的節(jié)點和邊，按原圖的連接關(guān)系，便會構(gòu)成一個樹型的有向圖，這種樹型有向圖稱為搜索樹。搜索進(jìn)行中，搜索樹會不斷增長，直到當(dāng)搜索樹中出現(xiàn)目標(biāo)節(jié)點，搜索便停止。這時從搜索樹中就可很容易地找出從初始節(jié)點到目標(biāo)節(jié)點的路徑（解）來。3.1.2狀態(tài)圖搜索1搜索方式樹式搜索

在搜索過程中記錄所經(jīng)過的所有節(jié)點和邊。樹式搜索所記錄的軌跡始終是一棵樹，這棵樹也就是搜索過程中所產(chǎn)生的搜索樹。線式搜索在搜索過程中只記錄那些當(dāng)前認(rèn)為在所找路徑上的節(jié)點和邊。不回溯線式搜索可回溯線式搜索3.1.2狀態(tài)圖搜索2搜索策略盲目搜索無向?qū)У乃阉鳎瑯涫矫つ克阉骶褪歉F舉搜索，不回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜索也是窮舉式搜索。啟發(fā)式搜索是利用“啟發(fā)性信息”引導(dǎo)的搜索策略?！皢l(fā)性信息”就是與問題有關(guān)的有利于盡快找到問題解的信息或知識。啟發(fā)式搜索分為不同的策略，如全局擇優(yōu)，局部擇優(yōu)，最佳圖搜索。按擴展順序不同分為廣度優(yōu)先和深度優(yōu)先。3.1.2狀態(tài)圖搜索3

搜索算法搜索的目的是為了尋找初始節(jié)點到目標(biāo)節(jié)點的路徑，搜索過程中就得隨時記錄搜索軌跡。ClOSED表動態(tài)數(shù)據(jù)結(jié)構(gòu)來記錄考察過的節(jié)點。OPEN表的動態(tài)數(shù)據(jù)結(jié)構(gòu)來專門登記當(dāng)前待考查的節(jié)點。節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號OPEN表CLOSED表3.1.2狀態(tài)圖搜索樹式搜索算法

步1

把初始節(jié)點S0放入OPEN表中。

步2

若OPEN表為空，則搜索失敗，退出。

步3

取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以順序編號n；

步4

若目標(biāo)節(jié)點Sg=N，成功退出。

步5

若N不可擴展，轉(zhuǎn)步2。

步6

擴展N，生成一組節(jié)點，對這組子節(jié)點作如下處理：3.1.2狀態(tài)圖搜索（1）刪除N的先輩節(jié)點（如果有的話）。（2）對已存在于OPEN表中的節(jié)點（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑“短”，則修改這些節(jié)點在OPEN表中的原返回指針，使其沿新路徑返回。（3）對已存在于CLOSED表的節(jié)點，作與（2）同樣的處理，并且將其移出CLOSED表，放入OPEN表中重新擴展。（4）對其余子節(jié)點配上指向N的返回指針后放入OPEN表中某處，或?qū)PEN表進(jìn)行重新排序，轉(zhuǎn)步2。3.1.2狀態(tài)圖搜索圖

3-5修改返回指針示例

樹式算法的幾點說明返回指針指的是父節(jié)點在CLOSED表中的編號。步6中修改指針的原因是返回初始節(jié)點的路徑有兩條，要選擇“短”的那條路徑。這里路徑長短以節(jié)點數(shù)來衡量，在后面將會看到以代價來衡量。按代價衡量修改返回指針的同時還要修改相應(yīng)的代價值。3.1.2狀態(tài)圖搜索樹式搜索例對于已存在于OPEN表中的節(jié)點（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點在OPEN表中的原返回指針，使其沿原路徑返回。Path1Path2S0mnP先擴展后擴展P在n之前已是某一節(jié)點m的后繼如圖所示：說明從S0→P至少有兩條路，這時有兩種情況：f（Path2）<f（Path1），當(dāng)前路徑較好，要修改P的指針，使其指向n，即搜索之后的最佳路徑。否則，原路徑好。3.1.2狀態(tài)圖搜索對已存在于CLOSED表的節(jié)點，作與（2）同樣的處理，并將其移出CLOSED表，放入OPEN表中重新擴展。S0過去生成P的路徑現(xiàn)在生成P的路徑過去對Ps的最優(yōu)路徑PsPmnka.P在n之前已是某一節(jié)點m的后繼，所以需要做如同（2）同樣的處理，如圖右部所示。b.P在Closed表中，說明P的后繼也在n之前已經(jīng)生成，稱為Ps。對Ps而言同樣可能由于n→P這一路徑的加入，又必須比較多條路徑之后而取代價小的一條，如圖左部所示。3.1.2狀態(tài)圖搜索例：設(shè)當(dāng)前搜索圖和搜索樹如圖所示S0nPmPs’PsS0nPmPs’PsFF3.1.2狀態(tài)圖搜索若啟發(fā)函數(shù)f(n)為從S0到節(jié)點n的最短路徑的長度，用邊的數(shù)目來考察，當(dāng)前擴展的節(jié)點是搜索圖中的n,P是n的后繼S0nPmPs’PsnPPs’PsS0mFF3.1.2狀態(tài)圖搜索不回溯線式搜索算法

步1

把初始節(jié)點S0放入CLOSED表中；

步2

令N＝S0

；

步3

若N是目標(biāo)節(jié)點，則搜索成功，結(jié)束。

步4若N不可擴展，則搜索失敗，退出。

步5

擴展N，選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點N1放入CLOSED表中，令N＝N1，轉(zhuǎn)步3。3.1.2狀態(tài)圖搜索可回溯的線式搜索步1把初始節(jié)點S0放入CLOSED表中；步2令N＝S0

；步3若N是目標(biāo)節(jié)點，則搜索成功，結(jié)束。步4若N不可擴展，則移出CLOSED表中的末端節(jié)點Ne

，若Ne＝S0，則搜索失敗，退出。否則以CLOSED表新的末端節(jié)點Ne作為

N，即令N＝Ne，轉(zhuǎn)步4；步5擴展N，選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點N1放入

CLOSED表中，令N＝N1

，轉(zhuǎn)步3。3.1.3窮舉式搜索廣度優(yōu)先搜索策略始終在同一級節(jié)點中考查，當(dāng)同一級節(jié)點考查完了之后，才考查下一級節(jié)點。搜索樹自頂向下一層一層逐漸生成。算法ABCDEFGHIJKLMNOPQRSTU廣度優(yōu)先搜索OPENCLOSEDOPENCLOSEDABCDEFGHIJKLMNOPQRSTUA廣度優(yōu)先搜索22OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDA廣度優(yōu)先搜索23OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEF廣度優(yōu)先搜索24OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGH廣度優(yōu)先搜索25OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGHDIJ廣度優(yōu)先搜索26OPENCLOSEDABCDEFGHIJKLMNOPQRSTUABCDABEFCGHDIJEKL廣度優(yōu)先搜索3.1.3窮舉式搜索廣度優(yōu)先搜索的特點廣度優(yōu)先中OPEN表是一個隊列，CLOSED表是一個順序表，表中各節(jié)點按順序編號，正被考察的節(jié)點在表中編號最大。廣度優(yōu)先策略是完備的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。缺點搜索效率低。3.1.3窮舉式搜索八數(shù)碼問題28314765初始狀態(tài)81324765目標(biāo)狀態(tài)3.1.3窮舉式搜索28314765123184765923184765828143765102837146578321476562831457611283147652231847653283147654283164751228316475138321476514283714651523418765161238476517281437651828314576192836417520283167542183214765222831647558132476523八數(shù)碼廣度優(yōu)先搜索3.1.3窮舉式搜索深度優(yōu)先搜索搜索策略

在搜索樹的每一層始終先擴展一個子節(jié)點，不斷地向縱深前進(jìn)，直到不能再前進(jìn)，才從當(dāng)前節(jié)點返回到上一級節(jié)點，從另一方向繼續(xù)前進(jìn)。算法

ABCDEFGHIJKLMNOPQRSTU深度優(yōu)先搜索OPENCLOSEDABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA深度優(yōu)先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDABCD深度優(yōu)先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDADCBIJ深度優(yōu)先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDADCBIR深度優(yōu)先搜索J3.1.3窮舉式搜索深度優(yōu)先搜索的特點OPEN表為一個堆棧。深度優(yōu)先又稱縱向搜索。一般不能保證找到最優(yōu)解。當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制，即有界深度優(yōu)先搜索。3.1.3窮舉式搜索2318476528314765283147652831647528314765128316475328316754428316475228316754281637545…八數(shù)碼深度優(yōu)先搜索3.1.4啟發(fā)式搜索啟發(fā)式搜索的目的利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度。啟發(fā)性信息的強弱

強：降低搜索的工作量，但可能導(dǎo)致找不到最優(yōu)解。

弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。3.1.4啟發(fā)式搜索啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計搜索樹節(jié)點x與目標(biāo)節(jié)點接近程度的一種函數(shù)，通常記為h（x）。定義啟發(fā)函數(shù)的參考思路一個節(jié)點到目標(biāo)節(jié)點的某種距離或差異的量度。一個節(jié)點處在最佳路徑上的概率根據(jù)主觀經(jīng)驗的主觀打分等。啟發(fā)式搜索算法啟發(fā)式搜索要用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點的擴展順序。3.1.4啟發(fā)式搜索全局擇優(yōu)搜索全局擇優(yōu)搜索就是利用啟發(fā)函數(shù)制導(dǎo)的一種啟發(fā)式搜索方法。該方法亦稱為最好優(yōu)先搜索法?；舅枷耄涸贠PEN表中保留所有已生成而未考察的節(jié)點，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M(jìn)行估價，從中選出最優(yōu)節(jié)點進(jìn)行擴展，而不管這個節(jié)點出現(xiàn)在搜索樹的什么地方。3.1.4啟發(fā)式搜索全局擇優(yōu)搜索算法

步1

把初始節(jié)點S0放入OPEN表中，計算h（S0

）；步2

若OPEN表為空，則搜索失敗，退出。步3

移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以序號n；步4

若目標(biāo)節(jié)點Sg＝N，則搜索成功結(jié)束。步5

若N不可擴展，則轉(zhuǎn)步2。步6

擴展N，計算每個子節(jié)點x的函數(shù)值h（x），并將所有子節(jié)點配以指向N的返回指針后放入OPEN表中，再對OPEN表中所有子節(jié)點按其函數(shù)值的大小以升序排列，轉(zhuǎn)步2。A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRST全局擇優(yōu)算法OPENCLOSEDA-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDA-5全局擇優(yōu)算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6全局擇優(yōu)算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4E-5F-5D-5全局擇優(yōu)算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5H-3G-4全局擇優(yōu)算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5O-2G-4H-3H-3P-3全局擇優(yōu)算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5F-5O-2G-4H-3H-3P-3全局擇優(yōu)算法3.1.4啟發(fā)式搜索-全局擇優(yōu)搜索算法啟發(fā)函數(shù)h(x)為節(jié)點x與目標(biāo)格局相比數(shù)碼不同的位置個數(shù)。從圖看出解為：S0，S1，S2，S3，

Sg。3.1.4啟發(fā)式搜索-局部擇優(yōu)搜索算法基本思想是當(dāng)每一個節(jié)點被擴展后，按h(x)對每一個子節(jié)點計算啟發(fā)值，并選擇最小者作為下一個要考察的節(jié)點，由于每次都只是在子節(jié)點的范圍內(nèi)選擇下一個要考察的節(jié)點，范圍比較狹窄，所以稱為局部擇優(yōu)搜索。步6

擴展N，計算N每個子節(jié)點x的函數(shù)值h（x），并將N的子節(jié)點按估計值升序排列放入OPEN表的首部，為每個子節(jié)點配置指向節(jié)點N的指針，轉(zhuǎn)步2。3.1.5加權(quán)狀態(tài)圖搜索例3.6交通圖A城是出發(fā)地，E是目的地，數(shù)字表示兩城之間交通費用。求A到E的最小費用的旅行路線。ADCEB464332邊上附有數(shù)值的狀態(tài)圖稱為加權(quán)狀態(tài)圖或賦權(quán)狀態(tài)圖，這種數(shù)值稱為權(quán)值。3.1.5加權(quán)狀態(tài)圖搜索加權(quán)狀態(tài)圖的搜索加權(quán)狀態(tài)圖的搜索與權(quán)值有關(guān)，并且要用權(quán)值來導(dǎo)航。具體來講，加權(quán)狀態(tài)圖的搜索算法，要在一般狀態(tài)圖搜索算法基礎(chǔ)上再增加權(quán)值的計算與傳播過程，并且要由權(quán)值來確定節(jié)點的擴展順序。代價的計算

g（x）表示從初始節(jié)點S0到節(jié)點x的代價。

c（xi，xj）表示父節(jié)點xi到子節(jié)點xj的代價

g（xj）＝g（xi）＋c（xi，xj）

g（x0）＝03.1.5加權(quán)狀態(tài)圖搜索加權(quán)狀態(tài)圖轉(zhuǎn)換為代價樹搜索從初始節(jié)點出發(fā)，先把每一個與初始節(jié)點相鄰的節(jié)點作為該節(jié)點的子節(jié)點。然后對其他節(jié)點依次類推，但對其他節(jié)點x，不能將其父節(jié)點及祖先再作為x的子節(jié)點。ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.1.5加權(quán)狀態(tài)圖搜索分支界限法其基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點進(jìn)行考察，而不管這個節(jié)點在搜索樹的什么位置上。與全局擇優(yōu)法的區(qū)別選取擴展節(jié)點標(biāo)準(zhǔn)計算方法分支界限法代價值g（x）g（x）與節(jié)點所處的位置有關(guān)，與邊也有關(guān)系，從初始節(jié)點S0計算而來。全局擇優(yōu)法啟發(fā)函數(shù)值h（x）h（x）與節(jié)點有關(guān)，與邊可能有關(guān)或無關(guān)，從目標(biāo)節(jié)點方向計算而來。3.1.5加權(quán)狀態(tài)圖搜索最近擇優(yōu)法（瞎子爬山法）基本思想：每次僅考察N的子節(jié)點的g（x），選取N的子節(jié)點中代價最小的子節(jié)點進(jìn)行擴展。最近擇優(yōu)法與局部擇優(yōu)法的區(qū)別：選取擴展節(jié)點標(biāo)準(zhǔn)計算方法最近擇優(yōu)法代價值g（x）g（x）與節(jié)點所處的位置有關(guān)，與邊也有關(guān)系，從初始節(jié)點S0計算而來。局部擇優(yōu)法啟發(fā)函數(shù)h（x）h（x）與節(jié)點有關(guān)，與邊可能有關(guān)或無關(guān)，從目標(biāo)節(jié)點方向計算而來。內(nèi)容回顧：樹式搜索策略比較全局局部深度d(x)寬度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)值h(x)全局擇優(yōu)搜索局部擇優(yōu)搜索代價值g(x)分支界限法瞎子爬山法范圍標(biāo)準(zhǔn)S0Sg23ab4615cdgfhijk5f543789h（x），有利于搜索縱向發(fā)展，提高搜索效率，但影響完備性。g（x），有利于搜索橫向發(fā)展，提高完備性，但影響搜索效率。窮舉式搜索啟發(fā)式搜索加權(quán)狀態(tài)圖搜索3.1.6A算法估價函數(shù)

將啟發(fā)函數(shù)與代價函數(shù)相結(jié)合，為了防止在單獨利用啟發(fā)函數(shù)的時候誤入歧途。

f（x）＝g（x）＋h（x）f（x）是初始節(jié)點S0到達(dá)節(jié)點x處已付出的代價與節(jié)點x到達(dá)目標(biāo)節(jié)點Sg的接近程度估計值總和。是g（x）與h（x）的折中。3.2狀態(tài)圖搜索問題求解3.2.1問題的狀態(tài)圖表示

1.狀態(tài)狀態(tài)就是問題在任一確定時刻的狀況,它表征了問題特征和結(jié)構(gòu)等。狀態(tài)在狀態(tài)圖中表示為節(jié)點。狀態(tài)一般用一組數(shù)據(jù)表示。在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對象等表示。

2.狀態(tài)轉(zhuǎn)換規(guī)則（操作operator）引起狀態(tài)中某些分量發(fā)生改變，從而使一個具體狀態(tài)變化到另一個具體狀態(tài)的作用。描述了狀態(tài)之間的關(guān)系。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。

3.2.1問題的狀態(tài)圖表示狀態(tài)空間（StateSpace）問題的狀態(tài)空間是一個表示該問題全部的可能狀態(tài)及相互關(guān)系的圖。狀態(tài)空間一般用賦值有向圖表示，記為：（S，F(xiàn)，G）S：問題的可能有的初始狀態(tài)的集合；F：操作的集合；G：目標(biāo)狀態(tài)的集合。3.2.1問題的狀態(tài)圖表示例3.7迷宮問題的狀態(tài)圖表示。S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝G：Sg迷宮問題規(guī)則集描述了圖中所有節(jié)點和邊。類似于這樣羅列出全部節(jié)點和邊的狀態(tài)圖稱為顯式狀態(tài)圖，或者說狀態(tài)圖的顯式表示。3.2.1問題的狀態(tài)圖表示補充例1三枚錢幣，能否從下面狀態(tài)翻動三次后出現(xiàn)全正或全反狀態(tài)。反正反正正正反反反初始狀態(tài)θs目標(biāo)狀態(tài)集合{θ0,θ7}3.2.1問題的狀態(tài)圖表示引入一個三元組(q0,q1,q2)來描述總狀態(tài)，錢幣正面為0，反面為1，全部可能的狀態(tài)為：

Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻動錢幣的操作抽象為改變上述狀態(tài)的算子，即F＝{a,b,c}

a:把錢幣q0翻轉(zhuǎn)一次

b:把錢幣q1翻轉(zhuǎn)一次

c:把錢幣q2翻轉(zhuǎn)一次問題的狀態(tài)空間為<{Q5},{Q0Q7},{a,b,c}>3.2.1問題的狀態(tài)圖表示狀態(tài)空間圖（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，1）（1，1，1）acabacabcbbc3.2.1問題的狀態(tài)圖表示

例3.9

二階梵塔問題一號桿有A、B兩個金盤，A小于B。要求將AB移至三號桿，每次只可移動一個盤子，任何時刻B不能在A上。用二元組（SA，SB）表示狀態(tài)，SA表示A所在桿號，SB表示B所在桿號，全部狀態(tài)如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）3.2.1問題的狀態(tài)圖表示AB123S0：（1，1）123S1：（1，2）123S2：（1，3）AA123S5：（2，3）123S4：（2，2）123S3：（2，1）123S8：（3，3）123S7：（3，2）123S6：（3，1）AAAAABABBBBB3.2.1問題的狀態(tài)圖表示轉(zhuǎn)換規(guī)則：A（i，j）表示金盤A從第i號桿移到j(luò)號桿

B（i，j）表示金盤B從第i號桿移到j(luò)號桿

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）初始狀態(tài)（1，1），目標(biāo)狀態(tài)（3，3）梵塔問題用狀態(tài)圖表示為：

<{(1,1)},{A(1,2),…，B(3,2)},{(3,3)}>3.2.1問題的狀態(tài)圖表示1,12,13,12,33,31,33,21,22,2A(1,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)3.2.1問題的狀態(tài)圖表示例3.8重排九宮問題（八數(shù)碼難題）X1X2X3X8X0X4X7X6X5將棋局用向量A＝(X0，X1，

X2，

X3，

X4，

X5，

X6，

X7，

X8)表示，其中Xi為變量，值表示方格Xi內(nèi)的數(shù)字。初始狀態(tài)S0＝（0，2，8，3，4，5，6，7，1）目標(biāo)狀態(tài)Sg

＝（0，1，2，3，4，5，6，7，8）數(shù)碼的移動規(guī)則就是該問題的狀態(tài)變化規(guī)則。經(jīng)分析，該問題共有24條規(guī)則，分為9組。2831476512384765初始棋局目標(biāo)棋局3.2.1問題的狀態(tài)圖表示0組規(guī)則

r1(X0=0

)(X2=n

)X0=nX2=0；

r2(X0=0

)(X4=n

)X0=nX4=0；

r3(X0=0

)(X6=n

)X0=nX6=0；

r4(X0=0

)(X8=n

)X0=nX8=0；1組規(guī)則

r5(X1=0

)(X2=n

)X1=nX2=0；

r6(X1=0

)(X8=n

)X1=nX8=0；8組規(guī)則:

r22(X8=0

)(X1=n

)X8=nX1=0；

r23(X8=0

)(X0=n

)X8=nX0=0；

r24(X8=0

)(X7=n

)X8=nX7=0；X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X53.2.1問題的狀態(tài)圖表示八數(shù)碼的狀態(tài)圖可表示為（{S0},{r1,r2,…,r24},{Sg}）八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點和目標(biāo)節(jié)點，其余節(jié)點需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。3.3與或圖搜索例3.15證明四邊形全等。分析：連接BD，B′D′，原來問題可以分解為兩個子問題：

Q1：證明ΔABC≌ΔA′B′C′

Q2：證明ΔBCD≌ΔB′C′D′原來問題可以分為兩個子問題解決。ABDCA′B′D′C′3.3.1與或圖問題Q1還可以再被分解為：

Q11

：證明AB＝A′B′

Q12

：證明AD＝A′D′

Q13

：證明∠A＝∠A′或

Q11′：證明AB＝A′B′

Q12′：證明AD＝A′D′

Q13′：證明BD＝B′D′問題Q2還可以再被分解為：

Q21

：證明BC＝B′C′

Q22

：證明CD＝C′D′

Q23

：證明∠C＝∠C′或

Q21′：證明BC＝B′C′

Q22′：證明CD＝C′D′

Q23′：證明BD＝B′D′′3.3.1與或圖將原問題用圖的形式表示如下：QQ1Q2Q11Q12Q13Q11'Q12'Q13'Q21Q22Q23Q21'Q22'Q23'弧線表示所連邊為“與”的關(guān)系不帶弧線的邊為或關(guān)系問題的解3.3.1與或圖與或圖的幾個概念直接可解的問題稱為本原問題。本原問題對應(yīng)的節(jié)點稱為終止節(jié)點。無子節(jié)點的節(jié)點稱為端節(jié)點。子節(jié)點為與關(guān)系，則該節(jié)點為與節(jié)點。子節(jié)點為或關(guān)系，則該節(jié)點為或節(jié)點。3.3.2與或圖搜索1.搜索方式,解圖(樹)與或圖搜索也分為樹式和“線”式兩種類型。與或圖搜索解圖(樹),不只是尋找目標(biāo)節(jié)點,而是邊擴展節(jié)點邊進(jìn)行邏輯判斷,以確定初始節(jié)點是否可解。一旦能夠確定初始節(jié)點的可解性,則搜索停止。根據(jù)返回指針便可從搜索樹中得到一個解圖(樹)。解圖(樹)實際上是由可解節(jié)點形成的一個子圖(樹),這個子圖(樹)的根為初始節(jié)點,葉為終止節(jié)點,且這個子圖(樹)還一定是與圖(樹)。

3.3.2與或圖搜索2.可解性判別

怎樣判斷一個節(jié)點的可解性呢？下面給出判別準(zhǔn)則。

(1)一個節(jié)點是可解,則節(jié)點須滿足下列條件之一: ①終止節(jié)點是可解節(jié)點。

②一個與節(jié)點可解,當(dāng)且僅當(dāng)其子節(jié)點全都可解。

③一個或節(jié)點可解,只要其子節(jié)點至少有一個可解。

(2)一個節(jié)點是不可解,則節(jié)點須滿足下列條件之一: ①非終止節(jié)點的端節(jié)點是不可解節(jié)點。

②一個與節(jié)點不可解,只要其子節(jié)點至少有一個不可解。

③

一個或節(jié)點不可解,當(dāng)且僅當(dāng)其子節(jié)點全都不可解。

3.3.2與或圖搜索4.搜索算法

與或樹的樹式搜索過程可概括為以下步驟：

步1把初始節(jié)點Qo放入OPEN表。步2移出OPEN表的第一個節(jié)點N放入CLOSED表,并冠以序號n。

步3若節(jié)點N可擴展,則做下列工作：

(1)擴展N,將其子節(jié)點配上指向父節(jié)點的指針后放入OPEN表。

(2)考察這些子節(jié)點中是否有終止節(jié)點。若有,則標(biāo)記它們?yōu)榭山夤?jié)點,并將它們也放入CLOSED表,然后由它們的可解反向推斷其先輩節(jié)點的可解性,并對其中的可解節(jié)點進(jìn)行標(biāo)記。如果初始節(jié)點也被標(biāo)記為可解節(jié)點,則搜索成功,結(jié)束。

(3)刪去OPEN表中那些具有可解先輩的節(jié)點(因為其先輩節(jié)點已經(jīng)可解,故已無再考察該節(jié)點的必要),轉(zhuǎn)步2。

3.3.2與或圖搜索步4若N不可擴展,則做下列工作：

(1)標(biāo)記N為不可解節(jié)點,然后由它的不可解反向推斷其先輩節(jié)點的可解性,并對其中的不可解節(jié)點進(jìn)行標(biāo)記。如果初始節(jié)點So也被標(biāo)記為不可解節(jié)點,則搜索失敗,退出。

(2)刪去OPEN表中那些具有不可解先輩的節(jié)點(因為其先輩節(jié)點已不可解,故已無再考察這些節(jié)點的必要),轉(zhuǎn)步2。

3.3.2與或圖搜索

例3.16

設(shè)有與或樹如圖3-15所示,其中1號節(jié)點為初始節(jié)點,t1、t2、t3、t4均為終止節(jié)點,A和B是不可解的端節(jié)點。采用廣度(優(yōu)先)搜索策略,搜索過程如下：

(1)擴展1號節(jié)點,得2號和3號節(jié)點,依次放入OPEN表尾部。由于這兩個節(jié)點都非終止節(jié)點,所以接著擴展2號節(jié)點。此時OPEN表中只有3號節(jié)點。

(2)2號節(jié)點擴展后,得4號節(jié)點和t1節(jié)點。此時OPEN表中依次有3號、4號和t1節(jié)點。由于t1是終止節(jié)點,故標(biāo)記它為可解節(jié)點,并將它放入CLOSED表,再判斷其先輩節(jié)點的可解性,但t1的父節(jié)點2是一個與節(jié)點,故僅由t1的可解還不能確定2號節(jié)點可解。所以,就繼續(xù)搜索。3.3.2與或圖搜索(3)擴展3號節(jié)點,得5號節(jié)點和B節(jié)點。兩者均非終止節(jié)點,所以繼續(xù)擴展4號節(jié)點。

(4)4號節(jié)點擴展后得節(jié)點A和t2。t2是終止節(jié)點,標(biāo)記為可解節(jié)點,放入CLOSED表。這時其先輩節(jié)點4和2也為可解節(jié)點,但1號節(jié)點還不能確定。這時從OPEN表中刪去節(jié)點A,因為其父節(jié)點4已經(jīng)可解。

(５)擴展5號節(jié)點得t3和t4。由于t3和t4都為終止節(jié)點(放入CLOSED表),故可推得節(jié)點5、3、1均為可解節(jié)點。搜索成功,結(jié)束。這時,由CLOSED表便得到由節(jié)點1、2、3、4、5和t1、t2、t3、t4構(gòu)成的解樹，如圖3-15中的粗線所示。

3.3.3啟發(fā)式與或樹搜索3.3.3啟發(fā)式與或樹搜索廣度優(yōu)先搜索及深度優(yōu)先搜索都是盲目搜索,其共同點是：

(1)搜索從初始節(jié)點開始,先自上而下地進(jìn)行搜索,尋找終止節(jié)點及端節(jié)點,然后再自下而上地進(jìn)行可解性標(biāo)記,一旦初始節(jié)點被標(biāo)記為可解節(jié)點或不可解節(jié)點,搜索就不再繼續(xù)進(jìn)行。

(2)搜索都是按確定路線進(jìn)行的,當(dāng)要選擇一個節(jié)點進(jìn)行擴展時,只是根據(jù)節(jié)點在與或樹中所處的位置,而沒有考慮要付出的代價,因而求得的解樹不一定是代價最小的解樹,即不一定是最優(yōu)解樹

。

為了求得最優(yōu)解樹，要在每次擴展節(jié)點時計算擴展該節(jié)點要付出的代價，并選擇代價最小的節(jié)點進(jìn)行擴展。像這樣根據(jù)代價決定搜索路線的方法稱為與或樹的有序搜索，是一種重要的啟發(fā)式搜索策略。3.3.3啟發(fā)式與或樹搜索

1.解樹的代價解樹的代價就是樹根的代價。樹根的代價是從樹葉開始自下而上逐層計算而求得的。而解樹的根對應(yīng)的是初始節(jié)點Qo。這就是說,在與或樹的搜索過程中,代價的計算方向與搜索樹的生長方向相反。這一點是與狀態(tài)圖不同的。具體來講,有下面的計算方法：設(shè)g(x)表示節(jié)點x的代價,c(x,y)表示節(jié)點x到其子節(jié)點y的代價(即邊xy的代價),則

(1)若x是終止節(jié)點,g(x)＝0。3.3.3啟發(fā)式與或樹搜索

(2)若x是或節(jié)點, 。其中y1,y2,…,yn是x的子節(jié)點。

(3)若x是與節(jié)點x,則有兩種計算公式。①和代價法： 。②最大代價法： 。其中y1,y2,…,yn是x的子節(jié)點。

(4)對非終止的端節(jié)點x,g(x)＝∞。

例3.17

如圖3-16所示的與或樹,其中包括兩棵解樹,一棵解樹由Qo,A,t1和t2組成；另一棵解樹由Qo,B,D,G,t4和t5組成。在此與或樹中,t1,t2,t3,t4,t5為終止節(jié)點；E,F是非終止的端節(jié)點,其代價均為∞；邊上的數(shù)字是該邊的代價。由右邊的解樹可得：按和代價：g(A)=11,g(Qo)=13

按最大代價：g(A)=6,g(Qo)=8由左邊的解樹可得：按和代價：g(G)=3,g(D)=4,g(B)=6,g(Qo)=8

按最大代價：g(G)=2,g(D)=3,g(B)=5,g(Qo)=73.3.3啟發(fā)式與或樹搜索課堂練習(xí)-習(xí)題三.12

12.設(shè)有如圖3-24所示的一棵與或樹，請指出解樹；并分別按和代價及最大代價求解樹代價；然后，指出最優(yōu)解樹。

一棵解樹由S0,A,D,t1,t2,t3組成；另一棵解樹由S0,B,E,t4,t5組成；左邊解樹：

按和代價：g(D)=4,g(A)=7,g(S0)=12

按最大代價：g(D)=2,g(A)=5,g(S0)=10右邊解樹：

按和代價：g(E)=2,g(B)=11,g(S0)=18

按最大代價：g(E)=2,g(B)=7,g(S0)=14按和代價計算，左邊的解樹為最優(yōu)解樹，按最大代價計算，仍是左邊的解樹為最優(yōu)解樹。因此，左邊的解樹為最優(yōu)解樹。3.3.3啟發(fā)式與或樹搜索有序搜索的目的是求出最優(yōu)解樹,即代價最小的解樹。這就要求搜索過程中任一時刻求出的部分解樹其代價都應(yīng)是最小的。為此,每次選擇欲擴展的節(jié)點時都應(yīng)挑選有希望成為最優(yōu)解樹一部分的節(jié)點進(jìn)行擴展。由于這些節(jié)點及其先輩節(jié)點(包括初始節(jié)點So)所構(gòu)成的與或樹有可能成為最優(yōu)解樹的一部分,因此稱它為“希望樹”。下面給出希望樹的定義：

(1)初始節(jié)點Qo在希望樹T中。

(2)如果節(jié)點x在希望樹T中,則一定有：①如果x是具有子節(jié)點y1,y2,…,yn的“或”節(jié)點,則具有值的那個子節(jié)點yi也應(yīng)在T中。②如果x是“與”節(jié)點,則它的全部子節(jié)點都應(yīng)在T中。3.3.3啟發(fā)式與或樹搜索

3.與或樹的有序搜索過程與或樹的有序搜索過程是一個不斷選擇、修正希望樹的過程。如果問題有解,則經(jīng)有序搜索將找到最優(yōu)解樹。其搜索過程如下：步1把初始節(jié)點Qo放入OPEN表中。步2求出希望樹T,即根據(jù)當(dāng)前搜索樹中節(jié)點的代價g求出以Qo為根的希望樹T。步3依次把OPEN表中T的端節(jié)點N選出放入CLOSED表中。3.3.3啟發(fā)式與或樹搜索步4如果節(jié)點N是終止節(jié)點,則做下列工作：

(1)標(biāo)示N為可解節(jié)點。

(2)對T應(yīng)用可解標(biāo)記過程,把N的先輩節(jié)點中的可解節(jié)點都標(biāo)記為可解節(jié)點。

(3)若初始節(jié)點Qo能被標(biāo)記為可解節(jié)點,則T就是最優(yōu)解樹,成功退出。

(4)否則,從OPEN表中刪去具有可解先輩的所有節(jié)點。步5如果節(jié)點N不是終止節(jié)點,且它不可擴展,則做下列工作：

(1)標(biāo)示N為不可解節(jié)點。

(2)對T應(yīng)用不可解標(biāo)記過程,把N的先輩節(jié)點中的不可解節(jié)點都標(biāo)記為不可解節(jié)點。

(3)若初始節(jié)點Qo也被標(biāo)記為不可解節(jié)點,則失敗退出。

(4)否則,從OPEN表中刪去具有不可解先輩的所有節(jié)點。步6如果節(jié)點N不是終止節(jié)點,但它可擴展,則可做下列工作：

(1)擴展節(jié)點N,產(chǎn)生N的所有子節(jié)點。

(2)把這些子節(jié)點都放入OPEN表中,并為每一個子節(jié)點配置指向父節(jié)點(節(jié)點N)的指針。

(3)計算這些子節(jié)點的g值及其先輩節(jié)點的g值。步7轉(zhuǎn)步2。3.3.3啟發(fā)式與或樹搜索

例3.18

下面我們舉例說明上述搜索過程。