第二章人工智能搜索問題

人工智能第二章搜索問題本章的內(nèi)容與目標搜索與搜索問題搜索問題的求解步驟無信息（盲目）搜索有信息（啟發(fā)式）搜索搜索與搜索問題

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

根據(jù)問題的實際情況不斷尋找可利用的知識，從而構(gòu)造一條代價較少的推理路線，使問題得到圓滿解決的過程稱之為搜索。搜索方法的經(jīng)典應用8數(shù)碼問題傳教士和野人問題旅行商問題4皇后問題迷宮問題博弈問題…………搜索方法的一般步驟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)，若不是則轉(zhuǎn)到4，否則轉(zhuǎn)到66、搜索成功,記錄搜索路徑用open表和closed表保存搜索經(jīng)過的各個節(jié)點open表和closed表的一般結(jié)構(gòu)無信息搜索又稱盲目搜索/窮舉式搜索，只能按照預先規(guī)定的搜索控制策略進行搜索，沒有任何中間信息來改變這些控制策略。具有盲目性，效率不高，不便于復雜問題的求解。常用方法有廣度優(yōu)先搜索和深度優(yōu)先搜索以及這兩種搜索方法的改良方法。寬度優(yōu)先搜索最簡便的圖的搜索算法之一，屬于一種盲目搜尋法。目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果?；舅枷胧鞘紫人阉骱统跏脊?jié)點距離為1的所有頂點，然后再去搜索和出始節(jié)點距離為2的其他頂點，依次類推它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

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

—代價樹寬度搜索代價樹寬度搜索（代價一致搜索）對于任意單步路徑耗散都是最優(yōu)的搜索策略其基本思想是優(yōu)先擴展路徑耗散最小的節(jié)點對于任意節(jié)點n，用f(n)來表示n到初始節(jié)點的路徑耗散，即代價代價樹寬度搜索例：旅行商問題設(shè)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,則搜索成功,結(jié)束。步5若N不可擴展,則轉(zhuǎn)步2。步6擴展N,將其所有子節(jié)點配上指向N的返回指針依次放入OPEN表的首部,轉(zhuǎn)步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)先搜索優(yōu)點：對內(nèi)存需求比較少，如果一個節(jié)點的全部后代都被完全探索過，那么這個節(jié)點和它的全部后繼都可以從內(nèi)存(open表和closed表)中刪掉了缺點：不完備，也不最優(yōu)回溯搜索策略回溯策略屬于深度優(yōu)先搜索的一種變形與深度優(yōu)先搜索的區(qū)別：擴展一個節(jié)點時，每次只產(chǎn)生一個后繼節(jié)點，而不是全部后繼回溯策略只保存單一的解路徑，占用內(nèi)存空間很少，只需要一張表即可完成搜索回溯搜索策略例：四皇后問題在４×４方格的棋盤內(nèi)，放置四個皇后使任意兩個皇后不在同一行、同一列、同一對角線（斜線）上要求：找出所有的擺法回溯搜索策略狀態(tài)描述：單個皇后位置的描述：用(i,j)表示皇后在第i行j列系統(tǒng)狀態(tài)的描述四個皇后((i1,j1),(i2,j2),(i3,j3),(i4,j4))深度優(yōu)先搜索的拓展

