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

搜索問(wèn)題1第三章 搜索問(wèn)題

3.1狀態(tài)空間搜索概述

3.2回溯策略

3.3圖搜索策略

3.4盲目的圖搜索過(guò)程

3.5啟發(fā)式圖搜索過(guò)程搜索與搜索問(wèn)題

人類的實(shí)際搜索行為人工智能所要解決的問(wèn)題大部分不具備明確的解題步驟，而只能是利用已有的知識(shí)一步一步地摸索前進(jìn)。

根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程稱之為搜索。搜索法的主要任務(wù)：確定以何種方式選擇規(guī)則？求任一解路的搜索策略：backtracking、HillClimbing、Breadth-first、Depth-first、BeamSearch、Best-first(A).求最佳解路的搜索策略：BritishMuseum、BranchandBound、DynamicProgramming、Optimalsearch(A*).求與或圖解圖的搜索策略：AO*、Minimax、Alpha-betaPruning、HeuristicPruning.搜索方法的經(jīng)典應(yīng)用8數(shù)碼問(wèn)題傳教士和野人問(wèn)題旅行商問(wèn)題4皇后問(wèn)題迷宮問(wèn)題博弈問(wèn)題…………搜索算法的輸入是給定的問(wèn)題，輸出時(shí)表示為動(dòng)作序列的方案。一旦有了方案，就可以執(zhí)行該方案所給出的動(dòng)作了。（執(zhí)行階段）求解問(wèn)題包括：目標(biāo)表示搜索執(zhí)行

內(nèi)容： 狀態(tài)空間的搜索問(wèn)題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問(wèn)題： 如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。搜索問(wèn)題3.1狀態(tài)空間搜索概述

3.1.1圖的概念圖是節(jié)點(diǎn)及連接節(jié)點(diǎn)的弧的集合。由方向性的弧連接的圖是有向圖。節(jié)點(diǎn)深度的表示：根節(jié)點(diǎn)深度為0，其他節(jié)點(diǎn)深度dn+1=dn+1。路徑：N個(gè)有序節(jié)點(diǎn)組成的序列中，若每對(duì)相鄰節(jié)點(diǎn)都表示一條弧，則稱該序列為圖中長(zhǎng)度為N-1的一條路徑。路徑耗散值：令C（ni，nj）為節(jié)點(diǎn)ni到節(jié)點(diǎn)nj這段路徑（或弧線）的耗散值，一條路徑的耗散值等于這條路徑上所有弧線耗散值的總和。路徑耗散值可按如下遞歸公式計(jì)算：C（ni，t）=C（ni，nj）+C（nj，t）節(jié)點(diǎn)的擴(kuò)展：操作符（規(guī)則）作用到節(jié)點(diǎn)（對(duì)應(yīng)于某一狀態(tài)描述）上，生成其所有后繼節(jié)點(diǎn)（新?tīng)顟B(tài)），并給出弧線的耗散值（相當(dāng)于使用規(guī)則的代價(jià)），這個(gè)過(guò)程叫做擴(kuò)展一個(gè)節(jié)點(diǎn)。3.1.2問(wèn)題狀態(tài)空間的圖描述

圖是最直觀的描述問(wèn)題狀態(tài)空間的工具，屬于顯式描述。 圖中的節(jié)點(diǎn)表示問(wèn)題的狀態(tài)，圖中的弧表示狀態(tài)之間的關(guān)系。 初始狀態(tài)對(duì)應(yīng)待求解問(wèn)題的已知信息，是圖的根節(jié)點(diǎn)。 3.1.3問(wèn)題狀態(tài)空間的搜索狀態(tài)空間法將一個(gè)待定問(wèn)題的求解過(guò)程定義為若干算子與搜索的有機(jī)結(jié)合體。算子定義了對(duì)狀態(tài)的操作，求解的目的在于找出從初始狀態(tài)轉(zhuǎn)換為某個(gè)（或某些）目標(biāo)狀態(tài)的一個(gè)（或一組）操作算子序列。以上問(wèn)題等價(jià)于在圖中尋找從根節(jié)點(diǎn)到某個(gè)（或某些）目標(biāo)節(jié)點(diǎn)的一條（或一組）路徑。為提供對(duì)問(wèn)題的形式描述，需要：定義狀態(tài)空間，包含問(wèn)題相關(guān)對(duì)象的各種可能排列。對(duì)空間的定義不必枚舉所有狀態(tài)。規(guī)定一個(gè)或多個(gè)屬于該空間的初始狀態(tài)。該狀態(tài)用以描述問(wèn)題求解過(guò)程開(kāi)始時(shí)的狀態(tài)。規(guī)定一個(gè)或多個(gè)屬于該空間的目標(biāo)狀態(tài)。該狀態(tài)用以判斷是否得到了問(wèn)題的解。規(guī)定一組規(guī)則。描述可使用的操作或算子。

將待求解問(wèn)題轉(zhuǎn)換成狀態(tài)空間描述后，使用控制策略對(duì)規(guī)則進(jìn)行選擇性的應(yīng)用，在問(wèn)題狀態(tài)空間內(nèi)進(jìn)行搜索，直到找出從初始狀態(tài)到目標(biāo)狀態(tài)的一條（或一組）路徑。3.1.4搜索的基本概念

狀態(tài)空間圖的搜索，是搜索滿足條件的一個(gè)（或一組）操作算子序列的過(guò)程，這個(gè)過(guò)程也是將一個(gè)隱式圖中包含目的節(jié)點(diǎn)的某個(gè)子圖變?yōu)轱@式的過(guò)程。這種搜索過(guò)程是狀態(tài)空間問(wèn)題求解的主要基礎(chǔ)。搜索過(guò)程的要點(diǎn)是：

