第三章 知識(shí)的狀態(tài)空間表示法

1、精選文檔第三章 學(xué)問的狀態(tài)空間表示法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ù)的定義方法。 3 學(xué)習(xí)指南：了解算法的每一個(gè)過程和細(xì)節(jié)問題，把握一些重要的定理和結(jié)論，在有條件的狀況下，程序?qū)崿F(xiàn)每一個(gè)算法，求解一些典型的問題。 4 難重點(diǎn)：回溯搜尋算法、 算法及其性質(zhì)、改進(jìn)的算法。5 學(xué)問點(diǎn)： 本章所要的爭(zhēng)辯的問題如下：

2、 有哪些常用的搜尋算法。 問題有解時(shí)能否找到解。 找到的解是最佳的嗎？ 什么狀況下可以找到最佳解？ 求解的效率如何。 3.1 狀態(tài)空間表示學(xué)問一、狀態(tài)空間表示學(xué)問要點(diǎn)1狀態(tài)狀態(tài)（State）用于描述敘述性學(xué)問的一組變量或數(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)，只要它有利于問題求解，就可以選用。2操作（規(guī)章或算符）操作（Operator）是把問題從一種狀態(tài)變成為另一種狀態(tài)的手段。當(dāng)對(duì)一個(gè)問題狀態(tài)使用某個(gè)可用操作時(shí)，它將引

3、起該狀態(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, fm3狀態(tài)空間狀態(tài)空間（State Space）是由問題的全部及一切可用算符（操作）所構(gòu)成的集合稱為問題的狀態(tài)空間。用三元組表示為：（Qs，F(xiàn)，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)，有向邊表示操作。二、狀態(tài)

4、圖搜尋1.搜尋方式用計(jì)算機(jī)來實(shí)現(xiàn)狀態(tài)圖的搜尋，有兩種最基本的方式：樹式搜尋和線式搜尋。 2.搜尋策略大體可分為盲目搜尋和啟發(fā)式（heuristic）搜尋兩大類。搜尋空間示意圖 例3.1 錢幣翻轉(zhuǎn)問題設(shè)有三枚硬幣，其初始狀態(tài)為（反，正，反），允許每次翻轉(zhuǎn)一個(gè)硬幣（只翻一個(gè)硬幣，必需翻一個(gè)硬幣）。必需連翻三次。問是否可以達(dá)到目標(biāo)狀態(tài)（正，正，正）或（反，反，反）。問題求解過程如下： 用數(shù)組表示的話，明顯每一硬幣需占一維空間，則用三維數(shù)組狀態(tài)變量表示這個(gè)學(xué)問： Q=（q1 , q2 , q3） 取q=0 表示錢幣的正面 q=1 表示錢幣的反面構(gòu)成的問題狀態(tài)空間明顯為： Q0=（0，0，0）， Q1=

5、（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.2 分油問題。 有兩只空油瓶，容量分別為8斤和6斤，另有一個(gè)大油桶，里面有足夠的油。我們可以任意從油桶中取出油灌滿某一油瓶，也可以把某瓶中的油全部倒回油桶，兩個(gè)油瓶之間可以相互灌。問如何在8斤油瓶中精確的得到4斤油。問題的求解明顯用2維數(shù)組或狀態(tài)空間描述比較合適，第一位

6、表示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ī)章：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)油全部裝入

7、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）3.2 搜尋問題爭(zhēng)辯（1）求任一解路的搜尋策略 回溯法（Backtracking）爬山法（Hill Climbing）寬度優(yōu)先法（Breadth-first）深度優(yōu)先法（Depth-first）限定范圍搜尋法（Beam Search）好的優(yōu)先法（Best-first）（2）求最佳解路的搜尋策略 大英博物館法（British Museu

