1、第三章 知識的狀態空間表示法第三章 知識的狀態空間表示法1 課前思考：人類的思維過程，可以看作是一個搜索的過程。某個方案所用的步驟是否最少？也就是說它是最優的嗎？如果不是，如何才能找到最優的方案？在計算機上又如何實現這樣的搜索？這些問題實際上就是本章我們要介紹的搜索問題。 2 學習目標：掌握回溯搜索算法、深度優先搜索算法、寬度優先搜索算法和A搜索算法，對典型問題，掌握啟發式函數的定義方法。 3 學習指南：了解算法的每一個過程和細節問題，掌握一些重要的定理和結論，在有條件的情況下，程序實現每一個算法，求解一些典型的問題。 4 難重點：回溯搜索算法、 算法及其性質、改進的算法。5 知識點： 本章所

2、要的討論的問題如下： 有哪些常用的搜索算法。 問題有解時能否找到解。 找到的解是最佳的嗎？ 什么情況下可以找到最佳解？ 求解的效率如何。 3.1 狀態空間表示知識一、狀態空間表示知識要點1狀態狀態（State）用于描述敘述性知識的一組變量或數組，也可以說成是描述問題求解過程中任意時刻的數據結構。通常表示成：Q=q1，q2，qn當給每一個分量以確定的值時，就得到一個具體的狀態，每一個狀態都是一個結點（節點）。實際上任何一種類型的數據結構都可以用來描述狀態，只要它有利于問題求解，就可以選用。2操作（規則或算符）操作（Operator）是把問題從一種狀態變成為另一種狀態的手段。當對一個問題狀態使用某

3、個可用操作時，它將引起該狀態中某一些分量發生變化，從而使問題由一個具體狀態變成另一個具體狀態。操作可以是一個機械步驟、一個運算、一條規則或一個過程。操作可理解為狀態集合上的一個函數，它描述了狀態之間的關系。通常可表示為：F= f1 , f2, fm3狀態空間狀態空間（State Space）是由問題的全部及一切可用算符（操作）所構成的集合稱為問題的狀態空間。用三元組表示為：（Qs，F，Qg）Qs：初始狀態，Qg：目標狀態，F：操作（或規則）。4狀態空間（轉換）圖狀態空間也可以用一個賦值的有向圖來表示，該有向圖稱為狀態空間圖，在狀態空間圖中包含了操作和狀態之間的轉換關系，節點表示問題的狀態，有向

4、邊表示操作。二、狀態圖搜索1.搜索方式用計算機來實現狀態圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。 2.搜索策略大體可分為盲目搜索和啟發式（heuristic）搜索兩大類。搜索空間示意圖 例3.1 錢幣翻轉問題設有三枚硬幣，其初始狀態為（反，正，反），允許每次翻轉一個硬幣（只翻一個硬幣，必須翻一個硬幣）。必須連翻三次。問是否可以達到目標狀態（正，正，正）或（反，反，反）。問題求解過程如下： 用數組表示的話，顯然每一硬幣需占一維空間，則用三維數組狀態變量表示這個知識： Q=（q1 , q2 , q3） 取q=0 表示錢幣的正面 q=1 表示錢幣的反面構成的問題狀態空間顯然為： Q0=（0

5、，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）引入操作：f1：把q1翻一面。 f2：把q2翻一面。f3：把q3翻一面。 顯然：F=f1，f2，f3 目標狀態：（找到的答案） Qg=（0，0，0）或（1，1，1） 例3.2 分油問題。 有兩只空油瓶，容量分別為8斤和6斤，另有一個大油桶，里面有足夠的油。我們可以任意從油桶中取出油灌滿某一油瓶，也可以把某瓶中的油全部倒回油桶，兩個油瓶之間可以互相灌。問如何在8斤油瓶中精確的得到4斤油。問題的求解顯然用2維數組或狀態空間

6、描述比較合適，第一位表示8斤油瓶油量，第二位表示6斤油瓶油量，構成整數序列偶（E，S）E：=0，1，2，3，4，5，6，7，8 。表示8斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示6斤油瓶中含有的油量?？偨Y出如下分油操作規則：f1：8斤油瓶不滿時裝滿（E，S）且 E 8（8，S）f2：6斤油瓶不滿時裝滿（E，S）且 S 0（0，S） f4：6斤油瓶不空時倒空（E，S）且 S 0（E，0） f5：8斤油瓶內油全部裝入6斤油瓶內 （E，S）E 0 且E+S 6（0，E+S）f6：6斤油瓶內油全部裝入8斤油瓶內 （E，S）S 0 且 E+S 8（E+S，0）f7：用6斤油瓶內油去灌滿8

