知識(shí)的狀態(tài)空間表示法及搜索問題討論

知識(shí)的狀態(tài)空間表示法及搜索問題討論演示文稿當(dāng)前1頁，總共116頁。知識(shí)的狀態(tài)空間表示法及搜索問題討論當(dāng)前2頁，總共116頁。1課前思考：人類的思維過程，可以看作是一個(gè)搜索的過程。某個(gè)方案所用的步驟是否最少？也就是說它是最優(yōu)的嗎？如果不是，如何才能找到最優(yōu)的方案？在計(jì)算機(jī)上又如何實(shí)現(xiàn)這樣的搜索？這些問題實(shí)際上就是本章我們要介紹的搜索問題。2學(xué)習(xí)目標(biāo)：掌握回溯搜索算法、深度優(yōu)先搜索算法、寬度優(yōu)先搜索算法和A搜索算法，對(duì)典型問題，掌握啟發(fā)式函數(shù)的定義方法。當(dāng)前3頁，總共116頁。3學(xué)習(xí)指南：了解算法的每一個(gè)過程和細(xì)節(jié)問題，掌握一些重要的定理和結(jié)論，在有條件的情況下，程序?qū)崿F(xiàn)每一個(gè)算法，求解一些典型的問題。4難重點(diǎn)：回溯搜索算法、算法及其性質(zhì)、改進(jìn)的Ａ＊算法。當(dāng)前4頁，總共116頁。5知識(shí)點(diǎn)：當(dāng)前5頁，總共116頁。本章所要的討論的問題如下：

有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。

當(dāng)前6頁，總共116頁。3.1狀態(tài)空間表示知識(shí)一、狀態(tài)空間表示知識(shí)要點(diǎn)1．狀態(tài)狀態(tài)（State）用于描述敘述性知識(shí)的一組變量或數(shù)組，也可以說成是描述問題求解過程中任意時(shí)刻的數(shù)據(jù)結(jié)構(gòu)。通常表示成：Q={q1，q2，……，qn}當(dāng)給每一個(gè)分量以確定的值時(shí)，就得到一個(gè)具體的狀態(tài)，每一個(gè)狀態(tài)都是一個(gè)結(jié)點(diǎn)（節(jié)點(diǎn)）。實(shí)際上任何一種類型的數(shù)據(jù)結(jié)構(gòu)都可以用來描述狀態(tài)，只要它有利于問題求解，就可以選用。當(dāng)前7頁，總共116頁。2．操作（規(guī)則或算符）操作（Operator）是把問題從一種狀態(tài)變成為另一種狀態(tài)的手段。當(dāng)對(duì)一個(gè)問題狀態(tài)使用某個(gè)可用操作時(shí)，它將引起該狀態(tài)中某一些分量發(fā)生變化，從而使問題由一個(gè)具體狀態(tài)變成另一個(gè)具體狀態(tài)。操作可以是一個(gè)機(jī)械步驟、一個(gè)運(yùn)算、一條規(guī)則或一個(gè)過程。操作可理解為狀態(tài)集合上的一個(gè)函數(shù)，它描述了狀態(tài)之間的關(guān)系。通?？杀硎緸椋篎={f1,f2,………fm}3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前8頁，總共116頁。3．狀態(tài)空間狀態(tài)空間（StateSpace）是由問題的全部及一切可用算符（操作）所構(gòu)成的集合稱為問題的狀態(tài)空間。用三元組表示為：（{Qs}，{F}，{Qg}）Qs：初始狀態(tài)，Qg：目標(biāo)狀態(tài)，F(xiàn)：操作（或規(guī)則）。4．狀態(tài)空間（轉(zhuǎn)換）圖狀態(tài)空間也可以用一個(gè)賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖，在狀態(tài)空間圖中包含了操作和狀態(tài)之間的轉(zhuǎn)換關(guān)系，節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作。3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前9頁，總共116頁。二、狀態(tài)圖搜索1.搜索方式用計(jì)算機(jī)來實(shí)現(xiàn)狀態(tài)圖的搜索，有兩種最基本的方式：樹式搜索和線式搜索。2.搜索策略大體可分為盲目搜索和啟發(fā)式（heuristic）搜索兩大類。3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前10頁，總共116頁。搜索空間示意圖當(dāng)前11頁，總共116頁。例3.1錢幣翻轉(zhuǎn)問題設(shè)有三枚硬幣，其初始狀態(tài)為（反，正，反），允許每次翻轉(zhuǎn)一個(gè)硬幣（只翻一個(gè)硬幣，必須翻一個(gè)硬幣）。必須連翻三次。問是否可以達(dá)到目標(biāo)狀態(tài)（正，正，正）或（反，反，反）。問題求解過程如下：用數(shù)組表示的話，顯然每一硬幣需占一維空間，則用三維數(shù)組狀態(tài)變量表示這個(gè)知識(shí)：

Q=（q1,q2,q3）

