新人工智能課件

一個智能系統(tǒng)搜索策略的優(yōu)劣直接影響到系統(tǒng)的性能語推理效率。

本章主要內(nèi)容：搜索的基本概念；狀態(tài)空間的盲目搜索；狀態(tài)空間的啟發(fā)式搜索；與或樹的盲目搜索；與或樹的啟發(fā)式搜索；博奕樹的啟發(fā)式搜索；第5章搜索測略1一個智能系統(tǒng)搜索策略的優(yōu)劣直接影響到系5.1搜索策略的基本概念

5.1.1搜索的含義1.搜索定義:根據(jù)問題的實(shí)際情況，不斷尋找可利用的知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的過程稱為搜索。2.組合爆炸問題：結(jié)構(gòu)良好，理論上有算法可依的問題，如果問題或算法的復(fù)雜性較高（按指數(shù)形式增長），由于受計(jì)算機(jī)在時間和空間上的限制，無法付諸實(shí)用。25.1搜索策略的基本概念5.1.1搜索的含義25.1搜索策略的基本概念3.搜索類型：(1)根據(jù)是否使用啟發(fā)信息分類：盲目搜索：按預(yù)定的控制策略進(jìn)行，在搜索過程中獲得的中間信息不改變控制策略。啟發(fā)式搜索：在搜索過程中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。35.1搜索策略的基本概念3.搜索類型：35.1搜索策略的基本概念(2)根據(jù)問題的表示方式分類：狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進(jìn)行的搜索。與/或樹搜索：用問題歸約法來求解問題時所進(jìn)行的搜索。45.1搜索策略的基本概念(2)根據(jù)問題的表示方式分類：45.1搜索策略的基本概念5.1.2狀態(tài)空間法1.狀態(tài)空間表示法（1）狀態(tài)(state):表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，形式的表示為：

Sk={Sk0,Sk1,…)當(dāng)對每一個分量都予以確定的值時，就得到了一個具體的狀態(tài)。55.1搜索策略的基本概念5.1.2狀態(tài)空間法55.1搜索策略的基本概念（2）操作（operator)（算符）把問題從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的手段?？梢允且粋€機(jī)械步驟、一個運(yùn)算、一條規(guī)則或一個過程?？衫斫鉃闋顟B(tài)集合上的一個函數(shù)，描述了狀態(tài)之間的關(guān)系。65.1搜索策略的基本概念（2）操作（operator)（算符5.1搜索策略的基本概念（3）狀態(tài)空間（statespace）描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用三元組表示:(S,F,G)S:為問題所有初始狀態(tài)的集合。

F:為操作的集合。

G:為目標(biāo)狀態(tài)的集合。75.1搜索策略的基本概念（3）狀態(tài)空間（statespac5.1搜索策略的基本概念狀態(tài)空間圖：賦值的有向圖。節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作.2.狀態(tài)空間問題求解任何以狀態(tài)和操作為基礎(chǔ)的問題求解方法都稱為狀態(tài)空間問題求解。簡稱為狀態(tài)空間法。狀態(tài)空間法的基本過程為：（1）為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法。85.1搜索策略的基本概念狀態(tài)空間圖：賦值的有向圖。節(jié)點(diǎn)表示5.1搜索策略的基本概念（2）從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止。（3）從初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是問題的一個解。95.1搜索策略的基本概念（2）從某個初始狀態(tài)出發(fā)，每次使用一5.1搜索策略的基本概念3.狀態(tài)空間的例子例5.1:二階梵塔問題：設(shè)有三根鋼針，它們的編號分別是1，2，3。在初始情況下，1號鋼針上穿有A、B兩個金片，A比B小，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。105.1搜索策略的基本概念3.狀態(tài)空間的例子105.1搜索策略的基本概念解：設(shè)用Sk={Sk0,Sk1}表示問題的狀態(tài)，其中，Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。全部可能的問題狀態(tài)共有以下9種：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0為初始狀態(tài)，S4和S8為目標(biāo)狀態(tài)。115.1搜索策略的基本概念解：設(shè)用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以狀態(tài)和操作為基礎(chǔ)的問題求解方法都稱為狀態(tài)空間問題求解。簡稱為狀態(tài)空間法。狀態(tài)空間法的基本過程為：（1）為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法。（2）從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止。（3）從初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是問題的一個解。125.1搜索策略的基本概念任何以狀態(tài)和操5.1搜索策略的基本概念例5.2修道士和野人問題.首先選取描述問題狀態(tài)的方法。用一個三元組表示狀態(tài)：S=(m,c,b)其中：m表示左岸的修道士數(shù)；c表示左岸的野人數(shù)；b表示左岸的船數(shù)；135.1搜索策略的基本概念例5.2修道士和野人問題.135.1搜索策略的基本概念右岸的狀態(tài)由下式確定：右岸的修道士數(shù)m’=3-m；右岸的野人數(shù)c’=3-c；

右岸的船數(shù)b’=1-b；

m和c的取值分別為0，1，2，3之一；b的取值分別為0，1;

共有4x4x2=32種狀態(tài)。145.1搜索策略的基本概念右岸的狀態(tài)由下式確定：145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二階樊塔狀態(tài)空間圖155.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的狀態(tài)和修道士被野人吃掉的狀態(tài)，余下的狀態(tài)由16種：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),165.1搜索策略的基本概念除去不合法的狀態(tài)和修道士被野人吃掉的5.1搜索策略的基本概念需要考慮的操作有：（1）船至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；（2）每次操作船上的人數(shù)不得超過2個；（3）操作應(yīng)保證不產(chǎn)生非法狀態(tài)。操作由兩部分組成：條件部分和動作部分。175.1搜索策略的基本概念需要考慮的操作有：175.1搜索策略的基本概念用Qij表示從右岸到左岸的運(yùn)人操作，可供選擇的操作由10種，操作集為：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01為例說明操作的條件和動作：操作符號條件動作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+1185.1搜索策略的基本概念用Qij表示從5.1搜索策略的基本概念例5.3猴子摘香蕉問題.

首先選取描述問題狀態(tài)的方法。用一個四元組表示狀態(tài)：S=(w,x,y,z)

其中：w表示猴子的水平位置；x表示箱子的水平位置；

y表示猴子是否在箱子上，當(dāng)猴子在箱子上時y=1否則y=0；