從初始或目的狀態(tài)出發(fā)，并將它作為當(dāng)前狀態(tài)。掃描操作算子集合，將適用于當(dāng)前狀態(tài)的一些操作算子作用在其上得到新的狀態(tài)，并建立新?tīng)顟B(tài)與父母節(jié)點(diǎn)的連接指針。檢查生成的新?tīng)顟B(tài)是否是結(jié)束狀態(tài)，如果是，則沿著有關(guān)指針從結(jié)束狀態(tài)反向到達(dá)開(kāi)始狀態(tài)，給出一個(gè)解；否則，將新?tīng)顟B(tài)作為當(dāng)前狀態(tài)，返回第2)步繼續(xù)搜索。搜索問(wèn)題S0Sg有哪些常用的搜索算法。問(wèn)題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。搜索需考慮的問(wèn)題盲目搜索只是可以區(qū)分出哪個(gè)是目標(biāo)狀態(tài)。一般是按預(yù)定的搜索策略進(jìn)行搜索。沒(méi)有考慮到問(wèn)題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。啟發(fā)式搜索是在搜索過(guò)程中加入了與問(wèn)題有關(guān)的啟發(fā)式信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解并找到最優(yōu)解。3.2回溯策略

回溯策略是一種嘗試狀態(tài)空間中各種不同路徑的技術(shù)。帶回溯策略的搜索從初始狀態(tài)出發(fā)，不停地、試探地尋找路徑直到找到目標(biāo)節(jié)點(diǎn)或“不可解節(jié)點(diǎn)”—“死胡同”。找到目標(biāo)節(jié)點(diǎn)，退出搜索，返回解路徑。遇到不可解節(jié)點(diǎn)時(shí)，回溯到路徑中最近的父節(jié)點(diǎn)上，查看該節(jié)點(diǎn)是否還有其他子節(jié)點(diǎn)未被擴(kuò)展，如有則沿這些子節(jié)點(diǎn)繼續(xù)搜索?？梢钥闯?，這種求解過(guò)程呈現(xiàn)出遞歸過(guò)程的性質(zhì)。求解過(guò)程在每個(gè)節(jié)點(diǎn)上的檢查遵循著遞歸方式。遞歸法是回溯策略的一種最直接的實(shí)現(xiàn)方法。

回溯搜索策略例：四皇后問(wèn)題在４×４方格的棋盤(pán)內(nèi)，放置四個(gè)皇后使任意兩個(gè)皇后不在同一行、同一列、同一對(duì)角線（斜線）上要求：找出所有的擺法回溯搜索策略狀態(tài)描述：?jiǎn)蝹€(gè)皇后位置的描述：用(i,j)表示皇后在第i行j列系統(tǒng)狀態(tài)的描述四個(gè)皇后((i1,j1),(i2,j2),(i3,j3),(i4,j4))()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((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))()((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))遞歸的思想從前有座山……

從前有座山……

從前有座山……遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g遞歸過(guò)程偽碼描述中用到的一些符號(hào)的含義：變量：DATA=當(dāng)前狀態(tài)；RULES=規(guī)則集合序列表；R=當(dāng)前調(diào)用規(guī)則；RDATA=新生成的狀態(tài)；PATH=當(dāng)前解路徑表。常量：NIL=空表；FAIL=回溯點(diǎn)標(biāo)記；LOOP=循環(huán)標(biāo)號(hào)。謂詞：TERM(DATA)；(DATA滿足結(jié)束條件)DEADEND(DATA)；(DATA是非法狀態(tài))NULL(RULES)。(規(guī)則集合序列表空)函數(shù)：RETURN返回自變量的值；APPRULES求可應(yīng)用的規(guī)則表；FIRST從表中取表頭的一個(gè)元素；TAIL除去表頭的一個(gè)元素后得到新表；GEN

調(diào)用規(guī)則生成新?tīng)顟B(tài)；CONS在表頭插入新元素，構(gòu)造新表；BACKTRACK(RDATA)遞歸過(guò)程作用于新?tīng)顟B(tài)。 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL?；厮菟阉魉惴ㄟf歸過(guò)程BACKTRACK(DATA)1. ifTERM(DATA),returnNIL； //當(dāng)DATA滿足終止條件時(shí)，返回空表.ifDEADEND(DATA),renturnFAIL； //當(dāng)DATA狀態(tài)不合法時(shí)，必須回溯。3. RULES←APPRULES(DATA) //DATA狀態(tài)的可用規(guī)則加入規(guī)則集合序列表。4. LOOP:ifNULL(RULES),returnFAIL； //如果規(guī)則集合序列表空，必須回溯。

5. R←FIRST(RULES)；

//讀規(guī)則集合序列表的第一條規(guī)則到變量R。6. RULES←TAIL(RULES)；

//從規(guī)則集合序列表刪除被選中的規(guī)則。7. RDATA←GEN（R，DATA）；

//被選中的規(guī)則作用于當(dāng)前狀態(tài)。8. PATH←BACKTRACK(RDATA)； //對(duì)新?tīng)顟B(tài)遞歸調(diào)用本過(guò)程9. ifPATH=FAIL,goLOOP；

//如果遞歸失敗，則用另一條規(guī)則10. returnCONS(R,PATH)；

//否則把R加在解路徑表中，向上傳遞成功的 規(guī)則表，過(guò)程返回解路徑規(guī)則表（或局部解 路徑子表）回溯搜索算法解決辦法：對(duì)搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑存在問(wèn)題及解決辦法當(dāng)前狀態(tài)問(wèn)題：深度問(wèn)題死循環(huán)問(wèn)題

對(duì)于可能出現(xiàn)重復(fù)狀態(tài)且搜索深度無(wú)限的問(wèn)題，必須設(shè)置深度范圍限制及防止出現(xiàn)重復(fù)狀態(tài)引起死循環(huán)這兩個(gè)回溯點(diǎn)。