7、斤油瓶 （E，S）且 E 8 且E+S 8（8，E+S-8）f8：用8斤油瓶內油去灌滿6斤油瓶 （E，S）且 S Dm GO LOOP;7、EXPAND(n) mi,G:=ADDmi,G;8、IF 目標在mi中 THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并標記mj到n指針;10、將mi重排序到open表頭部。11、GO LOOP;深度優先搜索性質一般不能保證找到最優解當深度限制不合理時,可能找不到解,可以將算法改為可變深度限制最壞情況時, 搜索空間等于窮舉與回溯法的差別:圖搜索是一個通用的與問題無關的方法3.4 回溯策略所謂回溯策略，簡單地說是這樣一種策略：首先將規則

8、給出一個固定的排序，在搜索時，對當前狀態（搜索開始時，當前狀態是初始狀態）依次檢測每一條規則，在當前狀態未使用過的規則中找到第一條可觸發規則，被應用于當前狀態，得到的新狀態重新設置為當前狀態，并重復以上搜索。如果當前狀態無規則可用，或者所有規則已經被試探用過仍未找到問題的解，則將當前狀態的前一個狀態（即直接生成該狀態的狀態）設置為當前狀態。重復以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止。一個遞歸的例子Int abc(int n) abc(m); 八數碼游戲回溯控制方式新生成的狀態在通向初始狀態的路徑上已出現過；從初始狀態開始，應用的規則數目達到所規定的數目之后還未找到

9、目標狀態（這一組規則的數目實際上就是搜索對當前狀態，再沒有可應用的規則。回溯搜索算法BACKTRACK（DATA）功能：如果從當前狀態DATA到目標狀態有路徑存在，則返回以規則序列表示的從DATA到目標狀態的路徑（以規則表的形式表示）；如果從當前狀態DATA到目標狀態沒有路徑存在，則返回FAIL。 遞歸過程BACKTRACK（DATA）IF TERM（DATA），RETURN NIL；TERM取真即找到目標，則過程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即該狀態不合法，則過程返回FAIL，必須回溯。RULES：APPRULES（DATA）；

10、APPRULES計算DATA的可應用規則集，依某種原則（任意排列或按啟發式準則）排列后賦給RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即規則用完未找到目標，過程返回FAIL，必須回溯。R：FIRST（RULES）；取頭條可應用規則。RULES：TAIL（RULES）；刪去頭條規則，減少可應用規則表的長度。RDATA：GEN（R，DATA）；調用規則R作用于當前狀態，生成新狀態。PATH：BACKTRACK（RDATA）；對新狀態遞歸調用本過程。IF PATHFAIL，GO LOOP；當PATHFAIL時，遞歸調用失敗，則轉移調用另一規則進行測試。R

11、ETURN CONS（R，PATH）；過程返回解路徑規則表（或局部解路徑子表）?；厮菟阉魉惴ǎǎ〣ACKTRACK1（DATALIST） DATALIST：從初始到當前的狀態表（逆向）返回值：同前面的算法一樣，是以規則序列表示的路徑表（當求解成功時），或者是FAIL（當求解失敗時）。 回溯搜索算法（續）DATA：FIRST（DATALIST）；設置DATA為當前狀態IF MEMBER（DATA，TAIL（DATALIST) )，RETURN FAIL；TAIL是取尾操作，表示取表DATALIST中除了第一個元素以外的所有元素。如果DATA在TAIL（DATALIST）中存在，則表示有環路出現，

12、過程返回FAIL，必須回溯。IF TERM（DATA），RETURN NIL；TERM取真即找到目標，則過程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即該狀態不合法，則過程返回FAIL，必須回溯。IF LENGTH（DATALIST）BOUND，RETURN FAIL；LENGTH計算DATALIST的長度，即搜索的深度，當搜索深度大于給定值BOUND時，則過程返回FAIL，必須回溯。RULES：APPRULES（DATA）；APPRULES計算DATA的可應用規則集，依某種原則（任意排列或按啟發式準則排列）排列后賦給RULES。LOOP：I