z表示猴子是否拿到香蕉，當(dāng)拿到香蕉時z=1否則z=0；195.1搜索策略的基本概念例5.3猴子摘香蕉問題.195.1搜索策略的基本概念所有可能的狀態(tài)有：S0=(a,b,0,0),初始狀態(tài)S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目標(biāo)狀態(tài)205.1搜索策略的基本概念所有可能的狀態(tài)有：205.1搜索策略的基本概念允許的操作為：Goto(u):猴子走到位置u，即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v，即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉，即:(c,c,1,0)→(c,c,1,1)215.1搜索策略的基本概念允許的操作為：215.1搜索策略的基本概念問題的狀態(tài)空間圖見書P172,圖5-3.由初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)的操作序列為：{Goto(b),Pushbox?,Climbbox,Grasp}225.1搜索策略的基本概念問題的狀態(tài)空間圖見書P172,圖5-5.1搜索策略的基本概念5.1.3問題歸約

問題是不同于狀態(tài)空間方法的另外一種形式化方法，基本思想是對問題進(jìn)行分解或變換。當(dāng)一個問題比較復(fù)雜時，直接求解比較困難，可以通過分解或變換，將其轉(zhuǎn)化為一系列較簡單的問題，然后通過對較簡單的球接來實(shí)現(xiàn)對原問題的求解。1.問題的分解與等價變換

當(dāng)把一個問題歸約為子問題時，可采用對原問題的分解或變換方法。235.1搜索策略的基本概念5.1.3問題歸約235.1搜索策略的基本概念（1）分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當(dāng)所有子問題Pi(I=1,2,…,n)都有解時，原問題P才有解，任何一個子問題Pi(I=1,2,…,n)無解都會導(dǎo)致原問題P無解。稱這種歸約為問題的分解。分解所得到的子問題的“與”與原問題P等價。245.1搜索策略的基本概念（1）分解245.1搜索策略的基本概念（2）等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且這些子問題Pi(I=1,2,…,n)中只要有一個有解則原問題P就有解，只有當(dāng)所有的子問題都無解時，原問題P才無解，稱這種歸約為問題的等價變換。簡稱變換。即變換所得的子問題的“或”與原問題P等價。255.1搜索策略的基本概念（2）等價變換255.1搜索策略的基本概念在實(shí)際問題的歸約過程中，有可能需要同時采用變換和分解的方法。無論是分解還是變換，都是要將原問題歸約為一系列本原問題。所謂本原問題是指那種不能分解（或不需要分解）或變換，且可以直接解答的子問題。本原問題可以作為終止歸約的限制條件。265.1搜索策略的基本概念在實(shí)際問題的歸5.1搜索策略的基本概念2.問題歸約的“與或樹”表示

當(dāng)把一個原問題歸約為一系列本原問題的過程可以很方便的用一個“與或樹”來表示。（1）與樹（2）或樹275.1搜索策略的基本概念2.問題歸約的“與或樹”表示275.1搜索策略的基本概念（3）與/或樹285.1搜索策略的基本概念（3）與/或樹285.1搜索策略的基本概念（4）端節(jié)點(diǎn)與終止節(jié)點(diǎn)端節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。終止節(jié)點(diǎn)：本原問題所對應(yīng)的節(jié)點(diǎn)。（5）可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)滿足以下三個條件的為可解節(jié)點(diǎn):任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)；對“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個可解節(jié)點(diǎn)時，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)；對“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時，則該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。295.1搜索策略的基本概念（4）端節(jié)點(diǎn)與終止節(jié)點(diǎn)295.1搜索策略的基本概念滿足以下三個條件的為不可解節(jié)點(diǎn):不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)；對“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)中為不可解節(jié)點(diǎn)時，則該或節(jié)點(diǎn)就是不可解節(jié)點(diǎn)；對“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個為不可解節(jié)點(diǎn)時，則該與節(jié)點(diǎn)才是不可解節(jié)點(diǎn)。305.1搜索策略的基本概念滿足以下三個條件的為不可解節(jié)點(diǎn):305.1搜索策略的基本概念（6）解樹由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（對應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為解樹。在解樹中一定包含初始節(jié)點(diǎn)。315.1搜索策略的基本概念（6）解樹315.1搜索策略的基本概念325.1搜索策略的基本概念325.1搜索策略的基本概念3.問題歸約的例子例5.4:三階梵塔問題：設(shè)有三根鋼針，它們的編號分別是1，2，3。在初始情況下，1號鋼針上穿有A、B、C三個金片，自上而下，有小到大，。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。用歸約法求解。335.1搜索策略的基本概念3.問題歸約的例子335.1搜索策略的基本概念解：為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。用三元組（i,j,k)表示問題任何時刻的狀態(tài)；用“→”表示狀態(tài)的轉(zhuǎn)換；i表示金片C的針號;j表示金片B的針號;k表示金片A的針號;345.1搜索策略的基本概念解：為了能夠解決這一問題，首先需要定5.1搜索策略的基本概念利用問題歸約方法，原問題可分解為以下三個子問題:(1)把金片A及B移到2號鋼針上的雙金片移動問題：(1,1,1)→(1,2,2)(2)把金片C移到3號鋼針上的單金片移動問題：(1,2,2)→(3,2,2)(1)把金片A及B移到3號鋼針上的雙金片移動問題：(3,2,2)→(3,3,3)355.1搜索策略的基本概念利用問題歸約方法，原問題可分解為以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)365.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始問題的解：(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)

