第3章-搜索原理

第3章搜索原理知識點(diǎn)重難點(diǎn)學(xué)習(xí)要求知識點(diǎn)盲目搜索啟發(fā)式搜索博弈樹搜索遺傳算法模擬退火算法

重難點(diǎn)寬度優(yōu)先深度優(yōu)先等代價搜索有序搜索A*算法博弈樹搜索學(xué)習(xí)要求重點(diǎn)掌握寬度優(yōu)先和深度優(yōu)先搜索算法掌握等代價搜索算法掌握啟發(fā)式搜索相關(guān)知識理解博弈樹搜索相關(guān)技術(shù)掌握遺傳算法基本原理理解模擬退火算法基本原理第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹搜索3.4遺傳算法3.5模擬退火算法3.1盲目搜索知識是解決問題的基礎(chǔ)，解決問題的方法一種就是算法，但對很多問題沒有有效的算法（或無現(xiàn)成算法），這時就可利用最一般方法即搜索來解決。1、搜索的概念根據(jù)問題的實際情況，按照一定的策略或規(guī)則，從知識庫中尋找可利用的知識，從而構(gòu)造出一條使問題獲得解決的推理路線的過程，就稱為搜索。盲目搜索（續(xù)）搜索包含兩層含義：一是要找到從初始事實到問題最終答案的一條推理路線，另一是找到的這條路線是時間和空間復(fù)雜度最小的求解路線。2、搜索的種類分為盲目搜索和啟發(fā)式搜索。

盲目搜索又稱無信息搜索，即在搜索過程中，只按預(yù)先規(guī)定的搜索控制策略進(jìn)行搜索，而沒有任何中間信息來改變這些控制策略。即問題本身的特性對搜索控制策略沒有任何影響，這就使搜索帶有盲目性，效率不高。只用于解決比較簡單的問題。盲目搜索（續(xù)）

啟發(fā)式搜索又稱有信息搜索，指搜索求解過程中，根據(jù)問題本身的特性或搜索過程中產(chǎn)生的一些信息來不斷改變或調(diào)整搜索的方向，使搜索朝著最有希望的方向前進(jìn)，加速問題的求解，并找到最優(yōu)解。求解的效率更高，更易于求解復(fù)雜的問題。盲目搜索（續(xù)）（1）寬度優(yōu)先搜索（2）深度優(yōu)先搜索（3）等代價搜索3.1.1圖搜索策略搜索法求解問題的基本思想:首先將問題的初始狀態(tài)(即狀態(tài)空間圖中的初始節(jié)點(diǎn))當(dāng)做當(dāng)前狀態(tài)，選擇一適當(dāng)?shù)乃惴饔糜诋?dāng)前狀態(tài)，生成一組后繼狀態(tài)（或稱后繼節(jié)點(diǎn)），然后檢查這組后繼狀態(tài)中有沒有目標(biāo)狀態(tài)。如果有，則說明搜索成功，從初始狀態(tài)到目標(biāo)狀態(tài)的一系列算符即是問題的解；若沒有，則按某種控制策略從已生成的狀態(tài)中再選一個狀態(tài)作為當(dāng)前狀態(tài)，重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或不再有可供操作的狀態(tài)及算符為止。圖搜索策略舉例從某王姓家族的四代中找王A的后代且其壽命為X的人。

王A：壽命47，有兒子王B1、王B3、王B2

王B1：壽命77，有兒子王C1、王C2

王B3：壽命52，有兒子王D1

王B2：壽命65，有兒子王E1、王E2

王F1：壽命32

王G1：壽命96

王C2：壽命87，有兒子王F1

王D1：壽命77，沒有兒子

王E1：壽命57，有兒子王G1

王E2：壽命92，有兒子王H1

王C1：壽命27，沒有兒子

王H1：壽命51

若X=57，下面討論一種可通用的圖搜索策略求解此問題。

