人工智能 搜索問(wèn)題

1、第 1 章 搜索問(wèn)題什么是狀態(tài)空間？回溯策略。圖搜索策略無(wú)信息的圖搜索策略啟發(fā)式圖搜索策略A*算法。A*算法的性質(zhì)。搜索算法的討論。狀態(tài)空間間計(jì)算機(jī)對(duì)對(duì)傳統(tǒng)的的問(wèn)題求求解方法法帶來(lái)了了根本性性的改變變。傳統(tǒng)方法法，由由專家給給出公式式，使使用者的的任務(wù)是是理解公公式，應(yīng)應(yīng)用公公式。有些問(wèn)題題用傳統(tǒng)統(tǒng)方法描描述很困困難,例如本節(jié)節(jié)的幾個(gè)個(gè)例子公式的推推導(dǎo)需要要很高的的水平， 與實(shí)實(shí)際問(wèn)題題相差較較遠(yuǎn)，對(duì)對(duì)應(yīng)用者者要求很很高。2.計(jì)算機(jī)利利用自己己強(qiáng)大的的計(jì)算能能力和存存儲(chǔ)能力力,采用”猜猜”的方方式,試探法.能解決問(wèn)問(wèn)題的領(lǐng)領(lǐng)域更廣廣,更結(jié)合實(shí)實(shí)際.例 智力力游戲問(wèn)問(wèn)題：傳傳教士與與野人渡渡河問(wèn)

2、題題傳教士與與野人渡渡河問(wèn)題題：有3個(gè)傳教士士帶3個(gè)野人渡渡河，河河的岸邊邊有一條條船，每每次最最多可載載2人，要求求無(wú)論在在河的哪哪一邊，野人的的數(shù)目不不能超過(guò)過(guò)傳教士士的數(shù)目目，問(wèn)為為安全起起見(jiàn)，應(yīng)應(yīng)如何何安排傳傳教士與與野人渡渡河？一種較為為簡(jiǎn)單的的表示方方式3元向量（x,y,z）x:河此岸的的傳教士士數(shù)，y:河此岸的的野人數(shù)數(shù)。x,y取值范圍圍0，1，2，3z:船在此岸岸，z取值范圍圍0，1初始狀態(tài)態(tài)： （3，3，1）目標(biāo)狀態(tài)態(tài)：（0，0，0）2831647512386475初始狀態(tài)態(tài)Initial目目標(biāo)標(biāo)狀態(tài)Goal例設(shè)有8數(shù)碼難題題如下:在33的框架中中有8個(gè)標(biāo)有數(shù)數(shù)字的硬硬紙片，

3、 這些些硬紙片片上標(biāo)的的數(shù)字分分別是1，2，,8， 每個(gè)個(gè)紙片都都可以移移進(jìn)相鄰鄰的空格格，8數(shù)碼難題題的初始始狀態(tài)和和目標(biāo)狀狀態(tài)分別別列出如如下，問(wèn)問(wèn)如何把把這個(gè)問(wèn)問(wèn)題由初初始狀態(tài)態(tài)移向目目標(biāo)狀態(tài)態(tài)？2831647512386475InitialGoal8 數(shù)碼碼難題（8-puzzle）的矩陣陣描述對(duì)于8數(shù)碼難題題，我我們選用用直接的的矩陣描描述，解解題過(guò)程程中的任任何一個(gè)個(gè)中間情情況都對(duì)對(duì)應(yīng)一個(gè)個(gè)3*3的矩陣， 用0,1，2，,8這9個(gè)數(shù)的一一個(gè)排列列依次去去充填這這個(gè)矩陣陣的各個(gè)個(gè)單元,就是求解解問(wèn)題的的一個(gè)可可能的情情況,共有9!種。14376582137465821437658212

4、37865212376582137465821374658214317658214357682143786521437865214376358214376258例 旅行行推銷員員問(wèn)題ABDCE75100125125501005075125100125問(wèn)題表示示,形形式為(A*)的字符符串和(A*A)的字字符串。其中*為為B,C,D,E的的排列.問(wèn)題的節(jié)節(jié)，形式式為(A*A)的字符符串,其其中*為B,C,D,E的的排列列.旅行推銷銷員問(wèn)題題的搜索索空間EADCBCDEAEDADCEAE100125100751501754252253252753753002501.1回回溯溯策略回溯策略略的主要要

