第1章搜索問(wèn)題什么是狀態(tài)空間？回溯策略。圖搜索策略無(wú)信息的圖搜索策略啟發(fā)式圖搜索策略A*算法。A*算法的性質(zhì)。搜索算法的討論。狀態(tài)空間計(jì)算機(jī)對(duì)傳統(tǒng)的問(wèn)題求解方法帶來(lái)了根本性的改變。傳統(tǒng)方法，由專家給出公式，使用者的任務(wù)是理解公式，應(yīng)用公式。有些問(wèn)題用傳統(tǒng)方法描述很困難,例如本節(jié)的幾個(gè)例子公式的推導(dǎo)需要很高的水平，與實(shí)際問(wèn)題相差較遠(yuǎn)，對(duì)應(yīng)用者要求很高。2.計(jì)算機(jī)利用自己強(qiáng)大的計(jì)算能力和存儲(chǔ)能力,采用”猜”的方式,試探法.能解決問(wèn)題的領(lǐng)域更廣,更結(jié)合實(shí)際.例智力游戲問(wèn)題：傳教士與野人渡河問(wèn)題傳教士與野人渡河問(wèn)題：有3個(gè)傳教士帶3個(gè)野人渡河，河的岸邊有一條船，每次最多可載2人，要求無(wú)論在河的哪一邊，野人的數(shù)目不能超過(guò)傳教士的數(shù)目，問(wèn)為安全起見(jiàn)，應(yīng)如何安排傳教士與野人渡河？一種較為簡(jiǎn)單的表示方式3元向量（x,y,z）x:河此岸的傳教士數(shù)，y:河此岸的野人數(shù)。x,y取值范圍{0，1，2，3}z:船在此岸，z取值范圍{0，1}初始狀態(tài)：（3，3，1）目標(biāo)狀態(tài)：（0，0，0）2831647512386475初始狀態(tài)Initial目標(biāo)狀態(tài)Goal例設(shè)有8數(shù)碼難題如下:在3×3的框架中有8個(gè)標(biāo)有數(shù)字的硬紙片，這些硬紙片上標(biāo)的數(shù)字分別是1，2，…,8，每個(gè)紙片都可以移進(jìn)相鄰的空格，8數(shù)碼難題的初始狀態(tài)和目標(biāo)狀態(tài)分別列出如下，問(wèn)如何把這個(gè)問(wèn)題由初始狀態(tài)移向目標(biāo)狀態(tài)？2831647512386475InitialGoal8數(shù)碼難題（8-puzzle）的矩陣描述對(duì)于8數(shù)碼難題，我們選用直接的矩陣描述，解題過(guò)程中的任何一個(gè)中間情況都對(duì)應(yīng)一個(gè)3*3的矩陣，用0,1，2，…,8這9個(gè)數(shù)的一個(gè)排列依次去充填這個(gè)矩陣的各個(gè)單元,就是求解問(wèn)題的一個(gè)可能的情況,共有9!種。1437658213746582143765821237865212376582137465821374658214317658214357682143786521437865214376358214376258例旅行推銷員問(wèn)題ABDCE75100125125501005075125100125問(wèn)題表示,形式為(A****)的字符串和(A****A)的字符串。其中****為B,C,D,E的排列.問(wèn)題的節(jié)，形式為(A****A)的字符串,其中****為B,C,D,E的排列.旅行推銷員問(wèn)題的搜索空間EADCBCDEAEDADCEAE100125100751501754252253252753753002501.1回溯策略回溯策略的主要思想:只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條解路徑,給變換狀態(tài)的規(guī)則給出一個(gè)排序方法,對(duì)當(dāng)前狀態(tài)使用規(guī)則產(chǎn)生新的狀態(tài),不斷地向前延伸解路徑.當(dāng)沒(méi)有規(guī)則可用,或向前延伸的狀態(tài)都是無(wú)解狀態(tài)(稱為死點(diǎn),deadend)時(shí),沿解路徑后退到前一個(gè)狀態(tài)(回溯),重新開(kāi)始搜索,直至找到解或宣布失敗.回溯策略是一種窮盡的搜索方法.