8、m）分枝界限法（Branch and Bound）動(dòng)態(tài)規(guī)劃法（Dynamic Programming）最佳圖搜尋法（A）（3）求與或關(guān)系解圖的搜尋法一般與或圖搜尋法（AO）微小極大法（Minimax）剪枝法（Alpha-beta Pruning）啟發(fā)式剪枝法（Heuristic Pruning）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)是否在其中消滅。若消滅，則搜尋成功，若不消滅，則按某種搜尋策略從已生成的狀態(tài)中再選一個(gè)狀態(tài)作為當(dāng)前狀態(tài)，重復(fù)上述過程，直到目標(biāo)狀態(tài)消滅，或者

9、不在有可供操作的狀態(tài)為止。一、顯示圖與隱式圖1顯式圖（顯式存儲(chǔ)） 把與問題有關(guān)的全部狀態(tài)空間以及相應(yīng)的有關(guān)學(xué)問（敘述性學(xué)問、過程性學(xué)問、把握性學(xué)問)都直接存入學(xué)問庫，稱為顯式圖，或“顯式存貯”。2隱式圖（隱式存貯）只存貯與問題有關(guān)的部分學(xué)問，存貯的狀態(tài)由初始狀態(tài)開頭運(yùn)用相應(yīng)的學(xué)問，逐步生成所需的部分狀態(tài)空間，通過搜尋推理，漸漸轉(zhuǎn)移到要求的目標(biāo)狀態(tài)，只需在學(xué)問庫中存貯局部的狀態(tài)空間，稱為“隱式圖”或“隱式存貯”。通常接受隱式圖進(jìn)行解題（搜尋推理）。二、 “隱式圖”求解問題的一般過程open表：用于存放剛生成的結(jié)點(diǎn)closed表：用于存放將要擴(kuò)展或者已擴(kuò)展的結(jié)點(diǎn)3.3 圖搜尋（續(xù)）狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編

10、號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)open表closed 表搜尋過程如下：1：把初始結(jié)點(diǎn)s0放入open表中。2：檢查open表是否為空，若空，問題無解，退出。3：把open表中的第一個(gè)結(jié)點(diǎn)取出放入closed表中，并證明該結(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步。一般的圖搜尋算法1、G=G0(G0=s)，OPEN:= (s);2、CLOSED:=( );3、LOOP:IF OPEN=( ) THEN EXIT(FAIL);4、n:=

11、FIRST(OPEN),REMOVE(n,OPEN),ADD (n,CLOSED),5、IF GOAL(n) THEN EXIT(SUCCESS);6、EXPAND(n)mi,G:=ADDmi,G;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、GO LOOP；一些基本概念節(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的路徑。路徑

12、的耗散值 一條路徑的耗散值等于連接這條路徑各節(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)”.三、廣度優(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)為止。廣度優(yōu)先搜尋算法流程G:=

13、G0（G0=s）,OPEN:=(s), CLOSED:=（）；LOOP：IF OPEN（ ）THEN EXIT（FAIL）；n:FIRST（OPEN）；IF GOAL（n）THEN EXIT（SUCCESS）；REMOVE（n，OPEN），ADD（n，CLOSED）；EXPAND（n）mi，G:ADD（ mi ，G）； IF 目標(biāo)在 mi 中，THEN EXIT（SUCCESS）； ADD（OPEN， mj ），并標(biāo)記 到n的指針；GO LOOP 寬度優(yōu)先搜尋示例8數(shù)碼問題的寬度優(yōu)先搜尋樹廣度優(yōu)先搜尋的性質(zhì)當(dāng)問題有解時(shí),肯定能找到解當(dāng)問題為單位耗散值時(shí),且問題有解時(shí),肯定能找到最優(yōu)解方法與問題

14、無關(guā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)為止。深度優(yōu)先搜尋1、G=G0(G0=s)，OPEN:= (s);，CLOSED:=( );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

15、SED),6、IF DEPTH(n)>Dm GO LOOP;7、EXPAND(n) mi,G:=ADDmi,G;8、IF 目標(biāo)在mi中 THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并標(biāo)記mj到n指針;10、將mi重排序到open表頭部。11、GO LOOP;深度優(yōu)先搜尋性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí),可能找不到解,可以將算法改為可變深度限制最壞狀況時(shí), 搜尋空間等于窮舉與回溯法的差別:圖搜尋是一個(gè)通用的與問題無關(guān)的方法3.4 回溯策略所謂回溯策略，簡(jiǎn)潔地說是這樣一種策略：首先將規(guī)章給出一個(gè)固定的排序，在搜尋時(shí)，對(duì)當(dāng)前狀態(tài)（搜尋開頭時(shí)，當(dāng)前狀態(tài)是初始狀