5、思想:只只保留從從初始狀狀態(tài)到當(dāng)當(dāng)前狀態(tài)態(tài)的一條條解路徑徑,給給變換狀狀態(tài)的規(guī)規(guī)則給出出一個(gè)排排序方法法,對(duì)對(duì)當(dāng)前狀狀態(tài)使用用規(guī)則產(chǎn)產(chǎn)生新的的狀態(tài), 不斷斷地向前前延伸解解路徑. 當(dāng)沒(méi)沒(méi)有規(guī)則則可用, 或向向前延伸伸的狀態(tài)態(tài)都是無(wú)無(wú)解狀態(tài)態(tài)(稱為為死點(diǎn),deadend)時(shí)時(shí),沿沿解路徑徑后退到到前一個(gè)個(gè)狀態(tài)(回溯),重重新開(kāi)始始搜索, 直至至找到解解或宣布布失敗. 回溯溯策略是是一種窮窮盡的搜搜索方法法.2.1回回溯溯算法BacktrackingStrategies遞遞歸過(guò)過(guò)程Asimplerecursiveprocedure輸輸入: 問(wèn)題題的初始始狀態(tài).Theinput:theinitial

6、 state.輸輸出:一一個(gè)規(guī)則則表.應(yīng)應(yīng)用這這個(gè)規(guī)則則表可以以把初始始狀態(tài)變變?yōu)槟繕?biāo)標(biāo)狀態(tài). 否則則回答FAIL.The outputoftheprocedure,a listofrules,usingitwecangetthegoalfrom theinitial state.Iftheprocedure cannotfindthesolution, it returnFAIL.RecursiveprocedureBACKTRCK(DATA)1ifTERM(DATA),returnNIL;2ifDEADEND(DATA),returnFAIL;3RULES APPRULES(DATA);4

7、LOOP:ifNULL(RULES), returnFAIL;5R FIRST(RULES);6RULESTAIL(RULES);7RDATAR(DATA);8PATHBACKTRACK(RDATA);9if PATH=FAIL ,goLOOP;10returnCONS(R,PATH)Instep 3, after getthelistofrulesusingthefunctionAPPRULES, we needtoorderthe rules in thelists.Theorderingisveryimportant.Ifthe“better”ruleisputinthe front o

8、f thelist,itcanbeusedfirstly,the efficiencyofthe systemishigh.If the“worse” ruleisput in thefront,thesystemneedstotrymorerules, theefficiency of thesystemispoor.TheExampleofBacktrackingprocedure.The 4queenproblem * * *在利用APPRUKES得得到規(guī)則則表之后后,需需要對(duì)表表中的規(guī)規(guī)則排序序,把把好的規(guī)規(guī)則放在在表的前前面優(yōu)先先使用, 這個(gè)個(gè)排序?qū)?duì)算法的的效率有有很大影影響.Th

9、eproblemrepresentationthe globaldatabase:4*4 arraytherule:RijIfi=1: there arenoqueeninthearray1 i= 4:Thereisa queen in therowi-1thenputa queen in therowi,column jWeorderthe rules accordingtothecolumn.我我們用Rij表表示在棋棋盤的第第 i行行第j列列放一個(gè)個(gè)王后.按按行的增增加順序序依次放放皇后, 在規(guī)規(guī)則的排排序上依依列的上上升次序序排序.Terminationcondition:therear

10、e 4queens in thechessboard,theycannot killeachother.終終止條條件:4皇皇后都放放到棋盤盤上,且且不能能互相殺殺死.Orderofrules:R11,R12, R13,R14R21, R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadendTheremany backtrackNIL()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)Wecanuse moreinformedruleorderingu

11、singfunctiondiag(i,j)我們們可以采采用含有有較多信信息的函函數(shù)diag(i,j).Diag(i,j)= thelengthofthe longestdiagonal passingthroughcell(i,j)diag(i,j)是是通過(guò)單單元(i,j)的最最長(zhǎng)對(duì)角角線的長(zhǎng)長(zhǎng)度,我我們們按diag(i,j)排序序,weorderRmn beforeRij, if diag(m,n) diag(i,j)RinbeforeRij,Ifdiag(i,n)=diag(i,j)and nBOUND, returnFAIL;6RULES APPRULES(DATA);7LOOP:ifN