2.1回溯算法BacktrackingStrategies

遞歸過(guò)程Asimplerecursiveprocedure

輸入:問(wèn)題的初始狀態(tài)..

Theinput:theinitialstate.

輸出:一個(gè)規(guī)則表.應(yīng)用這個(gè)規(guī)則表可以把初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài).否則回答FAIL.

Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.

RecursiveprocedureBACKTRCK(DATA)1ifTERM(DATA),returnNIL;2ifDEADEND(DATA),returnFAIL;3RULES←APPRULES(DATA);4LOOP:ifNULL(RULES),returnFAIL;5R←←FIRST(RULES);6RULES←←TAIL(RULES);7RDATA←←R(DATA);8PATH←←BACKTRACK(RDATA);9ifPATH=FAIL,goLOOP;10returnCONS(R,PATH)““better””ruleisputinthefrontofthelist,itcanbeusedfirstly,theefficiencyofthesystemishigh.Ifthe““worse”***在利利用用APPRUKES得得到到規(guī)規(guī)則則表表之之后后,需需要要對(duì)對(duì)表表中中的的規(guī)規(guī)則則排排序序,把把好好的的規(guī)規(guī)則則放放在在表表的的前前面面優(yōu)優(yōu)先先使使用用,這這個(gè)個(gè)排排序序?qū)?duì)算算法法的的效效率率有有很很大大影影響響.Theproblemrepresentationtheglobaldatabase:4*4arraytherule:RijIfi=1:therearenoqueeninthearray1<i<=4:Thereisaqueenintherowi-1thenputaqueenintherowi,columnjWeordertherulesaccordingtothecolumn.我我們們用用Rij表表示示在在棋棋盤盤的的第第i行行第第j列列放放一一個(gè)個(gè)王王后后.按按行行的的增增加加順順序序依依次次放放皇皇后后,在在規(guī)規(guī)則則的的排排序序上上依依列列的的上上升升次次序序排排序序.Terminationcondition:thereare4queensinthechessboard,theycannotkilleachother.終終止止條條件件:4皇皇后后都都放放到到棋棋盤盤上上,且且不不能能互互相相殺殺死死.Orderofrules:R11,R12,R13,R14R21,R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadendTheremanybacktrackNIL()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)Wecanusemoreinformedruleorderingusingfunctiondiag(i,j)我我們們可可以以采采用用含含有有較較多多信信息息的的函函數(shù)數(shù)diag(i,j).Diag(i,j)=thelengthofthelongestdiagonalpassingthroughcell(i,j)diag(i,j)是是通通過(guò)過(guò)單單元元(i,j)的的最最長(zhǎng)長(zhǎng)對(duì)對(duì)角角線線的的長(zhǎng)長(zhǎng)度度,我我們們按按diag(i,j)排排序2.1BacktrackingStrategiesAsimplerecursiveprocedureTheinputoftheprocedure,DATA:theinitialstate.Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.RecursiveprocedureBACKTRCK(DATALIST)1DATA←←FIRST(DATALIST);2ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL;3ifTERM(DATA),returnNIL;4ifDEADEND(DATA),returnFAIL;5ifLENGTH(DATALIST)>BOUND,returnFAIL;6RULES←←APPRULES(DATA);7LOOP:ifNULL(RULES),returnFAIL;8R←←FIRST(RULES);9RULES←←TAIL(RULES);10RDATA←R(DATA);11RDATALIST←←CONS(RDATA,DATALIST);12PATH←←BACKTRACK(RDATALIST);

13ifPATH=FAIL,goLOOP;

