1、LOGO主講：李 輝Email：第第3 3章章圖搜索與問題求解圖搜索與問題求解第第3章章 圖搜索與問題求解圖搜索與問題求解3.5 3.5 博弈樹搜索博弈樹搜索3.1 3.1 狀態圖搜索狀態圖搜索3.2 3.2 狀態圖搜索問題求解狀態圖搜索問題求解3.3 3.3 與或圖搜索與或圖搜索3.4 3.4 與或圖搜索問題求解與或圖搜索問題求解主要內容主要內容3.1 狀態圖搜索狀態圖搜索-搜索與求解搜索與求解 搜索搜索是人工智能技術中進行問題求解的基本技術，不管是是人工智能技術中進行問題求解的基本技術，不管是符號智能符號智能還是還是計算智能計算智能，最終往往都歸結為某種搜索，用，最終往往都歸結為某種搜索，

2、用某種搜索算法去實現。某種搜索算法去實現。 圖搜索模擬圖搜索模擬的是人腦分析問題、解決問題的過程，是基于的是人腦分析問題、解決問題的過程，是基于領域知識的問題求解技術。領域知識的問題求解技術。計算智能計算智能是借鑒或模擬某些自是借鑒或模擬某些自然現象或生命現象而實現的搜索和問題求解技術。然現象或生命現象而實現的搜索和問題求解技術。圖搜索技術是人工智能中的核心技術之一。圖搜索技術是人工智能中的核心技術之一。 3.1.1 狀態圖狀態圖例例3.1走迷宮走迷宮走迷宮問題就是從該有向圖的初始節點出發，走迷宮問題就是從該有向圖的初始節點出發，尋找目尋找目標節點標節點的問題，或者是的問題，或者是尋找尋找通向

3、目標節點的通向目標節點的路徑路徑問題。問題。3.1.1 狀態圖狀態圖例例3.2八數碼難題八數碼難題(重排九宮問題重排九宮問題) 2 83147 6512384765初始棋局目標棋局以上兩個問題抽象來看，都是某個有向圖中尋找目標以上兩個問題抽象來看，都是某個有向圖中尋找目標或路徑的問題，在人工智能技術中，把這種描述問題或路徑的問題，在人工智能技術中，把這種描述問題的有向圖稱為的有向圖稱為狀態空間圖，狀態空間圖，簡稱簡稱狀態圖狀態圖。棋局作為節點，相鄰節點通過移動數碼一個一個產生棋局作為節點，相鄰節點通過移動數碼一個一個產生出來，所有節點由它們的相鄰關系連成一個有向圖。出來，所有節點由它們的相鄰關

4、系連成一個有向圖。3.1.2 狀態圖搜索狀態圖搜索n搜索搜索：從初始節點出發，沿著與之相連的邊試探：從初始節點出發，沿著與之相連的邊試探地前進，尋找目標節點的過程。地前進，尋找目標節點的過程。n搜索過程中經過的節點和邊，按原圖的連接關系，搜索過程中經過的節點和邊，按原圖的連接關系，便會構成一個樹型的有向圖，這種樹型有向圖稱便會構成一個樹型的有向圖，這種樹型有向圖稱為為搜索樹搜索樹。n搜索進行中，搜索樹會不斷增長，直到當搜索樹搜索進行中，搜索樹會不斷增長，直到當搜索樹中出現目標節點，搜索便停止。這時從搜索樹中中出現目標節點，搜索便停止。這時從搜索樹中就可很容易地找出從初始節點到目標節點的路徑就可

5、很容易地找出從初始節點到目標節點的路徑（解解）來。）來。3.1.2 狀態圖搜索狀態圖搜索1 1 搜索方式搜索方式n樹式搜索樹式搜索 在搜索過程中記錄所經過的在搜索過程中記錄所經過的所有節點和邊所有節點和邊。樹式搜。樹式搜索所記錄的索所記錄的軌跡軌跡始終是一棵始終是一棵樹樹，這棵樹也就是搜索過，這棵樹也就是搜索過程中所產生的搜索樹。程中所產生的搜索樹。n線式搜索線式搜索 在搜索過程中只記錄那些在搜索過程中只記錄那些當前當前認為在所找路徑上的認為在所找路徑上的節點和邊節點和邊。n不回溯線式搜索不回溯線式搜索n可回溯線式搜索可回溯線式搜索3.1.2 狀態圖搜索狀態圖搜索2 2 搜索策略搜索策略n盲目

6、搜索盲目搜索 無向導的搜索，樹式盲目搜索就是窮舉搜索，不無向導的搜索，樹式盲目搜索就是窮舉搜索，不回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜索也是窮舉式搜索。索也是窮舉式搜索。n啟發式搜索啟發式搜索 是利用是利用“啟發性信息啟發性信息”引導的搜索策略。引導的搜索策略?！皢l啟發性信息性信息”就是與問題有關的有利于盡快找到問題解就是與問題有關的有利于盡快找到問題解的信息或知識。啟發式搜索分為不同的策略，如全的信息或知識。啟發式搜索分為不同的策略，如全局擇優，局部擇優，最佳圖搜索。局擇優，局部擇優，最佳圖搜索。n按按擴展順序擴展順序不同分為不同分為廣度