12、ULL(RULES), returnFAIL;8R FIRST(RULES);9RULESTAIL(RULES);10RDATA R(DATA);11RDATALISTCONS(RDATA, DATALIST);12PATHBACKTRACK( RDATALIST);13ifPATH =FAIL, go LOOP;14returnCONS(R,PATH)1.2圖搜索策策略graph-searchstrategies回溯算法法只包含含一條探探索路徑徑,如果發(fā)現(xiàn)現(xiàn)deadend節(jié)點(diǎn)或無(wú)無(wú)規(guī)則可可用時(shí)要要退回來(lái)來(lái),因此可能能產(chǎn)生把把探索過(guò)過(guò)的節(jié)點(diǎn)點(diǎn)擦掉后后又重新新產(chǎn)生的的現(xiàn)象.在圖搜索索算法中中.將

13、所有搜搜索過(guò)的的狀態(tài)用用一個(gè)圖圖(搜索圖)記錄下來(lái)來(lái),圖的弧反反映狀態(tài)態(tài)之間的的關(guān)系.在圖中選選擇節(jié)點(diǎn)點(diǎn)加以擴(kuò)擴(kuò)展,直至把搜搜索圖擴(kuò)擴(kuò)展到充充分大,包含解路路徑在內(nèi)內(nèi).Themainidea of graph searchInthebacktracking procedure,wepreserveonlya pathfrom theinitial state to thecurrent state,sosometimesweneedtoproductsome statesagainafterthestates wereremoved.However, in graph searchmethod

14、,Wepreservea graph in thememory, thegraphinclude allthestates we passedthrough andtherelationoftheirsequences.Whenwefind somenode(state)inthe graph is suitedtoexpandfor search,weexpand it,continueoursearching,untila solution is finded.圖論與狀態(tài)空間間表示有向圖G是一個(gè)偶偶對(duì)(N,E),其中N是節(jié)點(diǎn)集集合，E是有向弧弧的集合合。DECBA有向圖中中的有關(guān)關(guān)概念，父

15、親節(jié)節(jié)點(diǎn)，兒兒子節(jié)節(jié)點(diǎn)，葉葉節(jié)點(diǎn)點(diǎn)，路徑徑，回回路，有有向樹(shù)樹(shù)。用有向圖圖表示問(wèn)題題的狀態(tài)態(tài)空間是是一種很很自然的的方式， 節(jié)點(diǎn)點(diǎn)代表狀狀態(tài)描述述，弧弧代表狀狀態(tài)之間間的轉(zhuǎn)移移。但是，問(wèn)問(wèn)題的的狀態(tài)描描述與有有向圖又又有許多多本質(zhì)上上的不同同，需需要引起起我們注注意：1。 圖論論中研究究的有向向圖是有有限的，我們可可以把有有向圖全全部畫出出來(lái)。而而人工智智能中描描述問(wèn)題題的有向向圖一般般說(shuō)來(lái)是是無(wú)限的的，或或者說(shuō)雖雖然有限限，但但是非常常大，我我們不可可能將其其畫出來(lái)來(lái)。2。圖論中中的問(wèn)題題求解是是在對(duì)圖圖完全了了解的情情況下進(jìn)進(jìn)行。而而我們對(duì)對(duì)狀態(tài)空空間搜索索解的過(guò)過(guò)程是邊邊產(chǎn)生圖圖邊求解解

16、，這這里所產(chǎn)產(chǎn)生的圖圖是表示示狀態(tài)空空間的無(wú)無(wú)限圖的的顯式部部分，從從求解解的效率率 考慮慮，就就有把這這個(gè)無(wú)限限圖的顯顯式部分分向哪個(gè)個(gè)方向以以何種方方式擴(kuò)展展的問(wèn)題題。Motivation:thelimitation of backtrackingprocedureSometimes, after analyzingweneed to reproducesome statesagain.DB1DB2DB3DB4R1R2R32.2graph-searchstrategiesMotivation:thelimitation of backtrackingprocedureSometimes,

17、after analyzingweneed to reproducesome statesagain.DB1DB4R2DB1DB2DB4R1R2DB1DB2DB3DB4R1R2R3問(wèn)題的狀狀態(tài)和它它們之間間的關(guān)系系可以用用一個(gè)圖圖隱含地地加以描描述.狀狀態(tài)態(tài)用圖的的節(jié)點(diǎn)表表示,狀狀態(tài)之之間的關(guān)關(guān)系用圖圖中的弧弧表示.thestatesand their relationsaredefinedbyagraphimplicitly:statesnodesruleapplications arcs但是是,我我們們也應(yīng)該該注意到到它們之之間的區(qū)區(qū)別:However,generallythegraphi

