一章人工智能蔡自興

第一章搜索問(wèn)題內(nèi)容： 狀態(tài)空間的搜索問(wèn)題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問(wèn)題： 如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。1搜索問(wèn)題題（續(xù)1）S0Sg問(wèn)題全狀狀態(tài)空間間搜索空間間解路徑2搜索問(wèn)題題（續(xù)2）討論的問(wèn)問(wèn)題：有哪些常常用的搜搜索算法法。問(wèn)題有解解時(shí)能否否找到解解。找到的解解是最佳佳的嗎？？什么情況況下可以以找到最最佳解？？求解的效效率如何何。31.1回回溯策策略例：皇后后問(wèn)題4()5()Q((1,,1)))6()QQ((1,,1)))((1,,1)((2,,3)))7()Q((1,,1)))((1,,1)((2,,3)))8()QQ((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))9()QQ((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))Q((1,,1)((2,,4)((3..2)))10()QQ((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))11()Q((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))12()((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))13()((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))Q((1,,2)))14()((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))Q((1,,2)))Q((1,,2)((2,,4)))15()((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))Q((1,,2)))Q((1,,2)((2,,4)))Q((1,,2)((2,,4)((3,,1)))16()((1,,1)))((1,,1)((2,,3)))((1,,1)((2,,4)))((1,,1)((2,,4)((3..2)))Q((1,,2)))Q((1,,2)((2,,4)))Q((1,,2)((2,,4)((3,,1)))Q((1,,2)((2,,4)((3,,1)((4,,3)))17回溯策略略屬于盲盲目搜索索的一種種?；厮莶呗月允沁@樣樣一種策策略：首先將規(guī)規(guī)則給出出一個(gè)固固定排序序，在搜搜索時(shí)，，對(duì)當(dāng)前前狀態(tài)依依次檢查查每條規(guī)規(guī)則，在在當(dāng)前狀狀態(tài)未使使用過(guò)的的規(guī)則中中找到第第一條可可應(yīng)用規(guī)規(guī)則應(yīng)用用于當(dāng)前前狀態(tài)，，得到的的新?tīng)顟B(tài)態(tài)設(shè)置為為當(dāng)前狀狀態(tài)，并并重復(fù)以以上搜索索。如果當(dāng)前前狀態(tài)無(wú)無(wú)規(guī)則可可用，或或者所有有規(guī)則已已經(jīng)用過(guò)過(guò)仍未找找到問(wèn)題題的解，，則將當(dāng)當(dāng)前狀態(tài)態(tài)的前一一個(gè)狀態(tài)態(tài)（即直直接生成成該狀態(tài)態(tài)的狀態(tài)態(tài)）設(shè)置置為當(dāng)前前的狀態(tài)態(tài)。重復(fù)復(fù)以上搜搜索，直直到找到到問(wèn)題的的解?；厮莶呗月?8遞歸的思思想回溯有多多種實(shí)現(xiàn)現(xiàn)方法,,其中遞遞歸是一一種最直直接的實(shí)實(shí)現(xiàn)方法法.從前有座山……從前有座山……

從前有座山……19回溯搜索索算法遞歸過(guò)程程：BACKTRACK（DATA）

DATA：當(dāng)前前狀態(tài)。。返回值：：從當(dāng)前前狀態(tài)到到目標(biāo)狀狀態(tài)的路路徑（以規(guī)則則表的形形式表示示）或FAIL。20回溯搜索索算法遞歸過(guò)程程BACKTRACK(DATA))1,IFTERM(DATA)RETURNNIL;///滿足結(jié)束束條件時(shí)時(shí)返回2,IFDEADEND(DATA)RETURNFAIL;///不合法狀狀態(tài)的回回溯點(diǎn)3,RULES::=APPRULES(DATA));///可應(yīng)用規(guī)規(guī)則集4,LOOP:IFNULL((RULES))RETURNFAIL;///全部規(guī)則則均失敗敗的回溯溯點(diǎn)5,R:=FIRST(RULES);;6,RULES::=TAIL((RULES));///刪去第一一條規(guī)則則，減少少可應(yīng)用用規(guī)則表表的長(zhǎng)度度7,RDATA:=GEN(R,DATA);///調(diào)用規(guī)則則R作用用于當(dāng)前前狀態(tài)，，生成新新?tīng)顟B(tài)8,PATH:==BACKTRACK(RDATA);///對(duì)新?tīng)顟B(tài)態(tài)遞歸調(diào)調(diào)用9,IFPATH=FAILGOLOOP;10,RETURNCONS((R,PATH);;///返回解路路徑規(guī)則則表21遞歸的思思想（續(xù)續(xù)）當(dāng)前狀態(tài)態(tài)n目標(biāo)狀態(tài)態(tài)tr1r2ri-1rim1m2mi-1mi22存在問(wèn)題題及解決決辦法解決辦法法：對(duì)搜索深深度加以以限制記錄從初初始狀態(tài)態(tài)到當(dāng)前前狀態(tài)的的路徑當(dāng)前狀態(tài)問(wèn)題：深度問(wèn)題題死循環(huán)問(wèn)問(wèn)題23一些深入入問(wèn)題在回溯策策略中，，也可以以引入一一些與問(wèn)問(wèn)題有關(guān)關(guān)的信息息來(lái)加快快搜索解解的速度度?；舅枷胂?以皇皇后問(wèn)題題為例))：盡可能選選取劃去去對(duì)角線線上位置置數(shù)最少少的。QQQQ322324回溯搜索索算法1BACKTRACK1（DATALIST）

DATALIST：從從初始到到當(dāng)前的的狀態(tài)表表（逆向向）返回值：：從當(dāng)前前狀態(tài)到到目標(biāo)狀狀態(tài)的路路徑（以規(guī)則則表的形形式表示示）或FAIL。25回溯搜索索算法11,DATA:=FIRST(DATALIST)//設(shè)置DATA為當(dāng)前狀狀態(tài)2,IFMENBER((DATA,TAIL(DATALIST)))RETURNFAIL;//TAIL取尾操作作，取DATALIST中除第一一個(gè)以外外的所有有元素，，如果DATA在TAIL(DATALIST）中存在在，則說(shuō)說(shuō)明有回回路，返返回FAIL，必須回回溯.3,IFTERM(DATA))RETURNNIL;;//找到目標(biāo)標(biāo)，結(jié)束束4,IFDEADEND(DATA))RETURNFAIL;//狀態(tài)不合合法，返返回FAIL，必須回回溯.5,IFLENGTH((DATALIST))>BOUNDRETURNFAIL;//LENGTH計(jì)算DATALIST的長(zhǎng)度，，即搜索索深度，，當(dāng)搜索索深度大大于BOUND值時(shí)，搜搜索失敗敗，返回回FAIL，必須回回溯.6,RULES:==APPRULES((DATA);;//APPRULES計(jì)算DATA的可應(yīng)用用規(guī)則集集，依某某種原則則（任意意排列或或啟發(fā)式式排列））排列后后附給RULES.7,LOOP:IFNULL(RULES)RETURNFAIL;//規(guī)則用完完沒(méi)找到到目標(biāo)，，返回FAIL,必須回溯溯。26回溯搜索索算法1（續(xù)））8,R::=FIRST(RULES);//取第第一條規(guī)規(guī)則9,RULES:=TAIL(RULES);//刪去去第一條條規(guī)則，，減少可可應(yīng)用規(guī)規(guī)則表的的長(zhǎng)度10,RDATA::=GEN(R,DATA);//調(diào)用用規(guī)則R作用于于當(dāng)前狀狀態(tài)，生生成新?tīng)顮顟B(tài)11,RDATALIST:=CONS(RDATA,DATALIST);;//將新新?tīng)顟B(tài)加加入到表表DATALIST中中12,PATH:==BACKTRCK1(RDATALIST)//遞歸歸調(diào)用本本過(guò)程13,IFPATH=FAILGOLOOP;;//遞歸歸調(diào)用失失敗，轉(zhuǎn)轉(zhuǎn)移調(diào)用用另一規(guī)規(guī)則進(jìn)行行測(cè)試14,RETURNCONS((R,PATH);;//返回回解路徑徑規(guī)則表表27分析這個(gè)算法法與BACKRACK的差別別是遞歸歸過(guò)程自自變量是是狀態(tài)的的鏈表。。在過(guò)程BACKRACK1中中，形參參DATALIST是是從初始始狀態(tài)到到當(dāng)前狀狀態(tài)的逆逆序表，，即初始始狀態(tài)排排在表的的最后，，當(dāng)前狀狀態(tài)排在在表的最最前面。。在第2、、5步增增設(shè)了兩兩個(gè)回溯溯點(diǎn)以檢檢驗(yàn)是否否重新訪訪問(wèn)已出出現(xiàn)過(guò)的的狀態(tài)和和限定搜搜索深度度范圍。。

281.2圖圖搜索索策略問(wèn)題的引引出回溯搜索索：只保保留從初初始狀態(tài)態(tài)到當(dāng)前前狀態(tài)的的一條路路徑。圖搜索：：保留所所有已經(jīng)經(jīng)搜索過(guò)過(guò)的路徑徑。

29一些基本本概念節(jié)點(diǎn)深度度：根節(jié)點(diǎn)深深度=0其它節(jié)點(diǎn)點(diǎn)深度==父節(jié)點(diǎn)點(diǎn)深度++1012330一些基本本概念（（續(xù)1））路徑設(shè)一節(jié)點(diǎn)點(diǎn)序列為為(n0,n1,…,nk)，對(duì)于于i=1,…,,k，若若任一節(jié)節(jié)點(diǎn)ni-1都具有一一個(gè)后繼繼節(jié)點(diǎn)ni，則該節(jié)節(jié)點(diǎn)序列列稱為從從n0到nk的長(zhǎng)度為為k的一一條路徑徑。路徑的耗耗散值一條路徑徑的耗散散值等于于連接這這條路徑徑各節(jié)點(diǎn)點(diǎn)間所有有耗散值值的總和和。用C(ni,nj)表示從ni到nj的路徑的的耗散值值.路路徑耗散散值可按按如下遞遞推公式式計(jì)算：：C(ni,t))=C(ni,nj)+C(nj,t)31一些基本本概念（（續(xù)1））擴(kuò)展一個(gè)個(gè)節(jié)點(diǎn)生成出該該節(jié)點(diǎn)的的所有后后繼節(jié)點(diǎn)點(diǎn)，并給給出它們們之間的的耗散值值。這一一過(guò)程稱稱為“擴(kuò)擴(kuò)展一個(gè)個(gè)節(jié)點(diǎn)””。32一般的圖圖搜索算算法1,G=G0(G0=s),,OPEN::=(s);///設(shè)置open表表,最初初只含有有初始點(diǎn)點(diǎn)s2,CLOSED::=());//設(shè)置置closed表,初初始為空空表3,LOOP:IFOPEN==())THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,,OPEN)),ADD((n,CLOSED);//n為為當(dāng)前節(jié)節(jié)點(diǎn)5,IFGOAL(n))THENEXIT(SUCCESS);6,EXPAND((n)→→{mi},G:=ADD((mi,G));//子節(jié)節(jié)點(diǎn)集{{mi}中不包包含n的的父輩節(jié)節(jié)點(diǎn)33一般的圖圖搜索算算法（續(xù)續(xù)）7,標(biāo)標(biāo)記和修修改指針針：ADD((mj,OPEN)),并標(biāo)記mj到n的指指針；//mj為open表表和closed表中中未出現(xiàn)現(xiàn)過(guò)的子子結(jié)點(diǎn)計(jì)算是否否要修改改mk、ml到n的指指針；//mk為已出現(xiàn)現(xiàn)在open表表中的子子結(jié)點(diǎn)，，ml為已出現(xiàn)現(xiàn)在closed表中中的子結(jié)結(jié)點(diǎn)，{{mj}={mj}∪{mk}∪{ml}計(jì)算是否否要修改改ml到其后繼繼節(jié)點(diǎn)的的指針；8,對(duì)對(duì)OPEN中的的節(jié)點(diǎn)按按某種原則則重新排序序；9,GOLOOP；34說(shuō)明這里給出出的是一一個(gè)圖搜搜索的一一般框架架，不是是一個(gè)具具體的算算法，關(guān)關(guān)鍵是算算法的第第8步，按不不同的原原則對(duì)OPEN表進(jìn)行排排序，將將得到不不同的圖圖搜索算算法。算法中有有兩個(gè)表表：OPEN表和CLOSED表。其中中OPEN表記錄的的是已經(jīng)經(jīng)被生成成出來(lái)，，但還沒(méi)沒(méi)有被擴(kuò)擴(kuò)展的節(jié)節(jié)點(diǎn)；CLOSED表記錄的的是已經(jīng)經(jīng)被擴(kuò)展展過(guò)的節(jié)節(jié)點(diǎn)。35幾類節(jié)點(diǎn)點(diǎn)的圖例例說(shuō)明如上圖所所示，假假設(shè)n是當(dāng)前被被擴(kuò)展的的節(jié)點(diǎn)。。在n被擴(kuò)展之之前，節(jié)節(jié)點(diǎn)mk和ml已經(jīng)被生生成出來(lái)來(lái)了，其其中mk還沒(méi)有被被擴(kuò)展，，他們?cè)谠贠PEN表中，而而ml已經(jīng)被擴(kuò)擴(kuò)展了，，他們?cè)谠贑LOSED表中。當(dāng)當(dāng)n被擴(kuò)展時(shí)時(shí)，它生生成了節(jié)節(jié)點(diǎn)mi，mi由mj、mk和ml三部分組組成，其其中mj是新出現(xiàn)現(xiàn)的節(jié)點(diǎn)點(diǎn)。36算法解釋釋圖搜索算算法，簡(jiǎn)簡(jiǎn)單地說(shuō)說(shuō)就是，，每次從從OPEN表中中取出第第一個(gè)節(jié)節(jié)點(diǎn)進(jìn)行行擴(kuò)展，，生成的的新節(jié)點(diǎn)點(diǎn)放到OPEN表中，，然后按按照某種種原則對(duì)對(duì)OPEN表進(jìn)進(jìn)行排序序。不同的排排序原則則構(gòu)成了了不同的的圖搜索索算法。。值得注意意的是算算法成功功結(jié)束的的判斷方方法，是是當(dāng)從OPEN表中取取出一個(gè)個(gè)節(jié)點(diǎn)后后，再判判斷該節(jié)節(jié)點(diǎn)是否否是目標(biāo)標(biāo)節(jié)點(diǎn)，，而不是是在擴(kuò)展展節(jié)點(diǎn)，，生成新新節(jié)點(diǎn)時(shí)時(shí)判斷。。這一點(diǎn)點(diǎn)一定要要注意，，在后面面將可以以看到，，這是構(gòu)構(gòu)成某些些最優(yōu)算算法的關(guān)關(guān)鍵所在在。37算法解釋釋這個(gè)過(guò)程程是在第第8步要要對(duì)OPEN表表上的節(jié)節(jié)點(diǎn)進(jìn)行行排序，，以便在在第4步步能選出出一個(gè)““最好””的節(jié)點(diǎn)點(diǎn)優(yōu)先擴(kuò)擴(kuò)展。不不同的排排序方法法便可構(gòu)構(gòu)成形式式多樣的的專門(mén)搜搜索算法法，這在在后面還還要進(jìn)一一步討論論。如果選出出待擴(kuò)展展的節(jié)點(diǎn)點(diǎn)是目標(biāo)標(biāo)節(jié)點(diǎn)，，則算法法在第5步成功功結(jié)束，，并可根根據(jù)回溯溯到s的的指針給給出解路路徑。如如果某個(gè)個(gè)循環(huán)中中，搜索索樹(shù)不再再剩有待待選的節(jié)節(jié)點(diǎn)，即即OPEN表變變空時(shí)，，則過(guò)程程失敗結(jié)結(jié)束，問(wèn)問(wèn)題找不不到解。。38算法解釋釋現(xiàn)在說(shuō)明明一下第第7步中中標(biāo)記和和修改指指針的問(wèn)問(wèn)題。如果要搜搜索的隱隱含圖是是一棵樹(shù)樹(shù)，則可可肯定第第6步生生成的后后繼節(jié)點(diǎn)點(diǎn)不可能能是以前前生成過(guò)過(guò)的，這這時(shí)搜索索圖就是是搜索樹(shù)樹(shù)，不存存在mk、ml這種類型型的子節(jié)節(jié)點(diǎn)，因因此不必必進(jìn)行修修改指針針的操作作。如果要搜搜索的隱隱含圖不不是一棵棵樹(shù)，則則有可能能出現(xiàn)這這樣的的子節(jié)點(diǎn)點(diǎn)，就是是說(shuō)這時(shí)時(shí)又發(fā)現(xiàn)現(xiàn)了到達(dá)達(dá)的新通通路，這這樣就要要比較不不同路徑徑的耗散散值，把把指針修修改到具具有較小小耗散值值的路徑徑上。39例如，下下圖所示示的兩個(gè)個(gè)搜索圖圖中，實(shí)實(shí)心圓點(diǎn)點(diǎn)在CLOSED表中（已已擴(kuò)展過(guò)過(guò)的節(jié)點(diǎn)點(diǎn)），空空心圓點(diǎn)點(diǎn)則在OPEN表中（待待擴(kuò)展點(diǎn)點(diǎn)）。先設(shè)下一一步輪到到要擴(kuò)展節(jié)點(diǎn)點(diǎn)6，并設(shè)生生成的兩兩個(gè)子節(jié)節(jié)點(diǎn)，其其中有一一個(gè)4已在OPEN中，那么么原先路路徑（s→3→→2→4）耗散值值為5（設(shè)每段段路徑均均為單位位耗散）），新路路徑（s→6→→4）的耗散散值為4，所以4的指針應(yīng)應(yīng)由指向向2修正到指指向6，如圖2.5（a）所示。。接著設(shè)下下一循環(huán)環(huán)要擴(kuò)展節(jié)點(diǎn)點(diǎn)1，若節(jié)點(diǎn)點(diǎn)1只生成一一個(gè)子節(jié)節(jié)點(diǎn)2（它已在在CLOSED上），顯顯然這時(shí)時(shí)節(jié)點(diǎn)2原先指向向節(jié)點(diǎn)3的指針，，要修改改到指向向節(jié)點(diǎn)1，由此又又引起子節(jié)點(diǎn)3的指針又又修改為為指向2，如圖2.5（b）所示。。401.3無(wú)無(wú)信息息圖搜索索過(guò)程無(wú)信息圖圖搜索屬屬于盲目目搜索，，這里給給兩種常常用的無(wú)無(wú)信息圖圖搜索方方法：深度優(yōu)先先搜索寬度優(yōu)先先搜索41所謂深度度優(yōu)先搜搜索，就就是在每每次擴(kuò)展展一個(gè)節(jié)節(jié)點(diǎn)時(shí)，，選擇到到目前為為止深度度最深的的節(jié)點(diǎn)優(yōu)優(yōu)先擴(kuò)展展。第7步中中的ADD（mj，OPEN）表表示將被被擴(kuò)展節(jié)節(jié)點(diǎn)n的的所有新新子節(jié)點(diǎn)點(diǎn)mj加到OPEN表表的前面面。開(kāi)始始時(shí)，OPEN表中只只有一個(gè)個(gè)初始節(jié)節(jié)點(diǎn)s，，s被擴(kuò)擴(kuò)展，其其子節(jié)點(diǎn)點(diǎn)被放入入OPEN表中中。在算法的的第3步步，OPEN表表的第一一個(gè)元素素(設(shè)為為n)被被取出擴(kuò)擴(kuò)展，這這時(shí)節(jié)點(diǎn)點(diǎn)n的深深度在OPEN表中是是最大的的，OPEN表表中的其其他節(jié)點(diǎn)點(diǎn)的深度度都不會(huì)會(huì)超過(guò)n的深度度。n的的子節(jié)點(diǎn)點(diǎn)被放到到OPEN表的的最前面面。由于于子節(jié)點(diǎn)點(diǎn)的深度度要大于于父節(jié)點(diǎn)點(diǎn)的深度度，實(shí)際際上OPEN表表是按照照節(jié)點(diǎn)的的深度進(jìn)進(jìn)行排序序的，深深度深的的節(jié)點(diǎn)被被排在了了前面，，而深度度淺的節(jié)節(jié)點(diǎn)被放放在了后后面。這這樣當(dāng)下下一個(gè)循循環(huán)再次次取出OPEN表的第第一個(gè)元元素時(shí)，，實(shí)際上上選擇的的就是到到目前為為止深度度最深的的節(jié)點(diǎn)，，從而實(shí)實(shí)現(xiàn)了深深度優(yōu)先先的搜索索策略。。42一般情況況下，當(dāng)當(dāng)問(wèn)題有有解時(shí)，，深度優(yōu)優(yōu)先搜索索不但不不能保證證找到最最優(yōu)解，，也不能能保證一一定能找找到解。。如果問(wèn)問(wèn)題的狀狀態(tài)空間間是有限限的，則則可以保保證找到到解，當(dāng)當(dāng)問(wèn)題的的狀態(tài)空空間是無(wú)無(wú)限的時(shí)時(shí)，則可可能陷入入"深淵淵"，而而找不到到解。為為此，像像回溯算算法一樣樣，可以以加上對(duì)搜搜索的深深度限制制。其方法法是在算算法的第第7步，，當(dāng)節(jié)點(diǎn)點(diǎn)的深度度達(dá)到限限制深度度時(shí)，則則不將其其子節(jié)點(diǎn)點(diǎn)加入到到OPEN表中中，從而而實(shí)現(xiàn)對(duì)對(duì)搜索深深度的限限制。當(dāng)當(dāng)然，這這個(gè)深度度限制應(yīng)應(yīng)該設(shè)置置的合適適，深度度過(guò)深影影響搜索索的效率率，而深深度過(guò)淺淺，則可可能影響響找到問(wèn)問(wèn)題的解解。43回溯和深深度優(yōu)先先的區(qū)別別在有些書(shū)書(shū)上所講講的深度度優(yōu)先實(shí)實(shí)際上指指的是我我們這里里所說(shuō)的的回溯策策略，在在本書(shū)中中還是將將二者區(qū)區(qū)分開(kāi)來(lái)來(lái)。從形形式上來(lái)來(lái)說(shuō)，二二者確實(shí)實(shí)很相似似，所表表現(xiàn)出來(lái)來(lái)的都是是每次選選擇深度度最深的的節(jié)點(diǎn)首首先擴(kuò)展展。但二二者還是是有區(qū)別別的，這這里所說(shuō)說(shuō)的深度度優(yōu)先屬屬于圖搜搜索策略略，不足足是占用用較多的的存儲(chǔ)空空間，好好處是對(duì)對(duì)于特殊殊的問(wèn)題題，可能能會(huì)提高高搜索的的效率。。44設(shè)某問(wèn)題題的狀態(tài)態(tài)空間如如圖所示示。從圖圖中可以以看出該該問(wèn)題的的特點(diǎn)：：初始節(jié)節(jié)點(diǎn)有若若干個(gè)子子節(jié)點(diǎn)，，每個(gè)子子節(jié)點(diǎn)都都鏈接到到三條很很深的路路徑中，，而目標(biāo)標(biāo)假定在在最右邊邊的路徑徑中。當(dāng)當(dāng)采用回回溯策略略時(shí)，由由于回溯溯策略只只保留從從初始節(jié)節(jié)點(diǎn)到當(dāng)當(dāng)前節(jié)點(diǎn)點(diǎn)的一條條路徑，，所以從從第一個(gè)個(gè)子節(jié)點(diǎn)點(diǎn)（從左左數(shù)）進(jìn)進(jìn)入第一一條路徑徑搜索（（從左遍遍數(shù)），，回溯后后，又進(jìn)進(jìn)入第二二條路徑徑。由于于沒(méi)有找找到解，，又回溯溯到第二二個(gè)子節(jié)節(jié)點(diǎn)。從從第二個(gè)個(gè)子節(jié)點(diǎn)點(diǎn)，同樣樣要搜索索第一條條路徑、、第二條條路徑。。第三個(gè)個(gè)字節(jié)點(diǎn)點(diǎn)、第四四個(gè)子節(jié)節(jié)點(diǎn)………也都同同樣。這這樣，第第一和第第二條路路徑將被被多次搜搜索，影影響了搜搜索的效效率。而而對(duì)于深深度優(yōu)先先策略（（單指這這里所說(shuō)說(shuō)的圖搜搜索深度度優(yōu)先）），由于于保留了了所有已已經(jīng)搜索索過(guò)的路路徑，當(dāng)當(dāng)通過(guò)第第一個(gè)節(jié)節(jié)點(diǎn)搜索索了第一一、第二二條路徑徑后，當(dāng)當(dāng)通過(guò)第第二個(gè)子子節(jié)點(diǎn)搜搜索時(shí)，，由于第第一、第第二條路路徑已經(jīng)經(jīng)被搜索索，并且且被記錄錄了，所所以就不不必重復(fù)復(fù)搜索了了，提高高了搜索索的效率率。這一一點(diǎn)在算算法中是是如何體體現(xiàn)出來(lái)來(lái)的呢？？關(guān)鍵是是算法的的第7步步，在n的子節(jié)節(jié)點(diǎn)中，，只將mj類節(jié)點(diǎn)加加入到了了OPEN表中中，而對(duì)對(duì)于mk類節(jié)點(diǎn)和和ml類節(jié)點(diǎn)則則不予考考慮。45深度優(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((mj,OPEN)),并并標(biāo)記mj到n的指指針;10,GOLOOP;46231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)47深度優(yōu)先先搜索的的性質(zhì)一般不能能保證找找到最優(yōu)優(yōu)解當(dāng)深度限限制不合合理時(shí)，，可能找找不到解解，可以以將算法法改為可可變深度度限制最壞情況況時(shí)，搜搜索空間間等同于于窮舉與回溯法法的差別別：圖搜搜索是一個(gè)通通用的與與問(wèn)題無(wú)無(wú)關(guān)的方方法48寬度優(yōu)先先搜索同深度優(yōu)優(yōu)先算法法一樣，，寬度優(yōu)優(yōu)先算法法也是從從一般的的圖搜索索算法變變化而成成。在深深度優(yōu)先先搜索中中，每次次選擇深深度最深深的節(jié)點(diǎn)點(diǎn)首先擴(kuò)擴(kuò)展，而而寬度優(yōu)優(yōu)先搜索索則正好好相反，，每次選選擇深度最淺淺的節(jié)點(diǎn)優(yōu)優(yōu)先擴(kuò)展展。與深深度優(yōu)先先算法不不同的只只是第7步，這里里ADD（OPEN，mj）表示將將mj類子節(jié)點(diǎn)點(diǎn)放到OPEN表的后邊邊，從而而實(shí)現(xiàn)了了對(duì)OPEN表中的元元素按節(jié)節(jié)點(diǎn)深度度排序，，只不過(guò)過(guò)這次將將深度淺淺的節(jié)點(diǎn)點(diǎn)放在OPEN表的前面面了，而而深度深深的節(jié)點(diǎn)點(diǎn)被放在在了OPEN表的后邊邊。當(dāng)問(wèn)問(wèn)題有解解時(shí)，寬寬度優(yōu)先先算法不不但能一一定找到到解，而而且在單單位耗散散的情況況下，可可以保證證找到最最優(yōu)解。。49寬度優(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,EXPAND((n)→→{mi},G:=ADD((mi,G));7,IF目目標(biāo)在{{mi}中THENEXIT((SUCCESS);;8,ADD((OPEN,mj),并標(biāo)記mj到n的指指針;9,GOLOOP;5023184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)823418765451寬度優(yōu)先先搜索的的性質(zhì)當(dāng)問(wèn)題有有解時(shí)，，一定能能找到解解當(dāng)問(wèn)題為為單位耗耗散值，，且問(wèn)題題有解時(shí)時(shí)，一定定能找到到最優(yōu)解解方法與問(wèn)問(wèn)題無(wú)關(guān)關(guān)，具有有通用性性效率較低低屬于圖搜搜索方法法521.4啟啟發(fā)式式圖搜索索利用知識(shí)識(shí)來(lái)引導(dǎo)導(dǎo)搜索，，達(dá)到減減少搜索索范圍，，降低問(wèn)問(wèn)題復(fù)雜雜度的目目的。啟發(fā)信息息的強(qiáng)度度強(qiáng)：降低低搜索工工作量，，但可能能導(dǎo)致找找不到最最優(yōu)優(yōu)解解弱：一般般導(dǎo)致工工作量加加大，極極限情況況下變?yōu)闉槊っつ克阉魉?，但可可能可以以找到最最?yōu)解53希望：引入啟發(fā)發(fā)知識(shí)，，在保證證找到最最佳解的的情況下下，盡可可能減少少搜索范范圍，提提高搜索索效率。。54基本思想想啟發(fā)式搜搜索過(guò)程程中，要要對(duì)OPEN表表進(jìn)行排排序，這這就需要要有一種種方法來(lái)來(lái)計(jì)算待待擴(kuò)展節(jié)節(jié)點(diǎn)有希希望通向向目標(biāo)節(jié)節(jié)點(diǎn)的不不同程度度，我們們總是希希望能找找到最有有希望通通向目標(biāo)標(biāo)節(jié)點(diǎn)的的待擴(kuò)展展節(jié)點(diǎn)優(yōu)優(yōu)先擴(kuò)展展。一種最常常用的方方法是定定義一個(gè)個(gè)評(píng)價(jià)函函數(shù)f（（Evaluationfunction）對(duì)對(duì)各個(gè)子子節(jié)點(diǎn)進(jìn)進(jìn)行計(jì)算算，其目目的就是是用來(lái)估估算出““有希望望”的節(jié)節(jié)點(diǎn)來(lái)。。定義一個(gè)個(gè)評(píng)價(jià)函函數(shù)可以以參考的的原則有有：一個(gè)個(gè)節(jié)點(diǎn)處處在最佳佳路徑上上的概率率；求出出任意一一個(gè)節(jié)點(diǎn)點(diǎn)與目標(biāo)標(biāo)節(jié)點(diǎn)集集之間的的距離度度量或差差異度量量；根據(jù)據(jù)格局（（博弈問(wèn)問(wèn)題）或或狀態(tài)的的特點(diǎn)來(lái)來(lái)打分。。即根據(jù)據(jù)問(wèn)題的的啟發(fā)信信息，從從概率角角度、差差異角度度或記分分法給出出計(jì)算評(píng)評(píng)價(jià)函數(shù)數(shù)的方法法。551.啟啟發(fā)式搜搜索算法法A（A算法））啟發(fā)式搜搜索算法法A，一般簡(jiǎn)簡(jiǎn)稱為A算法，是是一種典典型的啟啟發(fā)式搜搜索算法法。其基本思思想是：：定義一一個(gè)評(píng)價(jià)價(jià)函數(shù)f，對(duì)當(dāng)前前的搜索索狀態(tài)進(jìn)進(jìn)行評(píng)估估，找出出一個(gè)最最有希望望的節(jié)點(diǎn)點(diǎn)來(lái)擴(kuò)展展。評(píng)價(jià)函數(shù)數(shù)的格式式：f(n))=g(n)++h((n)f(n))：評(píng)價(jià)價(jià)函數(shù)h(n))：?jiǎn)l(fā)發(fā)函數(shù)56符號(hào)的意意義g*(n)：從s到n的最短路路徑的耗耗散值h*(n)：從n到g的最短路路徑的耗耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過(guò)n到g的最短路路徑的耗耗散值g(n))、h(n))、f(n))分別是g*(n)、h*(n)、f*(n)的估計(jì)值值,是一種預(yù)預(yù)測(cè)。A算法就是是利用這這種預(yù)測(cè)測(cè)，來(lái)達(dá)達(dá)到有效效搜索的的目的的的。它每每次按照照f(shuō)(n)值的大小小對(duì)OPEN表中的元元素進(jìn)行行排序，，f值小的節(jié)節(jié)點(diǎn)放在在前面，，而f值大的節(jié)節(jié)點(diǎn)則被被放在OPEN表的后面面，這樣樣每次擴(kuò)擴(kuò)展節(jié)點(diǎn)點(diǎn)時(shí)，都都是選擇擇當(dāng)前f值最小的的節(jié)點(diǎn)來(lái)來(lái)優(yōu)先擴(kuò)擴(kuò)展。57A算法利用評(píng)價(jià)價(jià)函數(shù)f（n））＝g（（n）＋＋h（n）來(lái)排排列OPEN表表節(jié)點(diǎn)順順序的圖圖搜索算算法稱為為A算法法。58A算法過(guò)程