——深度有限搜索深度有限搜索預先設(shè)定一個搜索深度l，用以解決搜索樹無邊界的問題搜索過程中認為深度為l的節(jié)點沒有后繼節(jié)點，必須回溯缺點：增加了算法的不完備性雙向搜索雙向搜索同時進行兩個搜索，可以采用任意搜索方法一個從初始狀態(tài)向前搜索另一個從目標狀態(tài)向后搜索當兩個搜索在某個節(jié)點相遇時，搜索成功無信息搜索的討論算法評判完備性——是否一定能找到目標節(jié)點最優(yōu)性——搜索得到的解是否最優(yōu)解時間復雜度——算法的時間需求空間復雜度——算法對計算機內(nèi)存的需求無信息搜索的討論重復狀態(tài)擴展一個節(jié)點時，新生成的節(jié)點已經(jīng)在open表或者closed表中存在了，這種情況稱為重復狀態(tài)有些情況下，重復狀態(tài)會導致搜索失??；有些情況下，重復狀態(tài)可以保留，但是會帶來額外的計算資源的消耗因此，一般期望盡可能避免重復狀態(tài)這時，有可能出現(xiàn)節(jié)點指針重新定向的情況無信息搜索的討論問題的形式化描述狀態(tài)描述——用數(shù)學方法定義系統(tǒng)狀態(tài)初始狀態(tài)、目標狀態(tài)行動規(guī)則——產(chǎn)生后繼節(jié)點目標測試——判斷當前節(jié)點是否就是目標節(jié)點路徑耗散——為每一條搜索路徑定義數(shù)值化的消耗值無信息搜索的討論狀態(tài)描述八數(shù)碼問題3X3的二維數(shù)組行動規(guī)則假設(shè)r[i][j]=0,則它跟相鄰元素可以互換無信息搜索的討論狀態(tài)描述4皇后問題狀態(tài)：在棋盤上任意放置1-4個皇后，每一種放置都是一個狀態(tài)狀態(tài)描述：逐一給出各個皇后的放置位置行動規(guī)則：增加一個皇后到棋盤上的任何空格無信息搜索的討論狀態(tài)描述四色問題，又稱四色猜想，世界近代三大數(shù)學難題之一要求：只用四種顏色對平面地圖染色，要求每兩個相同區(qū)域不能染成相同顏色1976年美國數(shù)學家阿佩爾（K.Appel）與哈肯（W.Haken）宣告借助電子計算機獲得了四色定理的證明，又為用計算機證明數(shù)學定理開拓了前景無信息搜索的討論四色問題的狀態(tài)描述若干地區(qū)，四種顏色狀態(tài)：對任意地區(qū)的進行染色，任意染色結(jié)果都是一種狀態(tài)狀態(tài)描述：用s[k]表示第k個地區(qū)的染色，逐一列出所有地區(qū)的染色就是系統(tǒng)的狀態(tài)描述行動規(guī)則：給一個沒有染色的地區(qū)染色無信息搜索的討論吸塵器的世界只有兩個房間A和B每個房間有可能有灰塵也可能沒有吸塵器可以在兩個房間里移動如果有灰塵，則吸??；否則移動到另一個房間狀態(tài)：吸塵器位置，房間A、B有沒有灰塵狀態(tài)描述：三元組（A,B,C）行動規(guī)則：三個（ToA,ToB,suck）無信息搜索的討論課堂練習自動抓藥系統(tǒng)三個勺子，容量分別為8克、5克和2克可以從藥箱把勺子裝滿或倒空，也可以從一個勺子倒進另一個勺子目標是從藥箱抓1克藥給出狀態(tài)描述、初始狀態(tài)、目標狀態(tài)以及行動規(guī)則狀態(tài)：三個勺子中藥物的數(shù)量狀態(tài)描述：（m1，m2，m3）初始狀態(tài)：（0，0，0）目標狀態(tài):(1,x,x)或(x,1,x)或(x,x,1)行動規(guī)則：抓滿、倒空或者倒進另一個勺子啟發(fā)式搜索啟發(fā)式搜索，也稱為有信息搜索，借助問題的特定知識來幫助選擇搜索方向在搜索過程中對待擴展的每一個節(jié)點進行評估，得到最好的位置，再從這個位置進行搜索直到目標。啟發(fā)式搜索的目的是省略大量無謂的搜索路徑，提到效率。在啟發(fā)式搜索中，對節(jié)點的評價是十分重要的，評價函數(shù)是搜索成敗的關(guān)鍵。啟發(fā)式搜索評價函數(shù)，也稱為啟發(fā)函數(shù)提供問題的啟發(fā)性信息，按其用途劃分，可分為以下三類：用于擴展節(jié)點的選擇，即用于決定應先擴展哪一個節(jié)點，以免盲目擴展用于生成節(jié)點的選擇，即用于決定應生成哪些后續(xù)節(jié)點，以免盲目地生成過多無用節(jié)點用于刪除節(jié)點的選擇，即用于決定應刪除哪些無用節(jié)點，以免造成進一步的時空浪費啟發(fā)式搜索一個節(jié)點n的評價函數(shù)的構(gòu)造通常由兩部分構(gòu)成從初始節(jié)點到當前節(jié)點n的路徑耗散從當前節(jié)點n到目標節(jié)點的期望耗散即：評價函數(shù)可表示為：這兩部分里，通常是比較明確的，容易得到而難以構(gòu)造，也沒有固定的模式，需要根據(jù)具體問題分析啟發(fā)式搜索貪婪搜索優(yōu)先擴展距離目標最近的節(jié)點例：西安到上海的貪婪搜索啟發(fā)式搜索貪婪搜索的啟發(fā)函數(shù)只考慮待擴展節(jié)點到目標節(jié)點的期望耗散，而不考慮初始節(jié)點到待擴展節(jié)點的實際耗散貪婪搜索類似于深度優(yōu)先搜索，總是先沿著一條枝搜索下去貪婪搜索既不是完備的，也不是最優(yōu)的啟發(fā)式搜索A算法代價樹寬度搜索只考慮初始節(jié)點到待擴展節(jié)點的路徑耗散貪婪搜索只考慮待擴展節(jié)點到目標節(jié)點的期望耗散A算法既考慮待擴展節(jié)點到目標節(jié)點的期望耗散，又考慮初始節(jié)點到待擴展節(jié)點的路徑耗散啟發(fā)式搜索A搜索算法的步驟步1把初始節(jié)點So放入OPEN表。步2若OPEN表為空,則搜索失敗,退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中,并冠以順序編號n。步4若目標節(jié)點Sg=N,則搜索成功,結(jié)束。步5若N不可擴展,則轉(zhuǎn)步2。步6擴展N,生成一組子節(jié)點,并利用評價函數(shù)為子節(jié)點估值，對這組子節(jié)點做如下處理：(1)處理重復狀態(tài)(2)對其余子節(jié)點配上指向N的返回指針后放入OPEN表中,并對OPEN表按f(n)值以升序排序,轉(zhuǎn)步2。取open表中f(n)最小的節(jié)點，放入closed表啟發(fā)式搜索A算法舉例八數(shù)碼問題確定用節(jié)點深度，也就是初始節(jié)點到待擴展節(jié)點移動的數(shù)碼的步數(shù)確定