14returnCONS(R,PATH)1.2圖搜索策策略graph-searchstrategies回溯算法法只包含含一條探探索路徑徑,如如果發(fā)現(xiàn)現(xiàn)deadend節(jié)點(diǎn)點(diǎn)或無(wú)規(guī)規(guī)則可用用時(shí)要退退回來(lái),因此此可能產(chǎn)產(chǎn)生把探探索過(guò)的的節(jié)點(diǎn)擦擦掉后又又重新產(chǎn)產(chǎn)生的現(xiàn)現(xiàn)象.在圖搜索索算法中中.將所所有搜索索過(guò)的狀狀態(tài)用一一個(gè)圖(搜索圖圖)記錄錄下來(lái),圖的的弧反映映狀態(tài)之之間的關(guān)關(guān)系.在在圖中選選擇節(jié)點(diǎn)點(diǎn)加以擴(kuò)擴(kuò)展,直直至把把搜索圖圖擴(kuò)展到到充分大大,包包含解路路徑在內(nèi)內(nèi).ThemainideaofgraphsearchInthebacktrackingprocedure,wepreserveonlyapathfromtheinitialstatetothecurrentstate,sosometimesweneedtoproductsomestatesagainafterthestateswereremoved.However,ingraphsearchmethod,Wepreserveagraphinthememory,thegraphincludeallthestateswepassedthroughandtherelationoftheirsequences.Whenwefindsomenode(state)inthegraphissuitedtoexpandforsearch,weexpandit,continueoursearching,untilasolutionisfinded.圖論與狀狀態(tài)空間間表示有有向圖G是一一個(gè)偶對(duì)對(duì)(N,E),其其中N是節(jié)節(jié)點(diǎn)集合合，E是是有向弧弧的集合合。DECBA有向圖中中的有關(guān)關(guān)概念，，父親節(jié)節(jié)點(diǎn)，兒兒子節(jié)節(jié)點(diǎn)，葉葉節(jié)點(diǎn)點(diǎn)，路徑徑，回回路，有有向樹(shù)樹(shù)。用有向圖圖表示問(wèn)問(wèn)題的狀狀態(tài)空間間是一種種很自然然的方式式，節(jié)節(jié)點(diǎn)代表表狀態(tài)描描述，弧弧代表表狀態(tài)之之間的轉(zhuǎn)轉(zhuǎn)移。但但是，，問(wèn)題題的狀態(tài)態(tài)描述與與有向圖圖又有許許多本質(zhì)質(zhì)上的不不同，需需要引引起我們們注意：：

1。。圖論論中研究究的有向向圖是有有限的，，我們可可以把有有向圖全全部畫(huà)出出來(lái)。而而人工智智能中描描述問(wèn)題題的有向向圖一般般說(shuō)來(lái)是是無(wú)限的的，或或者說(shuō)雖雖然有限限，但但是非常常大，我我們不可可能將其其畫(huà)出來(lái)來(lái)。2。圖論論中的問(wèn)問(wèn)題求解解是在對(duì)對(duì)圖完全全了解的的情況下下進(jìn)行。。而我們們對(duì)狀態(tài)態(tài)空間搜搜索解的的過(guò)程是是邊產(chǎn)生生圖邊求求解，這這里所所產(chǎn)生的的圖是表表示狀態(tài)態(tài)空間的的無(wú)限圖圖的顯式式部分，，從求求解的效效率考考慮，就就有把把這個(gè)無(wú)無(wú)限圖的的顯式部部分向哪哪個(gè)方向向以何種種方式擴(kuò)擴(kuò)展的問(wèn)問(wèn)題。Motivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproducesomestatesagain.DB1DB2DB3DB4R1R2R32.2graph-searchstrategiesMotivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproducesomestatesagain.DB1DB4R2DB1DB2DB4R1R2DB1DB2DB3DB4R1R2R3問(wèn)題的狀態(tài)和和它們之間的的關(guān)系可以用用一個(gè)圖隱含含地加以描述述.