1,OPEN:=((s),,f((s)::=g((s)++h(s);2,LOOP:IFOPEN=())THENEXIT((FAIL);;3,n:=FIRST(OPEN);4,IFGOAL(n))THENEXIT(SUCCESS);5,REMOVE((n,OPEN),,ADD(n,CLOSED));6,EXPAND((n)→→{mi},//{mi}={mj}∪{mk}∪{ml}①計(jì)算f((n,mi):=g(n,,mi)+h((mi);//g（n，mi）是從s通過(guò)n到mi的耗散值值，f（n，mi）是從s通過(guò)n、mi到目標(biāo)節(jié)節(jié)點(diǎn)耗散散值的估估計(jì)。59A算法（（續(xù)）②ADD((mj,OPEN)),標(biāo)標(biāo)記mj到n的指指針；③IFf(n,,mk)<f((mk)THENf(mk):=f(n,,mk),標(biāo)記mk到n的指指針；//比比較f（n,,mk）和f（（mk），f（mk）是擴(kuò)展展n之前前計(jì)算的的耗散值值。④IFf(n,,ml)<f((ml)THENf(ml):=f(n,,ml),標(biāo)記ml到n的指指針,ADD(ml,OPEN));7,OPEN中的節(jié)點(diǎn)點(diǎn)按f值值從小到到大排序序；8,GOLOOP；60A算法同同樣由一一般的圖圖搜索算算法改變變而成。。在算法法的第7步，按按照f(shuō)值值從小到到大對(duì)OPEN表中的的節(jié)點(diǎn)進(jìn)進(jìn)行排序序，體現(xiàn)現(xiàn)了A算算法的含含義。算法要計(jì)計(jì)算f((n)、、g(n)和h(n))的值，，g(n)根據(jù)據(jù)已經(jīng)搜搜索的結(jié)結(jié)果，按按照從初初始節(jié)點(diǎn)點(diǎn)s到節(jié)節(jié)點(diǎn)n的的路徑，，計(jì)算這這條路徑徑的耗散散值就可可以了。。而h((n)是是與問(wèn)題題有關(guān)的的，需要要根據(jù)具具體的問(wèn)問(wèn)題來(lái)定定義。有有了g((n)和和h(n)的值值，將他他們加起起來(lái)就得得到f((n)的的值。注意A算算法的結(jié)結(jié)束條件件：當(dāng)從從OPEN中取取出第一一節(jié)點(diǎn)時(shí)時(shí)，如果果該節(jié)點(diǎn)點(diǎn)是目標(biāo)標(biāo)節(jié)點(diǎn)，，則算法法成功結(jié)結(jié)束。而而不是在在擴(kuò)展一一個(gè)節(jié)點(diǎn)點(diǎn)時(shí)，只只要目標(biāo)標(biāo)節(jié)點(diǎn)一一出現(xiàn)就就立即結(jié)結(jié)束。我我們?cè)诤蠛竺鎸?huì)會(huì)看到，，正是由由于有了了這樣的的結(jié)束判判斷條件件，才使使得A算算法有很很好的性性質(zhì)。61算法中f（n））規(guī)定為為對(duì)從初初始節(jié)點(diǎn)點(diǎn)s出發(fā)發(fā)，約束束通過(guò)節(jié)節(jié)點(diǎn)n到到達(dá)目標(biāo)標(biāo)點(diǎn)t，，最小耗耗散值路路徑的耗耗散值f*(n)的估估計(jì)值，，通常取取正值。。f（n））由兩個(gè)個(gè)分量組組成，其其中g(shù)（（n）是是到目前前為止，，從s到到n的一一條最小小耗散值值路徑的的耗散值值，是作作為從s到n最最小耗散散值路徑徑的耗散散值g**(n))的估計(jì)計(jì)值，h（n））是從n到目標(biāo)標(biāo)節(jié)點(diǎn)t，最小小耗散值值路徑的的耗散值值h*((n)的的估計(jì)值值。62一個(gè)A算算法的例例子定義評(píng)價(jià)價(jià)函數(shù)：：f(n))=g(n)++h((n)g(n))為從初初始節(jié)點(diǎn)點(diǎn)到當(dāng)前前節(jié)點(diǎn)的的耗散值值h(n))為當(dāng)前前節(jié)點(diǎn)““不在位位”的將將牌數(shù)

283164751238476563h計(jì)算舉舉例h(n))=42831647512345768642831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4))A(6))B(4))C(6))D(5))E(5))F(6))G(6))H(7))I(5))J(7))K(5))L(5))M(7))目標(biāo)12345665根據(jù)目標(biāo)標(biāo)節(jié)點(diǎn)L返回到s的指針，，可得解解路徑S(4))，B(4))，E(5))，I(5))，K(5))，L(5))662．爬山山法爬山法（（局部搜搜索算法法）672．爬山山法過(guò)程Hill--climbing①n::=s；；s為初初始節(jié)點(diǎn)點(diǎn)