13、F NULL（RULES），RETURN FAIL；NULL取真，即規則用完未找到目標，過程返回FAIL，必須回溯。R：FIRST（RULES）；取頭條可應用規則。RULES：TAIL（RULES）；刪去頭條規則，減少可應用規則表的長度。RDATA：GEN（R，DATA）；調用規則R作用于當前狀態，生成新狀態。RDATALIST:CONS(RDATA，DATALIST)；將新狀態加入到表DATALIST中。PATH：BACKTRACK1（RDATALIST）；遞歸調用本過程。IF PATHFAIL，GO LO0P；當PATHFAIL時，遞歸調用失敗，則轉移調用另一規則進行測試。RETURN C

14、ONS（R，PATH）；過程返回解路徑規則表（或局部解路徑子表）。 2.1 回溯策略（Backtracking Strategies） 例：四皇后問題 QQQQ存在問題及解決辦法：問題：深度問題死循環問題解決辦法：對搜索深度加以限制記錄從初始狀態到當前狀態的路徑一些深入的問題失敗原因分析、多步回溯QQ一些深入的問題（續）回溯搜索中知識的利用 基本思想（以皇后問題為例）： 盡可能選取劃去對角線上位置數最少的QQQQ3.5 狀態空間的與/或樹表示法1、 分解（與樹）把一個復雜的問題變成簡單的子問題，各子問題又可以化成更為簡單的子問題，重復此過程，直到不能分解為止。然后對各子問題求解，最后把各子問題

15、復合起來就是問題的解。2、 等價變換（或樹）通過同結構的等價變換或同態的等價變換把問題分解成比較容易解的子問題，P1，P2，P3任何一個子問題有解，則問題P就可解，稱P1，P2，P3之間存在“或”的關系，節點P成為“或”節點，由P1，P2，P3，P之間構成的樹為“或”樹。幾個概念（1）父問題、子問題：問題空間是由一個個問題組成的空間，在問題求解中，用一個節點代表一個問題，若節點A有一邊通向B，則表示A的解決有賴于B的解決。A稱為父問題，B稱為子問題。（2）本原問題：不能再分解或變換，而且直接可解的子問題。（3）端節點與終止節點：沒有子節點的節點，本原問題對應的節點是終止節點。注意，終止節點一定

16、是端節點，但端節點不一定是終止節點。與或圖的搜索: 基本概念：與或圖是一個超圖，節點間通過連接符連接。K-連接符： 可解節點：終節點是可解節點；若非終節點有“或”子節點時，當且僅當其子節點至少有一能解，該非終節點才可解；若非終節點有“與”子節點時，當且僅當其子節點均能解，該非終節點才可解。不可解節點沒有后裔的非終節點是不可解節點；若非終節點有“或”子節點時，當且僅當所有子節點均不能解時，該非終節點才不可解；若非終節點有“與”子節點時，當至少有一子節點不能解時，該非終節點才不可解。“與/或”樹的搜索過程1. 把初始節點S0放入OPEN表；2. 移出OPEN表的第一個節點N放入CLOSED表，并冠

17、以序號n；3. 若節點N可擴展，則做下列工作： (1)擴展N,將其子節點配上指向父節點的指針后放入OPEN表； (2)考察這些子節點中是否有終止節點。 (3) 刪去OPEN表中那些具有可解先輩的節點（因為其先輩節點已經可解，故已無再考察該節點的必要），轉步驟2； 4. 若N不可擴展，則做下列工作： (1)標記N為不可解節點，然后由它的不可解返回推斷其先輩節點的可解性，并對其中的不可解節點進行標記。如果初始節點S0也被標記為不可解節點，則搜索失敗，退出。 (2)刪去OPEN表中那些具有不可解先輩的節點（因為其先輩節點已不可解，故已無再考察這些節點的必要），轉步驟2；與狀態圖搜索一樣，搜索成功后，