7、優先廣度優先和和深度優先深度優先。3.1.2 狀態圖搜索狀態圖搜索3 3 搜索算法搜索算法n搜索的目的是為了搜索的目的是為了尋找初始節點到目標節點的路徑尋找初始節點到目標節點的路徑，搜索過程中就得隨時記錄搜索軌跡。搜索過程中就得隨時記錄搜索軌跡。nClOSEDClOSED表表動態數據結構來動態數據結構來記錄考察過的節點記錄考察過的節點。nOPENOPEN表表的動態數據結構來專門的動態數據結構來專門登記當前待考查的節登記當前待考查的節點點。節點父節點編號編號節點父節點編號OPEN表CLOSED表3.1.2 狀態圖搜索狀態圖搜索n樹式搜索算法樹式搜索算法 步步1 1 把初始節點把初始節點S S0

8、0放入放入OPENOPEN表中。表中。 步步2 2 若若OPENOPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 3 取取OPENOPEN表中表中第一個節點第一個節點N N放在放在CLOSEDCLOSED表中；表中；并冠以順序編號并冠以順序編號n n； 步步4 4 若目標節點若目標節點Sg=NSg=N，成功退出。，成功退出。 步步5 5 若若N N不可擴展，轉步不可擴展，轉步2 2。 步步6 6 擴展擴展N N，生成一組節點，對這組子節點作如，生成一組節點，對這組子節點作如下處理：下處理：3.1.2 狀態圖搜索狀態圖搜索（1 1）刪除）刪除N N的先輩節點的先輩節點（如果有

9、的話）。（如果有的話）。（2 2）對）對已存在于已存在于OPENOPEN表中的節點表中的節點（如果有的話）也刪除（如果有的話）也刪除之；刪除之前要比較其返回初始節點的新路徑與原路之；刪除之前要比較其返回初始節點的新路徑與原路徑，如果新路徑徑，如果新路徑“短短”，則修改這些節點在，則修改這些節點在OPENOPEN表中表中的原返回指針，使其沿新路徑返回。的原返回指針，使其沿新路徑返回。（3 3）對）對已存在于已存在于CLOSEDCLOSED表的節點表的節點，作與（，作與（2 2）同樣的處）同樣的處理，并且將其移出理，并且將其移出CLOSEDCLOSED表，放入表，放入OPENOPEN表中重新擴展表

10、中重新擴展。（4 4）對）對其余子節點其余子節點配上指向配上指向N N的返回指針后放入的返回指針后放入OPENOPEN表表中中某處某處，或對，或對OPENOPEN表進行表進行重新排序重新排序，轉步，轉步2 2。3.1.2 狀態圖搜索狀態圖搜索圖 3-5 修改返回指針示例 n樹式算法的幾點說明樹式算法的幾點說明n返回指針返回指針指的是父節點在指的是父節點在CLOSEDCLOSED表中的編號。表中的編號。n步步6 6中中修改指針修改指針的原因是返回初始節點的路徑有兩的原因是返回初始節點的路徑有兩條，要選擇條，要選擇“短短”的那條路徑。的那條路徑。n這里這里路徑長短路徑長短以節點數來衡量，在后面將會

11、看到以以節點數來衡量，在后面將會看到以代價來衡量。按代價衡量修改返回指針的同時還要代價來衡量。按代價衡量修改返回指針的同時還要修改相應的代價值。修改相應的代價值。3.1.2 狀態圖搜索狀態圖搜索n樹式搜索例樹式搜索例n對于對于已存在于已存在于OPEN表中的節點表中的節點（如果有的話）也刪除之；刪（如果有的話）也刪除之；刪除之前要比較其返回初始節點的新路徑與原路徑，如果新路除之前要比較其返回初始節點的新路徑與原路徑，如果新路徑短，則修改這些節點在徑短，則修改這些節點在OPEN表中的原返回指針，使其沿原表中的原返回指針，使其沿原路徑返回。路徑返回。Path1Path2S0mnP先擴展后擴展P在n之

12、前已是某一節點m的后繼如圖所示：說明從如圖所示：說明從S0P至至少有兩條路，這時有兩少有兩條路，這時有兩種情況：種情況：f（Path2） f（Path1），），當前路徑較好，要修改當前路徑較好，要修改P的指針，使其指向的指針，使其指向n，即，即搜索之后的最佳路徑。搜索之后的最佳路徑。否則，原路徑好。否則，原路徑好。3.1.2 狀態圖搜索狀態圖搜索n對對已存在于已存在于CLOSED表的節點表的節點，作與（，作與（2）同樣的處理，并將）同樣的處理，并將其移出其移出CLOSED表，放入表，放入OPEN表中重新擴展。表中重新擴展。S0過去生成P的路徑現在生成P的路徑過去對Ps的最優路徑PsPmnka.

13、P在在n之前已是某一節點之前已是某一節點m的的后繼，所以需要做如同（后繼，所以需要做如同（2）同樣的處理，如圖右部所示。同樣的處理，如圖右部所示。b.P在在Closed表中，說明表中，說明P的后的后繼也在繼也在n之前已經生成，稱為之前已經生成，稱為Ps。對。對Ps而言同樣可能而言同樣可能 由于由于nP這一路徑的加入，又必這一路徑的加入，又必須比較多條路徑之后而取代價須比較多條路徑之后而取代價小的一條，如圖左部所示。小的一條，如圖左部所示。3.1.2 狀態圖搜索狀態圖搜索例：設當前搜索圖和搜索樹如圖所示例：設當前搜索圖和搜索樹如圖所示S0nPmPsPsS0nPmPsPsFF3.1.2 狀態圖搜索