用圖表示方法的家族表圖搜索策略（續(xù)）1、概念已擴(kuò)展節(jié)點(diǎn)：對于狀態(tài)圖中的某個節(jié)點(diǎn)，若求出了它的后繼節(jié)點(diǎn)，稱已擴(kuò)展節(jié)點(diǎn)。未擴(kuò)展節(jié)點(diǎn)：對于狀態(tài)圖中的某個節(jié)點(diǎn)，尚未求出它的后繼節(jié)點(diǎn)，稱未擴(kuò)展節(jié)點(diǎn)。擴(kuò)展：就是用合適的算符對某個節(jié)點(diǎn)進(jìn)行操作，生成一組后繼節(jié)點(diǎn)，擴(kuò)展過程實際上就是求后繼節(jié)點(diǎn)的過程。圖搜索策略（續(xù)）2、狀態(tài)空間圖的一般搜索算法用兩個表分別存放已擴(kuò)展節(jié)點(diǎn)和未擴(kuò)展節(jié)點(diǎn)，OPEN表存放未擴(kuò)展節(jié)點(diǎn)，CLOSED表存放已擴(kuò)展節(jié)點(diǎn)。兩個表的結(jié)構(gòu)如下：

OPEN表：

CLOSED表：節(jié)點(diǎn)父節(jié)點(diǎn)編號節(jié)點(diǎn)父節(jié)點(diǎn)狀態(tài)空間圖的一般搜索算法（1）建立一個只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到OPEN表中。（2）建立CLOSED表，且置為空表。（3）若OPEN表是空表，則問題無解，失敗退出。狀態(tài)空間圖的一般搜索算法（4）選擇OPEN表中的第一個節(jié)點(diǎn)，把它從OPEN表移出，并放入CLOSED表中，將此節(jié)點(diǎn)記為節(jié)點(diǎn)n，它是CLOSED表中節(jié)點(diǎn)的編號。（5）若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出。問題的解即可從圖G中沿著指針從n到S這條路徑而得到。

IFGOAL(N)THENEXIT(SUCCESS)狀態(tài)空間圖的一般搜索算法（6）擴(kuò)展節(jié)點(diǎn)n，同時生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M中的這些成員作為n的后繼節(jié)點(diǎn)加入圖G中。狀態(tài)空間圖的一般搜索算法（7）針對M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理對那些未曾在G中出現(xiàn)過的（既未曾在OPEN表上或CLOSED表上出現(xiàn)過的）M成員設(shè)置一個通向n的指針。把M的這些成員加進(jìn)OPEN表。對已經(jīng)在OPEN表或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后繼節(jié)點(diǎn)的指針方向。狀態(tài)空間圖的一般搜索算法（8）按某種搜索策略對OPEN表中的節(jié)點(diǎn)進(jìn)行排序。（9）轉(zhuǎn)第（3）步。

GOLOOP一般搜索過程框圖例子例子SOPENCLOSE{S}{}123{}{S}{1,2,3}{S}{2,1,3}{S}45{1,3}{S,2}{1,3,4,5}{S,2}{3,1,4,5}{S,2}{1,4,5}{S,2,3}6{1,4,5,6}{S,2,3}圖搜索策略（續(xù)）3、搜索圖與搜索樹

圖搜索過程生成一個明確的圖G（稱為搜索圖）和一個G的子集T（稱為搜索樹），樹T上的每個節(jié)點(diǎn)也在圖G中。例：二階Hanoi塔問題。狀態(tài)空間圖如下。（1，1）（2，1）（3，1）（2，3）（3，2）（3，3）（1，3）（1，2）（2，2）A(2,1)A(1,2)初始狀態(tài)目標(biāo)狀態(tài)SS1S2S3S4S5S6S7S8圖搜索策略（續(xù)）搜索圖G為：搜索樹T為：SS1S2S3S4S5S6S7S8S8SS1S2S3S4S5S6S7圖搜索策略（續(xù)）4、圖搜索方法的幾點(diǎn)分析（1）對OPEN表進(jìn)行排序（盲目或啟發(fā)式搜索）。（2）被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時，成功，回溯，可找到路徑。否則，失敗終止情況下沒有解路徑。

在利用狀態(tài)空間搜索方法求解問題時，并不是將整個問題的狀態(tài)空間圖全部輸入計算機(jī)，而是只存入問題有關(guān)的部分狀態(tài)空間圖，這部分是在搜索過程中生成的，并且每前進(jìn)一步，都要檢查是否到達(dá)目標(biāo)節(jié)點(diǎn)，這樣就可盡量減少生成與問題求解無關(guān)的狀態(tài)，從而提高了解題效率，節(jié)省了存儲空間。3.1.2寬度優(yōu)先搜索定義如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。寬度優(yōu)先搜索又稱廣度優(yōu)先搜索，是一種盲目搜索策略。其基本思想是：從初始節(jié)點(diǎn)開始，逐層對節(jié)點(diǎn)進(jìn)行依次擴(kuò)展，并考慮它是否為目標(biāo)節(jié)點(diǎn)，在對下層節(jié)點(diǎn)進(jìn)行擴(kuò)展（或搜索）前，必須完成對當(dāng)前層的所有節(jié)點(diǎn)的擴(kuò)展（或搜索）。寬度優(yōu)先搜索特點(diǎn)：OPEN表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面寬度優(yōu)先搜索示意圖寬度優(yōu)先搜索算法(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解答)。