18、sendless ,We cannotdrawthegraphsinordinaryway.Startingfrom theinitial state,wegenerateansub-graph(anexplicitpartofthegraphimplicitlydefined by productionsystem),thenweselectthenodeinthesub-graph to expandit,if thesub-graphdoesnotcontainthegoalnode,wecontinuetoexpandit, until thesub-graphislargeenoug

19、h toincludethegoalnode ,and we findthe solution pathfromtheinitialnodetothe goalnode.Theprocedure GRAPHSEARCHinput :theproductionsystem(the initialnose,productionrule,goal node)output:thesolutionpathfrom theinitial nodetoagoal nodeProcedureGRAPHSEARCHG=s, OPEN=(s);G為搜索索圖,初初始化化為問(wèn)題題的初始始狀態(tài)s,建建立OPEN表表,初

20、始化為為只含初初始狀態(tài)態(tài)s.CLOSED=(),建立CLOSED表,初始化為為空表.LOOP:IFOPEN=(),THEN EXIT(FAIL)n=FIRST(OPEN),REMOVE(n, OPEN),ADD(n, CLOSED);稱n為當(dāng)前節(jié)節(jié)點(diǎn).IFGOAL(n) THENEXIT(SUCCESS);由n循指針?lè)捣祷豷,可以獲得得解路徑徑.EXPAND(n)mi, G=ADD(mi, G),子節(jié)點(diǎn)集集mi中不包含含n的父輩節(jié)節(jié)點(diǎn).7 標(biāo)記記和修改改指針ADD(mj, OPEN),并并標(biāo)記mj連接到n的指針針,mj是未在OPEN和CLOSED中出出現(xiàn)過(guò)的的子節(jié)點(diǎn)點(diǎn).計(jì)算是否否需要修修改mk

21、, ml到n的指針;mk是出現(xiàn)在在OPEN表中中的子節(jié)節(jié)點(diǎn),ml是出現(xiàn)在在CLOSED表中的子子節(jié)點(diǎn),Mi=MjMkMl計(jì)算是否否需要修修改mi到其后記記節(jié)點(diǎn)的的指針.8.對(duì)OPEN表中的節(jié)節(jié)點(diǎn)按某某種原則則重新排排序.9.GO LOOP.對(duì) GRAPHSEARCH算法的的幾點(diǎn)說(shuō)說(shuō)明:兩個(gè)圖,G:搜搜索圖圖,它它是記錄錄算法訪訪問(wèn)過(guò)的的所有節(jié)節(jié)點(diǎn)的圖圖,初始化為為問(wèn)題的的初始狀狀態(tài)s,在搜索過(guò)過(guò)程中不不斷地?cái)U(kuò)擴(kuò)展.T:G的有向支支撐樹(shù),與G有同樣的的節(jié)點(diǎn),由指針定定義.記錄由該該節(jié)點(diǎn)到到s的最短路路徑,在搜索過(guò)過(guò)程中需需要不斷斷調(diào)整.2.兩個(gè)表: OPEN和CLOSED, OPEN表記錄搜搜索

22、圖的的前沿, CLOSED表記錄已已經(jīng)擴(kuò)展展過(guò)的節(jié)節(jié)點(diǎn).3.樹(shù)T的指針的的建立和和調(diào)整.樹(shù)T中節(jié)點(diǎn)的的指針記記錄從該該節(jié)點(diǎn)到到初始節(jié)節(jié)點(diǎn)s的最短路路徑,隨著算法法的進(jìn)行行,圖的擴(kuò)展展,這些指針針需要不不斷地調(diào)調(diào)整.對(duì)新產(chǎn)生生的節(jié)點(diǎn)點(diǎn),為其建立立指針.對(duì)OPEN和CLOSED表中的節(jié)節(jié)點(diǎn),需要考慮慮調(diào)整其其指針,對(duì)于CLOSED表中節(jié)點(diǎn)點(diǎn),還需要考考慮調(diào)整整其后繼繼節(jié)點(diǎn)的的指針.Notesabouttheprocedure GRAPHSEARCH1.Twographs:G:Theexplicitpartofthegraphgenerated by theproduction system,its