狀態(tài)態(tài)用圖的節(jié)點(diǎn)點(diǎn)表示,狀狀態(tài)之間的關(guān)關(guān)系用圖中的的弧表示.thestatesandtheirrelationsaredefinedbyagraphimplicitly:states———————————>nodesruleapplications————————>arcs但但是,我我們也應(yīng)該該注意到它們們之間的區(qū)別別:However,generallythegraphisendless,Wecannotdrawthegraphsinordinaryway.Startingfromtheinitialstate,wegenerateansub-graph(anexplicitpartofthegraphimplicitlydefinedbyproductionsystem),thenweselectthenodeinthesub-graphtoexpandit,ifthesub-graphdoesnotcontainthegoalnode,wecontinuetoexpandit,untilthesub-graphislargeenoughtoincludethegoalnode,andwefindthesolutionpathfromtheinitialnodetothegoalnode.TheprocedureGRAPHSEARCHinput:theproductionsystem(theinitialnose,productionrule,goalnode)

output:thesolutionpathfromtheinitialnodetoagoalnodeProcedureGRAPHSEARCHG=s,OPEN=(s);G為搜索圖,初始化為為問(wèn)題的初始始狀態(tài)s,建建立OPEN表,初始化為只含含初始狀態(tài)s.CLOSED=(),建立CLOSED表,初初始化為空表表.LOOP:IFOPEN=(),THENEXIT(FAIL)n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);稱n為為當(dāng)前節(jié)點(diǎn).IFGOAL(n)THENEXIT(SUCCESS);由由n循指針針?lè)祷豷,可可以獲得解解路徑.EXPAND(n)→mi,G=ADD(mi,G),子節(jié)點(diǎn)點(diǎn)集{mi}中不包含n的父輩節(jié)點(diǎn)點(diǎn).7標(biāo)記和修修改指針ADD(mj,OPEN),并標(biāo)標(biāo)記mj連接到n的指指針,mj是未在OPEN和CLOSED中出出現(xiàn)過(guò)的子節(jié)節(jié)點(diǎn).計(jì)算是否需要要修改mk,ml到n的指針;mk是出現(xiàn)在OPEN表中的的子節(jié)點(diǎn),ml是出現(xiàn)在CLOSED表表中的子節(jié)點(diǎn)點(diǎn),{Mi}={Mj}∪{Mk}∪{Ml}計(jì)算是否需要要修改mi到到其后記節(jié)點(diǎn)點(diǎn)的指針.8.對(duì)OPEN表中的節(jié)節(jié)點(diǎn)按某種原原則重新排序序.9.GOLOOP.對(duì)GRAPHSEARCH算法的的幾點(diǎn)說(shuō)明:兩個(gè)圖,G:搜索索圖,它是是記錄算法訪訪問(wèn)過(guò)的所有有節(jié)點(diǎn)的圖,初始化為問(wèn)題題的初始狀態(tài)態(tài)s,在搜搜索過(guò)程中不不斷地?cái)U(kuò)展.T:G的有有向支撐樹(shù),與G有同同樣的節(jié)點(diǎn),由指針定定義.記錄錄由該節(jié)點(diǎn)到到s的最短路路徑,在搜搜索過(guò)程中需需要不斷調(diào)整整.2.兩個(gè)表表:OPEN和CLOSED,OPEN表表記錄搜索圖圖的前沿,CLOSED表記錄已已經(jīng)擴(kuò)展過(guò)的的節(jié)點(diǎn).3.樹(shù)T的的指針的建立立和調(diào)整.樹(shù)T中節(jié)點(diǎn)的的指針記錄從從該節(jié)點(diǎn)到初初始節(jié)點(diǎn)s的的最短路徑,隨著算法的進(jìn)進(jìn)行,圖的的擴(kuò)展,這這些指針需要要不斷地調(diào)整整.對(duì)新產(chǎn)產(chǎn)生的節(jié)點(diǎn),為其建立立指針.對(duì)對(duì)OPEN和和CLOSED表中的節(jié)節(jié)點(diǎn),需要要考慮調(diào)整其其指針,對(duì)對(duì)于CLOSED表中節(jié)節(jié)點(diǎn),還需需要考慮調(diào)整整其后繼節(jié)點(diǎn)點(diǎn)的指針.NotesabouttheprocedureGRAPHSEARCH1.Twographs:G:Theexplicitpartofthegraphgeneratedbytheproductionsystem,itsinitialnodeistheinitialstate,itisexpandedconstantly.T:thedirectedsupporttreeofG,ithassamenodesasthegraphG,hisarc(onlyoneoutgoingarcfromanode)directtheshortestpathfromonenodetoanothernode.Thearcsaremarkedbypointers.Inordertopreservethecharacter,theprocedureneedtoreadjustthearcsofthetreeconstantly.2.Twolist:OPENthefrontiernodesofgraphG,fromwhich,weselectanodetoexpand.CLOSEDtheinteriornodesofgraphG,thenodehavebeenexpanded.3.TheestablishmentandreadjustmentofthepointersoftreeT.Forthenewlygeneratednodes,weneedtoestablishthepointerforthem.ForthenodesinthelistsonOPENandCLOSED,weneedtoconsidertoreadjusttheirpointers.ForthenodesofCLOSED,weneedtoconsiderthereadjustmentoftheirdescendants,fortheadjustmentofthenodesofCLOSEDmayinfluencetheirdescendant’spointerss12121.3無(wú)無(wú)信息的圖圖搜索過(guò)程深深度優(yōu)先先和寬度優(yōu)先先深度優(yōu)先和寬寬度優(yōu)先的思思想在數(shù)據(jù)結(jié)結(jié)構(gòu)中已經(jīng)講講過(guò),在數(shù)數(shù)據(jù)結(jié)構(gòu)中是是作為樹(shù)的遍遍歷的方法講講的,人工工智能中在狀狀態(tài)空間中搜搜索解的過(guò)程程也類似于遍遍歷.所不不同的是這里里搜索的是圖圖而不是樹(shù).所以這里我我們只討論與與解有關(guān)的問(wèn)問(wèn)題寬寬度優(yōu)先先在搜索解的的過(guò)程中總是是在探索了層層數(shù)小于或等等于n的節(jié)點(diǎn)之后才才進(jìn)入到n+1層節(jié)點(diǎn)的的探索,所所以這中方法法獲得的解具具有最短的解解路徑.但如如果圖的分枝枝系數(shù)很高,或者解路路徑很長(zhǎng),效效率會(huì)很低.深深度優(yōu)先可可以很快地使使實(shí)驗(yàn)解路徑徑延伸到很長(zhǎng)長(zhǎng),如果剛剛好在延伸的的過(guò)程中遇到到解,這種種方法的效率率會(huì)很高,但但不能保證證找到有最短短的解路徑.甚至即使使在原問(wèn)題有有解的時(shí)候,也會(huì)發(fā)生生會(huì)在錯(cuò)誤的的方向上無(wú)限限延伸下去而而找不到解的的情況,深度優(yōu)先算法法ProcedureDEPTH-FIRTSTSEARCH1G=s,OPEN=(s),CLOSED=().2LOOP:IFOPEN=(),THENEXIT(FAIL)n=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);6EXPAND(n)→{mi},G=ADD(mi,G);ADD(mi,OPEN),并并標(biāo)記mi到到n的指針,把不在OPEN和CLOSED中的節(jié)點(diǎn)點(diǎn)放在最前面面,使深度度大的節(jié)點(diǎn)可可以優(yōu)先擴(kuò)展展.8GOLOOP使用DEPTH-FIRST-SEARCH搜索的的例D6C4B4A5H3G4F5E5O2JIKP3TSKKLMNgoal為保證深度優(yōu)優(yōu)先算法在問(wèn)問(wèn)題有解的情情況下總能找找到解,需需要增加深度度限制,而而且深度限制制必須超過(guò)解解的長(zhǎng)度.1.4啟啟發(fā)式搜搜索4。0簡(jiǎn)介介heuristicOforrelatingtoausuallyspeculativeformulationservingasaguideintheinvestigationorsolutionofaproblem:

探索索的,做為調(diào)調(diào)查或解決問(wèn)問(wèn)題的向?qū)У牡囊环N通常為為推測(cè)性系統(tǒng)統(tǒng)闡述回回溯溯式搜索，深深度優(yōu)先和和寬度優(yōu)先都都不使用領(lǐng)域域知識(shí)，效效率很低。啟啟發(fā)式搜索索使用關(guān)于領(lǐng)領(lǐng)域的信息指指導(dǎo)，使搜搜索向著有利利于獲得解的的方向進(jìn)展。。如果應(yīng)用得得好，可以明明顯地縮小搜搜索空間，提提高搜索效效率例例如，，在九宮游游戲中使用啟啟發(fā)式搜索，，就可以顯顯著地減少搜搜索空間MINMAX在九宮游戲中中使用啟發(fā)式式搜索：使使用用啟發(fā)函數(shù)h(s)=MAX已已投下的子子可以占據(jù)的的行，列和和對(duì)角線數(shù)MINMAX54432434445啟發(fā)式搜索算算法最佳優(yōu)先搜索索。根據(jù)啟啟發(fā)函數(shù)對(duì)尚尚為探索的節(jié)節(jié)點(diǎn)進(jìn)行排序序，把最有有希望的節(jié)點(diǎn)點(diǎn)排再前面，，在擴(kuò)展節(jié)節(jié)點(diǎn)時(shí)把最有有希望的節(jié)點(diǎn)點(diǎn)拿出來(lái)考慮慮。最最佳優(yōu)先先搜索算法functionbest-first-search算算法保存2個(gè)表，，一個(gè)是open表，，記錄已經(jīng)經(jīng)產(chǎn)生但尚未未探索的節(jié)點(diǎn)點(diǎn)，另一個(gè)個(gè)是closed表，，記錄已經(jīng)經(jīng)探索過(guò)的節(jié)節(jié)點(diǎn)，算法法把新產(chǎn)生的的節(jié)點(diǎn)加入到到open表表中，然然后按啟發(fā)函函數(shù)值將它們們排序，把把最有希望的的節(jié)點(diǎn)排在前前面，選出出來(lái)加以測(cè)試試和擴(kuò)展啟發(fā)式搜索算算法A