取q=0表示錢幣的正面q=1表示錢幣的反面3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前12頁，總共116頁。構(gòu)成的問題狀態(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）引入操作：f1：把q1翻一面。

f2：把q2翻一面。f3：把q3翻一面。顯然：F={f1，f2，f3}目標(biāo)狀態(tài)：（找到的答案）Qg=（0，0，0）或（1，1，1）3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前13頁，總共116頁。3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前14頁，總共116頁。例3.2分油問題。

有兩只空油瓶，容量分別為8斤和6斤，另有一個(gè)大油桶，里面有足夠的油。我們可以任意從油桶中取出油灌滿某一油瓶，也可以把某瓶中的油全部倒回油桶，兩個(gè)油瓶之間可以互相灌。問如何在8斤油瓶中精確的得到4斤油。3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前15頁，總共116頁。問題的求解顯然用2維數(shù)組或狀態(tài)空間描述比較合適，第一位表示8斤油瓶油量，第二位表示6斤油瓶油量，構(gòu)成整數(shù)序列偶（E，S）E：=0，1，2，3，4，5，6，7，8。表示8斤油瓶中含有的油量。S：=0，1，2，3，4，5，6。表示6斤油瓶中含有的油量?？偨Y(jié)出如下分油操作規(guī)則：3.1狀態(tài)空間表示知識(shí)（續(xù)）當(dāng)前16頁，總共116頁。f1：8斤油瓶不滿時(shí)裝滿（E，S）且E<8—→（8，S）f2：6斤油瓶不滿時(shí)裝滿（E，S）且S<6—→（E，6）

f3：8斤油瓶不空時(shí)倒空（E，S）且E>0—→（0，S）

f4：6斤油瓶不空時(shí)倒空（E，S）且S>0—→（E，0）

f5：8斤油瓶?jī)?nèi)油全部裝入6斤油瓶?jī)?nèi)（E，S）E>0且E+S≤6—→（0，E+S）f6：6斤油瓶?jī)?nèi)油全部裝入8斤油瓶?jī)?nèi)（E，S）S>0且E+S≤8—→（E+S，0）f7：用6斤油瓶?jī)?nèi)油去灌滿8斤油瓶

（E，S）且E<8且E+S≥8—→（8，E+S-8）f8：用8斤油瓶?jī)?nèi)油去灌滿6斤油瓶

（E，S）且S<6且E+S≥6—→（E+S-6，6）當(dāng)前17頁，總共116頁。3.2搜索問題討論（1）求任一解路的搜索策略

回溯法（Backtracking）爬山法（HillClimbing）寬度優(yōu)先法（Breadth-first）深度優(yōu)先法（Depth-first）限定范圍搜索法（BeamSearch）好的優(yōu)先法（Best-first）

當(dāng)前18頁，總共116頁。（2）求最佳解路的搜索策略

大英博物館法（BritishMuseum）分枝界限法（BranchandBound）動(dòng)態(tài)規(guī)劃法（DynamicProgramming）最佳圖搜索法（A﹡）

當(dāng)前19頁，總共116頁。（3）求與或關(guān)系解圖的搜索法一般與或圖搜索法（AO﹡）極小極大法（Minimax）

α－β剪枝法（Alpha-betaPruning）啟發(fā)式剪枝法（HeuristicPruning）當(dāng)前20頁，總共116頁。3.3圖搜索

用計(jì)算機(jī)進(jìn)行狀態(tài)空間問題求解的基本思路：首先把問題的初始狀態(tài)（即初結(jié)點(diǎn)）作為當(dāng)前狀態(tài)，選擇合適的算符對(duì)其進(jìn)行操作，生成一組子狀態(tài)，然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)，重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)，或者不在有可供操作的狀態(tài)為止。當(dāng)前21頁，總共116頁。一、顯示圖與隱式圖1．顯式圖（顯式存儲(chǔ)）