23、initial nodeisthe initialstate, it is expanded constantly.T:the directedsupport treeofG,it hassame nodesasthegraphG,hisarc(onlyone outgoing arcfrom anode)direct theshortestpath fromone nodetoanothernode.The arcsare markedbypointers.In order to preserve thecharacter, theprocedureneedtoreadjustthearcs

24、ofthetreeconstantly.2.Twolist:OPENthe frontier nodes of graph G,from which,weselectanode to expand.CLOSEDthe interiornodesofgraphG,the nodehavebeenexpanded.3.The establishmentandreadjustmentofthepointersoftreeT.Forthenewlygenerated nodes,weneed to establishthepointerforthem.For thenodesinthelistson

25、OPENand CLOSED,weneed toconsidertoreadjusttheirpointers.For thenodesofCLOSED, we needtoconsiderthe readjustmentoftheirdescendants,for theadjustment of thenodesofCLOSEDmayinfluence their descendantspointerss12121.3無(wú)信息的的圖搜索索過(guò)程深度優(yōu)先先和寬度度優(yōu)先深度優(yōu)先先和寬度度優(yōu)先的的思想在在數(shù)據(jù)結(jié)結(jié)構(gòu)中已已經(jīng)講過(guò)過(guò),在數(shù)據(jù)結(jié)結(jié)構(gòu)中是是作為樹(shù)樹(shù)的遍歷歷的方法法講的,人工智能能中在狀狀態(tài)空

26、間間中搜索索解的過(guò)過(guò)程也類類似于遍遍歷.所不同的的是這里里搜索的的是圖而而不是樹(shù)樹(shù).所以這里里我們只只討論與與解有關(guān)關(guān)的問(wèn)題題寬度優(yōu)先先在搜索索解的過(guò)過(guò)程中總總是在探探索了層層數(shù)小于于或等于于n的節(jié)點(diǎn)之之后才進(jìn)進(jìn)入到n+1層節(jié)點(diǎn)的的探索,所以這中中方法獲獲得的解解具有最最短的解解路徑.但如果圖圖的分枝枝系數(shù)很很高,或者解路路徑很長(zhǎng)長(zhǎng),效率會(huì)很很低.深度優(yōu)先先可以很很快地使使實(shí)驗(yàn)解解路徑延延伸到很很長(zhǎng),如果剛好好在延伸伸的過(guò)程程中遇到到解,這種方法法的效率率會(huì)很高高,但不能保保證找到到有最短短的解路路徑.甚至即使使在原問(wèn)問(wèn)題有解解的時(shí)候候,也會(huì)發(fā)生生會(huì)在錯(cuò)錯(cuò)誤的方方向上無(wú)無(wú)限延伸伸下去而而找不到

27、到解的情情況,深度優(yōu)先先算法ProcedureDEPTH-FIRTSTSEARCH1G=s, OPEN=(s),CLOSED=().2LOOP:IFOPEN=(),THEN EXIT(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)點(diǎn)可以優(yōu)優(yōu)先擴(kuò)展展.8GOLOOP使用DEPTH-FIRST-SEARCH搜索的例例D

28、6C4B4A5H3G4F5E5O2JIKP3TSKKLMNgoal為保證深深度優(yōu)先先算法在在問(wèn)題有有解的情情況下總總能找到到解,需要增加加深度限限制,而且深度度限制必必須超過(guò)過(guò)解的長(zhǎng)長(zhǎng)度.1.4啟發(fā)式搜搜索4。0簡(jiǎn)介heuristicOforrelatingtoa usuallyspeculativeformulationservingasa guide in theinvestigation or solution of aproblem:探索的,做為調(diào)查查或解決決問(wèn)題的的向?qū)У牡囊环N通通常為推推測(cè)性系系統(tǒng)闡述述回溯式搜搜索，深深度優(yōu)優(yōu)先和寬寬度優(yōu)先先都不使使用領(lǐng)域域知識(shí)， 效率率很低。啟發(fā)