18、解樹已經記錄在CLOSED表中。這時需按指向父節點的指針找出整個解樹。 例 3.9 三階梵塔問題設有A，B，C三個金片（盤）以及三個鋼針，盤按自上而下從小到大的順序穿在1號鋼針上，要求將它們全部移到3號鋼針上。規則：一次只能搬移一個金片，任何時刻都不能把大的金片壓在小的金片上，2號鋼針作為過渡使用。 解法1：用狀態轉換圖法。用三維狀態空間來表示知識或過程。（i，j，k）i表示C片所鋼針號，j表示B片所在鋼針號，k表示A中所在鋼針號。顯然，組成的狀態空間有27個（3*3*3）S0=（1，1，1） S1=（1，1，2） S2=（1，1，3）S3=（1，2，1） S4=（1，2，2） S5=（1，2

19、，3）S6=（1，3，1） S7=（1，3，2） S8=（1，3，3）S9=（2，1，1） S10=（2，1，2） S11=（2，1，3）S12=（2，2，1） S13=（2，2，2） S14=（2，2，3）S15=（2，3，1） S16=（2，3，2） S17=（2，3，3）S18=（3，1，1） S19=（3，1，2） S20=（3，1，3）S21=（3，2，1） S22=（3，2，2） S23=（3，2，3）S24=（3，3，1） S25=（3，3，2） S26=（3，3，3）依題意規則可用18個狀態空間表示算子，A（），B（），C（）A（1，2）表示從1號針移到2號針，以下類推：A盤共

20、有6種搬移規則。A（1，3） A（2，1）.A（3，1） A（3，2） B（1，2） B（1，3） B（3，1） B（3，2）C（1，2） C（1，3）C（3，1） C（3，2） 解法2：用“與/或”樹解題為把3個金片移到3號針可分解成如下步驟：1）把A，B金片移到2號針問題，雙片移動問題。2）把C片移到3號針問題，終止節點，單片移動。3）把A，B金片移到3號針問題，雙片移動問題。用“=”表示狀態變換，則由 博弈樹的搜索 博弈問題:雙人一人一步雙方信息完備零和分錢幣問題: 中國象棋問題:每個勢態有40種不同的走法，如果一盤棋雙方平均走50步，則搜索的位置有(402)50=10160 ，即深度達

21、100層，總節點數約為10161個。假設一毫微秒走一步,約需10145年。結論：不可能窮舉。極小極大過程： 一字棋在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結果就取勝。設程序方MAX的棋子用（）表示，對手MIN的棋子用（）表示，MAX先走。靜態估計函數f（p）規定如下：若p對任何一方來說都不是獲勝的格局，則f（p）（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對角）的總（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對角）的總數）若p是MAX獲勝的格局，則f（p）；若p是MIN獲勝的格局，則f（p）。 -搜索過程 極大節點的下界為

22、極小節點的上界為剪枝的條件：（后繼層）（先輩層）， 剪枝；（后繼層）（先輩層）， 剪枝。簡記為：極小極大， 剪枝；極大極小， 剪枝；一字棋第一階段-剪枝方法 -搜索過程的博弈樹 3.7 啟發式搜索 啟發式圖搜索利用知識來引導搜索,以達到減少搜索范圍,降低問題復雜度的目的啟發信息的強度強：降低搜索工作量,但可能導致找不到最優解弱：一般導致工作量加大,極限情況下變為盲目搜索,但可能可以找到最優解希望：引入啟發知識,在保證找到最佳解的情況下,盡可能減少搜索范圍,提高搜索效率基本思想：定義一個評價函數f,對當前的搜索狀態進行評估,找出一個最有希望的節點來擴展啟發式搜索算法A(A算法)評價函數的格式：

23、f(n)=g(n)+h(n) f(n)：評價函數 h(n)：啟發函數 符號的意義g*(n):從s到n的最短路徑的耗散值h*(n):從n到g的最短路徑的耗散值f*(n)= g*(n)+ h*(n):從s經過n到g的最短路徑的耗散值g(n)、 h(n)、f(n) 分別是g*(n)、 h*(n)f*(n)的估計值A 算 法1.OPEN:= (s), f(s)=g(s)+h(s);2.LOOP:IF OPEN=( ) THEN EXIT(FAIL);3.n:=FIRST(OPEN);4.IF GOAL(n) THEN EXIT(SUCCESS);5.REMOVE(n,OPEN), ADD (n,CLO

24、SED);6. EXPAND(n) mi,計算f(n,mi):=g(n,mi)+h(mi) ADD (mi,OPEN),標記mi到n的指針 若mi在open表或closed表中有重復，根據耗散值確定取舍。7.OPEN中的節點按f值從小到大排序8.GO LOOP一個A算法的例子 h計算舉例21823318604477655h(n)=4 2.最佳圖搜索算法A*(A*算法)在A算法中如果滿足條件 h(n)h*(n) 則A算法稱為A*算法89A*條件舉例8數碼問題h1(n)=“不在位”的將牌數h2(n)=將牌“不在位”的距離和21823318604477655h1(n)=4 h2(n)=5A*算法的性