16、態(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ù)以上搜尋，直到找到問題的解，或者摸索了全部可能后仍找不到問題的解為止。一個(gè)遞歸的例子Int abc(int n) abc(m); 八數(shù)碼玩?；厮莅盐辗绞叫律傻臓顟B(tài)在通向初始狀態(tài)的路徑上已消滅過；從初始狀態(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ī)章

17、。回溯搜尋算法BACKTRACK（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。 遞歸過程BACKTRACK（DATA）IF TERM（DATA），RETURN NIL；TERM取真即找到目標(biāo)，則過程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即該狀態(tài)不合法，則過程返回FAIL，必需回溯。RULES：APPRULES（DATA）；APPRULES計(jì)算DATA的可應(yīng)用規(guī)章集，依某種原則（任意排列或按啟

18、發(fā)式準(zhǔn)則）排列后賦給RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即規(guī)章用完未找到目標(biāo)，過程返回FAIL，必需回溯。R：FIRST（RULES）；取頭條可應(yīng)用規(guī)章。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)用本過程。IF PATHFAIL，GO LOOP；當(dāng)PATHFAIL時(shí)，遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一規(guī)章進(jìn)行測(cè)試。RETURN CONS（R，PATH）；過程返回解路徑規(guī)章表（或局部解路

19、徑子表）。回溯搜尋算法（）BACKTRACK1（DATALIST） DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：同前面的算法一樣，是以規(guī)章序列表示的路徑表（當(dāng)求解成功時(shí)），或者是FAIL（當(dāng)求解失敗時(shí)）。 回溯搜尋算法（續(xù)）DATA：FIRST（DATALIST）；設(shè)置DATA為當(dāng)前狀態(tài)IF MEMBER（DATA，TAIL（DATALIST) )，RETURN FAIL；TAIL是取尾操作，表示取表DATALIST中除了第一個(gè)元素以外的全部元素。假如DATA在TAIL（DATALIST）中存在，則表示有環(huán)路消滅，過程返回FAIL，必需回溯。IF TERM（DATA），RETURN

20、NIL；TERM取真即找到目標(biāo)，則過程返回空表NIL。IF DEADEND（DATA），RETURN FAIL；DEADEND取真，即該狀態(tài)不合法，則過程返回FAIL，必需回溯。IF LENGTH（DATALIST）BOUND，RETURN FAIL；LENGTH計(jì)算DATALIST的長(zhǎng)度，即搜尋的深度，當(dāng)搜尋深度大于給定值BOUND時(shí)，則過程返回FAIL，必需回溯。RULES：APPRULES（DATA）；APPRULES計(jì)算DATA的可應(yīng)用規(guī)章集，依某種原則（任意排列或按啟發(fā)式準(zhǔn)則排列）排列后賦給RULES。LOOP：IF NULL（RULES），RETURN FAIL；NULL取真，即規(guī)

21、章用完未找到目標(biāo)，過程返回FAIL，必需回溯。R：FIRST（RULES）；取頭條可應(yīng)用規(guī)章。RULES：TAIL（RULES）；刪去頭條規(guī)章，削減可應(yīng)用規(guī)章表的長(zhǎng)度。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)用本過程。IF PATHFAIL，GO LO0P；當(dāng)PATHFAIL時(shí)，遞歸調(diào)用失敗，則轉(zhuǎn)移調(diào)用另一規(guī)章進(jìn)行測(cè)試。RETURN CONS（R，PATH）；過程返回解路徑規(guī)章表（或局部解路徑子表）。 2