不在位數(shù)碼的總數(shù)初始狀態(tài)：不在位的數(shù)碼為1，2，6，8；共四個數(shù)碼不在位由CLOSED表可知，解路徑為S0-S2-S5-S9-S11-S12啟發(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)，算法的搜索效率越高，對內(nèi)存和時間的需求越小如果滿足h(n)=h*(n)，是最完美的A*算法h(n)的設(shè)計是A*算法的核心，也是最困難的地方啟發(fā)式搜索啟發(fā)式函數(shù)的構(gòu)造思想之一松弛法放松行動規(guī)則約束的思想方法八數(shù)碼問題：行動規(guī)則：如果以下條件成立，則一個數(shù)碼可以從A方格移動到B方格

1、B為空

2、A與B相鄰放松約束1：A可以移動到B

放松約束2：如果A與B相鄰，則A可以移動到B

放松約束3：如果B為空，則A可以移動到B啟發(fā)式搜索啟發(fā)式搜索與最優(yōu)化問題求解現(xiàn)實問題時往往不能明確的知道解的形式，而是只有一堆約束條件，滿足約束條件的狀態(tài)就是一個合法的解滿足約束條件的解可能有很多個，人們希望找出使某個目標最滿意的解，稱為最優(yōu)解這樣的問題稱為最優(yōu)化問題目標條件就是搜索中的評價函數(shù)啟發(fā)式搜索最優(yōu)化問題目標條件（評價函數(shù)）約束條件表示在所有滿足約束條件的解中取目標條件最小的為最優(yōu)解啟發(fā)式搜索-爬山法爬山法模擬人們出游爬山的決策過程以目標值增加的方向為搜索方向如果有多個增加的方向，選使目標值增加速度最快的方向爬山法會在某個峰頂終止，其相鄰狀態(tài)中沒有更高的目標值了，稱為局部極大值啟發(fā)式搜索-爬山法爬山法的基本步驟1、初始化，確定初始節(jié)點等參數(shù)2、檢查當前節(jié)點是否滿足目標條件，如果滿足，則搜索成功，結(jié)束3、取鄰域中每一個相鄰節(jié)點，計算其目標函數(shù)的改進值4、取改進值最大的相鄰節(jié)點作為搜索目標，替換當前節(jié)點5、檢查是否滿足循環(huán)終止條件。如果滿足，則中止循環(huán)，否則轉(zhuǎn)步2啟發(fā)式搜索-爬山法爬山法的缺陷難以處理山肩的情況貪婪搜索方向不一定是正確的搜索方向啟發(fā)式搜索-爬山法爬山法的改進隨機爬山法：在上山移動中隨機的選擇下一步可回溯爬山法：給定啟發(fā)式的回溯策略，允許回頭搜索其他節(jié)點洪水爬山法：不斷尋找改進方向允許水平移動可回溯啟發(fā)式搜索-模擬退火算法模擬退火算法（simulatedannealing）爬山法是不完備的，有可能停留在局部最優(yōu)解上隨機行走（遍歷）是完備的，但是搜索效率很差模擬退火算法將爬山法與隨機行走結(jié)合起來，希望同時得到效率和完備性啟發(fā)式搜索-模擬退火算法模擬退火過程思想來源于固體退火原理，屬于熱力學范疇將固體加溫至充分高，再讓其緩慢冷卻加溫時，固體內(nèi)部的粒子隨溫升脫離原先的平衡態(tài)，變?yōu)闊o序狀緩慢冷卻時，粒子活性逐漸下降，逐漸停留在不同狀態(tài)，重新形成粒子的排列結(jié)構(gòu)如果降溫過程足夠緩慢，粒子的排列就會達到一種平衡態(tài)，使系統(tǒng)能量最小啟發(fā)式搜索-模擬退火算法初始狀態(tài)加溫冷卻啟發(fā)式搜索-模擬退火算法模擬退火的基本步驟:

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

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

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

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

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

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