評(píng)價(jià)價(jià)函數(shù)依據(jù)領(lǐng)域知識(shí)識(shí)，對(duì)狀態(tài)態(tài)空間的狀態(tài)態(tài)的好壞程度度的度量。通常使用的評(píng)評(píng)價(jià)函數(shù)為：：f(n)=g(n)+h(n)g*(n)初初始節(jié)點(diǎn)點(diǎn)到節(jié)點(diǎn)n的距離.h*(n)節(jié)節(jié)點(diǎn)n到到目標(biāo)節(jié)點(diǎn)g的距離.f*(n)=g*(n)+h*(n),從從初始節(jié)點(diǎn)點(diǎn)到目標(biāo)節(jié)點(diǎn)點(diǎn)g的距距離.f(n),g(n),h(n)分分別是f*(n),g*(n),h*(n)的估計(jì)計(jì)值.A算法ProcedureA1G=s,OPEN=(s),CLOSED=().2LOOP:IFOPEN=(),THENEXIT(FAIL)3n=FIRST(OPEN);4IF4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);EXPAND(n)→{mi},G=ADD(mi,G);建立和調(diào)整指指針,計(jì)算算各節(jié)點(diǎn)的f值.并并按各點(diǎn)的f值調(diào)整指針針.7把OPEN表中中的節(jié)點(diǎn)按f值從小到大大排序.8GOLOOP2831647528316475283147652831647541+5=61+3=41+5=612384765目標(biāo)狀態(tài)h值是偏離離目標(biāo)位置的的塊數(shù)W(n)283164752831647528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goalnode6s4A6B4C6D5E5F6G6H7I5J7K5L5M77初始化.Open=[s4];closed=[]1.測(cè)試s4,Open=[B4,A6,C6];closed=[s4]2.測(cè)試B4,Open=[D5,E5,A6,C6,F6];closed=[s4,B4]

3.測(cè)測(cè)試D5,Open=[E5,A6,C6,F6,G6,H7];closed=[s4,B4,D5]

