搜索問題-人工智能

搜索問題1第三章 搜索問題

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

3.2回溯策略

3.3圖搜索策略

3.4盲目的圖搜索過程

3.5啟發(fā)式圖搜索過程搜索與搜索問題

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

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

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

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

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

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

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

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

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

回溯搜索策略例：四皇后問題在４×４方格的棋盤內，放置四個皇后使任意兩個皇后不在同一行、同一列、同一對角線（斜線）上要求：找出所有的擺法回溯搜索策略狀態(tài)描述：單個皇后位置的描述：用(i,j)表示皇后在第i行j列系統(tǒng)狀態(tài)的描述四個皇后((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ù)）當前狀態(tài)目標狀態(tài)g遞歸過程偽碼描述中用到的一些符號的含義：變量：DATA=當前狀態(tài)；RULES=規(guī)則集合序列表；R=當前調用規(guī)則；RDATA=新生成的狀態(tài)；PATH=當前解路徑表。常量：NIL=空表；FAIL=回溯點標記；LOOP=循環(huán)標號。謂詞：TERM(DATA)；(DATA滿足結束條件)DEADEND(DATA)；(DATA是非法狀態(tài))NULL(RULES)。(規(guī)則集合序列表空)函數(shù)：RETURN返回自變量的值；APPRULES求可應用的規(guī)則表；FIRST從表中取表頭的一個元素；TAIL除去表頭的一個元素后得到新表；GEN

調用規(guī)則生成新狀態(tài)；CONS在表頭插入新元素，構造新表；BACKTRACK(RDATA)遞歸過程作用于新狀態(tài)。 BACKTRACK（DATA）

DATA：當前狀態(tài)。 返回值：從當前狀態(tài)到目標狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL?；厮菟阉魉惴ㄟf歸過程BACKTRACK(DATA)1. ifTERM(DATA),returnNIL； //當DATA滿足終止條件時，返回空表.ifDEADEND(DATA),renturnFAIL； //當DATA狀態(tài)不合法時，必須回溯。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ī)則作用于當前狀態(tài)。8. PATH←BACKTRACK(RDATA)； //對新狀態(tài)遞歸調用本過程9. ifPATH=FAIL,goLOOP；

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

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

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

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

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

[3]

ifTERM(DATA),returnNIL //到達目標，成功返回[4]

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

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

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

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

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

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

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

圖搜索策略3.3圖搜索策略

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

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

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

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

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

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

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

(Closed)待擴展的節(jié)點

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

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

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

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

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

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

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

f(n)=g(n)+h(n) f(n)：評價函數(shù)

h(n)：啟發(fā)函數(shù)g(x)——從初始節(jié)點S0到節(jié)點x的實際代價；h(x)——從x到目標節(jié)點Sg的最優(yōu)路徑的評估代價，它體現(xiàn)了問題的啟發(fā)式信息，其形式要根據(jù)問題的特性確定，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)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值91/64符號的意義92/64開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針失敗成功圖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é)點添入G，計算

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é)點按f

值從小到大排序;

8.

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

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

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

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

w(n)=4h計算舉例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)目標123456OPEN和CLOSED表的元素排列如下：

OPEN表：1）初始化（s（4））2）第一循環(huán)結束（B（4）A（6）C（6））3)第二循環(huán)結束（D（5）E（5）A（6）C（6）F（6））4)第三循環(huán)結束（E（5）A（6）C（6）F（6）G（6）H（7））5)第四循環(huán)結束（I（5）A（6）C（6）F（6）G（6）H（7）J（7））6)第五循環(huán)結束（K（5）A（6）C（6）F（6）G（6）H（7）J（7））7)第六循環(huán)結束（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循環(huán)結束在算法第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)極大地依賴于評價函數(shù)，特別是h(n),即：從節(jié)點n到目標節(jié)點最佳路徑的估計耗散假定h*(n)表示節(jié)點n到目標節(jié)點最佳路徑的實際耗散如果h(n)>

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

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

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

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

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

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

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

又是什么問題2：這個啟發(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*算法當h(n)<=h*(n)

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

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

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

(3)產生新解S’

(4)計算增量Δt’=C(S’)-C(S)，其中C(S)為評價函數(shù)

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

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

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

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

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

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

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

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

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

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

●但注意：代價值g(x)是從初始節(jié)點So方向計算而來的,而啟發(fā)函數(shù)值h(x)則是朝目標節(jié)點方向計算的。

分支限界法

過程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}，計算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路徑g值最小者排在前面；7）GOLOOP；例：八城市地圖網(wǎng)問題應用分支限界法求解圖3-14的最短路徑問題，其搜索圖如圖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 分支限界搜索圖求解過程中QUEUE的結果：

初始（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）結束。3.5.4 動態(tài)規(guī)劃法

動態(tài)規(guī)劃法實際上是對分支限界法的改進。動態(tài)規(guī)劃原理指出，求s→t的最佳路徑時，對某個中間節(jié)點I，只考慮s到I中具有最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的。具有動態(tài)規(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}，計算g（mi）=g（n，mi），REMOVE