14、狀態圖搜索n若啟發函數若啟發函數f(n)為從為從S0到節點到節點n的最短路徑的長度，用的最短路徑的長度，用邊的數目來考察，當前擴展的節點是搜索圖中的邊的數目來考察，當前擴展的節點是搜索圖中的n,P是是n的后繼的后繼S0nPmPsPsnPPsPsS0mFF3.1.2 狀態圖搜索狀態圖搜索n不回溯線式搜索算法不回溯線式搜索算法 步步1 把初始節點把初始節點S0放入放入CLOSED表中；表中； 步步2 令令N S0 ； 步步3 若若N是目標節點，則搜索成功，結束。是目標節點，則搜索成功，結束。 步步4 若若N不可擴展，則搜索失敗，退出。不可擴展，則搜索失敗，退出。 步步5 擴展擴展N，選取其一個未在

15、，選取其一個未在CLOSED表中出現過的表中出現過的 子節點子節點N1放入放入 CLOSED表中，令表中，令NN1，轉步，轉步3。3.1.2 狀態圖搜索狀態圖搜索n可回溯的線式搜索可回溯的線式搜索步步1 把初始節點把初始節點S0放入放入CLOSED表中；表中；步步2 令令N S0 ；步步3 若若N是目標節點，則搜索成功，結束。是目標節點，則搜索成功，結束。步步4 若若N不可擴展，則移出不可擴展，則移出CLOSED表中的末端節點表中的末端節點Ne ，若，若NeS0， 則搜索失敗，退出。否則以則搜索失敗，退出。否則以CLOSED表新的末端節點表新的末端節點Ne作為作為 N，即令，即令N Ne，轉步

16、，轉步4；步步5 擴展擴展N，選取其一個未在，選取其一個未在CLOSED表中出現過的子節點表中出現過的子節點N1放入放入 CLOSED表中，令表中，令N N1 ，轉步，轉步3。3.1.3 窮舉式搜索窮舉式搜索n廣度優先搜索廣度優先搜索n策略策略 始終在始終在同一級節點同一級節點中考查，當同一級節點考查完了之中考查，當同一級節點考查完了之后，才考查下一級節點。搜索樹后，才考查下一級節點。搜索樹自頂向下一層一層自頂向下一層一層逐漸逐漸生成。生成。n算法算法開始開始把S把S0 0送入OPEN表送入OPEN表OPEN表空OPEN表空？把OPEN表的第一個節把OPEN表的第一個節點（節點N）從表中移點（

17、節點N）從表中移出，放入CLOSED表中出，放入CLOSED表中節點N為目標節點？節點N為目標節點？節點N可擴展？節點N可擴展？擴展節點N，將其子節擴展節點N，將其子節點放入OPEN表點放入OPEN表尾部尾部，并為每個子節點配置并為每個子節點配置指向節點N的指針。指向節點N的指針。失敗，退出失敗，退出成功，退出成功，退出YNYNYNABCDEFGHIJKLMNOPQRSTU廣度優先搜索廣度優先搜索OPENCLOSEDOPENCLOSEDABCDEFGHIJKLMNOPQRSTUA廣度優先搜索廣度優先搜索22OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DA廣度優先搜索

18、廣度優先搜索23OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE F廣度優先搜索廣度優先搜索24OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG H廣度優先搜索廣度優先搜索25OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG HDI J廣度優先搜索廣度優先搜索26OPENCLOSEDABCDEFGHIJKLMNOPQRSTUAB C DABE FCG HDI JEK L廣度優先搜索廣度優先搜索3.1.3 窮舉式搜索窮舉式搜索n廣度優先搜索的特點廣度優先搜索的特點n廣度優先中廣度優先中

19、OPEN表表是一個是一個隊列隊列，CLOSED表表是一是一個個順序表順序表，表中各節點按順序編號，正被考察的節，表中各節點按順序編號，正被考察的節點在表中編號最大。點在表中編號最大。n廣度優先策略是廣度優先策略是完備完備的，即如果問題的解存在，則的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優解。它一定可以找到解，并且找到的解還是最優解。n廣度優先搜索策略與問題無關，具有通用性。廣度優先搜索策略與問題無關，具有通用性。n缺點搜索缺點搜索效率低效率低。3.1.3 窮舉式搜索窮舉式搜索n八數碼問題2 8 31 47 6 5初始狀態8 1 32 47 6 5目標狀態3.1.3 窮舉式

20、搜索窮舉式搜索2 8 31 47 6 51 2 3 1 8 47 6 592 31 8 47 6 582 81 4 37 6 5102 8 37 1 4 6 57 8 32 1 47 6 562 8 31 4 57 6112 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 4 7 5122 8 31 6 47 5138 32 1 47 6 5142 8 37 1 46 5152 3 41 87 6 5161 2 3 8 47 6 5172 81 4 37 6 5182 8 31 4 57 6192 8 3 6 41 7 5202 8 31 6

21、 7 5 4218 32 1 47 6 5222 8 31 6 47 558 1 32 47 6 523八數碼廣度優先搜索八數碼廣度優先搜索3.1.3 窮舉式搜索窮舉式搜索n深度優先搜索深度優先搜索n搜索策略搜索策略 在搜索樹的每一層始終先擴展一個子節點，不斷地向縱深前進，在搜索樹的每一層始終先擴展一個子節點，不斷地向縱深前進，直到不能再前進，才從當前節點返回到上一級節點，從另一方向直到不能再前進，才從當前節點返回到上一級節點，從另一方向繼續前進。繼續前進。n算法算法 開始開始把S把S0 0送入OPEN表送入OPEN表OPEN表空OPEN表空？把OPEN表的第一個節把OPEN表的第一個節點（節