②LOOP：IFGOAL（n））THENEXIT(SUCCESS)；③③EXPAND（（n）→→{mi}，計(jì)算算h(mi)，nextn:=m(minh(mi)的節(jié)點(diǎn)點(diǎn))；④④IFh(n))<h((nextn))THENEXIT(FAIL);⑤⑤n:=nextn；⑥⑥GOLOOP；顯顯然如果果將山頂頂作為目目標(biāo)，h(n))表示山山頂與當(dāng)當(dāng)前位置置n之間間高度之之差，則則該算法法相當(dāng)于于總是登登向山頂頂，在單單峰的條條件下，，必能到到達(dá)山峰峰。683．分支支界限法法分支界限限法是優(yōu)優(yōu)先擴(kuò)展展當(dāng)前具具有最小小耗散值值分支路路徑的端端節(jié)點(diǎn)n，其評(píng)評(píng)價(jià)函數(shù)數(shù)為f((n)==g(n)。該該算法的的基本思思想很簡(jiǎn)簡(jiǎn)單，實(shí)實(shí)際上是是建立一一個(gè)局部部路徑（（或分支支）的隊(duì)隊(duì)列表，，每次都都選耗散散值最小小的那個(gè)個(gè)分支上上的端節(jié)節(jié)點(diǎn)來(lái)擴(kuò)擴(kuò)展，直直到生成成出含有有目標(biāo)節(jié)節(jié)點(diǎn)的路路徑為止止。69過(guò)程Branch-Bound①Q(mào)UEUE:=((s-s)，g(s))=0;;

②LOOP：IFQUEUE=(()THENEXIT(FAIL));③③PATH::=FIRST(QUEUE)，n:=LAST(PATH));④④IFGOAL((n)THENEXIT(SUCCESS));⑤⑤EXPAND(n)→{{mi}}，計(jì)算算g(mi)==g(n，mi)，REMOVE（（s--n，，QUEUE）），ADD((s-mi，QUEUE);;

⑥QUEUE中中局部路路徑g值值最小者者排在前前面；⑦⑦GOLOOP；70應(yīng)用分支支界限法法求下圖圖的最短短路徑，，求解過(guò)過(guò)程中QUEUE的結(jié)結(jié)果簡(jiǎn)記記如下（（D(4)代表表耗散值值為4的的s-D分支，，其余類類推）：：g=771初始（s(0))）1.（A（3））D（4））2.（（D（4）B（（7）D（8）））3.（E（6））B（7）D（（8）A（9）））4.（B（7））D（8）A（（9）F（10）B（（11）））5.（D（8））A（9）F（（10））B（11）C（11）E（（12）））6.（A（9））E（10）F（10）B（（11））C（11）E（12））7.（（E（10）F（10）B（（11））C（11）E（12）B（（13）））8.（F（10）B（（11））C（11）E（12）B（（13））F（14）B（15））9.（（B（11）C（11）E（（12））t（13）B（13）F（（14））B（15）））