(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)375.1搜索策略的基本概念原始問題的解：375.2狀態(tài)空間的盲目搜索狀態(tài)空間的搜索策略可分為盲目搜索和啟發(fā)式搜索。啟發(fā)式搜索需要抽取與問題本身有關(guān)的特征信息，而信息抽取比較困難，所以盲目搜索仍不失為一種有效的搜索策略。385.2狀態(tài)空間的盲目搜索狀態(tài)空間的搜索策略可分為盲目搜5.2狀態(tài)空間的盲目搜索5.2.1一般圖搜索過程當(dāng)用狀態(tài)空間法解決問題時，需要考慮：（1）對于很大問題，計(jì)算機(jī)無法保存其全部狀態(tài)空間；（2）對于具體問題，與解有關(guān)的狀態(tài)空間一般僅是全部狀態(tài)空間的一部分。因此在問題求解過程中，沒有必要生成和保存該問題的全部狀態(tài)空間，只要能夠生成和保存與解有關(guān)的那部分狀態(tài)空間即可。解決問題的方法是采用狀態(tài)空間搜索技術(shù)。395.2狀態(tài)空間的盲目搜索5.2.1一般圖搜索過程395.2狀態(tài)空間的盲目搜索對狀態(tài)空間的搜索，由于問題的狀態(tài)空間可用一個有向圖來表示，因此狀態(tài)空間搜索實(shí)際上就是對有向圖的搜索。405.2狀態(tài)空間的盲目搜索對狀態(tài)空間的搜5.2狀態(tài)空間的盲目搜索狀態(tài)空間搜索的基本思想是：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒有出現(xiàn)，則按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，重復(fù)上述過程，指導(dǎo)目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供擴(kuò)展的節(jié)點(diǎn)為止。415.2狀態(tài)空間的盲目搜索狀態(tài)空間搜索的基本思想是：415.2狀態(tài)空間的盲目搜索狀態(tài)空間算法：需要設(shè)立數(shù)據(jù)結(jié)構(gòu)Open和Closed表。Open表（未擴(kuò)展節(jié)點(diǎn)表）：用于存放剛生成沒有擴(kuò)展的節(jié)點(diǎn)；Closed表（已擴(kuò)展節(jié)點(diǎn)表）：用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn)。425.2狀態(tài)空間的盲目搜索狀態(tài)空間算法：425.2狀態(tài)空間的盲目搜索狀態(tài)空間的一般圖搜索過程為：（1）把初始節(jié)點(diǎn)S0放入Open表并建立目前僅包含S0的圖G;（2）檢查Open表是否為空，若為空，則問題無解，失敗退出；（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；435.2狀態(tài)空間的盲目搜索狀態(tài)空間的一般圖搜索過程為：435.2狀態(tài)空間的盲目搜索（5）擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)n先輩的那部分子節(jié)點(diǎn)記入集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中。（6）針對M中子節(jié)點(diǎn)的不同情況，分別作如下處理：對那些沒有在G中出現(xiàn)過的M成員設(shè)置一個指向其父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它放入Open表；對那些原來已在G中出現(xiàn)過，但還沒有被擴(kuò)展的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；445.2狀態(tài)空間的盲目搜索（5）擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把5.2狀態(tài)空間的盲目搜索對于先前已在G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（7）按某種策略對Open表中的節(jié)點(diǎn)進(jìn)行排序；（8）轉(zhuǎn)(2)步。455.2狀態(tài)空間的盲目搜索對于先前已在G中出現(xiàn)過，并已經(jīng)擴(kuò)展了5.2狀態(tài)空間的盲目搜索搜索過程說明：（1）狀態(tài)空間圖搜索算法具有通用性，其它的各種狀態(tài)空間搜索策略都是上述的一個特例。各種搜索策略的主要區(qū)別在于對Open表中節(jié)點(diǎn)的排列順序不同。如廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面；深度優(yōu)先搜索把后生成的子節(jié)點(diǎn)排在前面。465.2狀態(tài)空間的盲目搜索搜索過程說明：465.2狀態(tài)空間的盲目搜索（2）在第(5)步對節(jié)點(diǎn)n擴(kuò)展后，生成并記入M的子節(jié)點(diǎn)有以下三種情況：該子節(jié)點(diǎn)從未被任何節(jié)點(diǎn)生成過，由n第一次生成；該子節(jié)點(diǎn)原來被其它節(jié)點(diǎn)生成過，但還沒有被擴(kuò)展，這一次又被n再次生成；該子節(jié)點(diǎn)原來被其它節(jié)點(diǎn)生成過，并且已經(jīng)被擴(kuò)展過，這一次又被n再次生成。475.2狀態(tài)空間的盲目搜索（2）在第(5)步對節(jié)點(diǎn)n擴(kuò)展后，生5.2狀態(tài)空間的盲目搜索對于一般圖搜索算法，具有以上三種情況；對于盲目搜索，由于其狀態(tài)空間是樹狀結(jié)構(gòu)，因此不會出現(xiàn)后兩種情況，每個節(jié)點(diǎn)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。（3）在第（6）步針對M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時，如果發(fā)生上面第2種情況，一般是由原時節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價來決定。485.2狀態(tài)空間的盲目搜索對于一般圖搜索5.2狀態(tài)空間的盲目搜索例題見書P1775.2.2廣度優(yōu)先搜索廣度優(yōu)先搜索也成為寬度優(yōu)先搜索，是一種先生成的節(jié)點(diǎn)限擴(kuò)展的策略。

495.2狀態(tài)空間的盲目搜索例題見書P177495.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索策略搜索過程為：從初始節(jié)點(diǎn)S0開始逐層向下擴(kuò)展，在第n曾節(jié)點(diǎn)還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入Open表的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。505.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索策略搜索過程為：5.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；（5）若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。515.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索算法如下：515.2狀態(tài)空間的盲目搜索（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.5八數(shù)碼難題。見書P178525.2狀態(tài)空間的盲目搜索（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Op5.2狀態(tài)空間的盲目搜索5.2.3深度優(yōu)先搜索深度優(yōu)先搜索是一種后生成的節(jié)點(diǎn)先擴(kuò)展的策略。深度優(yōu)先搜索策略搜索過程為：從初始節(jié)點(diǎn)S0開始，在其子節(jié)點(diǎn)中選擇一個最新生成的節(jié)點(diǎn)進(jìn)行考察，如果該子解不是目標(biāo)節(jié)點(diǎn)而且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個最新生成的節(jié)點(diǎn)進(jìn)行考察，依次向下搜索，直到某個子節(jié)點(diǎn)即不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。535.2狀態(tài)空間的盲目搜索5.2.3深度優(yōu)先搜索535.2狀態(tài)空間的盲目搜索Open表示一種棧結(jié)構(gòu)，最先進(jìn)入的節(jié)點(diǎn)排在最后面，最后進(jìn)入的節(jié)點(diǎn)排在最前面。

深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;545.2狀態(tài)空間的盲目搜索Open表示一5.2狀態(tài)空間的盲目搜索（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；（5）若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.6八數(shù)碼難題。見書P179555.2狀態(tài)空間的盲目搜索（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是5.2狀態(tài)空間的盲目搜索5.2.4有界深度優(yōu)先搜索深度優(yōu)先搜索如果目標(biāo)不在搜索的分支上，且該分支又是一個無限分支，則搜索過程就不可能找到解。即使能夠找到節(jié)，按深度優(yōu)先找到的解也不一定是最優(yōu)解。有界深度優(yōu)先搜索過程總體上按深度優(yōu)先策略進(jìn)行，但對搜索深度需要給出一個深度限制dm，當(dāng)搜索深度達(dá)到了dm，但還沒有找到目標(biāo)時，就停止該分支的搜索，換到另外一個分支進(jìn)行搜索。565.2狀態(tài)空間的盲目搜索5.2.4有界深度優(yōu)先搜索565.2狀態(tài)空間的盲目搜索有界深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；575.2狀態(tài)空間的盲目搜索有界深度優(yōu)先搜索算法如下：575.2狀態(tài)空間的盲目搜索（5）若節(jié)點(diǎn)n的深度d(n)=dm，則轉(zhuǎn)第（2）步。(6)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。（7）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.7八數(shù)碼難題。見書P180585.2狀態(tài)空間的盲目搜索（5）若節(jié)點(diǎn)n的深度d(n)=dm，5.2狀態(tài)空間的盲目搜索5.2.5代價樹搜索需要在搜索樹的每條邊標(biāo)上其代價。這種有代價的樹稱為代價樹。在代價樹中，用g(n)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的代價，用c(n1,n2)表從父節(jié)點(diǎn)n1到其子節(jié)點(diǎn)n2的代價，對節(jié)點(diǎn)n2的代價有：