改進(jìn)的算法如下BACKTRACK1(DATALIST):[1]

DATAFIRST(DATALIST)[2]ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL //有環(huán)路，回溯

[3]

ifTERM(DATA),returnNIL //到達(dá)目標(biāo)，成功返回[4]

ifDEADEND(DATA),returnFAIL //到達(dá)不合理狀態(tài)，回溯[5]

ifLENGTH(DATALIST)>BOUND,returnFAIL //已到深度限制，回溯[6]

RULESAPPRULES(DATA) //得出可應(yīng)用的規(guī)則集[7]

LOOP:ifNULL(RULES),returnFAIL //進(jìn)入死胡同，回溯[8]

RFIRST(RULES) //取出第一條可應(yīng)用規(guī)則[9]

RULESTAIL(RULES)[10]RDATAGEN(R,DATA) //運(yùn)用規(guī)則，生成新?tīng)顟B(tài)[11]RDATALISTCONS(RDATA,DATALIST)[12]PATHBACKTRACK1(RDATALIST) //遞歸[13]ifPATH=FAIL,goLOOP[14]returnCONS(R,PATH)問(wèn)題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。不能找出全部解

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

圖搜索策略3.3圖搜索策略

在產(chǎn)生式系統(tǒng)中，如果控制系統(tǒng)保留應(yīng)用所有規(guī)則后生成并連接起來(lái)的狀態(tài)記錄圖，則稱控制系統(tǒng)使用了圖搜索策略。其實(shí)質(zhì)是，從一個(gè)隱含圖中生成確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示子圖的搜索過(guò)程。節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0

其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1一些基本概念0123路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。一些基本概念（續(xù)1）搜索方法的一般步驟1、定義狀態(tài)描述形式2、定義算符—是把問(wèn)題從一種狀態(tài)變換到另一種狀態(tài)的方法代號(hào)，即狀態(tài)演變規(guī)則3、確定初始狀態(tài)（初始節(jié)點(diǎn)）和目標(biāo)狀態(tài)（目標(biāo)節(jié)點(diǎn)）4、狀態(tài)更新——根據(jù)算符更新當(dāng)前狀態(tài)5、目標(biāo)測(cè)試——判斷更新后的狀態(tài)是否為目標(biāo)狀態(tài)，若不是則轉(zhuǎn)到4，否則轉(zhuǎn)到66、搜索成功,記錄搜索路徑用open表和closed表保存搜索經(jīng)過(guò)的各個(gè)節(jié)點(diǎn)open表和closed表的一般結(jié)構(gòu)開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功圖搜索過(guò)程框圖是是否否1.G:=G0(G0=s)，Open:=(s)；//G表示圖，s為初始節(jié)點(diǎn)，設(shè)置Open表，最初只含初始節(jié)點(diǎn)，存儲(chǔ)待擴(kuò)展的節(jié)點(diǎn)。2.Closed:=()； //設(shè)置Closed表,起始設(shè)置為空表，存儲(chǔ)已擴(kuò)展完的節(jié)點(diǎn)。3.

LOOP:IFOpen=(),THENEXIT(FAIL);4.n:=FIRST(Open),REMOVE(n,Open),ADD(n,Closed); //稱n為當(dāng)前節(jié)點(diǎn)。5.

IFGOAL(n)，THENEXIT(SUCCESS)； //返回由n到s的路徑上的指針，可給出解路徑。6.

EXPAND(n)→(mi),G:=ADD(mi,G)；//子節(jié)點(diǎn)集{mi}中不能包含n的先輩節(jié)點(diǎn)，即不能有環(huán)路。7.

標(biāo)記和修改指針//對(duì)出現(xiàn)多路徑的情況，根據(jù)耗散值選擇最好的解路，此時(shí){mi}={mj}∪{mk}∪{ml}7-1)ADD(mj，Open),并標(biāo)記mj連接到n的指針;

//mj表示Open和Closed中未出現(xiàn)過(guò)的子節(jié)點(diǎn)。7-2)計(jì)算是否要修改mk、ml到n的指針； //mk表示已出現(xiàn)在Open中的子節(jié)點(diǎn)，ml表示已出現(xiàn)在Closed中的子節(jié)點(diǎn)。7-3)計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8．對(duì)Open中的節(jié)點(diǎn)按某種原則重新排序； 9．GOLOOP(察看Open表)；一般的圖搜索算法{mi}節(jié)點(diǎn)類型說(shuō)明mjmkml12345已擴(kuò)展過(guò)的節(jié)點(diǎn)

(Closed)待擴(kuò)展的節(jié)點(diǎn)

(Open)s圖3-7(a)擴(kuò)展節(jié)點(diǎn)6得到的搜索圖實(shí)心圓點(diǎn)在Closed中（已擴(kuò)展節(jié)點(diǎn)），空心圓點(diǎn)在Open中（待擴(kuò)展點(diǎn)）

。設(shè)下一步要擴(kuò)展節(jié)點(diǎn)6，并設(shè)生成兩個(gè)子節(jié)點(diǎn):其中子節(jié)點(diǎn)4已在Open中(mk)，路徑（s→3→2→4）耗散值為5（設(shè)每段為單位耗散），新路徑（s→6→4）耗散值為4，則節(jié)點(diǎn)4的解路徑指針應(yīng)修正：（4→2）改為（4→6），如圖3-7(a)。