4.測(cè)測(cè)試E5,Open=[I5,A6,C6,F6,G6,H7,J7];closed=[s4,B4,D5,E5]5.測(cè)試I5,Open=[K5,A6,C6,F6,G6,H7,J7];closed=[s4,B4,D5,E5,I5]6.測(cè)試試K5,Open=[L5,A6,C6,F6,G6,H7,J7,M7];closed=[s4,B4,D5,E5,I5,K5]

7.L=goal,成功找到到了解283164752831647528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goalnode644646556675755772831647528316475Closed表中的的節(jié)點(diǎn)open表表中的節(jié)點(diǎn)點(diǎn)選擇節(jié)點(diǎn)D擴(kuò)展展時(shí)的Open表表和closed表表2.爬山山法f(n)=h(n)分支界限法法f(n)=g(n)4.動(dòng)態(tài)態(tài)規(guī)劃法對(duì)分支界限限法的改進(jìn)進(jìn),如果果有多條到到達(dá)某一節(jié)節(jié)點(diǎn)的路徑徑,只保保留費(fèi)用最最小的一條條.分支界限法法sDAEFtBC32534544設(shè)有7城城市,城城市之間間的距離如如圖,求求從s到t的最短通通路分支界限法法sDA1g=02g=33g=4分支界限法法sDA1g=02g=33g=4DB5g=76g=8分支界限法法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6分支界限法法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6Bg=11g=13F109分支界限法法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=121112109Bg=11g=13F分支界限法法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=12BEg=10g=11Bg=13FDFBFACtg=14g=16g=15g=14g=15g=15g=1311128109動(dòng)態(tài)規(guī)劃法法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECBg=11Fg=10tg=14g=131112109╳╳╳╳5.最佳佳圖搜索算算法A*在啟發(fā)式搜搜索中使用用評(píng)估函數(shù)數(shù)f(n)=g(n)+h(n)其其中，g(n)是是從初始始狀態(tài)到n費(fèi)用用；h(n)是是從n到目標(biāo)標(biāo)的啟發(fā)式式估計(jì)費(fèi)用用