g(n2)=g(n1)+c(n1,n2)595.2狀態(tài)空間的盲目搜索5.2.5代價樹搜索595.2狀態(tài)空間的盲目搜索在代價樹中，最小代價的路徑和最短路徑（即路徑長度最短）是有可能的。最短路徑不一定是代價最小的路徑；代價最小的路徑不一定是最短路徑。1.代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索也稱為分枝界限法。每次從Open表中選擇節(jié)點(diǎn)或往closed表中存放節(jié)點(diǎn)時，總是選擇代價小的節(jié)點(diǎn)排在前面，代價大的排在后面，與節(jié)點(diǎn)在樹中的位置無關(guān)。605.2狀態(tài)空間的盲目搜索在代價樹中，最5.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價g(s0)=0；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；615.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索算法如下：615.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點(diǎn)n，生成子節(jié)點(diǎn)ni(I=1,2,…),將這些子節(jié)點(diǎn)放入Open表中，并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針；按如下公式：

g(ni)=g(n)+c(n,ni)(i=1,2,…)計(jì)算各自節(jié)點(diǎn)的代價，并根據(jù)各節(jié)點(diǎn)的代價對Open表中的全部按照從小到大順序重新進(jìn)行排序，然后轉(zhuǎn)第（2）步。625.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（5.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索是完備的，如果問題有解，上述算法一定能夠找到，并且找到的是最優(yōu)解。例5.8城市交通問題。P181635.2狀態(tài)空間的盲目搜索代價樹的廣度5.2狀態(tài)空間的盲目搜索2.代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索每次從Open表中選擇節(jié)點(diǎn)或往closed表中存放節(jié)點(diǎn)時，總是從剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個代價最小的節(jié)點(diǎn)。645.2狀態(tài)空間的盲目搜索2.代價樹的深度優(yōu)先搜索645.2狀態(tài)空間的盲目搜索代價樹的深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價g(s0)=0；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；655.2狀態(tài)空間的盲目搜索代價樹的深度優(yōu)先搜索算法如下：655.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點(diǎn)n，生成子節(jié)點(diǎn)ni(I=1,2,…),將這些子節(jié)點(diǎn)按邊代價由小到大放入Open表的首部，并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針。然后轉(zhuǎn)第（2）步。例5.8城市交通問題。665.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（5.3狀態(tài)空間的啟發(fā)式搜索5.3.1啟發(fā)性信息和估價函數(shù)啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息，啟發(fā)性信息又是通過估價函數(shù)作用到搜索過程中。1.啟發(fā)性信息啟發(fā)性信息是至于具體問題求解過程無關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息。675.3狀態(tài)空間的啟發(fā)式搜索5.3.1啟發(fā)性信息和估價函數(shù)5.3狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息一般有三種:(1)有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息。(2)有效地幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息。(3)能決定在擴(kuò)展一個節(jié)點(diǎn)時哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除的信息。搜索過程的啟發(fā)性信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無用節(jié)點(diǎn)就越少。685.3狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息一般有三種:685.3狀態(tài)空間的啟發(fā)式搜索2.估價函數(shù)用來估計(jì)節(jié)點(diǎn)重要性的函數(shù)稱為估價函數(shù)。估價函數(shù)f(n)被定義為從初始節(jié)點(diǎn)S0出發(fā)到，約束經(jīng)過節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最小路徑代價的估計(jì)值。其一般形式為：

F(n)=g(n)+h(n)其中：g(n)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的實(shí)際代價；h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價。695.3狀態(tài)空間的啟發(fā)式搜索2.估價函數(shù)695.3狀態(tài)空間的啟發(fā)式搜索例5.9八數(shù)碼難題P1835.3.2A算法在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)F(n)=g(n)+h(n)對Open表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為A算法，由于估價函數(shù)中帶有自身的啟發(fā)性信息，A算法又稱為啟發(fā)式搜索算法。705.3狀態(tài)空間的啟發(fā)式搜索例5.9八數(shù)碼難題P183705.3狀態(tài)空間的啟發(fā)式搜索1.全局擇優(yōu)搜索在全局擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時總是從Open表的所有節(jié)點(diǎn)中選擇一個估計(jì)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，其搜索過程可描述如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表為空，則問題無解，失敗退出。715.3狀態(tài)空間的啟發(fā)式搜索1.全局擇優(yōu)搜索715.3狀態(tài)空間的啟發(fā)式搜索（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點(diǎn)n，生成子節(jié)點(diǎn)ni(i=1,2,…),計(jì)算每一個子節(jié)點(diǎn)的估價值f(ni)(I=1,2,…),并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針。然后將這些子節(jié)點(diǎn)放入Open表中。

725.3狀態(tài)空間的啟發(fā)式搜索（3）把Open表的第一個節(jié)點(diǎn)取5.3狀態(tài)空間的啟發(fā)式搜索（7）根據(jù)各節(jié)點(diǎn)的估價函數(shù)值，對Open表中的全部節(jié)點(diǎn)按從小到大的順序重新進(jìn)行排序。（8）轉(zhuǎn)第（2）步。如果估價函數(shù)F(n)=g(n),則退化為代價樹的廣度優(yōu)先搜索；如果估價函數(shù)F(n)=d(n),則退化為廣度優(yōu)先搜索；可見，廣度優(yōu)先搜索和代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。例5.10八數(shù)碼難題P184735.3狀態(tài)空間的啟發(fā)式搜索（7）根據(jù)各節(jié)點(diǎn)的估價函數(shù)值，對5.3狀態(tài)空間的啟發(fā)式搜索2.局部擇優(yōu)搜索在局部擇優(yōu)搜索中，每當(dāng)需要擴(kuò)展節(jié)點(diǎn)時總是從剛生成的子節(jié)點(diǎn)中選擇一個估價函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。其搜索過程可描述如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，f(S0)=g(S0)+h(S0);（2）如果Open表為空，則問題無解，失敗退出。745.3狀態(tài)空間的啟發(fā)式搜索2.局部擇優(yōu)搜索745.3狀態(tài)空間的啟發(fā)式搜索（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點(diǎn)n，生成子節(jié)點(diǎn)ni(i=1,2,…),計(jì)算每一個子節(jié)點(diǎn)的估價值f(ni)(i=1,2,…),并按股價值從小到大的順序依次放入Open表的首部，并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針。然后轉(zhuǎn)(2)步。755.3狀態(tài)空間的啟發(fā)式搜索（3）把Open表的第一個節(jié)點(diǎn)取5.3狀態(tài)空間的啟發(fā)式搜索可見，深度優(yōu)先搜索和代價樹的深度優(yōu)先搜索是局部擇優(yōu)搜索的兩個特例。5.3.3A*算法在啟發(fā)式搜索中沒有對估價函數(shù)f(n)做任何限制。實(shí)際上，估價函數(shù)對搜索過程是十分重要的，如果選擇不當(dāng)，則有可能找不到問題的界，為此，需要對估價函數(shù)進(jìn)行適當(dāng)?shù)南拗啤*算嘎就是對估價寒暑加上一些先之后的到的一種啟發(fā)式搜索算法。765.3狀態(tài)空間的啟發(fā)式搜索可見，深度5.3狀態(tài)空間的啟發(fā)式搜索1.A*算法的可納性2.A*算法的最優(yōu)性3.h(n)的單調(diào)限制5.3.4A*算法應(yīng)用舉例例5.11八樹碼難題P190例5.12修道士和野人問題P190775.3狀態(tài)空間的啟發(fā)式搜索1.A*算法的可納性775.4與/或樹的盲目搜索5.4.1與/或樹的一般搜索