假設(shè):下一循環(huán)擴(kuò)展節(jié)點(diǎn)1，若節(jié)點(diǎn)1只生成一個(gè)子節(jié)點(diǎn)2(Closed中已有，ml)。比較耗散值，顯然要修改節(jié)點(diǎn)2的指針（3→1），由此又會(huì)引起節(jié)點(diǎn)4指針的修改（６→２），如圖3-7(b)。圖3-7(b)擴(kuò)展節(jié)點(diǎn)1得到的搜索圖無(wú)信息搜索又稱盲目搜索/窮舉式搜索，只能按照預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，沒(méi)有任何中間信息來(lái)改變這些控制策略。具有盲目性，效率不高，不便于復(fù)雜問(wèn)題的求解。常用方法有廣度優(yōu)先搜索和深度優(yōu)先搜索以及這兩種搜索方法的改良方法。深度優(yōu)先搜索寬度優(yōu)先搜索無(wú)信息圖搜索過(guò)程寬度優(yōu)先搜索最簡(jiǎn)便的圖的搜索算法之一，屬于一種盲目搜尋法。目的是系統(tǒng)地展開(kāi)并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果?；舅枷胧鞘紫人阉骱统跏脊?jié)點(diǎn)距離為1的所有頂點(diǎn)，然后再去搜索和出始節(jié)點(diǎn)距離為2的其他頂點(diǎn)，依次類推它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

寬度優(yōu)先搜索寬度優(yōu)先搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中。步2若OPEN表為空,則搜索失敗,退出。步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放在CLOSED表中,并冠以順序編號(hào)n。步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的指針依次放入OPEN表尾部,轉(zhuǎn)步2。寬度優(yōu)先搜索例：8數(shù)碼問(wèn)題九宮格中有8個(gè)數(shù)碼，其中只有一個(gè)空格規(guī)則是一次只能把一個(gè)數(shù)碼移動(dòng)到空的格子中要求從一個(gè)初始狀態(tài)移動(dòng)到一個(gè)目標(biāo)狀態(tài)寬度優(yōu)先搜索根據(jù)CLOSED表確定解樹(shù)寬度優(yōu)先搜索優(yōu)點(diǎn)完備性：如果問(wèn)題有解，廣度優(yōu)先搜索總能夠在有限步內(nèi)找到目標(biāo)節(jié)點(diǎn)最優(yōu)性：在不考慮路徑耗散的前提下，廣度優(yōu)先搜索總能夠找到最淺的目標(biāo)節(jié)點(diǎn)缺點(diǎn)：遍歷各個(gè)節(jié)點(diǎn)，搜索效率差，消耗大量?jī)?nèi)存和時(shí)間寬度優(yōu)先搜索的拓展

—代價(jià)樹(shù)寬度搜索代價(jià)樹(shù)寬度搜索（代價(jià)一致搜索）對(duì)于任意單步路徑耗散都是最優(yōu)的搜索策略其基本思想是優(yōu)先擴(kuò)展路徑耗散最小的節(jié)點(diǎn)對(duì)于任意節(jié)點(diǎn)n，用f(n)來(lái)表示n到初始節(jié)點(diǎn)的路徑耗散，即代價(jià)代價(jià)樹(shù)寬度搜索例：旅行商問(wèn)題設(shè)A、B、C、D、E五個(gè)城市，旅行者從A出發(fā)，到達(dá)城市E，旅行費(fèi)用如圖所示，走怎樣的路線費(fèi)用最?。恳螽?huà)出代價(jià)樹(shù)、OPEN表和CLOSED表由CLOSED表倒推：E1—C1—A，因此最優(yōu)旅行路徑為：A—C—E，代價(jià)為3深度優(yōu)先搜索深度優(yōu)先搜索總是先擴(kuò)展搜索樹(shù)的當(dāng)前邊緣中最深的節(jié)點(diǎn)一種最原始的仿生學(xué)算法，來(lái)源于爬蟲(chóng)在樹(shù)枝的搜索過(guò)程深度優(yōu)先搜索深度優(yōu)先搜索算法：步1把初始節(jié)點(diǎn)S0放入OPEN表中。步2若OPEN表為空,則搜索失敗,退出。步3取OPEN表中前面第一個(gè)節(jié)點(diǎn)N放入CLOSED表中,并冠以順序編號(hào)n。步4若目標(biāo)節(jié)點(diǎn)Sg=N,則搜索成功,結(jié)束。步5若N不可擴(kuò)展,則轉(zhuǎn)步2。步6擴(kuò)展N,將其所有子節(jié)點(diǎn)配上指向N的返回指針依次放入OPEN表的首部,轉(zhuǎn)步2。深度優(yōu)先搜索例：傳教士和野人問(wèn)題有3個(gè)傳教士和3個(gè)野人過(guò)河只有一條能裝下兩個(gè)人的船在河的任何一方或者船上，如果野人的人數(shù)大于傳教士的人數(shù)，那么傳教士就會(huì)有危險(xiǎn).要求安全渡河深度優(yōu)先搜索分析：由于傳教士與野人的總數(shù)目是一常數(shù),所以只要表示出河的某一岸上的情況就可以了另外還需要表示出船的位置因此用一個(gè)三元組(M,C,B),來(lái)表示系統(tǒng)狀態(tài)M表示河左岸傳教士的人數(shù)C表示河左岸野人的人數(shù)B表示船的位置，1表示船在左岸，0表示船在右岸于是，初始狀態(tài)為目標(biāo)狀態(tài)為深度優(yōu)先搜索深度優(yōu)先搜索沿著樹(shù)的寬度遍歷樹(shù)的節(jié)點(diǎn)，它從深度為0的層開(kāi)始，直到最深的層次。它可以很容易地用隊(duì)列實(shí)現(xiàn)。一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法搜索最優(yōu)策略的比較寬度優(yōu)先搜索是一種盲目搜索，時(shí)間和空間復(fù)雜度都比較高，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)會(huì)產(chǎn)生許多無(wú)用的節(jié)點(diǎn)，搜索效率低。寬度優(yōu)先搜索中，時(shí)間需求是一個(gè)很大的問(wèn)題，特別是當(dāng)搜索的深度比較大時(shí)，尤為嚴(yán)重，但是空間需求是比執(zhí)行時(shí)間更嚴(yán)重的問(wèn)題。