22、點N）從表中移點（節點N）從表中移出，放入CLOSED表中出，放入CLOSED表中節點N為目標節點？節點N為目標節點？節點N可擴展？節點N可擴展？擴展節點N，將其子節擴展節點N，將其子節點放入OPEN表點放入OPEN表首部首部，并為每個子節點配置并為每個子節點配置指向節點N的指針。指向節點N的指針。失敗，退出失敗，退出成功，退出成功，退出YNYNYNABCDEFGHIJKLMNOPQRSTU深度優先搜索深度優先搜索OPENCLOSEDABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA深度優先搜索深度優先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDABCD深度

23、優先搜索深度優先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA DC BIJ深度優先搜索深度優先搜索ABCDEFGHIJKLMNOPQRSTUOPENCLOSEDA DC BIR深度優先搜索深度優先搜索J3.1.3 窮舉式搜索窮舉式搜索n深度優先搜索的特點深度優先搜索的特點nOPEN表為一個表為一個堆棧堆棧。n深度優先又稱深度優先又稱縱向搜索縱向搜索。n一般一般不能保證找到最優解不能保證找到最優解。n當深度限制不合理時，可能找不到解，可以將算法當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制，即有界深度優先搜索。改為可變深度限制，即有界深度優先搜索。3.1.3

24、 窮舉式搜索窮舉式搜索2 31 8 47 6 52 8 31 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 47 6 512 8 31 6 47 532 8 31 6 7 5 442 8 31 6 47 522 8 31 6 7 5 42 81 6 37 5 45八數碼深度優先搜索3.1.4 啟發式搜索啟發式搜索 啟發式搜索的目的啟發式搜索的目的利用知識來引導搜索，達到利用知識來引導搜索，達到減少搜索范圍減少搜索范圍，降低問題復，降低問題復雜度。雜度。 啟發性信息的強弱啟發性信息的強弱 強：強：降低搜索的工作量，但可能導致找不到最優解。降低搜索的工作量，但可能

25、導致找不到最優解。 弱：弱：一般導致工作量加大，極限情況下變為盲目搜索，一般導致工作量加大，極限情況下變為盲目搜索，但可能可以找到最優解。但可能可以找到最優解。3.1.4 啟發式搜索啟發式搜索n啟發函數啟發函數n啟發函數啟發函數是用來估計搜索樹節點是用來估計搜索樹節點x與目標節點接近與目標節點接近程度的一種函數，通常記為程度的一種函數，通常記為h（x）。）。n定義啟發函數的參考思路定義啟發函數的參考思路n一個節點到目標節點的某種距離或差異的量度。一個節點到目標節點的某種距離或差異的量度。n一個節點處在最佳路徑上的概率一個節點處在最佳路徑上的概率n根據主觀經驗的主觀打分等。根據主觀經驗的主觀打分

26、等。n啟發式搜索算法啟發式搜索算法n啟發式搜索要用啟發函數來導航，其搜索算法就要啟發式搜索要用啟發函數來導航，其搜索算法就要在狀態圖一般搜索算法基礎上再增加啟發函數值的在狀態圖一般搜索算法基礎上再增加啟發函數值的計算與傳播過程，并且由啟發函數值來確定節點的計算與傳播過程，并且由啟發函數值來確定節點的擴展順序。擴展順序。3.1.4 啟發式搜索啟發式搜索n全局擇優搜索全局擇優搜索n全局擇優搜索就是利用啟發函數制導的一種啟發式全局擇優搜索就是利用啟發函數制導的一種啟發式搜索方法。該方法亦稱為搜索方法。該方法亦稱為最好優先搜索法最好優先搜索法。n基本思想：在基本思想：在OPEN表中表中保留所有已生成而

27、未考察保留所有已生成而未考察的節點，并用啟發函數的節點，并用啟發函數h(x)對它們對它們全部全部進行估價，進行估價，從中選出最優節點進行擴展，而不管這個節點出現從中選出最優節點進行擴展，而不管這個節點出現在搜索樹的什么地方。在搜索樹的什么地方。3.1.4 啟發式搜索啟發式搜索n全局擇優搜索算法全局擇優搜索算法 步步1 把初始節點把初始節點S0放入放入OPEN表中，計算表中，計算h（ S0 ）；）； 步步2 若若OPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 移出移出OPEN表中第一個節點表中第一個節點N放入放入CLOSED表中，表中， 并冠以序號并冠以序號n； 步步4 若

28、目標節點若目標節點Sg N，則搜索成功結束。，則搜索成功結束。 步步5 若若N不可擴展，則轉步不可擴展，則轉步2。 步步6 擴展擴展N，計算每個子節點，計算每個子節點x的函數值的函數值h（x），并將），并將所有子節點配以指向所有子節點配以指向N的返回指針后放入的返回指針后放入OPEN表中，表中，再對再對OPEN表中所有子節點表中所有子節點按其函數值的大小以升序按其函數值的大小以升序排列，轉步排列，轉步2。A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRST全局擇優算法全局擇優算法OPENCLOSEDA-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2

29、 P-3QRSTOPENCLOSEDA-5全局擇優算法全局擇優算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4 D-6全局擇優算法全局擇優算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4 E-5 F-5 D-5全局擇優算法全局擇優算法A-5B-4C-4D-6E-5F-5G-4H-3IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5H-3 G-4全局擇優算法全局擇優算法A-5B-4C-4D-6E-5F-5