把與問題有關(guān)的全部狀態(tài)空間以及相應(yīng)的有關(guān)知識(shí)（敘述性知識(shí)、過程性知識(shí)、控制性知識(shí))都直接存入知識(shí)庫，稱為顯式圖，或“顯式存貯”。2．隱式圖（隱式存貯）只存貯與問題有關(guān)的部分知識(shí)，存貯的狀態(tài)由初始狀態(tài)開始運(yùn)用相應(yīng)的知識(shí)，逐步生成所需的部分狀態(tài)空間，通過搜索推理，逐漸轉(zhuǎn)移到要求的目標(biāo)狀態(tài)，只需在知識(shí)庫中存貯局部的狀態(tài)空間，稱為“隱式圖”或“隱式存貯”。通常采用隱式圖進(jìn)行解題（搜索推理）。3.3圖搜索（續(xù)）當(dāng)前22頁，總共116頁。二、“隱式圖”求解問題的一般過程open表：用于存放剛生成的結(jié)點(diǎn)closed表：用于存放將要擴(kuò)展或者已擴(kuò)展的結(jié)點(diǎn)3.3圖搜索（續(xù)）狀態(tài)結(jié)點(diǎn)父結(jié)點(diǎn)編號(hào)狀態(tài)結(jié)點(diǎn)父結(jié)點(diǎn)open表closed表當(dāng)前23頁，總共116頁。搜索過程如下：1：把初始結(jié)點(diǎn)s0放入open表中。2：檢查open表是否為空，若空，問題無解，退出。3：把open表中的第一個(gè)結(jié)點(diǎn)取出放入closed表中，并證實(shí)該結(jié)點(diǎn)為n結(jié)點(diǎn)。4：考察結(jié)點(diǎn)n為是否為目標(biāo)結(jié)點(diǎn)，若是，退出。5：擴(kuò)展結(jié)點(diǎn)n,生成一組子結(jié)點(diǎn)，把其中不是先輩的那些結(jié)點(diǎn)加入open表的尾部，并配以指向父結(jié)點(diǎn)的指針。6：按某種搜索策略對(duì)open表中的結(jié)點(diǎn)進(jìn)行排序7：轉(zhuǎn)入第2步。3.3圖搜索（續(xù)）當(dāng)前24頁，總共116頁。一般的圖搜索算法1、G=G0(G0=s)，OPEN:=(s);2、CLOSED:=();3、LOOP:IFOPEN=()THENEXIT(FAIL);4、n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED),5、IFGOAL(n)THENEXIT(SUCCESS);6、EXPAND(n)→{mi},G:=ADD{mi,G};→當(dāng)前25頁，總共116頁。一般的圖搜索算法(續(xù))7、標(biāo)記和修改指針:ADD(mi,OPEN),并標(biāo)記mi到n的指針;計(jì)算是否要修改mk、ml到n的指針；計(jì)算是否修改ml到其后續(xù)節(jié)點(diǎn)的指針；8、對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9、GOLOOP；當(dāng)前26頁，總共116頁。一些基本概念節(jié)點(diǎn)深度根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1路徑設(shè)一節(jié)點(diǎn)序列為（n0，n1，…

，nk）,對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后續(xù)節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。擴(kuò)展一個(gè)節(jié)點(diǎn)生成該節(jié)點(diǎn)的所有后續(xù)節(jié)點(diǎn),并給出它們之間的耗散值.這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”.當(dāng)前27頁，總共116頁。三、廣度優(yōu)先搜索流程圖

廣度優(yōu)先搜索的含義：在對(duì)第n層結(jié)點(diǎn)沒有搜索考察完之前，不對(duì)第n+1層結(jié)點(diǎn)進(jìn)行搜索，但在隱式圖優(yōu)先搜索中是講：從初始結(jié)點(diǎn)s0開始，按生成規(guī)則逐步生成下一級(jí)各子結(jié)點(diǎn)，在檢查同級(jí)子結(jié)點(diǎn)同時(shí)，生成下級(jí)子結(jié)點(diǎn)并放在open表的末尾，而后再檢查下一個(gè)同級(jí)結(jié)點(diǎn)，如不是目標(biāo)結(jié)點(diǎn)，則按規(guī)則生成下級(jí)子結(jié)點(diǎn)，并放在open表末尾，如此下去，直到找到目標(biāo)為止。3.3圖搜索（續(xù)）當(dāng)前28頁，總共116頁。廣度優(yōu)先搜索算法流程①G:=G0（G0=s）,OPEN:=(s),CLOSED:=（）；②LOOP：IFOPEN＝（）THENEXIT（FAIL）；③n:＝FIRST（OPEN）；④IFGOAL（n）THENEXIT（SUCCESS）；⑤REMOVE（n，OPEN），ADD（n，CLOSED）；3.3圖搜索（續(xù)）當(dāng)前29頁，總共116頁。⑥EXPAND（n）→{mi}，G:＝ADD（mi

，G）；⑦IF目標(biāo)在{mi}中，THENEXIT（SUCCESS）；⑧ADD（OPEN，mj

），并標(biāo)記到n的指針；⑨GOLOOP3.3圖搜索（續(xù)）當(dāng)前30頁，總共116頁。寬度優(yōu)先搜索示例8數(shù)碼問題的寬度優(yōu)先搜索樹當(dāng)前31頁，總共116頁。廣度優(yōu)先搜索的性質(zhì)當(dāng)問題有解時(shí),一定能找到解當(dāng)問題為單位耗散值時(shí),且問題有解時(shí),一定能找到最優(yōu)解方法與問題無關(guān),具有通用性效率較低屬于圖搜索方法3.3圖搜索（續(xù)）當(dāng)前32頁，總共116頁。四、深度優(yōu)先搜索流程