與/或樹的搜索過程實(shí)際上是一個不斷搜索尋找解樹的過程，其一般搜索過程為：（1）（2）（3)（4）見書P191785.4與/或樹的盲目搜索5.4.1與/或樹的一般搜索785.4與/或樹的盲目搜索5.4.2與/或樹的廣度優(yōu)先搜索P1925.4.3與/或樹的深度優(yōu)先搜索P193795.4與/或樹的盲目搜索5.4.2與/或樹的廣度優(yōu)先搜索5.5與/或樹的啟發(fā)式搜索5.5.1解樹的代價與希望樹5.5.2與或樹的啟發(fā)式搜索過程805.5與/或樹的啟發(fā)式搜索5.5.1解樹的代價與希望樹85.6博奕樹的啟發(fā)式搜索5.6.1概述5.5.2極大極小過程815.6博奕樹的啟發(fā)式搜索5.6.1概述81本章小結(jié)：82本章小結(jié)：82謝謝！83謝謝！83一個智能系統(tǒng)搜索策略的優(yōu)劣直接影響到系統(tǒng)的性能語推理效率。

本章主要內(nèi)容：搜索的基本概念；狀態(tài)空間的盲目搜索；狀態(tài)空間的啟發(fā)式搜索；與或樹的盲目搜索；與或樹的啟發(fā)式搜索；博奕樹的啟發(fā)式搜索；第5章搜索測略84一個智能系統(tǒng)搜索策略的優(yōu)劣直接影響到系5.1搜索策略的基本概念

5.1.1搜索的含義1.搜索定義:根據(jù)問題的實(shí)際情況，不斷尋找可利用的知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的過程稱為搜索。2.組合爆炸問題：結(jié)構(gòu)良好，理論上有算法可依的問題，如果問題或算法的復(fù)雜性較高（按指數(shù)形式增長），由于受計(jì)算機(jī)在時間和空間上的限制，無法付諸實(shí)用。855.1搜索策略的基本概念5.1.1搜索的含義25.1搜索策略的基本概念3.搜索類型：(1)根據(jù)是否使用啟發(fā)信息分類：盲目搜索：按預(yù)定的控制策略進(jìn)行，在搜索過程中獲得的中間信息不改變控制策略。啟發(fā)式搜索：在搜索過程中加入了與問題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。865.1搜索策略的基本概念3.搜索類型：35.1搜索策略的基本概念(2)根據(jù)問題的表示方式分類：狀態(tài)空間搜索：用狀態(tài)空間法來求解問題所進(jìn)行的搜索。與/或樹搜索：用問題歸約法來求解問題時所進(jìn)行的搜索。875.1搜索策略的基本概念(2)根據(jù)問題的表示方式分類：45.1搜索策略的基本概念5.1.2狀態(tài)空間法1.狀態(tài)空間表示法（1）狀態(tài)(state):表示問題求解過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)，形式的表示為：

Sk={Sk0,Sk1,…)當(dāng)對每一個分量都予以確定的值時，就得到了一個具體的狀態(tài)。885.1搜索策略的基本概念5.1.2狀態(tài)空間法55.1搜索策略的基本概念（2）操作（operator)（算符）把問題從一種狀態(tài)轉(zhuǎn)換為另一種狀態(tài)的手段?？梢允且粋€機(jī)械步驟、一個運(yùn)算、一條規(guī)則或一個過程?？衫斫鉃闋顟B(tài)集合上的一個函數(shù)，描述了狀態(tài)之間的關(guān)系。895.1搜索策略的基本概念（2）操作（operator)（算符5.1搜索策略的基本概念（3）狀態(tài)空間（statespace）描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關(guān)系。常用三元組表示:(S,F,G)S:為問題所有初始狀態(tài)的集合。

F:為操作的集合。

G:為目標(biāo)狀態(tài)的集合。905.1搜索策略的基本概念（3）狀態(tài)空間（statespac5.1搜索策略的基本概念狀態(tài)空間圖：賦值的有向圖。節(jié)點(diǎn)表示問題的狀態(tài)，有向邊表示操作.2.狀態(tài)空間問題求解任何以狀態(tài)和操作為基礎(chǔ)的問題求解方法都稱為狀態(tài)空間問題求解。簡稱為狀態(tài)空間法。狀態(tài)空間法的基本過程為：（1）為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法。915.1搜索策略的基本概念狀態(tài)空間圖：賦值的有向圖。節(jié)點(diǎn)表示5.1搜索策略的基本概念（2）從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止。（3）從初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是問題的一個解。925.1搜索策略的基本概念（2）從某個初始狀態(tài)出發(fā)，每次使用一5.1搜索策略的基本概念3.狀態(tài)空間的例子例5.1:二階梵塔問題：設(shè)有三根鋼針，它們的編號分別是1，2，3。在初始情況下，1號鋼針上穿有A、B兩個金片，A比B小，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。935.1搜索策略的基本概念3.狀態(tài)空間的例子105.1搜索策略的基本概念解：設(shè)用Sk={Sk0,Sk1}表示問題的狀態(tài)，其中，Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。全部可能的問題狀態(tài)共有以下9種：S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)其中S0為初始狀態(tài)，S4和S8為目標(biāo)狀態(tài)。945.1搜索策略的基本概念解：設(shè)用Sk={Sk0,Sk1}表5.1搜索策略的基本概念任何以狀態(tài)和操作為基礎(chǔ)的問題求解方法都稱為狀態(tài)空間問題求解。簡稱為狀態(tài)空間法。狀態(tài)空間法的基本過程為：（1）為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法。（2）從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止。（3）從初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是問題的一個解。955.1搜索策略的基本概念任何以狀態(tài)和操5.1搜索策略的基本概念例5.2修道士和野人問題.首先選取描述問題狀態(tài)的方法。用一個三元組表示狀態(tài)：S=(m,c,b)其中：m表示左岸的修道士數(shù)；c表示左岸的野人數(shù)；b表示左岸的船數(shù)；965.1搜索策略的基本概念例5.2修道士和野人問題.135.1搜索策略的基本概念右岸的狀態(tài)由下式確定：右岸的修道士數(shù)m’=3-m；右岸的野人數(shù)c’=3-c；