(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。

(3)把第一個節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。

寬度優(yōu)先搜索算法(4)擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。

(5)把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。

(6)如果n的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。寬度優(yōu)先搜索算法框圖寬度優(yōu)先搜索方法分析（1）將OPEN表作為“先進(jìn)先出”的隊列進(jìn)行操作；（2）寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短路徑（即寬度優(yōu)先搜索策略是完備的）；（3）搜索樹提供了所有存在的路徑；（4）盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)較遠(yuǎn)時，將產(chǎn)生大量無用節(jié)點(diǎn)。重排九宮問題初始狀態(tài)目標(biāo)狀態(tài)算符：左移、上移、右移、下移優(yōu)點(diǎn)：只要有解，用廣度優(yōu)先搜素總可以得到，而且路徑最短缺點(diǎn)：搜索效率低，特別是目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題3.1.3深度優(yōu)先搜索定義深度優(yōu)先搜索也是一種盲目搜索策略，其基本思想是：首先擴(kuò)展最新產(chǎn)生的（即最深）節(jié)點(diǎn)，即從初始節(jié)點(diǎn)S開始，在其后繼節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)，對其進(jìn)行考察，若它不是目標(biāo)節(jié)點(diǎn)，則對該節(jié)點(diǎn)進(jìn)行擴(kuò)展，并再從它的后繼節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察。依次類推，一直搜索下去，當(dāng)?shù)竭_(dá)某個既非目標(biāo)節(jié)點(diǎn)又無法繼續(xù)擴(kuò)展的節(jié)點(diǎn)時，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。深度優(yōu)先搜索示意圖定義節(jié)點(diǎn)的深度(1)起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。

(2)任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1。

深度優(yōu)先搜索（續(xù)）有界深度優(yōu)先搜索為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴(kuò)展下去)，往往給出一個節(jié)點(diǎn)擴(kuò)展的最大深度，即深度界限(dm)。任何節(jié)點(diǎn)如果達(dá)到了深度界限，都將被作為沒有后繼節(jié)點(diǎn)處理。有界深度優(yōu)先搜索算法(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個解。

(2)如果OPEN為一空表，則失敗退出。

(3)把第一個節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移到CLOSED表。

(4)如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向(2)。

(5)擴(kuò)展節(jié)點(diǎn)n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向(2)。

(6)如果后繼節(jié)點(diǎn)中有任一個為目標(biāo)節(jié)點(diǎn)，則求得一個解，成功退出；否則，轉(zhuǎn)向(2)。

有界深度優(yōu)先搜索算法框圖深度優(yōu)先搜索策略分析（1）將OPEN表作為“先進(jìn)后出”的棧進(jìn)行操作；（2）深度優(yōu)先搜索所求得的解答路徑不一定是最短路徑；（3）深度界限得選擇很重要，過大，可能會影響搜索效率，過小，有可能求不到解。有界深度優(yōu)先搜索策略是不完備的。深度界限dm的選擇先任意給定一個較小的數(shù)作為dm，進(jìn)行有界深度的優(yōu)先搜索，當(dāng)深度達(dá)到dm時仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，且CLOSE表中人有待擴(kuò)展節(jié)點(diǎn)時，將這些節(jié)點(diǎn)送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。只要有解，一定可以找到。按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，深度界限為53.1.4等代價搜索定義有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。等代價搜索（續(xù)）代價樹：邊上有代價（或費(fèi)用）S：起始節(jié)點(diǎn)。c(i,j):

節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的連接弧線代價。g(i):

起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價，在搜索樹上它也是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)i的最少代價路徑上的代價。代價的計算公式：g(j)=g(i)+c(i,j)等代價搜索的基本思想每次從OPEN表中選擇節(jié)點(diǎn)向CLOSE中傳送時，總是選擇其代價為最小的節(jié)點(diǎn)等代價搜索（續(xù)）等代價搜索算法