把使用用這種估值值函數(shù)的啟啟發(fā)式程序序叫做A算算法。如如果狀狀態(tài)空間的的圖搜索問(wèn)問(wèn)題存在解解路徑，搜搜索算法法f一一定能找到到該問(wèn)題的的最優(yōu)解路路徑，則則稱算法f是可可采納的。。如如果在A算算法中使用用的啟發(fā)函函數(shù)滿足h(n)≦h*(n)則則稱之為為A*算算法。。A*算法是是可采納的的若存在從初初始節(jié)點(diǎn)s到目標(biāo)節(jié)節(jié)點(diǎn)t的路路徑，則則A*算法法必能找到到最佳解路路徑。例如，在在寬度優(yōu)先先搜索中，，h(n)≦0，滿足足h(n)≦h*(n)，是是可采納納的。和和前面舉例例的f(n)=g(n)+h(n)中中，h(n)取取為偏離目目標(biāo)位置的的塊數(shù)，滿滿足h(n)≦≦h*(n)，，也是可采采納的。單調(diào)性在算法A中，g(n)是g*(n)的估計(jì)計(jì)值，定定義為在已已經(jīng)產(chǎn)生的的節(jié)點(diǎn)中從從初始節(jié)點(diǎn)點(diǎn)到n的最短路徑徑的費(fèi)用，，在算法法進(jìn)行的過(guò)過(guò)程中，我我們需要要不斷地計(jì)計(jì)算，比比較和調(diào)整整這條最短短路徑，這這要消耗耗大量的計(jì)計(jì)算時(shí)間，，因而也影影響算法的的效率，如如果能對(duì)啟啟發(fā)函數(shù)增增加某些限限制條件，，使得在在這種限制制條件下，，理論上就就可以證明明g(n)就是是g*(n),則則為獲得得g(n)所需要要的計(jì)算就就可以省略略了。這這個(gè)條件就就是單調(diào)性性。定義：?jiǎn)螁握{(diào)性啟發(fā)函數(shù)單單調(diào)的條件件是：1。。對(duì)于所所有的狀態(tài)態(tài)ni和nj，其其中nj是是ni的后后繼h(ni)-h(nj)≦cost(ni,nj)cost(ni,nj)是節(jié)節(jié)點(diǎn)ni和和nj之間間的實(shí)際最最小費(fèi)用2。h(goal)=0啟發(fā)函數(shù)的的比較設(shè)有兩個(gè)算算法，分分別使用兩兩個(gè)啟發(fā)函函數(shù)算算法1，f1(n)=g1(n)+h1(n)算法2，f2(n)=g2(n)+h2(n)哪一個(gè)更好好一些呢？？定義信息息度對(duì)于兩個(gè)A*啟發(fā)式式函數(shù)h1(n)和h2(n)，，如果對(duì)對(duì)于搜索空空間中的所所有的節(jié)點(diǎn)點(diǎn)n,都有h1(n)≦h2(n)

則稱稱h2(n)比h1(n)有更高高的信息度度。如如果h2(n)比比h1(n)有有更高的信信息度，則則算法2所擴(kuò)展的的節(jié)點(diǎn)一定定會(huì)被算法法1所擴(kuò)展展，換句句話說(shuō)，算算法2所所擴(kuò)展的節(jié)節(jié)點(diǎn)比算法法1擴(kuò)展的的節(jié)點(diǎn)少。。A*算法的的應(yīng)用舉例例.(1)8數(shù)碼問(wèn)問(wèn)題h(n)=P(n),P(n)為為每一方塊塊與目標(biāo)位位置的距離離的總和.(2)傳傳教士與與野人問(wèn)題題h(n)=0h(n)=M+Ch(n)=M+C-2B傳教士與野野人渡河問(wèn)問(wèn)題：有N個(gè)傳傳教士帶N個(gè)野野人渡河，，河的岸邊邊有一條船船，每次次最多可載載K人人，要求無(wú)無(wú)論在河的的哪一邊，，或是在船船上，野人人的數(shù)目不不能超過(guò)傳傳教士的數(shù)數(shù)目，問(wèn)為為安全起見(jiàn)見(jiàn)，應(yīng)如如何安排傳傳教士與野野人渡河？？N=5，K=3。。28316475283164752831476528316475283147652318476528314765231847652318476512384765123847651237846583214765283714652345Goalnode6G6H7I5P=5f=5P=2f=7P=6f=7P=4f=5P=6f=7P=5f=7P=3f=5P=5f=7P=2f=5P=4f=7P=1f=5P=0f=5(5,5,1)(4,4,0)(5,2,0)(5,3,0)(5,4,0)(5,3,1)(5,4,1)(5,0,0)(5,1,0)(3,3,0)(5,1,1)(5,2,1)(4,4,1)(0,3,0)(3,3,1)(2,2,0)h(n)=0圖雖然簡(jiǎn)單單,但包包括許多經(jīng)經(jīng)仔細(xì)考慮慮后的剪忮忮迷宮問(wèn)題求從入口到到出口通過(guò)過(guò)迷宮的最最短路徑入口出口迷宮問(wèn)題入口(1,1)出口(4,4)問(wèn)題描述R1:if(x,y)then(x+1,y)R2:if(x,y)then(x,y-1)R1:if(x,y)then(x-1,y)R1:if(x,y)then(x,y+1)h(n)=|Xg-xn|+|Yg-yn|其其中(Xg,Yg)為目標(biāo)標(biāo)點(diǎn)坐標(biāo),(xn,yn)為節(jié)點(diǎn)點(diǎn)n的坐標(biāo)標(biāo),(1,1)(1,2)(1,3)(2,3)(2,2)(2,4)(3,4)(1,4)(2,1)(3,2)(3,1)(3,3)(4,1)(4,2)(4,3)(4,4)(1,1)(2,3)(2,2)(2,4)(1,4)(3,2)(3,4)(3,3)(4,2)(4,3)