右岸的船數(shù)b’=1-b；

m和c的取值分別為0，1，2，3之一；b的取值分別為0，1;

共有4x4x2=32種狀態(tài)。975.1搜索策略的基本概念右岸的狀態(tài)由下式確定：145.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二階樊塔狀態(tài)空間圖985.1搜索策略的基本概念3,32,12,31,21,3A(35.1搜索策略的基本概念除去不合法的狀態(tài)和修道士被野人吃掉的狀態(tài)，余下的狀態(tài)由16種：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),995.1搜索策略的基本概念除去不合法的狀態(tài)和修道士被野人吃掉的5.1搜索策略的基本概念需要考慮的操作有：（1）船至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應(yīng)該等于到達(dá)岸邊的m和c的增加數(shù)目；（2）每次操作船上的人數(shù)不得超過2個；（3）操作應(yīng)保證不產(chǎn)生非法狀態(tài)。操作由兩部分組成：條件部分和動作部分。1005.1搜索策略的基本概念需要考慮的操作有：175.1搜索策略的基本概念用Qij表示從右岸到左岸的運(yùn)人操作，可供選擇的操作由10種，操作集為：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01為例說明操作的條件和動作：操作符號條件動作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+11015.1搜索策略的基本概念用Qij表示從5.1搜索策略的基本概念例5.3猴子摘香蕉問題.

首先選取描述問題狀態(tài)的方法。用一個四元組表示狀態(tài)：S=(w,x,y,z)

其中：w表示猴子的水平位置；x表示箱子的水平位置；

y表示猴子是否在箱子上，當(dāng)猴子在箱子上時y=1否則y=0；

z表示猴子是否拿到香蕉，當(dāng)拿到香蕉時z=1否則z=0；1025.1搜索策略的基本概念例5.3猴子摘香蕉問題.195.1搜索策略的基本概念所有可能的狀態(tài)有：S0=(a,b,0,0),初始狀態(tài)S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目標(biāo)狀態(tài)1035.1搜索策略的基本概念所有可能的狀態(tài)有：205.1搜索策略的基本概念允許的操作為：Goto(u):猴子走到位置u，即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v，即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉，即:(c,c,1,0)→(c,c,1,1)1045.1搜索策略的基本概念允許的操作為：215.1搜索策略的基本概念問題的狀態(tài)空間圖見書P172,圖5-3.由初始狀態(tài)變?yōu)槟繕?biāo)狀態(tài)的操作序列為：{Goto(b),Pushbox?,Climbbox,Grasp}1055.1搜索策略的基本概念問題的狀態(tài)空間圖見書P172,圖5-5.1搜索策略的基本概念5.1.3問題歸約

問題是不同于狀態(tài)空間方法的另外一種形式化方法，基本思想是對問題進(jìn)行分解或變換。當(dāng)一個問題比較復(fù)雜時，直接求解比較困難，可以通過分解或變換，將其轉(zhuǎn)化為一系列較簡單的問題，然后通過對較簡單的球接來實(shí)現(xiàn)對原問題的求解。1.問題的分解與等價變換

當(dāng)把一個問題歸約為子問題時，可采用對原問題的分解或變換方法。1065.1搜索策略的基本概念5.1.3問題歸約235.1搜索策略的基本概念（1）分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當(dāng)所有子問題Pi(I=1,2,…,n)都有解時，原問題P才有解，任何一個子問題Pi(I=1,2,…,n)無解都會導(dǎo)致原問題P無解。稱這種歸約為問題的分解。分解所得到的子問題的“與”與原問題P等價。1075.1搜索策略的基本概念（1）分解245.1搜索策略的基本概念（2）等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且這些子問題Pi(I=1,2,…,n)中只要有一個有解則原問題P就有解，只有當(dāng)所有的子問題都無解時，原問題P才無解，稱這種歸約為問題的等價變換。簡稱變換。即變換所得的子問題的“或”與原問題P等價。1085.1搜索策略的基本概念（2）等價變換255.1搜索策略的基本概念在實(shí)際問題的歸約過程中，有可能需要同時采用變換和分解的方法。無論是分解還是變換，都是要將原問題歸約為一系列本原問題。所謂本原問題是指那種不能分解（或不需要分解）或變換，且可以直接解答的子問題。本原問題可以作為終止歸約的限制條件。1095.1搜索策略的基本概念在實(shí)際問題的歸5.1搜索策略的基本概念2.問題歸約的“與或樹”表示