30、G-4IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5O-2G-4H-3H-3P-3全局擇優算法全局擇優算法A-5B-4C-4D-6E-5F-5G-4IJKLMNO-2 P-3QRSTOPENCLOSEDB-4A-5C-4D-6E-5 F-5O-2G-4H-3H-3P-3全局擇優算法全局擇優算法3.1.4 啟發式搜索啟發式搜索-全局擇優搜索算法全局擇優搜索算法啟發函數啟發函數h(x)為節點為節點x與目標格局相比與目標格局相比數碼不同的位置個數。數碼不同的位置個數。從圖看出解為：從圖看出解為： S0 ，S1 ，S2 ，S3， Sg。3.1.4 啟發式搜

31、索啟發式搜索-局部擇優搜索算法局部擇優搜索算法 基本思想是當每一個節點被擴展后，按基本思想是當每一個節點被擴展后，按h(x)對每一個子節對每一個子節點計算啟發值，并選擇最小者作為下一個要考察的節點，點計算啟發值，并選擇最小者作為下一個要考察的節點，由于每次都只是在由于每次都只是在子節點的范圍內子節點的范圍內選擇下一個要考察的節選擇下一個要考察的節點，范圍比較狹窄，所以稱為點，范圍比較狹窄，所以稱為局部擇優局部擇優搜索。搜索。步步6 擴展擴展N，計算，計算N每個子節點每個子節點x的函數值的函數值h（x），并將并將N的子節點按估計值升序排列的子節點按估計值升序排列放入放入OPEN表的首部，為每表的

32、首部，為每個子節點配置指向節點個子節點配置指向節點N的指針，轉步的指針，轉步2。3.1.5 加權狀態圖搜索加權狀態圖搜索例例3.6 3.6 交通圖交通圖A A城是出發地，城是出發地，E E是目的地，數字表示兩城是目的地，數字表示兩城之間交通費用。求之間交通費用。求A A到到E E的最小費用的旅行路線。的最小費用的旅行路線。ADCEB464332邊上附有數值的狀態圖稱為邊上附有數值的狀態圖稱為加權狀態圖加權狀態圖或或賦權狀態圖賦權狀態圖，這種數值稱為這種數值稱為權值權值。3.1.5 加權狀態圖搜索加權狀態圖搜索n加權狀態圖的搜索加權狀態圖的搜索加權狀態圖的搜索與權值有關，并且要用權值來導航。具體

33、加權狀態圖的搜索與權值有關，并且要用權值來導航。具體來講，加權狀態圖的搜索算法，要在一般狀態圖搜索算法基來講，加權狀態圖的搜索算法，要在一般狀態圖搜索算法基礎上再礎上再增加權值的計算與傳播過程增加權值的計算與傳播過程，并且要由權值來確定節，并且要由權值來確定節點的擴展順序。點的擴展順序。n代價的計算代價的計算 g（x）表示從初始節點）表示從初始節點S0到節點到節點x的代價。的代價。 c（xi，xj）表示父節點）表示父節點xi到子節點到子節點xj的代價的代價 g（ xj ）g（ xi ） c（xi，xj） g（ x0 ）03.1.5 加權狀態圖搜索加權狀態圖搜索n加權狀態圖轉換為代價樹搜索加權狀

34、態圖轉換為代價樹搜索n從初始節點出發，先把每一個與初始節點相鄰的從初始節點出發，先把每一個與初始節點相鄰的節點作為該節點的子節點。節點作為該節點的子節點。n然后對其他節點依次類推，但對其他節點然后對其他節點依次類推，但對其他節點x，不，不能將其父節點及祖先再作為能將其父節點及祖先再作為x的子節點。的子節點。ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.1.5 加權狀態圖搜索加權狀態圖搜索n分支界限法分支界限法n其基本思想是：每次從其基本思想是：每次從OPEN表中選出表中選出g(x)值最小值最小的節點進行考察，而不管這個節點在搜索樹的什么

35、的節點進行考察，而不管這個節點在搜索樹的什么位置上。位置上。n與全局擇優法的區別與全局擇優法的區別選取擴展節點標準選取擴展節點標準計算方法計算方法分支界限分支界限法法代價值代價值g（x）g（x）與節點所處的位置有）與節點所處的位置有關，與邊也有關系，從初始節關，與邊也有關系，從初始節點點S0計算而來。計算而來。全局擇優全局擇優法法啟發函數值啟發函數值h（x） h（x）與節點有關，與邊可）與節點有關，與邊可能有關或無關，從目標節點方能有關或無關，從目標節點方向計算而來。向計算而來。3.1.5 加權狀態圖搜索加權狀態圖搜索n最近擇優法最近擇優法（瞎子爬山法）（瞎子爬山法）n基本思想：每次僅考察基本

36、思想：每次僅考察N的子節點的的子節點的g（x），選?。x取N的子節點中代價最小的子節點進行擴展。的子節點中代價最小的子節點進行擴展。n最近擇優法與局部擇優法的區別：最近擇優法與局部擇優法的區別：選取擴展節點標選取擴展節點標準準計算方法計算方法最近擇優法最近擇優法代價值代價值g（x）g（x）與節點所處的位置有關，）與節點所處的位置有關，與邊也有關系，從初始節點與邊也有關系，從初始節點S0計算而來。計算而來。局部擇優法局部擇優法啟發函數啟發函數h（x）h（x）與節點有關，與邊可能）與節點有關，與邊可能有關或無關，從目標節點方向有關或無關，從目標節點方向計算而來。計算而來。內容回顧：樹式搜索策略比