22、.1 回溯策略（Backtracking Strategies） 例：四皇后問題 QQQQ存在問題及解決方法：?jiǎn)栴}：深度問題死循環(huán)問題解決方法：對(duì)搜尋深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑一些深化的問題失敗緣由分析、多步回溯QQ一些深化的問題（續(xù)）回溯搜尋中學(xué)問的利用 基本思想（以皇后問題為例）： 盡可能選取劃去對(duì)角線上位置數(shù)最少的QQQQ3.5 狀態(tài)空間的與/或樹表示法1、 分解（與樹）把一個(gè)簡(jiǎn)單的問題變成簡(jiǎn)潔的子問題，各子問題又可以化成更為簡(jiǎn)潔的子問題，重復(fù)此過程，直到不能分解為止。然后對(duì)各子問題求解，最終把各子問題復(fù)合起來就是問題的解。2、 等價(jià)變換（或樹）通過同結(jié)構(gòu)的等價(jià)變換或同態(tài)

23、的等價(jià)變換把問題分解成比較簡(jiǎn)潔解的子問題，P1，P2，P3任何一個(gè)子問題有解，則問題P就可解，稱P1，P2，P3之間存在“或”的關(guān)系，節(jié)點(diǎn)P成為“或”節(jié)點(diǎn)，由P1，P2，P3，P之間構(gòu)成的樹為“或”樹。幾個(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)。與或圖的搜尋: 基本概念：與或圖是

24、一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。K-連接符： 可解節(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)才可解。不行解節(jié)點(diǎn)沒有后裔的非終節(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)才不行解?！芭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é)

25、點(diǎn)配上指向父節(jié)點(diǎn)的指針后放入OPEN表； (2)考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。 (3) 刪去OPEN表中那些具有可解先輩的節(jié)點(diǎn)（由于其先輩節(jié)點(diǎn)已經(jīng)可解，故已無再考察該節(jié)點(diǎn)的必要），轉(zhuǎn)步驟2； 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)（由于其先輩節(jié)點(diǎn)已不行解，故已無再考察這些節(jié)點(diǎn)的必要），轉(zhuǎn)步驟2；與狀態(tài)圖搜尋一樣，搜尋成功后，解樹已經(jīng)記錄在CLOSED表中。這時(shí)需按指向父節(jié)點(diǎn)的指針找出整個(gè)解樹。

26、 例 3.9 三階梵塔問題設(shè)有A，B，C三個(gè)金片（盤）以及三個(gè)鋼針，盤按自上而下從小到大的挨次穿在1號(hào)鋼針上，要求將它們?nèi)恳频?號(hào)鋼針上。規(guī)章：一次只能搬移一個(gè)金片，任何時(shí)刻都不能把大的金片壓在小的金片上，2號(hào)鋼針作為過渡使用。 解法1：用狀態(tài)轉(zhuǎn)換圖法。用三維狀態(tài)空間來表示學(xué)問或過程。（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）