與寬度優(yōu)先搜索算法區(qū)別，以g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，即根據(jù)節(jié)點(diǎn)的代價大小對OPEN表中的所有節(jié)點(diǎn)進(jìn)行從小到大的排序。（1）把起始節(jié)點(diǎn)S放到OPEN表中。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解；否則令g(S)=0；（2）如果OPEN表是個空表，則沒有解而失敗退出；等代價搜索（續(xù)）（3）從OPEN表中選擇一個節(jié)點(diǎn)i，使其g(i)為最小。如果有幾個節(jié)點(diǎn)都合格，那么就要選擇一個目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn)i（如果有目標(biāo)節(jié)點(diǎn)）；否則，就從中選一個作為節(jié)點(diǎn)i。把節(jié)點(diǎn)i從OPEN表移至CLOSED表中；（4）如果節(jié)點(diǎn)i為目標(biāo)節(jié)點(diǎn)，則求得一個解；（5）擴(kuò)展節(jié)點(diǎn)i。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向步驟（2）（6）對于節(jié)點(diǎn)i的每個后繼節(jié)點(diǎn)j，計算g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點(diǎn)j放進(jìn)OPEN表。提供回到節(jié)點(diǎn)i的指針。（7）轉(zhuǎn)向步驟（2）。等代價搜索（續(xù)）舉例分析例：推銷員旅行問題。

假設(shè)A，B，C，D，E是5個城市，推銷員從城市A出發(fā)，到達(dá)城市E，走怎樣的路線費(fèi)用最省？5個城市間的交通圖及每兩個城市間的旅行費(fèi)用如圖所示。ABCDE675348畫代價樹的原則作業(yè)1、分別用寬度優(yōu)先搜索、有界深度優(yōu)先搜索（深度界限5）求解下圖所示八數(shù)碼難題。初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，并畫出對應(yīng)搜索樹。2318476512384765S0Sg作業(yè)（續(xù)）2、推銷員旅行問題。設(shè)有5個相互直達(dá)的城市A、B、C、D、E，如下圖所示，各城市間的交通費(fèi)用已在圖中標(biāo)出。推銷員從城市A出發(fā)，去每個城市各旅行一次，最后到達(dá)城市E，請找出一條費(fèi)用最省的旅行路線。80ABCDE90858065170110140160100第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹搜索3.4遺傳算法3.5模擬退火算法3.1啟發(fā)式搜索

啟發(fā)式搜索要用到問題自身的某些特性信息，以指導(dǎo)搜索朝著有希望的方向前進(jìn)。搜索效率高概念：啟發(fā)性信息啟發(fā)信息是進(jìn)行搜索技術(shù)所需要的一些有關(guān)具體問題領(lǐng)域的特性的信息。按用途可分為3種。（1）用于決定要擴(kuò)展的下一個節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴(kuò)展。概念：啟發(fā)性信息（2）在擴(kuò)展一個節(jié)點(diǎn)的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點(diǎn)，以免盲目地同時生成所有可能的節(jié)點(diǎn)。（3）用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。概念：估價函數(shù)用于評估節(jié)點(diǎn)重要性的函數(shù)，叫做估價函數(shù)概念：估價函數(shù)一個節(jié)點(diǎn)的“希望”有幾種不同的定義方法。在狀態(tài)空間問題中，一種定義是估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離；另一種定義是整條路徑（包括被估價過的節(jié)點(diǎn)）的長度或難度。用符號f來標(biāo)記估價函數(shù)，用f(n)表示節(jié)點(diǎn)n的估價函數(shù)值。估價函數(shù)的一般形式f(x)=g(x)+h(x)f(x)：估價函數(shù)定義為從初始節(jié)點(diǎn)經(jīng)過節(jié)點(diǎn)x到達(dá)目標(biāo)節(jié)點(diǎn)的最小代價路徑的代價估計值。作用是估價OPEN表中各節(jié)點(diǎn)的重要性，決定OPEN表的次序；g(x)為初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)付出的實際代價；h(x)為從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的估計的最小路徑代價。

搜索信息主要由h(x)來體現(xiàn)，稱為啟發(fā)函數(shù)。估價函數(shù)的要點(diǎn)啟發(fā)式搜索（續(xù)）3、有序搜索用估價函數(shù)f來排列OPEN表上的節(jié)點(diǎn)，選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索或最佳優(yōu)先搜索。它總是選擇最有希望的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)。有序搜索又可分為兩種：局部最佳優(yōu)先搜索和全局最佳優(yōu)先搜索。有序搜索的算法1)把起始節(jié)點(diǎn)S放到OPEN表中，計算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來。