從初始結(jié)點(diǎn)s0開始，按生成規(guī)則逐步生成下一級(jí)各子結(jié)點(diǎn)，在檢查同級(jí)子結(jié)點(diǎn)同時(shí)，生成下級(jí)子結(jié)點(diǎn)并放在open表的首部，而后再檢查下一個(gè)同級(jí)結(jié)點(diǎn)，如不是目標(biāo)結(jié)點(diǎn)，則按規(guī)則生成下級(jí)子結(jié)點(diǎn)，并放在open表首部，如此下去，直到找到目標(biāo)為止。3.3圖搜索（續(xù)）當(dāng)前33頁，總共116頁。深度優(yōu)先搜索1、G=G0(G0=s)，OPEN:=(s);，CLOSED:=();2、LOOP:IFOPEN=()THENEXIT(FAIL);3、n:=FIRST(OPEN),4、IFGOAL(n)THENEXIT(SUCCESS);5、REMOVE(n,OPEN),ADD(n,CLOSED),6、IFDEPTH(n)>DmGOLOOP;7、EXPAND(n)→{mi},G:=ADD{mi,G};8、IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9、ADD(mi,OPEN),并標(biāo)記mj到n指針;10、將mi重排序到open表頭部。11、GOLOOP;當(dāng)前34頁，總共116頁。23184765283147652318476523184765283164752831476528314765123847652831647528316475832147652837146528143765283145761237846512384765283641752831675483214765283714652814376528314576目標(biāo)①③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁②當(dāng)前35頁，總共116頁。深度優(yōu)先搜索性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí),可能找不到解,可以將算法改為可變深度限制最壞情況時(shí),搜索空間等于窮舉與回溯法的差別:圖搜索是一個(gè)通用的與問題無關(guān)的方法當(dāng)前36頁，總共116頁。3.4回溯策略所謂回溯策略，簡(jiǎn)單地說是這樣一種策略：首先將規(guī)則給出一個(gè)固定的排序，在搜索時(shí)，對(duì)當(dāng)前狀態(tài)（搜索開始時(shí)，當(dāng)前狀態(tài)是初始狀態(tài)）依次檢測(cè)每一條規(guī)則，在當(dāng)前狀態(tài)未使用過的規(guī)則中找到第一條可觸發(fā)規(guī)則，被應(yīng)用于當(dāng)前狀態(tài)，得到的新狀態(tài)重新設(shè)置為當(dāng)前狀態(tài)，并重復(fù)以上搜索。如果當(dāng)前狀態(tài)無規(guī)則可用，或者所有規(guī)則已經(jīng)被試探用過仍未找到問題的解，則將當(dāng)前狀態(tài)的前一個(gè)狀態(tài)（即直接生成該狀態(tài)的狀態(tài)）設(shè)置為當(dāng)前狀態(tài)。重復(fù)以上搜索，直到找到問題的解，或者試探了所有可能后仍找不到問題的解為止。當(dāng)前37頁，總共116頁。一個(gè)遞歸的例子Intabc(intn){…abc(m);…}當(dāng)前38頁，總共116頁。遞歸的思想從前有座山……從前有座山……從前有座山……從前有座山……當(dāng)前39頁，總共116頁。八數(shù)碼游戲回溯控制方式①新生成的狀態(tài)在通向初始狀態(tài)的路徑上已出現(xiàn)過；②從初始狀態(tài)開始，應(yīng)用的規(guī)則數(shù)目達(dá)到所規(guī)定的數(shù)目之后還未找到目標(biāo)狀態(tài)（這一組規(guī)則的數(shù)目實(shí)際上就是搜索③對(duì)當(dāng)前狀態(tài)，再?zèng)]有可應(yīng)用的規(guī)則。當(dāng)前40頁，總共116頁?；厮菟阉魉惴ǎǎ保〣ACKTRACK（DATA）功能：如果從當(dāng)前狀態(tài)DATA到目標(biāo)狀態(tài)有路徑存在，則返回以規(guī)則序列表示的從DATA到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）；如果從當(dāng)前狀態(tài)DATA到目標(biāo)狀態(tài)沒有路徑存在，則返回FAIL。當(dāng)前41頁，總共116頁。回溯搜索算法（２）遞歸過程BACKTRACK（DATA）①IFTERM（DATA），RETURNNIL；TERM取真即找到目標(biāo)，則過程返回空表NIL。②IFDEADEND（DATA），RETURNFAIL；DEADEND取真，即該狀態(tài)不合法，則過程返回FAIL，必須回溯。③RULES：＝APPRULES（DATA）；APPRULES計(jì)算DATA的可應(yīng)用規(guī)則集，依某種原則（任意排列或按啟發(fā)式準(zhǔn)則）排列后賦給RULES。④LOOP：IFNULL（RULES），RETURNFAIL；NULL取真，即規(guī)則用完未找到目標(biāo)，過程返回FAIL，必須回溯。⑤R：＝FIRST（RULES）；取頭條可應(yīng)用規(guī)則。當(dāng)前42頁，總共116頁。回溯搜索算法（３）⑥RULES：＝TAIL（RULES）；刪去頭條規(guī)則，減少可應(yīng)用規(guī)則表的長(zhǎng)度。⑦RDATA：＝GEN（R，DATA）；調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)。⑧PATH：＝BACKTRACK（RDATA）；對(duì)新狀態(tài)遞歸調(diào)用本過程。⑨IFPATH＝FAIL，GOLOOP；當(dāng)PATH＝FAIL時(shí)，遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一規(guī)則進(jìn)行測(cè)試。⑩RETURNCONS（R，PATH）；過程返回解路徑規(guī)則表（或局部解路徑子表）。當(dāng)前43頁，總共116頁?；厮菟阉魉惴ǎ保ǎ保〣ACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：同前面的算法一樣，是以規(guī)則序列表示的路徑表（當(dāng)求解成功時(shí)），或者是FAIL（當(dāng)求解失敗時(shí)）。當(dāng)前44頁，總共116頁?；厮菟阉魉惴ǎ保ɡm(xù)）⑴DATA：＝FIRST（DATALIST）；設(shè)置DATA為當(dāng)前狀態(tài)⑵IFMEMBER（DATA，TAIL（DATALIST))，RETURNFAIL；TAIL是取尾操作，表示取表DATALIST中除了第一個(gè)元素以外的所有元素。如果DATA在TAIL（DATALIST）中存在，則表示有環(huán)路出現(xiàn)，過程返回FAIL，必須回溯。⑶IFTERM（DATA），RETURNNIL；TERM取真即找到目標(biāo)，則過程返回空表NIL。⑷IFDEADEND（DATA），RETURNFAIL；DEADEND取真，即該狀態(tài)不合法，則過程返回FAIL，必須回溯。當(dāng)前45頁，總共116頁。回溯搜索算法１（續(xù)）⑸IFLENGTH（DATALIST）＞BOUND，RETURNFAIL；LENGTH計(jì)算DATALIST的長(zhǎng)度，即搜索的深度，當(dāng)搜索深度大于給定值BOUND時(shí)，則過程返回FAIL，必須回溯。⑹RULES：＝APPRULES（DATA）；APPRULES計(jì)算DATA的可應(yīng)用規(guī)則集，依某種原則（任意排列或按啟發(fā)式準(zhǔn)則排列）排列后賦給RULES。⑺LOOP：IFNULL（RULES），RETURNFAIL；NULL取真，即規(guī)則用完未找到目標(biāo)，過程返回FAIL，必須回溯。⑻R：＝FIRST（RULES）；取頭條可應(yīng)用規(guī)則。⑼RULES：＝TAIL（RULES）；刪去頭條規(guī)則，減少可應(yīng)用規(guī)則表的長(zhǎng)度。當(dāng)前46頁，總共116頁?；厮菟阉魉惴ǎ保ɡm(xù)）⑽RDATA：＝GEN（R，DATA）；調(diào)用規(guī)則R作用于當(dāng)前狀態(tài)，生成新狀態(tài)。⑾RDATALIST:＝CONS(RDATA，DATALIST)；將新狀態(tài)加入到表DATALIST中。⑿PATH：＝BACKTRACK1（RDATALIST）；遞歸調(diào)用本過程。⒀IFPATH＝FAIL，GOLO0P；當(dāng)PATH＝FAIL時(shí)，遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一規(guī)則進(jìn)行測(cè)試。⒁RETURNCONS（R，PATH）；過程返回解路徑規(guī)則表（或局部解路徑子表）。