29、式搜搜索使用用關(guān)于領(lǐng)領(lǐng)域的信信息指導(dǎo)導(dǎo)，使使搜索向向著有利利于獲得得解的方方向進(jìn)展展。如果果應(yīng)用得得好，可可以明顯顯地縮小小搜索空空間，提提高搜搜索效率率例如，在在九宮宮游戲中中使用啟啟發(fā)式搜搜索，就就可以以顯著地地減少搜搜索空間間MINMAX在九宮游游戲中使使用啟發(fā)發(fā)式搜索索：使使用啟啟發(fā)函數(shù)數(shù)h(s) =MAX已投下的的子可以以占據(jù)的的行，列列和對(duì)對(duì)角線數(shù)數(shù)MINMAX54432434445啟發(fā)式搜搜索算法法最佳優(yōu)先先搜索。 根據(jù)據(jù)啟發(fā)函函數(shù)對(duì)尚尚為探索索的節(jié)點(diǎn)點(diǎn)進(jìn)行排排序，把把最有有希望的的節(jié)點(diǎn)排排再前面面，在在擴(kuò)展節(jié)節(jié)點(diǎn)時(shí)把把最有希希望的節(jié)節(jié)點(diǎn)拿出出來(lái)考慮慮。最佳優(yōu)先先搜索算算法fun

30、ctionbest-first-search算法保存存2個(gè)表，一一個(gè)是是open表，記記錄已經(jīng)經(jīng)產(chǎn)生但但尚未探探索的節(jié)節(jié)點(diǎn)，另另一個(gè)個(gè)是closed表，記記錄已經(jīng)經(jīng)探索過(guò)過(guò)的節(jié)點(diǎn)點(diǎn)，算算法把新新產(chǎn)生的的節(jié)點(diǎn)加加入到open表中，然然后按按啟發(fā)函函數(shù)值將將它們排排序，把把最有有希望的的節(jié)點(diǎn)排排在前面面，選選出來(lái)加加以測(cè)試試和擴(kuò)展展啟發(fā)式搜搜索算法法A評(píng)評(píng)價(jià)函數(shù)數(shù)依據(jù)領(lǐng)域域知識(shí)， 對(duì)狀狀態(tài)空間間的狀態(tài)態(tài)的好壞壞程度的的度量。通常使用用的評(píng)價(jià)價(jià)函數(shù)為為：f(n)=g(n)+h(n)g*(n)初初始節(jié)節(jié)點(diǎn)到節(jié)節(jié)點(diǎn)n 的距距離.h*(n)節(jié)節(jié)點(diǎn)點(diǎn) n到到目標(biāo)標(biāo)節(jié)點(diǎn)g 的距距離.f*(n)=g*(n)+h

31、*(n),從從初始始節(jié)點(diǎn)到到目標(biāo)節(jié)節(jié)點(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=(),THEN EXIT(FAIL)3n=FIRST(OPEN);4IF4IF GOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN), ADD(n,CLOSED);EXPAND(n)mi,G=ADD(mi, G);建立和調(diào)調(diào)整指針針,計(jì)計(jì)算各節(jié)節(jié)點(diǎn)的f 值. 并按按各點(diǎn)的的f值調(diào)調(diào)整指針針.7把把OPEN表表中的節(jié)節(jié)點(diǎn)按f值從小小到

32、大排排序.8GOLOOP2831647528316475283147652831647541+5=61+3=41+5=612384765目標(biāo)狀態(tài)態(tài)h 值是是偏離目目標(biāo)位置置的塊數(shù)數(shù)W(n)283164752831647528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goal node6s4A6B4C6D5E5F6G6H7I5J7K5L5M77初始化. Open=s4;closed=1.測(cè)試s4,Open=B4, A6,C6; closed=

33、 s42.測(cè)試B4,Open= D5,E5,A6, C6,F6;closed=s4, B43.測(cè)試D5,Open= E5,A6,C6, F6,G6,H7;closed=s4, B4,D54.測(cè)試E5,Open= I5,A6,C6, F6,G6,H7,J7;closed=s4, B4,D5,E55.測(cè)試I5,Open= K5,A6,C6, F6,G6,H7,J7;closed=s4, B4,D5,E5,I56.測(cè)試K5,Open= L5,A6,C6, F6,G6,H7,J7, M7;closed=s4, B4,D5,E5,I5,K57.L =goal,成功找到到了解283164752831647

34、528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goal node644646556675755772831647528316475Closed表中的節(jié)節(jié)點(diǎn)open表中的節(jié)節(jié)點(diǎn)選擇節(jié)點(diǎn)點(diǎn) D擴(kuò)擴(kuò)展時(shí)時(shí)的Open表和closed表表2.爬山法f(n)=h(n)分支界限限法f(n)=g(n)4.動(dòng)態(tài)規(guī)劃劃法對(duì)分支界界限法的的改進(jìn),如果有多多條到達(dá)達(dá)某一節(jié)節(jié)點(diǎn)的路路徑,只保留費(fèi)費(fèi)用最小小的一條條.分支界限限法sDAEFtBC32534544設(shè)有7