37、較內容回顧：樹式搜索策略比較全局全局局部局部深度深度d(x)d(x)寬度優先搜索寬度優先搜索 深度優先搜索深度優先搜索啟發值啟發值h(x)h(x)全局擇優搜索全局擇優搜索 局部擇優搜索局部擇優搜索代價值代價值g(x)g(x)分支界限法分支界限法瞎子爬山法瞎子爬山法范圍范圍標準標準S S0 0S Sg g2 23 3a ab b4 46 61 15 5c cd dg gf fh hi ij jk k5 5f f5 54 43 37 78 89 9h（x），有利于搜索縱向發展，有利于搜索縱向發展，提高搜索效率，但影響完備性。提高搜索效率，但影響完備性。g（x），有利于搜索橫向發展，有利于搜索橫向發

38、展，提高完備性，但影響搜索效率。提高完備性，但影響搜索效率。窮舉式搜索窮舉式搜索啟發式搜索啟發式搜索加權狀態圖搜索加權狀態圖搜索3.1.6 A算法算法估價函數估價函數 將啟發函數與代價函數相結合，為了防止在單獨利將啟發函數與代價函數相結合，為了防止在單獨利用啟發函數的時候誤入歧途。用啟發函數的時候誤入歧途。 f（x） g（x）h（x）f f（x x）是初始節點是初始節點S S0 0到達節點到達節點x x處已付出的處已付出的代價與代價與節點節點x x到達目標節點到達目標節點S Sg g的的接近程度估計值總和接近程度估計值總和。是是g g（x x）與）與h h（x x）的折中）的折中。3.2 狀態

39、圖搜索問題求解狀態圖搜索問題求解3.2.1 問題的狀態圖表示問題的狀態圖表示 1. 狀態狀態狀態就是問題在任一確定時刻的狀況狀態就是問題在任一確定時刻的狀況,它表征了問題特征它表征了問題特征和結構等。狀態在狀態圖中表示為和結構等。狀態在狀態圖中表示為節點節點。狀態一般用一組數。狀態一般用一組數據表示。在程序中用字符、數字、記錄、數組、結構、對象據表示。在程序中用字符、數字、記錄、數組、結構、對象等表示。等表示。 2. 狀態轉換規則（操作狀態轉換規則（操作 operator）n引起狀態中某些分量發生改變，從而使一個具體狀態引起狀態中某些分量發生改變，從而使一個具體狀態變化到另一個具體狀態的作用。

40、變化到另一個具體狀態的作用。n描述了狀態之間的關系。描述了狀態之間的關系。n狀態轉換規則在狀態圖中表示為狀態轉換規則在狀態圖中表示為邊邊。在程序中狀態轉。在程序中狀態轉換規則可用數據對、條件語句、規則、函數、過程等換規則可用數據對、條件語句、規則、函數、過程等表示。表示。 3.2.1 問題的狀態圖表示問題的狀態圖表示n狀態空間（狀態空間（State Space）n問題的狀態空間是一個表示該問題全部的可能狀態問題的狀態空間是一個表示該問題全部的可能狀態及相互關系的圖。及相互關系的圖。n狀態空間一般用賦值有向圖表示，記為：狀態空間一般用賦值有向圖表示，記為： （S，F，G）nS：問題的可能有的初始

41、狀態的集合；：問題的可能有的初始狀態的集合；nF：操作的集合；：操作的集合；nG：目標狀態的集合。：目標狀態的集合。3.2.1 問題的狀態圖表示問題的狀態圖表示例例 3.7 迷宮問題的狀態圖表示。迷宮問題的狀態圖表示。 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,

42、Sg)G：Sg 迷宮問題規則集描述了圖中所有節點和邊。類似于迷宮問題規則集描述了圖中所有節點和邊。類似于這樣羅列出全部節點和邊的狀態圖稱為這樣羅列出全部節點和邊的狀態圖稱為顯式狀態圖顯式狀態圖，或者說或者說狀態圖狀態圖的的顯式顯式表示。表示。3.2.1 問題的狀態圖表示問題的狀態圖表示補充例補充例1 三枚錢幣，能否從下面狀態翻動三次后三枚錢幣，能否從下面狀態翻動三次后出現全正或全反狀態。出現全正或全反狀態。反正反正正正反反反初始狀態s目標狀態集合0, 73.2.1 問題的狀態圖表示問題的狀態圖表示引入一個三元組引入一個三元組(q0,q1,q2)來描述總狀態，錢幣正面為來描述總狀態，錢幣正面為0

43、，反面，反面為為1，全部可能的狀態為：，全部可能的狀態為： 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)。翻動錢幣的操作抽象為改變上述狀態的算子，翻動錢幣的操作抽象為改變上述狀態的算子， 即即Fa, b, c a:把錢幣把錢幣q0翻轉一次翻轉一次 b:把錢幣把錢幣q1翻轉一次翻轉一次 c:把錢幣把錢幣q2翻轉一次翻轉一次 問題的狀態空間為問題的狀態空間為3.2.1 問題的狀態圖表示問題的狀態圖表示狀態空間圖（0，0，0）（1，0，1）（0，0，1）（

44、0，1，0）（1，1，0）（1，0，0）（0，1，1）（1，1，1）acabacabcbbc3.2.1 問題的狀態圖表示問題的狀態圖表示 例例3.9 二階梵塔問題二階梵塔問題 一號桿有一號桿有A、B兩個金盤，兩個金盤，A小于小于B。要求將。要求將AB移至三號桿，每次只可移動一個盤子，任移至三號桿，每次只可移動一個盤子，任何時刻何時刻B不能在不能在A上。上。 用二元組（用二元組（SA，SB）表示狀態，）表示狀態，SA表示表示A所在桿號，所在桿號，SB表示表示B所在桿號，全部狀態如下：所在桿號，全部狀態如下： （1，1），（），（1，2），（），（1，3） （2，1），（），（2，2），（），（2