當(dāng)前47頁，總共116頁。2.1回溯策略

（BacktrackingStrategies）例：四皇后問題QQQQ當(dāng)前48頁，總共116頁。存在問題及解決辦法：?jiǎn)栴}：深度問題死循環(huán)問題解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前49頁，總共116頁。一些深入的問題失敗原因分析、多步回溯QQ當(dāng)前50頁，總共116頁。一些深入的問題（續(xù)）回溯搜索中知識(shí)的利用基本思想（以皇后問題為例）：盡可能選取劃去對(duì)角線上位置數(shù)最少的QQQQ當(dāng)前51頁，總共116頁。3.5狀態(tài)空間的與/或樹表示法1、分解（與樹）把一個(gè)復(fù)雜的問題變成簡(jiǎn)單的子問題，各子問題又可以化成更為簡(jiǎn)單的子問題，重復(fù)此過程，直到不能分解為止。然后對(duì)各子問題求解，最后把各子問題復(fù)合起來就是問題的解。當(dāng)前52頁，總共116頁。2、等價(jià)變換（或樹）通過同結(jié)構(gòu)的等價(jià)變換或同態(tài)的等價(jià)變換把問題分解成比較容易解的子問題，P1，P2，P3任何一個(gè)子問題有解，則問題P就可解，稱P1，P2，P3之間存在“或”的關(guān)系，節(jié)點(diǎn)P成為“或”節(jié)點(diǎn)，由P1，P2，P3，P之間構(gòu)成的樹為“或”樹。3.5狀態(tài)空間的與/或樹表示法（續(xù)）當(dāng)前53頁，總共116頁。幾個(gè)概念（1）父問題、子問題：?jiǎn)栴}空間是由一個(gè)個(gè)問題組成的空間，在問題求解中，用一個(gè)節(jié)點(diǎn)代表一個(gè)問題，若節(jié)點(diǎn)A有一邊通向B，則表示A的解決有賴于B的解決。A稱為父問題，B稱為子問題。（2）本原問題：不能再分解或變換，而且直接可解的子問題。（3）端節(jié)點(diǎn)與終止節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，本原問題對(duì)應(yīng)的節(jié)點(diǎn)是終止節(jié)點(diǎn)。注意，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。3.5狀態(tài)空間的與/或樹表示法（續(xù)）當(dāng)前54頁，總共116頁。與或圖的搜索:當(dāng)前55頁，總共116頁?；靖拍睿号c或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。K-連接符：當(dāng)前56頁，總共116頁。當(dāng)前57頁，總共116頁?？山夤?jié)點(diǎn)：①終節(jié)點(diǎn)是可解節(jié)點(diǎn)；②若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解，該非終節(jié)點(diǎn)才可解；③若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解，該非終節(jié)點(diǎn)才可解。當(dāng)前58頁，總共116頁。不可解節(jié)點(diǎn)①?zèng)]有后裔的非終節(jié)點(diǎn)是不可解節(jié)點(diǎn)；②若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不可解；③若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有一子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不可解。當(dāng)前59頁，總共116頁?！芭c/或”樹的搜索過程1.把初始節(jié)點(diǎn)S0放入OPEN表；2.移出OPEN表的第一個(gè)節(jié)點(diǎn)N放入CLOSED表，并冠以序號(hào)n；3.若節(jié)點(diǎn)N可擴(kuò)展，則做下列工作：(1)擴(kuò)展N,將其子節(jié)點(diǎn)配上指向父節(jié)點(diǎn)的指針后放入OPEN表；(2)考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。(3)刪去OPEN表中那些具有可解先輩的節(jié)點(diǎn)（因?yàn)槠湎容吂?jié)點(diǎn)已經(jīng)可解，故已無再考察該節(jié)點(diǎn)的必要），轉(zhuǎn)步驟2；