35、城市,城市之間間的距離離如圖,求從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=

36、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=1311121095.最佳圖搜搜索算法法A*在啟發(fā)式式搜索中中使用評(píng)評(píng)估函數(shù)數(shù)f(n) =g(n)+ h(n)其中，g(n)是從初始始狀態(tài)到到n費(fèi)用；h(n)是從n到目標(biāo)的的啟發(fā)式式估計(jì)費(fèi)費(fèi)用把使用這這種估值值函數(shù)的的啟發(fā)式式程序叫叫做A算法。如果狀態(tài)態(tài)空間的的圖搜索索問(wèn)題存存在解路路徑，搜搜索算算法f一定能找找到該問(wèn)問(wèn)題的最最優(yōu)解路路徑，則則稱算算法f是可采納納的。如果在A

37、算法中使使用的啟啟發(fā)函數(shù)數(shù)滿足h(n) h*(n)則稱之為為A*算法。A*算法法是可采采納的若存在從從初始節(jié)節(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īng)產(chǎn)產(chǎn)生的節(jié)節(jié)點(diǎn)中從從初始節(jié)節(jié)點(diǎn)到n的最短路路徑的費(fèi)費(fèi)用，在在算法法進(jìn)行的的過(guò)程中中，我我們需要要不斷地地計(jì)算， 比較較和調(diào)整整這條最最短路徑徑，

38、這這要消耗耗大量的的計(jì)算時(shí)時(shí)間，因因而也影影響算法法的效率率，如果果能對(duì)啟啟發(fā)函數(shù)數(shù)增加某某些限制制條件， 使得得在這種種限制條條件下，理論上上就可以以證明g(n)就是g*(n),則為獲得得g(n)所需要的的計(jì)算就就可以省省略了。 這個(gè)個(gè)條件就就是單調(diào)調(diào)性。定義：?jiǎn)螁握{(diào)性性啟發(fā)函數(shù)數(shù)單調(diào)的的條件是是：1。 對(duì)于于所有的的狀態(tài)ni和nj，其中nj是ni的后繼h(ni) -h(nj) cost(ni,nj)cost(ni,nj)是節(jié)點(diǎn)ni和nj之間的實(shí)際最最小費(fèi)用用2。h(goal) =0啟發(fā)函數(shù)數(shù)的比較較設(shè)有兩個(gè)個(gè)算法， 分別別使用兩兩個(gè)啟發(fā)發(fā)函數(shù)算算法法1，f1(n)= g1(n) +h1(n

39、)算法2，f2(n)= g2(n) +h2(n)哪一個(gè)更更好一些些呢？定義信信息度對(duì)于兩個(gè)個(gè)A*啟啟發(fā)式函函數(shù)h1(n)和h2(n)，如果對(duì)于于搜索空空間中的的所有的的節(jié)點(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é)點(diǎn)比比算法1擴(kuò)展的節(jié)節(jié)點(diǎn)少。A*算法法的應(yīng)用用舉例.(1)8數(shù)數(shù)碼問(wèn)題題h(n) =P(n),P(n)為每一一方塊與與目標(biāo)位位置的距距離的總總和.(2) 傳教教士與野野人問(wèn)題題h(n)=0h(n)=M+Ch(n)=M+C

40、-2B傳教士與與野人渡渡河問(wèn)題題：有N個(gè)傳教士士帶N個(gè)野人渡渡河，河河的岸邊邊有一條條船，每每次最最多可載載K人，要求求無(wú)論在在河的哪哪一邊，或是在在船上，野人的的數(shù)目不不能超過(guò)過(guò)傳教士士的數(shù)目目，問(wèn)為為安全起起見(jiàn)，應(yīng)應(yīng)如何何安排傳傳教士與與野人渡渡河？N=5，K=3。28316475283164752831476528316475283147652318476528314765231847652318476512384765123847651237846583214765283714652345Goal node6G6H7I5P=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)簡(jiǎn)單,但包括許許多經(jīng)仔仔細(xì)考慮慮后的剪剪忮迷宮問(wèn)題題求從入口口到出口口通過(guò)迷迷宮的最最短路徑徑入口