10.（C（11）E（（12））t（13）B（13）F（（14））A（15）B（15）C（（15）））11.（（E（12）t（13）B（（13））F（14）A（15）B（（15））C（15）））

12.（t（13）B（（13））F（14）D（14）A（（15））B（15）C（15）F（（16）））13.結(jié)結(jié)束。724．動(dòng)態(tài)態(tài)規(guī)劃法法在A算法法中，當(dāng)當(dāng)h(n)≡0時(shí)，則則A算法法演變?yōu)闉閯?dòng)態(tài)規(guī)規(guī)劃算法法。由于于在A算算法中，，很多問(wèn)問(wèn)題的啟啟發(fā)函數(shù)數(shù)h難于于定義，，因此動(dòng)動(dòng)態(tài)規(guī)劃劃算法是是至今一一直被經(jīng)經(jīng)常使用用的算法法。734．動(dòng)態(tài)態(tài)規(guī)劃法法動(dòng)態(tài)規(guī)劃劃法實(shí)際際上是對(duì)對(duì)分支界界限法的的改進(jìn)。。從圖2.9看出，第第二循環(huán)環(huán)擴(kuò)展A（3）后生成成的D（8）節(jié)點(diǎn)（（D（4）已在QUEUE上）和第第三循環(huán)環(huán)擴(kuò)展D（4）之后生生成的A（9）節(jié)點(diǎn)（（A（3）已以QUEUE上）都是是多余的的分支，，因?yàn)橛捎蓅－D到達(dá)目標(biāo)標(biāo)的路徑徑顯然要要比s－A－D到達(dá)目標(biāo)標(biāo)的路徑徑要好。。因此刪刪去類似似于s－A－D或s－D－A這樣一些些多余的的路徑將將會(huì)大大大提高搜搜索效率率。動(dòng)態(tài)態(tài)規(guī)劃原原理指出出，求s→t的最佳路路徑時(shí)，，對(duì)某一一個(gè)中間間節(jié)點(diǎn)I，只要考考慮s到I中最小耗耗散值這這一條局局部路徑徑就可以以，其余余s到I的路徑是是多余的的，不必必加以考考慮。74動(dòng)態(tài)規(guī)劃劃st第一階段段第二階段段第三階段段第四階段段第五階段段754．動(dòng)態(tài)態(tài)規(guī)劃法法過(guò)程Dynamic--Programming①Q(mào)UEUE:=((s-s)，g(s))=0;;