寬度優(yōu)先搜索優(yōu)點(diǎn)：目標(biāo)節(jié)點(diǎn)如果存在，用寬度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且是最?。醋疃搪窂剑┑墓?jié)點(diǎn)。深度優(yōu)先搜索的優(yōu)點(diǎn)是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹(shù)的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒(méi)有完全展開(kāi)的節(jié)點(diǎn)標(biāo)志所組成。深度優(yōu)先搜索的存儲(chǔ)器要求是深度約束的線性函數(shù)。目的解決寬度優(yōu)先方法的空間問(wèn)題和回溯方法不能找到最優(yōu)解的問(wèn)題。思想 首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。漸進(jìn)式深度優(yōu)先搜索方法有界深度優(yōu)先搜索過(guò)程總體上按深度優(yōu)先算法方法進(jìn)行，但對(duì)搜索深度需要給出一個(gè)深度限制dm，當(dāng)深度達(dá)到了dm的時(shí)候，如果還沒(méi)有找到解答，就停止對(duì)該分支的搜索，換到另外一個(gè)分支進(jìn)行搜索。3.2.3迭代加深搜索（1）深度限制dm很重要。當(dāng)問(wèn)題有解，且解的路徑長(zhǎng)度小于或等于dm時(shí)，則搜索過(guò)程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。但是當(dāng)dm取得太小，解的路徑長(zhǎng)度大于dm時(shí)，則搜索過(guò)程中就找不到解，即這時(shí)搜索過(guò)程甚至是不完備的。（2）深度限制dm不能太大。當(dāng)dm太大時(shí)，搜索過(guò)程會(huì)產(chǎn)生過(guò)多的無(wú)用節(jié)點(diǎn)，既浪費(fèi)了計(jì)算機(jī)資源，又降低了搜索效率。（3）有界深度搜索的主要問(wèn)題是深度限制值dm的選取。策略說(shuō)明:

改進(jìn)方法：（迭代加深搜索）先任意給定一個(gè)較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)沒(méi)有找到問(wèn)題的解，則增大深度限制dm，繼續(xù)搜索。迭代加深搜索，試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等。如果初始深度為0，則該算法只生成根節(jié)點(diǎn)，并檢測(cè)它。如果根節(jié)點(diǎn)不是目標(biāo)，則深度加1，通過(guò)典型的深度優(yōu)先算法，生成深度為1的樹(shù)。當(dāng)深度限制為m時(shí)，樹(shù)的深度為m。迭代加深搜索看起來(lái)會(huì)很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)都可能擴(kuò)展多次。然而對(duì)于很多問(wèn)題，這種多次的擴(kuò)展負(fù)擔(dān)實(shí)際上很小，直覺(jué)上可以想象，如果一棵樹(shù)的分支系數(shù)很大，幾乎所有的節(jié)點(diǎn)都在最底層上，則對(duì)于上面各層節(jié)點(diǎn)擴(kuò)展多次對(duì)整個(gè)系統(tǒng)來(lái)說(shuō)影響不是很大。表注：b是分支系數(shù)，d是解答的深度，m是搜索樹(shù)的最大深度，l是深度限制。搜索最優(yōu)策略的比較啟發(fā)式搜索啟發(fā)式搜索，也稱為有信息搜索，借助問(wèn)題的特定知識(shí)來(lái)幫助選擇搜索方向在搜索過(guò)程中對(duì)待擴(kuò)展的每一個(gè)節(jié)點(diǎn)進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。啟發(fā)式搜索的目的是省略大量無(wú)謂的搜索路徑，提到效率。在啟發(fā)式搜索中，對(duì)節(jié)點(diǎn)的評(píng)價(jià)是十分重要的，評(píng)價(jià)函數(shù)是搜索成敗的關(guān)鍵。啟發(fā)式搜索評(píng)價(jià)函數(shù)，也稱為啟發(fā)函數(shù)提供問(wèn)題的啟發(fā)性信息，按其用途劃分，可分為以下三類：用于擴(kuò)展節(jié)點(diǎn)的選擇，即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn)，以免盲目擴(kuò)展用于生成節(jié)點(diǎn)的選擇，即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn)，以免盲目地生成過(guò)多無(wú)用節(jié)點(diǎn)用于刪除節(jié)點(diǎn)的選擇，即用于決定應(yīng)刪除哪些無(wú)用節(jié)點(diǎn)，以免造成進(jìn)一步的時(shí)空浪費(fèi)啟發(fā)式搜索一個(gè)節(jié)點(diǎn)n的評(píng)價(jià)函數(shù)的構(gòu)造通常由兩部分構(gòu)成從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的路徑耗散從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的期望耗散即：評(píng)價(jià)函數(shù)可表示為：這兩部分里，通常是比較明確的，容易得到而難以構(gòu)造，也沒(méi)有固定的模式，需要根據(jù)具體問(wèn)題分析利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解啟發(fā)式圖搜索引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。希望：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展?；舅枷朐u(píng)價(jià)函數(shù)的格式：

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

h(n)：?jiǎn)l(fā)函數(shù)g(x)——從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的實(shí)際代價(jià)；h(x)——從x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的評(píng)估代價(jià)，它體現(xiàn)了問(wèn)題的啟發(fā)式信息，其形式要根據(jù)問(wèn)題的特性確定，h(x)稱為啟發(fā)式函數(shù)。90/641，啟發(fā)式搜索算法A（A算法）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ì)值91/64符號(hào)的意義92/64開(kāi)始把S放入OPEN表，計(jì)算估價(jià)函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖3.9有序搜索算法框圖是否是否算法93/64A算法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作為n的后繼節(jié)點(diǎn)添入G，計(jì)算