(2)如果OPEN是個空表，則失敗退出，無解。

(3)從OPEN表中選擇一個f值最小的節(jié)點(diǎn)i。結(jié)果有幾個節(jié)點(diǎn)合格，當(dāng)其中有一個為目標(biāo)節(jié)點(diǎn)時，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個節(jié)點(diǎn)作為節(jié)點(diǎn)i。

有序搜索的算法(4)把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。

(5)如果i是個目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個解。

(6)擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對于i的每一個后繼節(jié)點(diǎn)j：有序搜索的算法(a)計算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時記住一個解答路徑。(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則

有序搜索的算法(i)以此新值取代舊值。

(ii)從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii)如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表(7)轉(zhuǎn)向(2)，即GOTO(2)。

有序搜索的算法框圖估價函數(shù)例子——解決九宮問題

采用簡單的估價函數(shù)f(n)=d(n)+w(n),d(n)是搜索樹中節(jié)點(diǎn)n的深度；w(n)用來計算節(jié)點(diǎn)n與目標(biāo)狀態(tài)節(jié)點(diǎn)Sg相比較，錯位的數(shù)碼個數(shù)。估價函數(shù)例子——解決九宮問題28316475初始狀態(tài)f值等于0+4=4

1（4）（6）

（6）

（7）4（5）

2（4）

（6）5（5）

6（5）

（5）

（7）

（7）

（7）（6）（5）估價函數(shù)例子結(jié)論估價函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點(diǎn)數(shù)用估價函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程有序搜索寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索均是有序搜索的特例。寬度優(yōu)先搜索，f(i)是節(jié)點(diǎn)i的深度。等代價搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價。有序搜索的特點(diǎn)即使有解，不一定能找到解特點(diǎn)是使用啟發(fā)式信息（估價函數(shù)），可他有時也會騙人，使人誤入歧途。有序搜索即使能找到解，也不一定是最優(yōu)的有序搜索（續(xù)）

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。

A算法定義：在圖搜索過程中，如果OPEN表節(jié)點(diǎn)順序是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，稱該過程為A算法。A*算法一般搜索過程滿足了如下限制A*算法的定義如果對于所有的x，h(x)≤h*(x)成立。采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。說明：搜索算法的可采納性

在搜索圖存在從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)解答路徑的情況下，若一個搜索方法總能找到最短（代價最?。┑慕獯鹇窂?，則稱該算法具有可采納性。A*算法為了考察啟發(fā)式搜索算法A的可采納性，首先引入估價函數(shù)f*：f*(x)=g*(x)+h*(x)f*(x)、g*(x)、h*(x)分別指示當(dāng)經(jīng)由節(jié)點(diǎn)x的最短（代價最?。┙獯鹇窂秸业綍r實際的路徑代價（長度）、該路徑前段（自初始節(jié)點(diǎn)到節(jié)點(diǎn)x）代價和后段（自節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)）代價。A*算法一般來講，g(x)的值容易從迄今已生成的搜索樹中計算出來，不必專門定義計算公式。這時g(x)≥g*(x)。然而h(x)的設(shè)計依賴于啟發(fā)式知識的應(yīng)用，所以如何挖掘貼切的啟發(fā)式知識是設(shè)計估價函數(shù)乃至A算法的關(guān)鍵?？梢宰C明，若確保對于搜索圖中的節(jié)點(diǎn)x，總是有h(x)≤h*(x)，則A算法具有可采納性，既總能搜索到最短（代價最?。┑慕獯鹇窂健Ｋ訟*算法是可采納的。A*算法(1)把S放入OPEN表，記f=h，令CLOSED為空表。(2)重復(fù)下列過程，直至找到目標(biāo)節(jié)點(diǎn)止。若OPEN為空表，則宣告失敗。(3)選取OPEN表中未設(shè)置過的具有最小f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn)BESTNODE，并把它放入CLOSED表。(4)若BESTNODE為一目標(biāo)節(jié)點(diǎn)，則成功求得一解。(5)若BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn)SUCCSSOR。(6)對每個SUCCSSOR進(jìn)行下列過程：