當(dāng)前60頁，總共116頁。4.若N不可擴(kuò)展，則做下列工作：(1)標(biāo)記N為不可解節(jié)點(diǎn)，然后由它的不可解返回推斷其先輩節(jié)點(diǎn)的可解性，并對(duì)其中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)記。如果初始節(jié)點(diǎn)S0也被標(biāo)記為不可解節(jié)點(diǎn)，則搜索失敗，退出。(2)刪去OPEN表中那些具有不可解先輩的節(jié)點(diǎn)（因?yàn)槠湎容吂?jié)點(diǎn)已不可解，故已無再考察這些節(jié)點(diǎn)的必要），轉(zhuǎn)步驟2；與狀態(tài)圖搜索一樣，搜索成功后，解樹已經(jīng)記錄在CLOSED表中。這時(shí)需按指向父節(jié)點(diǎn)的指針找出整個(gè)解樹。當(dāng)前61頁，總共116頁。例3.9三階梵塔問題設(shè)有A，B，C三個(gè)金片（盤）以及三個(gè)鋼針，盤按自上而下從小到大的順序穿在1號(hào)鋼針上，要求將它們?nèi)恳频?號(hào)鋼針上。規(guī)則：一次只能搬移一個(gè)金片，任何時(shí)刻都不能把大的金片壓在小的金片上，2號(hào)鋼針作為過渡使用。當(dāng)前62頁，總共116頁。解法1：用狀態(tài)轉(zhuǎn)換圖法。用三維狀態(tài)空間來表示知識(shí)或過程。（i，j，k）i表示C片所鋼針號(hào)，j表示B片所在鋼針號(hào)，k表示A中所在鋼針號(hào)。顯然，組成的狀態(tài)空間有27個(gè)（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，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）當(dāng)前63頁，總共116頁。依題意規(guī)則可用18個(gè)狀態(tài)空間表示算子，A（），B（），C（）A（1，2）表示從1號(hào)針移到2號(hào)針，以下類推：A盤共有6種搬移規(guī)則。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）當(dāng)前64頁，總共116頁。當(dāng)前65頁，總共116頁。解法2：用“與/或”樹解題為把3個(gè)金片移到3號(hào)針可分解成如下步驟：1）把A，B金片移到2號(hào)針問題，雙片移動(dòng)問題。2）把C片移到3號(hào)針問題，終止節(jié)點(diǎn)，單片移動(dòng)。3）把A，B金片移到3號(hào)針問題，雙片移動(dòng)問題。用“=>”表示狀態(tài)變換，則由當(dāng)前66頁，總共116頁。當(dāng)前67頁，總共116頁。博弈樹的搜索博弈問題:雙人一人一步雙方信息完備零和當(dāng)前68頁，總共116頁。分錢幣問題:當(dāng)前69頁，總共116頁。中國象棋問題:每個(gè)勢(shì)態(tài)有40種不同的走法，如果一盤棋雙方平均走50步，則搜索的位置有(402)50=10160

，即深度達(dá)100層，總節(jié)點(diǎn)數(shù)約為10161個(gè)。假設(shè)一毫微秒走一步,約需10145年。結(jié)論：不可能窮舉。當(dāng)前70頁，總共116頁。極小極大過程：當(dāng)前71頁，總共116頁。一字棋在九宮格棋盤上，兩位選手輪流在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結(jié)果就取勝。

設(shè)程序方MAX的棋子用（×）表示，對(duì)手MIN的棋子用（○）表示，MAX先走。當(dāng)前72頁，總共116頁。靜態(tài)估計(jì)函數(shù)f（p）規(guī)定如下：

若p對(duì)任何一方來說都不是獲勝的格局，則

f（p）＝（所有空格都放上MAX的棋子之后，MAX的三子成線（行、列、對(duì)角）的總

－（所有空格都放上MIN的棋子之后，MIN的三子成線（行、列、對(duì)角）的總數(shù)）

若p是MAX獲勝的格局，則f（p）＝∞；