45、，3） （3，1），（），（3，2），（），（3，3）3.2.1 問題的狀態圖表示問題的狀態圖表示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 問題的狀態圖表示問題的狀態圖表示轉換規則：轉換規則：A（i，j）表示金盤）表示金盤A從第從第i號桿移到號桿移到j號桿號桿 B（i，j）表示金盤）表示金盤B從第從第i號桿移到號桿移到j號桿號桿 A（1，2），），A（1，3），

46、）， 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）初始狀態初始狀態（1，1），目標狀態，目標狀態（3，3）梵塔問題用狀態圖表示為梵塔問題用狀態圖表示為： 3.2.1 問題的狀態圖表示問題的狀態圖表示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 問題的狀態圖表示問題的狀態圖表示例例3.8重排九宮問題（八數碼難題）重排九宮問題（八數碼難題）X1X2X3X8X0X4X7X6X5將棋局用向

47、量將棋局用向量A(X0，X1 ， X2 ， X3 ， X4 ， X5 ， X6 ， X7 ， X8)表示，其中表示，其中Xi為變量，值表示方格為變量，值表示方格Xi內的數字。內的數字。 初始狀態初始狀態 S0 （0，2，8，3，4，5，6，7，1） 目標狀態目標狀態 Sg （0，1，2，3，4，5，6，7，8）數碼的移動規則就是該問題的狀態變化規則。經分析，該問題共有數碼的移動規則就是該問題的狀態變化規則。經分析，該問題共有24條規則，分為條規則，分為9組。組。2 83147 6512384765初始棋局初始棋局目標棋局目標棋局3.2.1 問題的狀態圖表示問題的狀態圖表示0組規則組規則 r1(

48、X0=0 ) (X2=n ) X0 = n X2 =0； r2(X0=0 ) (X4=n ) X0 = n X4 =0； r3(X0=0 ) (X6=n ) X0 = n X6 =0； r4(X0=0 ) (X8=n ) X0 = n X8 =0；1組規則組規則 r5(X1=0 ) (X2=n ) X1 = n X2 =0； r6(X1=0 ) (X8=n ) X1 = n X8 =0；8組規則組規則: r22(X8=0 ) (X1=n ) X8 = n X1 =0； r23(X8=0 ) (X0=n ) X8 = n X0=0； r24(X8=0 ) (X7=n ) X8 = n X7 =0

49、；X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X5X1X2X3X8X0X4X7X6X53.2.1 問題的狀態圖表示問題的狀態圖表示八數碼的狀態圖可表示為八數碼的狀態圖可表示為 （S0, r1 , r2 , , r24 , Sg）八數碼問題狀態圖僅給出了初始節點和目標八數碼問題狀態圖僅給出了初始節點和目標節點，其余節點需用狀態轉換規則來產生。節點，其余節點需用狀態轉換規則來產生。類似于這樣表示的狀態圖稱為類似于這樣表示的狀態圖稱為隱式狀態圖隱式狀態圖，或者說或者說狀態圖狀態圖的的隱式表示隱式表示。3.3 與或圖搜索與或圖搜索例例3.15 證明四邊形全等。證明四邊形全等。分

50、析：連接分析：連接BD， B D ，原來問題可以分解為兩個子問題：，原來問題可以分解為兩個子問題： Q1：證明：證明ABC ABC Q2：證明：證明BCD BCD原來問題可以原來問題可以分為兩個子問題解決。分為兩個子問題解決。ABDCA B D C 3.3.1 與或圖與或圖問題問題Q1還可以再被分解為：還可以再被分解為： Q11 ：證明：證明AB AB Q12 ：證明：證明AD AD Q13 ：證明：證明A A或或 Q11 ：證明：證明ABAB Q12 ：證明：證明ADAD Q13 ：證明：證明BDBD 問題問題Q2還可以再被分解為：還可以再被分解為： Q21 ：證明：證明BC BC Q22

51、：證明：證明CD CD Q23 ：證明：證明 C C 或或 Q21 ：證明：證明BC B C Q22 ：證明：證明CDC D Q23 ：證明：證明BD BD 3.3.1 與或圖與或圖將原問題用圖的形式表示如下：將原問題用圖的形式表示如下：QQ1Q2Q11Q12Q13Q11 Q12 Q13 Q21Q22Q23Q21 Q22 Q23 弧線表示所連邊為弧線表示所連邊為“與與”的關系的關系不帶弧線的邊不帶弧線的邊為或關系為或關系問題的解問題的解3.3.1 與或圖與或圖n與或圖的幾個概念與或圖的幾個概念n直接可解的問題稱為直接可解的問題稱為本原問題本原問題。n本原問題對應的節點稱為本原問題對應的節點稱為

52、終止節點終止節點。n無子節點的節點稱為無子節點的節點稱為端節點端節點。n子節點為與關系，則該節點為子節點為與關系，則該節點為與節點與節點。n子節點為或關系，則該節點為子節點為或關系，則該節點為或節點或節點。3.3.2 與或圖搜索與或圖搜索1. 1. 搜索方式搜索方式, ,解圖解圖( (樹樹) )與或圖搜索也分為樹式和“線”式兩種類型。 與或圖搜索解圖(樹),不只是尋找目標節點,而是邊擴展節點邊進行邏輯判斷, 以確定初始節點是否可解。一旦能夠確定初始節點的可解性,則搜索停止。根據返回指針便可從搜索樹中得到一個解圖(樹)。解圖(樹)實際上是由可解節點形成的一個子圖(樹), 這個子圖(樹)的根為初始