A*算法(a)建立從SUCCSSOR返回BESTNODE的指針。(b)計算g(SUC)=g(BES)+g(BES,SUC)。(c)如果SUCCSSOR∈OPEN，則稱此節(jié)點(diǎn)為OLD，并把它添至BESTNODE的后繼節(jié)點(diǎn)表中。(d)比較新舊路徑代價。如果g(SUC)＜g(OLD),則重新確定OLD的父輩節(jié)點(diǎn)為BESTNODE，記下較小代價g(OLD),并修正f(OLD)值。A*算法(e)若至OLD節(jié)點(diǎn)的代價較低或一樣，則停止擴(kuò)展節(jié)點(diǎn)。(f)若SUCCSSOR不在CLOSE表中，則看其是否在CLOSED表中。(g)若SUCCSSOR在CLOSE表中，則轉(zhuǎn)向c。(h)若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，則把它放入OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向(7)(i)計算f值。(7)GOLOOP

作業(yè)分別利用估價函數(shù)f(n)=d(n)+w(n)和f(n)=d(n)+p(n)，采用最佳優(yōu)先搜索方法求解下列八數(shù)碼問題。初始狀態(tài)S0，目標(biāo)狀態(tài)Sg，要求尋找從初始狀態(tài)到目標(biāo)狀態(tài)的路徑，并畫出對應(yīng)搜索樹。1372468512384765S0Sg第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹搜索3.4遺傳算法3.5模擬退火算法3.3博弈樹搜索下棋、打牌、戰(zhàn)爭等一類競爭性智能活動稱為博弈。3.3博弈樹搜索1、概述討論最簡單的“二人零和、全信息、非偶然”博弈，特征有：（1）對壘雙方輪流采取行動，結(jié)果有3種：甲勝、乙勝、和局；（2）在對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷史；（3）雙方都是很理智的決定自己的行動。博弈樹搜索（續(xù)）描述博弈過程的與或樹稱為博弈樹，有如下特點(diǎn)：（1）博弈的初始格局是初始節(jié)點(diǎn)；（2）在博弈樹中，“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的。自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。雙方輪流地擴(kuò)展節(jié)點(diǎn)。（3）所有自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都認(rèn)為是不可解節(jié)點(diǎn)。極大極小分析法（1）設(shè)博弈的雙方一方為MAX，另一方為MIN，然后為其中的一方（例如MAX）尋找一個最優(yōu)行動方案；（2）考慮每一方案實施后，對方可能采取的所有行動，計算可能的得分；（3）定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時估算出來的得分稱為靜態(tài)估值；博弈樹搜索（續(xù)）（4）推算出父節(jié)點(diǎn)的得分。對“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最大的得分作為父節(jié)點(diǎn)的得分；對“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個最小的得分作為父節(jié)點(diǎn)的得分。這樣計算出的父節(jié)點(diǎn)的得分稱為倒推值；例：倒推值的計算（5）若一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好得行動方案。博弈樹搜索（續(xù)）可行的辦法是只生成一定深度的博弈樹，然后進(jìn)行極大極小分析，找出當(dāng)前最好的行動方案。此后，再在已選定的分支上擴(kuò)展一定深度，再選最好的行動方案，如此進(jìn)行下去，直到取得勝敗的結(jié)果為止。至于每生成博弈樹深度，當(dāng)然是越大越好，具體視情況而定。博弈樹搜索（續(xù)）實例：“一”字棋游戲極大極小分析法九個空格，誰先使自己的棋子構(gòu)成“三子成一線”（同一行或同一列或?qū)蔷€全是某人的棋子），誰就取得了勝利。用叉號代表MAX，用圓圈代表MIN。如下圖為MIN取勝的棋局。博弈樹搜索（續(xù)）為了不致于生成太大的博弈樹，假設(shè)每次擴(kuò)展兩層。估價函數(shù)定義如下：設(shè)棋局為P，估價函數(shù)為e(P)；（1）若P對任何一方來說都不是獲勝位置，則e(P)=e(那些仍為MIN空著的完全的行、列、對角線的總數(shù))-e(那些仍為MAX空著的完全行、列、對角線的總數(shù))；（2）若P是MAX必勝的棋局，則e(P)=+∞；（3）若P是MIN必勝的棋局，則e(P)=-∞。博弈樹搜索（續(xù)）比如P如右圖所示，則：e(P)=6-4=2要注意利用棋盤位置的對稱性，在生成后繼節(jié)點(diǎn)位置時，下列結(jié)局都是相同的棋局。博弈樹搜索（續(xù)）下面是經(jīng)過兩層搜索生成的博弈樹，靜態(tài)估值記在端節(jié)點(diǎn)下面。博弈樹搜索例2剪枝技術(shù)剪枝原因博弈樹生成的工作量大，鑒于博弈樹具有“與”節(jié)點(diǎn)，“或”節(jié)點(diǎn)逐層交替出現(xiàn)的特點(diǎn)，若能邊生成節(jié)點(diǎn)邊計算估值及倒推值，則可刪除一些不必要的節(jié)點(diǎn)。減少搜索計算的工作量剪枝技術(shù)的基本思想在生成博弈樹的同時計算評估各節(jié)點(diǎn)的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。剪枝技術(shù)例α-β剪枝技術(shù)α-β剪枝的一般規(guī)律α-β剪枝例子第3章搜索原理3.1盲目搜索3.2啟發(fā)式搜索3.3博弈樹搜索3.4遺傳算法3.5模擬退火算法3.4遺傳算法遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類搜索算法，是對生物進(jìn)化過程進(jìn)行的數(shù)學(xué)方式仿真。1965年由霍蘭德提出，現(xiàn)在國際上已經(jīng)形成了一個比較活躍的研究領(lǐng)域。遺傳算法已用于求解帶有應(yīng)用前景的一些問題，例如遺傳程序設(shè)計、函數(shù)優(yōu)化、排序問題、人工神經(jīng)網(wǎng)絡(luò)、分類系統(tǒng)、計算機(jī)圖像處理和機(jī)器人運(yùn)動規(guī)劃等。遺傳算法（續(xù)）生物種群的生存過程普遍遵循達(dá)爾文進(jìn)化準(zhǔn)則，群體中的個體根據(jù)對環(huán)境的適應(yīng)能力而被大自然所選擇或淘汰。進(jìn)化過程的結(jié)果反映在個體的結(jié)構(gòu)上，其染色體包含若干基因，相應(yīng)的表現(xiàn)型和基因型的聯(lián)系體現(xiàn)了個體的外部特性與內(nèi)部機(jī)理間邏輯關(guān)系。通過個體之間的交叉、變異來適應(yīng)大自然環(huán)境。生物染色體用數(shù)學(xué)方式或計算機(jī)方式來體現(xiàn)就是一串?dāng)?shù)碼，仍叫染色體，有時也叫個體；適應(yīng)能力是對應(yīng)著一個染色體的一個數(shù)值來衡量；染色體的選擇或淘汰則按所面對的問題是求最大還是最小來進(jìn)行。遺傳算法的基本原理霍蘭德(Holland)的遺傳算法通常被稱為“簡單遺傳算法”(簡稱SGA)，以此作為討論主要對象，加上適當(dāng)?shù)母倪M(jìn)，分析遺傳算法的結(jié)構(gòu)和機(jī)理。