f(n→mi)=g(n→mi)+h(mi)；6-1)ADD(mj,Open);6-2)IFf(n→mk)<f(mk)THENf(mk):=f(n→mk);6-3)IFf(n→ml)<f(ml)THENf(ml):=f(n→ml);ADD(ml,Open);7.Open中的節(jié)點(diǎn)按f

值從小到大排序;

8.

GOLOOP;算法的說(shuō)明：A算法由一般的圖搜索算法改變而成。算法第7步每次按照f(shuō)(n)值的大小對(duì)Open表中的元素進(jìn)行排序，f(n)值小的節(jié)點(diǎn)排在前面，而f(n)值大的節(jié)點(diǎn)則放在Open表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時(shí)，都選擇當(dāng)前f(n)值最小的節(jié)點(diǎn)來(lái)優(yōu)先擴(kuò)展。A算法是按f(n)遞增的順序來(lái)排列Open表中節(jié)點(diǎn)的，因而優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，體現(xiàn)了好的優(yōu)先搜索的思想，所以算法A是一個(gè)好的優(yōu)先搜索策略。擴(kuò)展n后新生成的子節(jié)點(diǎn)m1({mj})、m2({mk})、m3({ml})分別計(jì)算評(píng)價(jià)函數(shù)值：f(m1)=g(m1)+h(m1)f(n,m2)=g(n,m2)+h(m2)f(n,m3)=g(n,m3)+h(m3)按第6步比較不同路徑的耗散值并進(jìn)行相應(yīng)的指針修正.snf(n)m2m1m3m31m32f(m3)f(m1)f(m2)f(m31)f(m32)圖3-12搜索示意圖定義評(píng)價(jià)函數(shù)：

f(x)=d(x)+w(x)

d(x)表示節(jié)點(diǎn)在x搜索樹(shù)中的深度，w(x)表示節(jié)點(diǎn)x中不在目標(biāo)狀態(tài)中相應(yīng)位置的數(shù)碼個(gè)數(shù)，w(x)就包含了問(wèn)題的啟發(fā)式信息。一般來(lái)說(shuō)某節(jié)點(diǎn)的w(x)越大，即“不在目標(biāo)位”的數(shù)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。

一個(gè)A算法的例子2831647512384765對(duì)初始節(jié)點(diǎn)S0，由于d(S0)=0，w(S0)=5，因此f(S0)=5。在搜索過(guò)程中除了需要計(jì)算初始節(jié)點(diǎn)的評(píng)估函數(shù)外，更多的是需要計(jì)算新生節(jié)點(diǎn)的評(píng)估函數(shù)。

w(n)=4h計(jì)算舉例2

831

64751234576

8由CLOSED表可知，解路徑為S0-S2-S5-S9-S11-S122831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)123456OPEN和CLOSED表的元素排列如下：

OPEN表：1）初始化（s（4））2）第一循環(huán)結(jié)束（B（4）A（6）C（6））3)第二循環(huán)結(jié)束（D（5）E（5）A（6）C（6）F（6））4)第三循環(huán)結(jié)束（E（5）A（6）C（6）F（6）G（6）H（7））5)第四循環(huán)結(jié)束（I（5）A（6）C（6）F（6）G（6）H（7）J（7））6)第五循環(huán)結(jié)束（K（5）A（6）C（6）F（6）G（6）H（7）J（7））7)第六循環(huán)結(jié)束（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循環(huán)結(jié)束在算法第4步成功退出CLOSED表：1)（）2)（s（4））3)（s（4）B（4））4)（s（4）B（4）D（5））5)（s（4）B（4）D（5）E（5））6)（s（4）B（4）D（5）E（5）I（5））7)（s（4）B（4）D（5）E（5）I（5）K（5））啟發(fā)式搜索A算法的表現(xiàn)極大地依賴于評(píng)價(jià)函數(shù)，特別是h(n),即：從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)耗散假定h*(n)表示節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的實(shí)際耗散如果h(n)>

h*(n),搜索的節(jié)點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。如果h(n)<=h*(n)

，這種情況下，搜索的節(jié)點(diǎn)數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解啟發(fā)式搜索滿足h(n)<=h*(n)

條件的A搜索，稱為A*(A-star)搜索A*搜索中，h(n)越接近h*(n)