27、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）依題意規(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）

28、 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個(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)變換，則由 博弈樹的搜尋 博弈問題:雙人一人一步雙方信息完備零和分錢幣問題: 中國象棋問題:每個(gè)勢(shì)態(tài)有40種不同的走法，假如一盤棋雙方平均走50步，則搜尋的位置有(402)50=10160 ，即深度達(dá)100層，總節(jié)點(diǎn)數(shù)約為10161個(gè)。假設(shè)一毫微秒走一步,約需1

29、0145年。結(jié)論：不行能窮舉。微小極大過程： 一字棋在九宮格棋盤上，兩位選手輪番在棋盤上擺各自的棋子（每次一枚），誰先取得三子一線的結(jié)果就取勝。設(shè)程序方MAX的棋子用（×）表示，對(duì)手MIN的棋子用（）表示，MAX先走。靜態(tài)估量函數(shù)f（p）規(guī)定如下：若p對(duì)任何一方來說都不是獲勝的格局，則f（p）（全部空格都放上MAX的棋子之后，MAX的三子成線（行、列、對(duì)角）的總（全部空格都放上MIN的棋子之后，MIN的三子成線（行、列、對(duì)角）的總數(shù)）若p是MAX獲勝的格局，則f（p）；若p是MIN獲勝的格局，則f（p）。 -搜尋過程 極大節(jié)點(diǎn)的下界為微小節(jié)點(diǎn)的上界為剪枝的條件：（后繼層）（先輩層），

30、 剪枝；（后繼層）（先輩層）， 剪枝。簡(jiǎn)記為：微小極大， 剪枝；極大微小， 剪枝；一字棋第一階段-剪枝方法 -搜尋過程的博弈樹 3.7 啟發(fā)式搜尋 啟發(fā)式圖搜尋利用學(xué)問來引導(dǎo)搜尋,以達(dá)到削減搜尋范圍,降低問題簡(jiǎn)單度的目的啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜尋工作量,但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大,極限狀況下變?yōu)槊つ克褜?但可能可以找到最優(yōu)解期望：引入啟發(fā)學(xué)問,在保證找到最佳解的狀況下,盡可能削減搜尋范圍,提高搜尋效率基本思想：定義一個(gè)評(píng)價(jià)函數(shù)f,對(duì)當(dāng)前的搜尋狀態(tài)進(jìn)行評(píng)估,找出一個(gè)最有期望的節(jié)點(diǎn)來擴(kuò)展啟發(fā)式搜尋算法A(A算法)評(píng)價(jià)函數(shù)的格式： f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù)

31、h(n)：?jiǎn)l(fā)函數(shù) 符號(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)的估量值A(chǔ) 算 法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,CLOSED);6. EXPAND(n) mi,計(jì)算f(

32、n,mi):=g(n,mi)+h(mi) ADD (mi,OPEN),標(biāo)記mi到n的指針 若mi在open表或closed表中有重復(fù)，依據(jù)耗散值確定取舍。7.OPEN中的節(jié)點(diǎn)按f值從小到大排序8.GO LOOP一個(gè)A算法的例子 h計(jì)算舉例21823318604477 655h(n)=4 2.最佳圖搜尋算法A*(A*算法)在A算法中假如滿足條件 h(n)h*(n) 則A算法稱為A*算法89A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和21823318604477 655h1(n)=4 h2(n)=5A*算法的性質(zhì)A*算法的假設(shè) 設(shè)ni,nj是任意兩個(gè)節(jié)點(diǎn),

33、有: 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)定理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)引理2.2 A*結(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) =

34、f*(s)定理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)致沖突推論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ò)展.得證定理3(可接受性定理): 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑,則A*必能找到最佳

35、解結(jié)束可接受性的證明由定理1、2知A*肯定找到一條路徑結(jié)束設(shè)找到的路徑st不是最佳的(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é)束條件推論3.1 A*選擇擴(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),得證.假如nn,由于A*選擇n擴(kuò)展,而不是n所以有 f(n)f(n)f*(s),得證.

36、定理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ù).留意: 在定理4中,評(píng)價(jià)指標(biāo)是”擴(kuò)展的節(jié)點(diǎn)數(shù)”也就是說,同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次,都只計(jì)算一次.定理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í),定理成立.

37、(歸納假設(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中。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ò)展，故有g(shù)1(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è)不成立。證畢102對(duì)h的評(píng)價(jià)方法：平均分叉數(shù)：設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜尋了N個(gè)節(jié)點(diǎn)，則： 其中b*稱為平均分叉數(shù)b*越好，說明h效果越好試驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化對(duì)h的評(píng)價(jià)舉例：例：數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)使用h1：d=14,N=53