當(dāng)把一個原問題歸約為一系列本原問題的過程可以很方便的用一個“與或樹”來表示。（1）與樹（2）或樹1105.1搜索策略的基本概念2.問題歸約的“與或樹”表示275.1搜索策略的基本概念（3）與/或樹1115.1搜索策略的基本概念（3）與/或樹285.1搜索策略的基本概念（4）端節(jié)點(diǎn)與終止節(jié)點(diǎn)端節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。終止節(jié)點(diǎn)：本原問題所對應(yīng)的節(jié)點(diǎn)。（5）可解節(jié)點(diǎn)與不可解節(jié)點(diǎn)滿足以下三個條件的為可解節(jié)點(diǎn):任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)；對“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個可解節(jié)點(diǎn)時，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)；對“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時，則該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。1125.1搜索策略的基本概念（4）端節(jié)點(diǎn)與終止節(jié)點(diǎn)295.1搜索策略的基本概念滿足以下三個條件的為不可解節(jié)點(diǎn):不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)；對“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)中為不可解節(jié)點(diǎn)時，則該或節(jié)點(diǎn)就是不可解節(jié)點(diǎn)；對“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個為不可解節(jié)點(diǎn)時，則該與節(jié)點(diǎn)才是不可解節(jié)點(diǎn)。1135.1搜索策略的基本概念滿足以下三個條件的為不可解節(jié)點(diǎn):305.1搜索策略的基本概念（6）解樹由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（對應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為解樹。在解樹中一定包含初始節(jié)點(diǎn)。1145.1搜索策略的基本概念（6）解樹315.1搜索策略的基本概念1155.1搜索策略的基本概念325.1搜索策略的基本概念3.問題歸約的例子例5.4:三階梵塔問題：設(shè)有三根鋼針，它們的編號分別是1，2，3。在初始情況下，1號鋼針上穿有A、B、C三個金片，自上而下，有小到大，。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。用歸約法求解。1165.1搜索策略的基本概念3.問題歸約的例子335.1搜索策略的基本概念解：為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。用三元組（i,j,k)表示問題任何時刻的狀態(tài)；用“→”表示狀態(tài)的轉(zhuǎn)換；i表示金片C的針號;j表示金片B的針號;k表示金片A的針號;1175.1搜索策略的基本概念解：為了能夠解決這一問題，首先需要定5.1搜索策略的基本概念利用問題歸約方法，原問題可分解為以下三個子問題:(1)把金片A及B移到2號鋼針上的雙金片移動問題：(1,1,1)→(1,2,2)(2)把金片C移到3號鋼針上的單金片移動問題：(1,2,2)→(3,2,2)(1)把金片A及B移到3號鋼針上的雙金片移動問題：(3,2,2)→(3,3,3)1185.1搜索策略的基本概念利用問題歸約方法，原問題可分解為以下5.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)1195.1搜索策略的基本概念(1,1,1)→(3,3,3)(15.1搜索策略的基本概念原始問題的解：(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(1,2,2)→(3,2,2)

(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)1205.1搜索策略的基本概念原始問題的解：375.2狀態(tài)空間的盲目搜索狀態(tài)空間的搜索策略可分為盲目搜索和啟發(fā)式搜索。啟發(fā)式搜索需要抽取與問題本身有關(guān)的特征信息，而信息抽取比較困難，所以盲目搜索仍不失為一種有效的搜索策略。1215.2狀態(tài)空間的盲目搜索狀態(tài)空間的搜索策略可分為盲目搜5.2狀態(tài)空間的盲目搜索5.2.1一般圖搜索過程當(dāng)用狀態(tài)空間法解決問題時，需要考慮：（1）對于很大問題，計(jì)算機(jī)無法保存其全部狀態(tài)空間；（2）對于具體問題，與解有關(guān)的狀態(tài)空間一般僅是全部狀態(tài)空間的一部分。因此在問題求解過程中，沒有必要生成和保存該問題的全部狀態(tài)空間，只要能夠生成和保存與解有關(guān)的那部分狀態(tài)空間即可。解決問題的方法是采用狀態(tài)空間搜索技術(shù)。1225.2狀態(tài)空間的盲目搜索5.2.1一般圖搜索過程395.2狀態(tài)空間的盲目搜索對狀態(tài)空間的搜索，由于問題的狀態(tài)空間可用一個有向圖來表示，因此狀態(tài)空間搜索實(shí)際上就是對有向圖的搜索。1235.2狀態(tài)空間的盲目搜索對狀態(tài)空間的搜5.2狀態(tài)空間的盲目搜索狀態(tài)空間搜索的基本思想是：先把問題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行擴(kuò)展，生成一組子節(jié)點(diǎn)，然后檢查問題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)，則搜索成功，找到了問題的解；若沒有出現(xiàn)，則按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，重復(fù)上述過程，指導(dǎo)目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒有可供擴(kuò)展的節(jié)點(diǎn)為止。1245.2狀態(tài)空間的盲目搜索狀態(tài)空間搜索的基本思想是：415.2狀態(tài)空間的盲目搜索狀態(tài)空間算法：需要設(shè)立數(shù)據(jù)結(jié)構(gòu)Open和Closed表。Open表（未擴(kuò)展節(jié)點(diǎn)表）：用于存放剛生成沒有擴(kuò)展的節(jié)點(diǎn)；Closed表（已擴(kuò)展節(jié)點(diǎn)表）：用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展的節(jié)點(diǎn)。1255.2狀態(tài)空間的盲目搜索狀態(tài)空間算法：425.2狀態(tài)空間的盲目搜索狀態(tài)空間的一般圖搜索過程為：（1）把初始節(jié)點(diǎn)S0放入Open表并建立目前僅包含S0的圖G;（2）檢查Open表是否為空，若為空，則問題無解，失敗退出；（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；1265.2狀態(tài)空間的盲目搜索狀態(tài)空間的一般圖搜索過程為：435.2狀態(tài)空間的盲目搜索（5）擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)n先輩的那部分子節(jié)點(diǎn)記入集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入G中。（6）針對M中子節(jié)點(diǎn)的不同情況，分別作如下處理：對那些沒有在G中出現(xiàn)過的M成員設(shè)置一個指向其父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它放入Open表；對那些原來已在G中出現(xiàn)過，但還沒有被擴(kuò)展的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；1275.2狀態(tài)空間的盲目搜索（5）擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把5.2狀態(tài)空間的盲目搜索對于先前已在G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（7）按某種策略對Open表中的節(jié)點(diǎn)進(jìn)行排序；（8）轉(zhuǎn)(2)步。1285.2狀態(tài)空間的盲目搜索對于先前已在G中出現(xiàn)過，并已經(jīng)擴(kuò)展了5.2狀態(tài)空間的盲目搜索搜索過程說明：（1）狀態(tài)空間圖搜索算法具有通用性，其它的各種狀態(tài)空間搜索策略都是上述的一個特例。各種搜索策略的主要區(qū)別在于對Open表中節(jié)點(diǎn)的排列順序不同。如廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面；深度優(yōu)先搜索把后生成的子節(jié)點(diǎn)排在前面。1295.2狀態(tài)空間的盲目搜索搜索過程說明：465.2狀態(tài)空間的盲目搜索（2）在第(5)步對節(jié)點(diǎn)n擴(kuò)展后，生成并記入M的子節(jié)點(diǎn)有以下三種情況：該子節(jié)點(diǎn)從未被任何節(jié)點(diǎn)生成過，由n第一次生成；該子節(jié)點(diǎn)原來被其它節(jié)點(diǎn)生成過，但還沒有被擴(kuò)展，這一次又被n再次生成；該子節(jié)點(diǎn)原來被其它節(jié)點(diǎn)生成過，并且已經(jīng)被擴(kuò)展過，這一次又被n再次生成。1305.2狀態(tài)空間的盲目搜索（2）在第(5)步對節(jié)點(diǎn)n擴(kuò)展后，生5.2狀態(tài)空間的盲目搜索對于一般圖搜索算法，具有以上三種情況；對于盲目搜索，由于其狀態(tài)空間是樹狀結(jié)構(gòu)，因此不會出現(xiàn)后兩種情況，每個節(jié)點(diǎn)擴(kuò)展后生成的子節(jié)點(diǎn)都是第一次出現(xiàn)的節(jié)點(diǎn)，不必檢查并修改指向父節(jié)點(diǎn)的指針。（3）在第（6）步針對M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時，如果發(fā)生上面第2種情況，一般是由原時節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價來決定。1315.2狀態(tài)空間的盲目搜索對于一般圖搜索5.2狀態(tài)空間的盲目搜索例題見書P1775.2.2廣度優(yōu)先搜索廣度優(yōu)先搜索也成為寬度優(yōu)先搜索，是一種先生成的節(jié)點(diǎn)限擴(kuò)展的策略。