1.編碼與譯碼將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫譯碼。我們把位串形式編碼表示叫染色體，有時也叫個體。1.編碼與譯碼應(yīng)用舉例----貨郎擔(dān)問題(TravellingSalesmanProblem，簡記為TSP)：設(shè)有n個城市，城市i和城市j之間的距離為d(i，j)i,j=1,...,n．TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短。

1.編碼與譯碼對TSP可以按一條回路城市的次序進(jìn)行編碼，比如碼串134567829表示從城市1開始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情況是從城市w1開始，依次經(jīng)過城市w2,……，wn，最后回到城市w1，我們就有如下編碼表示：

w1w2……wn

由于是回路，記wn+1=w1。它其實是1，……，n的一個循環(huán)排列。要注意w1,w2,……，wn是互不相同的。

2.適應(yīng)度函數(shù)為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)。通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)勝劣汰原則。對優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以為TSP的適應(yīng)度函數(shù)：

請注意其中wn+1=w1。2.適應(yīng)度函數(shù)

適應(yīng)度函數(shù)要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距，一個染色體與問題的最優(yōu)解染色體之間的差距小，則對應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。

3.遺傳操作

簡單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。

遺傳操作——選擇操作選擇操作也叫復(fù)制操作，根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應(yīng)度較大(優(yōu)良)個體有較大的存在機(jī)會，而適應(yīng)度較小（低劣）的個體繼續(xù)存在的機(jī)會也較小。

遺傳操作——交叉操作交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進(jìn)行交換。假設(shè)有如下八位長的二個體：