，搜索效率越高寬度優(yōu)先算法可以看作A*算法的特例，即：g(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0

代價(jià)樹(shù)寬度搜索也可以看作A*算法的特例，即：g(n)是節(jié)點(diǎn)n的實(shí)際路徑耗散，h(n)=0跟前兩個(gè)算法一樣，A*算法也具有完備性和最優(yōu)性啟發(fā)式搜索例：八數(shù)碼問(wèn)題啟發(fā)函數(shù)1：h1(n)=不在位的數(shù)碼的總數(shù)問(wèn)題1：圖中S0狀態(tài)h(S0)是什么，h*(S0)

又是什么問(wèn)題2：這個(gè)啟發(fā)函數(shù)是否一定滿足h(n)<=h*(n)

問(wèn)題3：對(duì)于八數(shù)碼問(wèn)題，還能提出其他的啟發(fā)函數(shù)嗎？h(S0)=4h*(S0)=5啟發(fā)式搜索例：八數(shù)碼問(wèn)題啟發(fā)函數(shù)2：h2(n)=所有數(shù)碼到目標(biāo)位置的距離和（曼哈頓距離）問(wèn)題1：圖中S0狀態(tài)h(S0)是什么，h*(S0)

又是什么問(wèn)題2：這個(gè)啟發(fā)函數(shù)是否一定滿足h(n)<=h*(n)

數(shù)碼1：1數(shù)碼2：1數(shù)碼3：0數(shù)碼4：0數(shù)碼5：0數(shù)碼6：1數(shù)碼7：0數(shù)碼8：2h2(S0)=5啟發(fā)式搜索A*算法當(dāng)h(n)<=h*(n)

時(shí)，同時(shí)滿足完備性和最優(yōu)性要求h(n)越接近于真實(shí)耗散h*(n)，算法的搜索效率越高，對(duì)內(nèi)存和時(shí)間的需求越小如果滿足h(n)=h*(n)，是最完美的A*算法h(n)的設(shè)計(jì)是A*算法的核心，也是最困難的地方完備的最優(yōu)的效率最優(yōu)的但，在搜索空間中處于目標(biāo)等值線內(nèi)的節(jié)點(diǎn)數(shù)仍然是解長(zhǎng)度的指數(shù)級(jí)，并且，它在內(nèi)存空間中保存了所有的節(jié)點(diǎn)。108/69A*算法分析爬山法搜索模擬退火搜索局部剪枝搜索遺傳算法109/69局部搜索算法啟發(fā)式搜索-爬山法爬山法模擬人們出游爬山的決策過(guò)程以目標(biāo)值增加的方向?yàn)樗阉鞣较蛉绻卸鄠€(gè)增加的方向，選使目標(biāo)值增加速度最快的方向爬山法會(huì)在某個(gè)峰頂終止，其相鄰狀態(tài)中沒(méi)有更高的目標(biāo)值了，稱為局部極大值啟發(fā)式搜索-爬山法爬山法的基本步驟1、初始化，確定初始節(jié)點(diǎn)等參數(shù)2、檢查當(dāng)前節(jié)點(diǎn)是否滿足目標(biāo)條件，如果滿足，則搜索成功，結(jié)束3、取鄰域中每一個(gè)相鄰節(jié)點(diǎn)，計(jì)算其目標(biāo)函數(shù)的改進(jìn)值4、取改進(jìn)值最大的相鄰節(jié)點(diǎn)作為搜索目標(biāo)，替換當(dāng)前節(jié)點(diǎn)5、檢查是否滿足循環(huán)終止條件。如果滿足，則中止循環(huán)，否則轉(zhuǎn)步2啟發(fā)式搜索-爬山法爬山法的缺陷難以處理山肩的情況貪婪搜索方向不一定是正確的搜索方向啟發(fā)式搜索-爬山法爬山法的改進(jìn)隨機(jī)爬山法：在上山移動(dòng)中隨機(jī)的選擇下一步可回溯爬山法：給定啟發(fā)式的回溯策略，允許回頭搜索其他節(jié)點(diǎn)洪水爬山法：不斷尋找改進(jìn)方向允許水平移動(dòng)可回溯啟發(fā)式搜索-模擬退火算法模擬退火算法（simulatedannealing）爬山法是不完備的，有可能停留在局部最優(yōu)解上隨機(jī)行走（遍歷）是完備的，但是搜索效率很差模擬退火算法將爬山法與隨機(jī)行走結(jié)合起來(lái)，希望同時(shí)得到效率和完備性模擬退火搜索：結(jié)合爬山法和隨機(jī)行走比喻：在冶金中退火是為了增強(qiáng)金屬和玻璃的韌性和硬度而先把它們加熱到高溫然后逐漸冷卻的過(guò)程115/69啟發(fā)式搜索-模擬退火算法模擬退火過(guò)程思想來(lái)源于固體退火原理，屬于熱力學(xué)范疇將固體加溫至充分高，再讓其緩慢冷卻加溫時(shí)，固體內(nèi)部的粒子隨溫升脫離原先的平衡態(tài)，變?yōu)闊o(wú)序狀緩慢冷卻時(shí)，粒子活性逐漸下降，逐漸停留在不同狀態(tài)，重新形成粒子的排列結(jié)構(gòu)如果降溫過(guò)程足夠緩慢，粒子的排列就會(huì)達(dá)到一種平衡態(tài)，使系統(tǒng)能量最小啟發(fā)式搜索-模擬退火算法初始狀態(tài)加溫冷卻啟發(fā)式搜索-模擬退火算法模擬退火的基本步驟:

(1)初始化：初始溫度T(充分大)，初始狀態(tài)S，迭代次數(shù)L

(2)對(duì)k=1，……，L重復(fù)第(3)至第6步：

(3)產(chǎn)生新解S’

(4)計(jì)算增量Δt’=C(S’)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)

(5)若Δt’<0則接受S’作為新的當(dāng)前解，否則以概率exp(-Δt’/T)接受S’作為新的當(dāng)前解

(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法。

(7)T逐漸減少，且T>0，然后轉(zhuǎn)第2步。啟發(fā)式搜索-模擬退火算法冷卻進(jìn)度表：是指調(diào)整模擬退火法的一系列重要參數(shù)，它控制溫度參數(shù)T的初值及其衰減函數(shù)。冷卻進(jìn)度表的內(nèi)容：控制參數(shù)T的初值;控制參數(shù)T的衰減函數(shù)；每一個(gè)溫度下的迭代次數(shù)L，即每一次隨機(jī)游走過(guò)程，要迭代多少次，才能趨于一個(gè)準(zhǔn)平衡分布結(jié)束條件啟發(fā)式搜索-模擬退火算法Metropolis準(zhǔn)則:假設(shè)在狀態(tài)xold時(shí)，系統(tǒng)受到某種擾動(dòng)而使其狀態(tài)變?yōu)閤new。與此相對(duì)應(yīng)，系統(tǒng)的能量也從E(xold)變成E(xnew)系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接受概率p為：若Δt’<0則接受S’作為新的當(dāng)前解S，否則以概率exp(-Δt’/T)接受S’作為新的當(dāng)前解S