53、節點, 葉為終止節點, 且這個子圖(樹)還一定是與圖(樹)。 3.3.2 與或圖搜索與或圖搜索2. 2. 可解性判別可解性判別怎樣判斷一個節點的可解性呢？ 下面給出判別準則。 (1) 一個節點是可解, 則節點須滿足下列條件之一: 終止節點是可解節點。 一個與節點可解, 當且僅當其子節點全都可解。 一個或節點可解, 只要其子節點至少有一個可解。 (2) 一個節點是不可解, 則節點須滿足下列條件之一: 非終止節點的端節點是不可解節點。 一個與節點不可解, 只要其子節點至少有一個不可解。 一個或節點不可解, 當且僅當其子節點全都不可解。 3.3.2 與或圖搜索與或圖搜索4. 4. 搜索算法搜索算法與

54、或樹的樹式搜索過程可概括為以下步驟： 步1 把初始節點Qo放入OPEN表。 步2 移出OPEN表的第一個節點N放入CLOSED表, 并冠以序號n。 步3 若節點N可擴展, 則做下列工作： (1) 擴展N, 將其子節點配上指向父節點的指針后放入OPEN表。(2)考察這些子節點中是否有終止節點。 若有, 則標記它們為可解 節點, 并將它們也放入CLOSED表, 然后由它們的可解反向推斷其先輩節點的可解性, 并對其中的可解節點進行標記。 如果初始節點也被標記為可解節點, 則搜索成功,結束。(3)刪去OPEN表中那些具有可解先輩的節點(因為其先輩節點已經可解, 故已無再考察該節點的必要), 轉步2。

55、3.3.2 與或圖搜索與或圖搜索步4 若N不可擴展, 則做下列工作： (1)標記N為不可解節點, 然后由它的不可解反向推斷其先輩節點的可解性, 并對其中的不可解節點進行標記。如果初始節點So也被標記為不可解節點, 則搜索失敗, 退出。(2)刪去OPEN表中那些具有不可解先輩的節點(因為其先輩節點已不可解,故已無再考察這些節點的必要), 轉步2。 3.3.2 與或圖搜索與或圖搜索例例 3.16設有與或樹如圖3-15所示, 其中1號節點為初始節點,t1、t2、t3、t4均為終止節點, A和B是不可解的端節點。采用廣度(優先)搜索策略, 搜索過程如下： (1) 擴展1號節點, 得2號和3號節點, 依

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

57、時其先輩節點4和2也為可解節點, 但1號節點還不能確定。這時從OPEN表中刪去節點A,因為其父節點4已經可解。 () 擴展5號節點得t3和t4。由于t3和t4都為終止節點(放入CLOSED表), 故可推得節點5、3、1均為可解節點。 搜索成功, 結束。 這時,由CLOSED表便得到由節點1、2、3、4、5和t1、t2、 t3、t4構成的解樹，如圖3-15 中的粗線所示。 3.3.3 啟發式與或樹搜索啟發式與或樹搜索3.3.3 3.3.3 啟發式與或樹搜索啟發式與或樹搜索廣度優先搜索及深度優先搜索都是盲目搜索, 其共同點是： (1) 搜索從初始節點開始,先自上而下地進行搜索,尋找終止節點及端節點

58、, 然后再自下而上地進行可解性標記,一旦初始節點被標記為可解節點或不可解節點, 搜索就不再繼續進行。 (2) 搜索都是按確定路線進行的,當要選擇一個節點進行擴展時,只是根據節點在與或樹中所處的位置,而沒有考慮要付出的代價,因而求得的解樹不一定是代價最小的解樹, 即不一定是最優解樹 。 為了求得最優解樹，要在每次擴展節點時計算擴展該節點要付出的代價，并選擇代價最小的節點進行擴展。像這樣根據代價決定搜索路線的方法稱為與或樹的有序搜索，是一種重要的啟發式搜索策略。3.3.3 啟發式與或樹搜索啟發式與或樹搜索1. 解樹的代價解樹的代價解樹的代價就是樹根的代價。樹根的代價是從樹葉開始自下而上逐層計算而求

59、得的。而解樹的根對應的是初始節點Qo。 這就是說,在與或樹的搜索過程中,代價的計算方向與搜索樹的生長方向相反。這一點是與狀態圖不同的。具體來講,有下面的計算方法：設g(x)表示節點x的代價,c(x,y)表示節點x到其子節點y的代價(即邊xy的代價), 則 (1) 若x是終止節點, g(x)0。 3.3.3 啟發式與或樹搜索啟發式與或樹搜索(2) 若x是或節點, 。其中y1, y2, , yn是x的子節點。 (3) 若x是與節點x, 則有兩種計算公式。 和代價法： 。 最大代價法： 。其中y1, y2, , yn是x的子節點。 (4) 對非終止的端節點x, g(x)。 )(),(min)(1ii

60、niygyxcxg)(),()(1iiniygyxcxg)(),(max)(1iiniygyxcxg例例3.17 如圖3-16所示的與或樹, 其中包括兩棵解樹, 一棵解樹由Qo,A,t1和t2組成；另一棵解樹由Qo,B,D,G,t4和t5組成。 在此與或樹中,t1,t2,t3,t4,t5為終止節點；E,F是非終止的端節點, 其代價均為；邊上的數字是該邊的代價。 由右邊的解樹可得： 按和代價： 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