1325.2狀態(tài)空間的盲目搜索例題見書P177495.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索策略搜索過程為：從初始節(jié)點(diǎn)S0開始逐層向下擴(kuò)展，在第n曾節(jié)點(diǎn)還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入Open表的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。1335.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索策略搜索過程為：5.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；（5）若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。1345.2狀態(tài)空間的盲目搜索廣度優(yōu)先搜索算法如下：515.2狀態(tài)空間的盲目搜索（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.5八數(shù)碼難題。見書P1781355.2狀態(tài)空間的盲目搜索（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Op5.2狀態(tài)空間的盲目搜索5.2.3深度優(yōu)先搜索深度優(yōu)先搜索是一種后生成的節(jié)點(diǎn)先擴(kuò)展的策略。深度優(yōu)先搜索策略搜索過程為：從初始節(jié)點(diǎn)S0開始，在其子節(jié)點(diǎn)中選擇一個最新生成的節(jié)點(diǎn)進(jìn)行考察，如果該子解不是目標(biāo)節(jié)點(diǎn)而且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)，然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個最新生成的節(jié)點(diǎn)進(jìn)行考察，依次向下搜索，直到某個子節(jié)點(diǎn)即不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。1365.2狀態(tài)空間的盲目搜索5.2.3深度優(yōu)先搜索535.2狀態(tài)空間的盲目搜索Open表示一種棧結(jié)構(gòu)，最先進(jìn)入的節(jié)點(diǎn)排在最后面，最后進(jìn)入的節(jié)點(diǎn)排在最前面。

深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;1375.2狀態(tài)空間的盲目搜索Open表示一5.2狀態(tài)空間的盲目搜索（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；（5）若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。（6）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.6八數(shù)碼難題。見書P1791385.2狀態(tài)空間的盲目搜索（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是5.2狀態(tài)空間的盲目搜索5.2.4有界深度優(yōu)先搜索深度優(yōu)先搜索如果目標(biāo)不在搜索的分支上，且該分支又是一個無限分支，則搜索過程就不可能找到解。即使能夠找到節(jié)，按深度優(yōu)先找到的解也不一定是最優(yōu)解。有界深度優(yōu)先搜索過程總體上按深度優(yōu)先策略進(jìn)行，但對搜索深度需要給出一個深度限制dm，當(dāng)搜索深度達(dá)到了dm，但還沒有找到目標(biāo)時，就停止該分支的搜索，換到另外一個分支進(jìn)行搜索。1395.2狀態(tài)空間的盲目搜索5.2.4有界深度優(yōu)先搜索565.2狀態(tài)空間的盲目搜索有界深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；1405.2狀態(tài)空間的盲目搜索有界深度優(yōu)先搜索算法如下：575.2狀態(tài)空間的盲目搜索（5）若節(jié)點(diǎn)n的深度d(n)=dm，則轉(zhuǎn)第（2）步。(6)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。（7）擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部。并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第（2）步。例5.7八數(shù)碼難題。見書P1801415.2狀態(tài)空間的盲目搜索（5）若節(jié)點(diǎn)n的深度d(n)=dm，5.2狀態(tài)空間的盲目搜索5.2.5代價樹搜索需要在搜索樹的每條邊標(biāo)上其代價。這種有代價的樹稱為代價樹。在代價樹中，用g(n)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的代價，用c(n1,n2)表從父節(jié)點(diǎn)n1到其子節(jié)點(diǎn)n2的代價，對節(jié)點(diǎn)n2的代價有：

g(n2)=g(n1)+c(n1,n2)1425.2狀態(tài)空間的盲目搜索5.2.5代價樹搜索595.2狀態(tài)空間的盲目搜索在代價樹中，最小代價的路徑和最短路徑（即路徑長度最短）是有可能的。最短路徑不一定是代價最小的路徑；代價最小的路徑不一定是最短路徑。1.代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索也稱為分枝界限法。每次從Open表中選擇節(jié)點(diǎn)或往closed表中存放節(jié)點(diǎn)時，總是選擇代價小的節(jié)點(diǎn)排在前面，代價大的排在后面，與節(jié)點(diǎn)在樹中的位置無關(guān)。1435.2狀態(tài)空間的盲目搜索在代價樹中，最5.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價g(s0)=0；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，成功退出；1445.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索算法如下：615.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（2）步。(6）擴(kuò)展節(jié)點(diǎn)n，生成子節(jié)點(diǎn)ni(I=1,2,…),將這些子節(jié)點(diǎn)放入Open表中，并為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)指針；按如下公式：

g(ni)=g(n)+c(n,ni)(i=1,2,…)計(jì)算各自節(jié)點(diǎn)的代價，并根據(jù)各節(jié)點(diǎn)的代價對Open表中的全部按照從小到大順序重新進(jìn)行排序，然后轉(zhuǎn)第（2）步。1455.2狀態(tài)空間的盲目搜索(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第（5.2狀態(tài)空間的盲目搜索代價樹的廣度優(yōu)先搜索是完備的，如果問題有解，上述算法一定能夠找到，并且找到的是最優(yōu)解。例5.8城市交通問題。P1811465.2狀態(tài)空間的盲目搜索代價樹的廣度5.2狀態(tài)空間的盲目搜索2.代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索每次從Open表中選擇節(jié)點(diǎn)或往closed表中存放節(jié)點(diǎn)時，總是從剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個代價最小的節(jié)點(diǎn)。1475.2狀態(tài)空間的盲目搜索2.代價樹的深度優(yōu)先搜索645.2狀態(tài)空間的盲目搜索代價樹的深度優(yōu)先搜索算法如下：（1）把初始節(jié)點(diǎn)S0放入Open表中，置S0的代價g(s0)=0；（2）如果Open表為空，則問題無解，失敗退出。（3）把Open表的第一個節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n;（4）考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問題的解，