(7)T逐漸減少，且T>0，然后轉(zhuǎn)第2步。啟發(fā)式搜索-模擬退火算法冷卻進度表：是指調(diào)整模擬退火法的一系列重要參數(shù)，它控制溫度參數(shù)T的初值及其衰減函數(shù)。冷卻進度表的內(nèi)容：控制參數(shù)T的初值;控制參數(shù)T的衰減函數(shù)；每一個溫度下的迭代次數(shù)L，即每一次隨機游走過程，要迭代多少次，才能趨于一個準平衡分布結(jié)束條件啟發(fā)式搜索-模擬退火算法Metropolis準則:假設(shè)在狀態(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ā)式搜索-模擬退火算法模擬退火算法的關(guān)鍵點初始溫度必須足夠高在每一個溫度下，狀態(tài)的轉(zhuǎn)換必須足夠充分溫度T的下降必須足夠緩慢啟發(fā)式搜索-模擬退火算法模擬退火算法的優(yōu)缺點

優(yōu)點：計算過程簡單，通用，魯棒性強適用于并行處理，可用于求解復雜的非線性優(yōu)化問題缺點：如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢;如果降溫過程過快，很可能得不到全局最優(yōu)解啟發(fā)式搜索-遺傳算法遺傳算法(geneticalgorithm,GA)

模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型是一種通過模擬自然進化過程的隨機優(yōu)化搜索方法美國Michigan大學J.Holland教授于1975年首先提出來的啟發(fā)式搜索-遺傳算法自然選擇過程遺傳算法啟發(fā)式搜索-遺傳算法遺傳算法的基本思想遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象在每次迭代中，根據(jù)適應度評估群體中的所有成員，然后選取適應度最高的個體產(chǎn)生新一代群體在被選中的個體中，一部分保持原樣地進入下一代群體；另一部分利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群重復此過程，直到滿足某種收斂指標為止。啟發(fā)式搜索-遺傳算法編碼編碼就是模擬染色體的結(jié)構(gòu)，染色體是由基因排成的串通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串，常用由0，1組成的字串常用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。啟發(fā)式搜索-遺傳算法例：將[0，1]之間的數(shù)編碼，精確到小數(shù)點以后兩位，即0.01，0.02，0.03…0.991、確定編碼長度：根據(jù)取值空間，可知有99種編碼結(jié)果，而，因此01編碼的長度為7位2、編碼：乘以100，然后轉(zhuǎn)化為7位二進制0.01→00000010.02→00000100.03→00000110.99→11000113、解碼啟發(fā)式搜索-遺傳算法啟發(fā)式搜索-遺傳算法適應度函數(shù)即評價函數(shù)，用來描述一個個體的好壞遺傳算法中，適應度函數(shù)值越大，解的質(zhì)量越好適應度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的