啟發(fā)式搜索-模擬退火算法模擬退火算法的關(guān)鍵點(diǎn)初始溫度必須足夠高在每一個(gè)溫度下，狀態(tài)的轉(zhuǎn)換必須足夠充分溫度T的下降必須足夠緩慢啟發(fā)式搜索-模擬退火算法模擬退火算法的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：計(jì)算過(guò)程簡(jiǎn)單，通用，魯棒性強(qiáng)適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問(wèn)題缺點(diǎn)：如果降溫過(guò)程足夠緩慢，多得到的解的性能會(huì)比較好，但與此相對(duì)的是收斂速度太慢;如果降溫過(guò)程過(guò)快，很可能得不到全局最優(yōu)解隨機(jī)搜索算法動(dòng)態(tài)規(guī)劃算法 如果對(duì)于任何n，當(dāng)h(n)=0時(shí)，A*算法就成為了動(dòng)態(tài)規(guī)劃算法。其他的搜索算法（續(xù)1）啟發(fā)式搜索-遺傳算法遺傳算法(geneticalgorithm,GA)

模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型是一種通過(guò)模擬自然進(jìn)化過(guò)程的隨機(jī)優(yōu)化搜索方法美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出來(lái)的啟發(fā)式搜索-遺傳算法遺傳算法的基本思想遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象在每次迭代中，根據(jù)適應(yīng)度評(píng)估群體中的所有成員，然后選取適應(yīng)度最高的個(gè)體產(chǎn)生新一代群體在被選中的個(gè)體中，一部分保持原樣地進(jìn)入下一代群體；另一部分利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。遺傳算法通過(guò)把兩個(gè)父狀態(tài)結(jié)合來(lái)生成后繼8皇后的例子，其中每個(gè)狀態(tài)用一個(gè)長(zhǎng)度為8的字符串來(lái)表示，適應(yīng)度函數(shù)取作不相互攻擊的皇后對(duì)數(shù)目。128/69前一頁(yè)圖中（c）1和2生成（d）1啟發(fā)式搜索-遺傳算法遺傳算法的特點(diǎn)遺傳算法是一種成功的自適應(yīng)方法，具有很好的健壯性，易于并處理遺傳算法長(zhǎng)于全局搜索,它不受搜索空間的限制性假設(shè)的約束,能以很大的概率從離散的、多極值的、含有噪聲的復(fù)雜問(wèn)題中找到全局最優(yōu)解。遺傳欺騙：在遺傳算法進(jìn)化過(guò)程中，有時(shí)會(huì)產(chǎn)生一些超常的個(gè)體，因競(jìng)爭(zhēng)力太突出而控制了選擇運(yùn)算過(guò)程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個(gè)局部最優(yōu)解遺傳算法最主要的優(yōu)點(diǎn)（如果有的話）來(lái)自于雜交的操作但，數(shù)學(xué)上可以證明，如果基因編碼的位置在初始時(shí)候就隨機(jī)地轉(zhuǎn)換的話，雜交就沒(méi)有優(yōu)勢(shì)了。用模式的思想解釋遺傳算法模式是其中某些位置未確定的子串，例如246*****。但，目前還不清楚在什么情況下使用遺傳算法能夠達(dá)到好的效果。JamesBaldwin：在生物體存活的時(shí)間內(nèi)學(xué)習(xí)到的行為能夠加快進(jìn)化速度已被計(jì)算機(jī)仿真確認(rèn)130/69討論3.5.3 分支限界法

分支限界法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的葉節(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)為f(n)=g(n)。其思想是：建立一個(gè)局部路徑（或分支）的隊(duì)列表，每次都選耗散值最小的那個(gè)分支上的葉節(jié)點(diǎn)來(lái)擴(kuò)展，直到生成含有目標(biāo)節(jié)點(diǎn)的路徑為止。132/69分支界限法(最小代價(jià)優(yōu)先法)

●基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點(diǎn)進(jìn)行考察,而不管這個(gè)節(jié)點(diǎn)在搜索樹(shù)的什么位置上。

●算法與前面的“全局擇優(yōu)法”

僅有引導(dǎo)搜索的函數(shù)不同，前者為啟發(fā)函數(shù)h(x)，后者為代價(jià)g(x)。

●但注意：代價(jià)值g(x)是從初始節(jié)點(diǎn)So方向計(jì)算而來(lái)的,而啟發(fā)函數(shù)值h(x)則是朝目標(biāo)節(jié)點(diǎn)方向計(jì)算的。

分支限界法

過(guò)程Branch-Bound1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，計(jì)算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路徑g值最小者排在前面；7）GOLOOP；例：八城市地圖網(wǎng)問(wèn)題應(yīng)用分支限界法求解圖3-14的最短路徑問(wèn)題，其搜索圖如圖3-15所示。

圖3-14 八城市地圖網(wǎng)示意圖SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613圖3-15 分支限界搜索圖求解過(guò)程中QUEUE的結(jié)果：

初始（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）F（10）E（10）B（11）C（11）E（12））7）（F（10）E（10）B（11）C（11）E（12）B（13））8）（E（10）B（11）C（11）E（12）t（13)B（13）)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）B（15）A（15)C（15））11）（E（12）t（13）B（13）F（14）B（15）A（15）C（15））12）（t（13）B（13）F（14）D（14）B（15）A（15）C（15）F（16））13）結(jié)束。3.5.4 動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法實(shí)際上是對(duì)分支限界法的改進(jìn)。動(dòng)態(tài)規(guī)劃原理指出，求s→t的最佳路徑時(shí)，對(duì)某個(gè)中間節(jié)點(diǎn)I，只考慮s到I中具有最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的。具有動(dòng)態(tài)規(guī)劃原理的分支限界算法過(guò)程Dynamic-Programming1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE：=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，計(jì)算g（mi）=g（n，mi），REMOVE