若p是MIN獲勝的格局，則f（p）＝－∞。當(dāng)前73頁，總共116頁。一字棋第一階段搜索樹當(dāng)前74頁，總共116頁。一字棋第二階段搜索樹當(dāng)前75頁，總共116頁。一字棋第三階段搜索樹當(dāng)前76頁，總共116頁。α-β搜索過程MAX節(jié)點(diǎn)的α值為當(dāng)前子節(jié)點(diǎn)的最大倒推值MIN節(jié)點(diǎn)的β值為當(dāng)前子節(jié)點(diǎn)的最小倒推值剪枝的條件：任何MAX節(jié)點(diǎn)n的α值≥它先輩節(jié)點(diǎn)的β值，則n以下的分值可以停止搜索，并令節(jié)點(diǎn)n的倒推值為α。這種剪枝稱為β剪枝；任何MIN節(jié)點(diǎn)n的β值≤它先輩節(jié)點(diǎn)的α值，則n以下的分值可以停止搜索，并令節(jié)點(diǎn)n的倒推值為β，這種剪枝稱為α剪枝。當(dāng)前77頁，總共116頁。一字棋第一階段α-β剪枝方法當(dāng)前78頁，總共116頁。α-β搜索過程的博弈樹當(dāng)前79頁，總共116頁。3.7啟發(fā)式搜索當(dāng)前80頁，總共116頁。啟發(fā)式圖搜索利用知識(shí)來引導(dǎo)搜索,以達(dá)到減少搜索范圍,降低問題復(fù)雜度的目的啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量,但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大,極限情況下變?yōu)槊つ克阉?但可能可以找到最優(yōu)解當(dāng)前81頁，總共116頁。希望：引入啟發(fā)知識(shí),在保證找到最佳解的情況下,盡可能減少搜索范圍,提高搜索效率基本思想：定義一個(gè)評(píng)價(jià)函數(shù)f,對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估,找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展當(dāng)前82頁，總共116頁。啟發(fā)式搜索算法A(A算法)評(píng)價(jià)函數(shù)的格式：

f(n)=g(n)+h(n)

f(n)：評(píng)價(jià)函數(shù)

h(n)：?jiǎn)l(fā)函數(shù)

當(dāng)前83頁，總共116頁。符號(hào)的意義g*(n):從s到n的最短路徑的耗散值h*(n):從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n):從s經(jīng)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)f*(n)的估計(jì)值當(dāng)前84頁，總共116頁。A算法1.OPEN:=(s),f(s)=g(s)+h(s);2.LOOP:IFOPEN=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.擴(kuò)展結(jié)點(diǎn)n，生成出不是n祖先的后繼結(jié)點(diǎn)集{mi},

計(jì)算f(n,mi):=g(n,mi)+h(mi)；6.若mi沒有在OPEN表和CLOSED表中出現(xiàn)過，則ADD(mi,OPEN)；7.若mi在OPEN表中有重復(fù)結(jié)點(diǎn)k，且g(mi)<g(k)，則REMOVE(k,OPEN)，ADD(mi,OPEN);當(dāng)前85頁，總共116頁。A算法(續(xù))8.若mi在CLOSED表中有重復(fù)結(jié)點(diǎn)k，且g(mi)<g(k)，則(1)CLOSED表的結(jié)點(diǎn)k改為結(jié)點(diǎn)mi

；(2)按后繼元表，修改結(jié)點(diǎn)k的所有在OPEN表和CLOSED表中的后裔的g、f值；9.OPEN中的節(jié)點(diǎn)按f值從小到大排序；10.GOLOOP當(dāng)前86頁，總共116頁。一個(gè)A算法的例子

定義評(píng)價(jià)函數(shù):f(n)=g(n)+h(n)g(n)為初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值

h(n)為當(dāng)前節(jié)點(diǎn)”不在位”的將牌數(shù)2831647512384765當(dāng)前87頁，總共116頁。h計(jì)算舉例21823318604477

655h(n)=4

當(dāng)前88頁，總共116頁。當(dāng)前89頁，總共116頁。2.最佳圖搜索算法A*(A*算法)在A算法中如果滿足條件

h(n)≤h*(n)

則A算法稱為A*算法當(dāng)前90頁，總共116頁。A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和21823318604477

655h1(n)=4

h2(n)=5當(dāng)前91頁，總共116頁。A*算法的性質(zhì)A*算法的假設(shè)設(shè)ni,nj是任意兩個(gè)節(jié)點(diǎn),有:C(ni,nj)>ε

其中ε為大于0的常數(shù)幾個(gè)等式

f*(s)=f*(t)=h*(s)=g*(t)=f*(n)

其中s是初始節(jié)點(diǎn),t是目標(biāo)節(jié)點(diǎn),n是s到t的最佳路徑上的節(jié)點(diǎn)當(dāng)前92頁，總共116頁。A*算法的性質(zhì)(續(xù)1)定理1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。引理2.1

對(duì)無限圖,若有從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)t的路徑,則A*不結(jié)束時(shí),在OPEN表中即使最小的一個(gè)f值也將增到任意大,或有f(n)>f*(s)當(dāng)前93頁，總共116頁。A*算法的性質(zhì)(續(xù)3)引理2.2A*結(jié)束前,OPEN表中必存在一個(gè)節(jié)點(diǎn)n,n在最佳路徑上且滿足f(n)≤f*(s)f(n)=g(n)+h(n) =g*(n)+h(n)