②LOOP：IFQUEUE=（（）THENEXIT(FAIL));③③PATH::=FIRST(QUEUE)，n:=LAST(PATH));④④IFGOAL((n)THENEXIT(SUCCESS));⑤⑤EXPAND(n)→{{mi}}，計(jì)算算g(mi)==g(n，mi)，REMOVE（（s-n，QUEUE），ADD((s-mi，QUEUE);;

⑥若若QUEUE中有多多條到達(dá)達(dá)某一公公共節(jié)點(diǎn)點(diǎn)的路徑徑，則只只保留耗耗散值最最小的那那條路徑徑，其余余刪去，，并重新新排序，，g值最最小者排排在前面面；⑦⑦GOLOOP；；765.最佳佳圖搜索索算法A*（OptimalSearch））當(dāng)在算法法A的評(píng)價(jià)函函數(shù)中，，使用的的啟發(fā)函函數(shù)h(n)是處在h﹡（n）的下界界范圍，，即滿足足h(n)≤h*(n)時(shí)，則我我們把這這個(gè)算法法稱為算算法A﹡。775.A*算法法A﹡算法實(shí)際際上是分分支界限限和動(dòng)態(tài)態(tài)規(guī)劃原原理及使使用下界界范圍的的h相結(jié)合的的算法。。當(dāng)問(wèn)題有有解時(shí)，，A﹡一定能找找到一條條到達(dá)目目標(biāo)節(jié)點(diǎn)點(diǎn)的最佳佳路徑。。例如在在極端情情況下，，若h(n))≡0（肯定滿滿足下界界范圍條條件），，因而一一定能找找到最佳佳路徑;若g≡d，則算法法等同于于寬度優(yōu)優(yōu)先算法法。前面面已提到到過(guò)，寬寬度優(yōu)先先算法能能保證找找到一條條到達(dá)目目標(biāo)節(jié)點(diǎn)點(diǎn)最小長(zhǎng)長(zhǎng)度的路路徑，因因而這個(gè)個(gè)特例從從直觀上上就驗(yàn)證證了A﹡的一般結(jié)結(jié)論。一般地說(shuō)說(shuō)對(duì)任意意一個(gè)圖圖，當(dāng)s到目標(biāo)節(jié)節(jié)點(diǎn)有一一條路徑徑存在時(shí)時(shí)，如果果搜索算算法總是是在找到到一條從從s到目標(biāo)節(jié)節(jié)點(diǎn)的最最佳路徑徑上結(jié)束束，則稱稱該搜索索算法是是可采納納的（Admissibility）。A﹡就具有可可采納性性。78對(duì)于以下下的定理理、引理理和推論論，我們們只要求求掌握其其結(jié)論和和含義，，不要求求掌握其其具體的的證明過(guò)過(guò)程。但但是證明明過(guò)程有有助于你你對(duì)算法法的理解解。以下定理理的證明明，正文文部分是是嚴(yán)格的的，而解解釋部分分，則不不是嚴(yán)格格的證明明，只是是從直觀觀上，或或者從思思路上進(jìn)進(jìn)行說(shuō)明明。在以下的的定理證證明過(guò)程程中，要要明確這這樣幾個(gè)個(gè)關(guān)系：：f*(s)=f*(t)=h*(s)，其中s是初始節(jié)節(jié)點(diǎn)，t是目標(biāo)節(jié)節(jié)點(diǎn)（有有時(shí)也用用g表示）。。當(dāng)n是從初始始節(jié)點(diǎn)到到目標(biāo)節(jié)節(jié)點(diǎn)t的最優(yōu)路路徑上的的節(jié)點(diǎn)時(shí)時(shí)，f*(n)=f*((s)==f*((t)==h*((s)。5.A*算法法79A*算法法的性質(zhì)質(zhì)（續(xù)1）定理1..1：對(duì)有限圖圖，如果果從初始始節(jié)點(diǎn)s到目標(biāo)標(biāo)節(jié)點(diǎn)t有路徑徑存在，，則算法法A一定定成功結(jié)結(jié)束。證明：設(shè)設(shè)A搜索索失敗，，則算法法在第2步結(jié)束束，OPEN表表變空，，而CLOSED表中中的節(jié)點(diǎn)點(diǎn)是在結(jié)結(jié)束之前前被擴(kuò)展展過(guò)的節(jié)節(jié)點(diǎn)。由由于圖有有解，令令（n0=s，，n1，，n2，，…，nk=t）表示示某一解解路徑，，我們從從nk開(kāi)開(kāi)始逆向向逐個(gè)檢檢查該序序列的節(jié)節(jié)點(diǎn)，找找到出現(xiàn)現(xiàn)在CLOSED表中中的節(jié)點(diǎn)點(diǎn)ni，，即niCLOSED，ni+1CLOSED（ni一定定能找到到，因?yàn)闉閚0CLOSED，nkCLOSED）。。由于ni在CLOSES中中，必定定在第6步被擴(kuò)擴(kuò)展，且且ni++1被加加到OPEN中中，因此此在OPEN表表空之前前，ni+1已已被處理理過(guò)。若若ni++1是目目標(biāo)節(jié)點(diǎn)點(diǎn)，則搜搜索成功功，否則則它被加加入到CLOSED中中，這兩兩種情況況都與搜搜索失敗敗的假設(shè)設(shè)矛盾，，因此對(duì)對(duì)有限圖圖不失敗敗則成功功。[證證畢]80A*算法法的性質(zhì)質(zhì)（續(xù)2）引理1..1：：對(duì)無(wú)限圖圖，若有有從初始始節(jié)點(diǎn)s到目標(biāo)標(biāo)節(jié)點(diǎn)t的路徑徑，則A*不結(jié)結(jié)束時(shí)，，在OPEN表表中即使使最小的的一個(gè)f值也將將增到任任意大，，或有f(n))>f**(s))。該引理的的證明中中，隱含含了兩個(gè)個(gè)假設(shè)：：（1））任何兩兩個(gè)節(jié)點(diǎn)點(diǎn)之間的的耗散值值都大于于某個(gè)給給定的大大于零的的常量；；（2））h(n)對(duì)于于任何n來(lái)說(shuō)，，都大于于等于零零。由由于當(dāng)當(dāng)問(wèn)題有有解存在在時(shí)，從從初始節(jié)節(jié)點(diǎn)到目目標(biāo)節(jié)點(diǎn)點(diǎn)的路徑徑的耗散散值總是是一個(gè)有有限的常常量。那那么在該該解路徑徑上的任任何一個(gè)個(gè)節(jié)點(diǎn)n，由于于f(n)=g(n))+h((n)，，而g((n)是是有限的的，h((n)≤≤h*((n)也也是有限限的（因因?yàn)閔**(n))有限）），所以以f(n)也是是有限的的。而對(duì)對(duì)于一個(gè)個(gè)無(wú)限圖圖來(lái)說(shuō)，，那些不不在解路路徑上的的無(wú)限路路徑，隨隨著搜索索的進(jìn)行行，其耗耗散值總總會(huì)趨于于無(wú)窮大大，因此此那些在在解路徑徑上的節(jié)節(jié)點(diǎn)的f值值總會(huì)變變得最小小，總會(huì)會(huì)有機(jī)會(huì)會(huì)被排在在OPEN表的的第一個(gè)個(gè)位置，，從而被被A*擴(kuò)擴(kuò)展。而而目標(biāo)節(jié)節(jié)點(diǎn)也是是解路徑徑上的一一個(gè)節(jié)點(diǎn)點(diǎn)，這樣樣它同樣樣會(huì)有機(jī)機(jī)會(huì)被排排在OPEN表表的第一一個(gè)位置置，從而而使得算算法成功功結(jié)束，，找到問(wèn)問(wèn)題的解解路徑。。81A*算法法的性質(zhì)質(zhì)（續(xù)2）引理1..2：：對(duì)無(wú)限圖圖，若有有從初始始節(jié)點(diǎn)s到目標(biāo)標(biāo)節(jié)點(diǎn)t的路徑徑，則A*不結(jié)結(jié)束時(shí)，，在OPEN表表中即使使最小的的一個(gè)f值也將將增到任任意大，，或有f(n))>f**(s))。證明：設(shè)設(shè)d﹡((n)是是A﹡生生成的搜搜索樹(shù)中中，從s到任一一節(jié)點(diǎn)n最短路路徑長(zhǎng)度度的值（（設(shè)每個(gè)個(gè)弧的長(zhǎng)長(zhǎng)度均為為1），，搜索圖圖上每個(gè)個(gè)弧的耗耗散值為為C(ni，ni+1)（C取正））。令e=minC(ni，ni+1))，則g﹡(n)≥d﹡(n)e。。而g((n)≥≥g﹡((n)≥≥d﹡((n)e，故有有：f(n))=g((n)++h(n)≥g(n))≥d﹡﹡(n))e（設(shè)設(shè)h(n)≥0）若若A﹡不不結(jié)束，，d﹡((n)趨趨向于∞，f值將將增到任任意大。。82A*算法法的性質(zhì)質(zhì)（續(xù)2）該引理可可以這樣樣來(lái)理解解：如果果問(wèn)題從從初始節(jié)節(jié)點(diǎn)s到到目標(biāo)節(jié)節(jié)點(diǎn)g的的路徑存存在時(shí)，，則一定定有一個(gè)個(gè)最短路路徑存在在。在A*沒(méi)有有結(jié)束之之前，OPEN表中的的節(jié)點(diǎn)不不會(huì)為空空。由于于總是從從OPEN表中中取出節(jié)節(jié)點(diǎn)來(lái)擴(kuò)擴(kuò)展，所所以最優(yōu)優(yōu)路徑肯肯定要通通過(guò)OPEN表表中的某某個(gè)節(jié)點(diǎn)點(diǎn)，設(shè)該該節(jié)點(diǎn)為為n。那那么n有有兩個(gè)特特點(diǎn)，一一是n是是從s到到g的最最優(yōu)路徑徑上的節(jié)節(jié)點(diǎn)，二二是到目目前為止止已經(jīng)找找到了從從s到n的最優(yōu)優(yōu)路徑。。第一點(diǎn)點(diǎn)會(huì)比較較容易接接受，第第二點(diǎn)是是如何保保證的呢呢？如果果到目前前為止找找到的不不是從s到n的的最優(yōu)路路徑，同同樣的理理由，在在OPEN表中中一定有有一個(gè)節(jié)節(jié)點(diǎn)---假定為為n'---在從從s到n的最優(yōu)優(yōu)路徑上上，當(dāng)然然他也一一定在從從s到g的最優(yōu)優(yōu)路徑上上。用n'來(lái)代代替n，，重復(fù)下下去，一一直找到到滿足以以上兩個(gè)個(gè)特點(diǎn)的的n為止止。當(dāng)然然，我們們不一定定明確的的知道到到底OPEN表表中的哪哪個(gè)節(jié)點(diǎn)點(diǎn)滿足這這樣的特特點(diǎn)，但但從以上上的敘述述可以知知道，這這樣的節(jié)節(jié)點(diǎn)一定定存在。。

對(duì)于于具有這這樣特點(diǎn)點(diǎn)的n，，由于以以上所說(shuō)說(shuō)的第一一個(gè)特點(diǎn)點(diǎn)有g(shù)((n)==g*((n)，，所以有有f(n)=g*(n)+h(n))，而由由于算法法是A**的，所所以有h(n))≤h**(n))，所以以f(n)=g*(n)+h(n))≤g**(n))+h**(n))=f**(n))=f**(s))。對(duì)于于最后一一個(gè)等式式，是由由于對(duì)于于任何兩兩個(gè)最優(yōu)優(yōu)路徑上上的節(jié)點(diǎn)點(diǎn)n1和和n2，，都有f*(n1)==f*((n2))，而n和s都都是最優(yōu)優(yōu)路徑上上的節(jié)點(diǎn)點(diǎn)。引理理1.2得證。。83A*算法法的性質(zhì)質(zhì)（續(xù)3）引理1..3：A*結(jié)束前，，OPEN表中中必存在在f(n)≤f*(s)的節(jié)節(jié)點(diǎn)（n是在最最佳路徑徑上的節(jié)節(jié)點(diǎn)）。證明：設(shè)設(shè)從初始始節(jié)點(diǎn)s到目標(biāo)節(jié)節(jié)點(diǎn)t的一條最最佳路徑徑序列為為：(n0==s，n1，…，nk=t)算法初始始化時(shí)，，s在OPEN中，由于于A﹡沒(méi)有結(jié)束束，在OPEN中存在最最佳路徑徑上的節(jié)節(jié)點(diǎn)。設(shè)設(shè)OPEN表中的某某節(jié)點(diǎn)n是處在最最佳路徑徑序列中中（至少少有一個(gè)個(gè)這樣的的節(jié)點(diǎn)，，因s一開(kāi)始是是在OPEN上），顯顯然n的先輩節(jié)節(jié)點(diǎn)np已在CLOSED中，因此此能找到到s到np的最佳路路徑，而而n也在最佳佳路徑上上，因而而s到n的最佳路路徑也能能找到，，因此有有f(n)=g(n))+h((n)=g**(n)+h(n))≤g*(n)+h*(n))=f**(n))而最佳路路徑上任任一節(jié)點(diǎn)點(diǎn)均有f*（n）=f*((s)（f*(s)是最佳路路徑的耗耗散值）），所以以f(n))≤f*(s))。[證畢]84A*算法法的性質(zhì)質(zhì)（續(xù)3）定理1..2：對(duì)無(wú)限圖圖，若從從初始節(jié)節(jié)點(diǎn)s到到目標(biāo)節(jié)節(jié)點(diǎn)t有有路徑存存在，則則A*一一定成功功結(jié)束。。證明：假假定A*不結(jié)束，，由引理理2.1有f(n)＞f*(s)，或OPEN表中最小小的一個(gè)個(gè)f值也變成成無(wú)界，，這與引引理2.2的結(jié)論矛矛盾，所所以A*只能成功功結(jié)束。。[證畢]85A*算法法的性質(zhì)質(zhì)（續(xù)4）推論1..1：OPEN表上任任一具有有f(n)<f*(s)的節(jié)節(jié)點(diǎn)n，，最終都都將被A*選作作擴(kuò)展的的節(jié)點(diǎn)。。由定理1.2，知A*一定結(jié)束束，由A*的結(jié)束條條件，OPEN表中f(t))最小時(shí)才才結(jié)束。。而f(t))≥f*(t)＝f*(s)所以f(n))<f**(s))的n，均被擴(kuò)展展。得證證。86A*算法法的性質(zhì)質(zhì)（續(xù)5）定理1..3((可采納納性定理理)：若存在從從初始節(jié)節(jié)點(diǎn)s到到目標(biāo)節(jié)節(jié)點(diǎn)t有有路徑，，則A**必能找找到最佳佳解結(jié)束束。87可采納性性的證明明由定理1.1、、1.2知A**一定找找到一條條路徑結(jié)結(jié)束設(shè)找到的的路徑s→t不是最最佳的（（t為目目標(biāo)）則：f((t)==g(t))>f*((s)由引理1.2知知結(jié)束前前OPEN中存存在f((n)≤≤f*((s)的的節(jié)點(diǎn)n，所以以f(n))≤f*((s)<<f(t))因此A**應(yīng)選擇擇n擴(kuò)展展，而不不是t。。與假設(shè)設(shè)A*選選擇t結(jié)結(jié)束矛盾盾。得證證。注意：A*的的結(jié)束條條件88A*算法法的性質(zhì)質(zhì)（續(xù)6）推論1..2：A*選作作擴(kuò)展的的任一節(jié)節(jié)點(diǎn)n，，有f((n)≤≤f*((s)。。由引理2.2知知在A**結(jié)束前前，OPEN中中存在節(jié)節(jié)點(diǎn)n’’，f(n’’)≤f*(s)設(shè)此時(shí)A*選擇擇n擴(kuò)展展。如果n＝＝n’，，則f((n)≤≤f*((s)，，得證。。如果n≠≠n’’，由于于A*選選擇n擴(kuò)擴(kuò)展，而而不是n’，所所以有f(n))≤f(n’)≤≤f*((s)。。得證。。89A*算法法的性質(zhì)質(zhì)（續(xù)7）定理1..4：設(shè)設(shè)對(duì)同一一個(gè)問(wèn)題題定義了了兩個(gè)A*算法法A1和A2，若A2比A1有較多的的啟發(fā)信信息，即即對(duì)所有有非目標(biāo)標(biāo)節(jié)點(diǎn)有有h2(n)>>h1(n)，，則在具具有一條條從s到到t的路路徑的隱隱含圖上上，搜索索結(jié)束時(shí)時(shí)，由A2所擴(kuò)展的的每一個(gè)個(gè)節(jié)點(diǎn)，，也必定定由A1所擴(kuò)展，，即A1擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)至至少和A2一樣多。。簡(jiǎn)寫(xiě)：如如果h2(n)>h1(n)((目標(biāo)標(biāo)節(jié)點(diǎn)除除外)，，則A1擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)節(jié)點(diǎn)數(shù)90A*算法法的性質(zhì)質(zhì)（續(xù)7）注意：在定理1.4中中，評(píng)價(jià)價(jià)指標(biāo)是是“擴(kuò)展展的節(jié)點(diǎn)點(diǎn)數(shù)”，，也就是是說(shuō)，同同一個(gè)節(jié)節(jié)點(diǎn)無(wú)論論被擴(kuò)展展多少次次，都只只計(jì)算一一次。91定理1..4的證證明使用數(shù)學(xué)學(xué)歸納法法，對(duì)節(jié)節(jié)點(diǎn)的深深度進(jìn)行行歸納（1）當(dāng)當(dāng)d(n)＝0時(shí)，即即只有一一個(gè)節(jié)點(diǎn)點(diǎn)，顯然然定理成成立。（2）設(shè)設(shè)d(n)≤k時(shí)定理理成立。。（歸納納假設(shè)））（3）當(dāng)當(dāng)d(n)=k+1時(shí)時(shí)，用反反證法。。設(shè)存在一一個(gè)深度度為k＋＋1的節(jié)節(jié)點(diǎn)n，，被A2擴(kuò)展，但但沒(méi)有被被A1擴(kuò)展。而而由假設(shè)設(shè)，A1擴(kuò)展了n的父節(jié)節(jié)點(diǎn)，即即n已經(jīng)經(jīng)被生成成了。因因此當(dāng)A1結(jié)束時(shí)，，n將被被保留在在OPEN中。。92定理1..4的證證明（續(xù)續(xù)1）所以有：：f1(n)≥≥f*(s)即：g1(n)++h1(n)≥≥f*(s)所以：h1(n)≥≥f*(s)--g1(n)另一方面面，由于于A2擴(kuò)展了n，有f2(n)≤≤f**(s))即：h2(n)≤≤f*(s)––g2(n)((A)由于d((n)==k時(shí)，，A2擴(kuò)展的節(jié)節(jié)點(diǎn)A1一定擴(kuò)展展，有g(shù)1(n)≤≤g2(n)((因?yàn)锳2的路A1均走到了了)所以：h1(n)≥≥f*(s)--g1(n)≥≥f*(s)––g2(n)((B)比較A、、B兩式式，有h1(n)≥≥h2(n)，，與定定理?xiàng)l件件矛盾。。故定理理得證。。933，A**算法的的改進(jìn)問(wèn)題的提提出：因A算法法第6步步對(duì)ml類節(jié)點(diǎn)可可能要重重新放回回到OPEN表表中，因因此可能能會(huì)導(dǎo)致致多次重重復(fù)擴(kuò)展展同一個(gè)個(gè)節(jié)點(diǎn)，，導(dǎo)致搜搜索效率率下降。。94s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子子：OPEN表CLOSED表s(10)s(10)A(7))B((8)C(9)A(7))s((10))B(8))C((9)G(14)A(5))C((9)G(14)C(9))G((12))