25、質A*算法的假設 設ni,nj是任意兩個節點,有: C(ni,nj) 其中為大于0的常數幾個等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n) 其中s是初始節點,t是目標節點,n是s到t的最佳路徑上的節點定理1：對有限圖，如果從初始節點s到目標節點t有路徑存在，則算法A一定成功結束。引理2.1 對無限圖,若有從初始節點S到目標節點t的路徑,則A*不結束時,在OPEN表中即使最小的一個f值也將增到任意大,或有f(n)f*(s)引理2.2 A*結束前,OPEN表中必存在一個節點n, n在最佳路徑上且滿足f(n)f*(s)f(n)=g(n)+h(n) =g*(n)+h(n) g*(n)

26、+h*(n) =f*(n) =f*(s)定理2 對無限圖,若從初始節點s到目標節點t有路徑存在,則A*一定成功結束證明：引理2.1: A*如果不結束,則OPEN中所有的n有f(n)f*(s)引理2.2: 在A結束前,必存在節點n,使得f(n)f*(s)所以,如果A*不結束,將導致矛盾推論2.1: OPEN表上任意一具有f(n)f*(s)由引理2.2知結束前OPEN中存在f(n)f*(s)的節點n, 所以 f(n)f*(s)h1(n),則在一條從s到t的路徑的隱含圖上,搜索結束時,由A2所擴展的每一個節點,也必定由A1所擴展,即A1所擴展的節點數至少和A2一樣多. 簡寫:如果h2(n)h1(n)

27、(目標節點除外), 則A1擴展的節點數 A2擴展的節點數.注意: 在定理4中,評價指標是”擴展的節點數”也就是說,同一個節點無論被擴展多少次,都只計算一次.定理4的證明使用數學歸納法,對節點的深度進行歸納. (1)當 d(n)=0時,即只有一個節點,顯然定理成立. (2)設d(n)k時,定理成立.(歸納假設) (3)當d(n)=k+1時,用反證法.設存在一個深度為k+1的節點n,被A2擴展, 但沒有被A1擴展.而由假設,A1擴展了n的父節點，即n已經被生成了。因此當A1結束時，n將被保留在OPEN中。n沒有被A1選擇擴展，有f1(n)f*(s)，即g1(n)+h1(n)f*(s)所以 h1(n

28、)f*(s) g1(n) （1）另一方面A2擴展了n，有f2(n)f*(s)，即g2(n)+h2(n)f*(s)所以 h2(n)f*(s)g2(n) （2）由于d=k時，A2擴展的節點，A1也一定擴展，故有g1(n)g2(n)（因A1擴展的節點數可能較多）所以 h1(n)f*(s) g1(n)f*(s) g2(n) （3）比較式（2）、（3）可得：至少在節點n上有h1(n)h2(n)，這與定理的前提條件矛盾，因此存在節點n的假設不成立。證畢102對h的評價方法：平均分叉數：設共擴展了d層節點，共搜索了N個節點，則： 其中b*稱為平均分叉數b*越好，說明h效果越好實驗表明，b*是一個比較穩定的常

29、數，同一問題基本不隨問題規模變化對h的評價舉例：例：數碼問題，隨機產生若干初始狀態使用h1：d=14,N=539,b*=1.44d=20,N=7276,b*=1.47使用h2：d=14,N=113,b*=1.23d=20,N=676,b*=1.27A*的復雜性：一般說來，*的算法復雜性是指數型的,可以證明當且僅當以下條件成立時：abs(h(n)-h*(n)O(log(h*(n)*的算法復雜性才是非指數型的，但是通常情況下，h和h*的差別至少是和離目標的距離成正比的A*算法的改進在A算法的第六步，對于ml類節點，存在重新放回到OPEN表的可能，因此一個節點有可能被反復擴展多次。因此單純用擴展的節點數并不能客觀地來評判搜索算法的好壞。因為即便是擴展的節點數比較少