遺傳操作——交叉操作產(chǎn)生一個在1到7之間的隨機(jī)數(shù)c，假如現(xiàn)在產(chǎn)生的是3，將P1和P2的低三位交換：P1的高五位與P2的低三位組成數(shù)串10001001，這就是P1和P2的一個后代Q1個體；P2的高五位與P1的低三位組成數(shù)串11011110，這就是P1和P2的一個后代Q2個體。其交換過程如下圖所示：

遺傳操作——變異操作變異操作的簡單方式是改變數(shù)碼串的某個位置上的數(shù)碼。我們先以最簡單的二進(jìn)制編碼表示方式來說明，二進(jìn)制編碼表示的每一個位置的數(shù)碼只有0與1這兩個可能，比如有如下二進(jìn)制編碼表示：

遺傳操作——變異操作其碼長為8，隨機(jī)產(chǎn)生一個1至8之間的數(shù)k，假如現(xiàn)在k=5，對從右往左的第5位進(jìn)行變異操作，將原來的0變?yōu)?，得到如下數(shù)碼串：

二進(jìn)制編碼表示時的簡單變異操作是將0與1互換：0變異為1，1變異為0。

TSP的變異操作隨機(jī)產(chǎn)生一個1至n之間的數(shù)k，決定對回路中的第k個城市的代碼wk作變異操作，又產(chǎn)生一個1至n之間的數(shù)w，替代wk，并將wk加到尾部，得到：w1w2……wk-1wwk+1……wnwk這個串有n+1個數(shù)碼，注意數(shù)w其實在此串中出現(xiàn)重復(fù)了，必須刪除與數(shù)w相重復(fù)的，得到合法的染色體。

4.控制參數(shù)（1）交叉操作和變異操作的概率

交叉概率取0.6至0.95之間的值；變異概率取0.001至0.01之間的值（2）種群規(guī)模

通常種群規(guī)模為30至100

（3）個體的長度

有定長和變長兩種。它對算法的性能也有影響。

二、遺傳算法的結(jié)構(gòu)遺傳算法類似于自然進(jìn)化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會。二、遺傳算法的結(jié)構(gòu)在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群。對這個新種群進(jìn)行下一輪進(jìn)化。這就是遺傳算法的基本原理。

簡單遺傳算法框圖簡單遺傳算法框圖程序的停止條件有二種完成了預(yù)先給定的進(jìn)化代數(shù)則停止；種群中的最優(yōu)個體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時停止。

三、遺傳算法的收斂性一般的遺傳算法不一定收斂，只有每代保存了最優(yōu)個體時才收斂。在實際應(yīng)用中，使用了上述結(jié)論來保證收斂性。采用優(yōu)秀個體保護(hù)法就是將每代中的最優(yōu)個體，直接進(jìn)入子代，相應(yīng)淘汰其子代中適應(yīng)度最差的個體，使種群規(guī)模不變。當(dāng)遺傳算法收斂時，求到的解通常只是所要解決問題的最優(yōu)解的一個近似解，或者叫滿意解。

四、遺傳算法的性能（1）種群規(guī)模（2）適應(yīng)度函數(shù)的構(gòu)造（3）交叉和變異操作（影響最大）（4）交叉和變異概率（5）停止條件（與解的質(zhì)量有關(guān)）交叉和變異概率變異概率大會擴(kuò)大搜索范圍，使搜索過程不陷入局部極小，但也可能使正朝著最優(yōu)解緩慢前進(jìn)的個體改變方向，破壞好個體；變異概率大則對染色體的破壞大，因此常設(shè)定一大一小兩個變異概率，當(dāng)整個種群平均適應(yīng)度增長較快時，使用小變異概率；反之使用較大變異概率。對整個種群使用相同的變異概率，并不利于優(yōu)良個體的成長和劣個體的改良。

交叉或變異產(chǎn)生的新個體能否與父個體進(jìn)行競爭？按簡單遺傳算法，交叉或變異產(chǎn)生的新個體不論優(yōu)劣都取代父個體，并不科學(xué)。對新個體要有與父個體進(jìn)行競爭的機(jī)會，當(dāng)父個體比新個體優(yōu)時，按一定的概率保留父個體而舍去新個體。

停止條件按預(yù)設(shè)的進(jìn)化代數(shù)作停止條件，由于不同的問題的復(fù)雜度不同，而且對同一問題構(gòu)造的遺傳操作不同其算法性能不同，因此很難合理地預(yù)設(shè)。另一個常用的停止條件是種群中的最優(yōu)個體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時，這是一個比較合理的方式。但可能由于構(gòu)造的算法