≤g*(n)+h*(n)=f*(n)=f*(s)當(dāng)前94頁，總共116頁。A*算法的性質(zhì)(續(xù)3)定理2

對(duì)無限圖,若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在,則A*一定成功結(jié)束證明：引理2.1:A*如果不結(jié)束,則OPEN中所有的n有f(n)>f*(s)引理2.2:在A結(jié)束前,必存在節(jié)點(diǎn)n,使得

f(n)≤f*(s)所以,如果A*不結(jié)束,將導(dǎo)致矛盾當(dāng)前95頁，總共116頁。A*算法的性質(zhì)(續(xù)4)推論2.1:OPEN表上任意一具有f(n)<f*(s)的節(jié)點(diǎn)n,最終將被A*選作擴(kuò)展節(jié)點(diǎn)

由定理2,知A*一定結(jié)束,由A*的結(jié)束條件,OPEN表中f(t)最小時(shí)才結(jié)束,而

f(t)≥f*(t)=f*(s)

所以f(n)＜f*(s)的n均被擴(kuò)展.得證當(dāng)前96頁，總共116頁。A*算法的性質(zhì)(續(xù)5)定理3(可采納性定理):

若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑,則A*必能找到最佳解結(jié)束當(dāng)前97頁，總共116頁?？刹杉{性的證明由定理1、2知A*一定找到一條路徑結(jié)束設(shè)找到的路徑s→t不是最佳的(t為目標(biāo))

則:f(t)=g(t)>f*(s)由引理2.2知結(jié)束前OPEN中存在f(n)≤f*(s)的節(jié)點(diǎn)n,

所以f(n)≤f*(s)<f(t)因此A*應(yīng)選擇n擴(kuò)展,而不是t.而假設(shè)A*選擇t結(jié)束矛盾.得證.注意:A*的結(jié)束條件當(dāng)前98頁，總共116頁。A*算法的性質(zhì)(續(xù)6)推論3.1A*選擇擴(kuò)展的任一節(jié)點(diǎn)n,有f(n)≤f*(s)由引理2.2知在A*結(jié)束前,OPEN中存在節(jié)點(diǎn)n’,f(n’)≤f*(s).設(shè)此時(shí)A*選擇n擴(kuò)展.如果n=n’,則f(n)≤f*(s),得證.如果n≠n’,由于A*選擇n擴(kuò)展,而不是n’所以有f(n)≤f(n’)≤f*(s),得證.當(dāng)前99頁，總共116頁。A*算法的性質(zhì)(續(xù)7)

定理4:

設(shè)對(duì)同一問題定義了兩個(gè)A*算法A1和A2,若A2比A1有較多的啟發(fā)信息,即對(duì)所有非目標(biāo)節(jié)點(diǎn)有h2(n)>h1(n),則在一條從s到t的路徑的隱含圖上,搜索結(jié)束時(shí),由A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn),也必定由A1所擴(kuò)展,即A1所擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多.

簡(jiǎn)寫:如果h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外),則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù).當(dāng)前100頁，總共116頁。A*算法的性質(zhì)(續(xù)7)注意:

在定理4中,評(píng)價(jià)指標(biāo)是”擴(kuò)展的節(jié)點(diǎn)數(shù)”也就是說,同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次,都只計(jì)算一次.當(dāng)前101頁，總共116頁。定理4的證明使用數(shù)學(xué)歸納法,對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納.(1)當(dāng)d(n)=0時(shí),即只有一個(gè)節(jié)點(diǎn),顯然定理成立.(2)設(shè)d(n)≤k時(shí),定理成立.(歸納假設(shè))(3)當(dāng)d(n)=k+1時(shí),用反證法.設(shè)存在一個(gè)深度為k+1的節(jié)點(diǎn)n,被A2擴(kuò)展,但沒有被A1擴(kuò)展.而由假設(shè),A1擴(kuò)展了n的父節(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時(shí)，n將被保留在OPEN中。當(dāng)前102頁，總共116頁。定理4的證明（續(xù)１）n沒有被A1選擇擴(kuò)展，有

f1(n)≥f*(s)，即g1(n)+h1(n)≥f*(s)

所以h1(n)≥f*(s)－g1(n)

（1）另一方面A2擴(kuò)展了n，有

f2(n)≤f*(s)，即g2(n)+h2(n)≤f*(s)

所以h2(n)≤f*(s)－g2(n)

（2）由于d=k時(shí)，A2擴(kuò)展的節(jié)點(diǎn)，A1也一定擴(kuò)展，故有

g1(n)≤g2(n)（因A1擴(kuò)展的節(jié)點(diǎn)數(shù)可能較多）所以h1(n)≥f*(s)－g1(n)≥f*(s)－g2(n)

（3）比較式（2）、（3）可得：至少在節(jié)點(diǎn)n上有h1(n)≥h2(n)，這與定理的前提條件矛盾，因此存在節(jié)點(diǎn)n的假設(shè)不成立。[證畢]當(dāng)前103頁，總共116頁。