人工智能ppt課件-3-搜索的基本策略

第3章搜索的基本策略

第3章搜索的基本策略13.1盲目的搜索方法盲目搜索方法又叫非啟發(fā)式搜索，是一種無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問(wèn)題。下面我們要討論的幾個(gè)搜索方法，它們均屬于盲目搜索方法。3.1盲目的搜索方法23.1.1寬度優(yōu)先搜索如果搜索是以同層鄰近節(jié)點(diǎn)依次擴(kuò)展節(jié)點(diǎn)的,那么這種搜索就叫寬度優(yōu)先搜索,這種搜索是逐層進(jìn)行的,在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前,必須搜索完本層的所有節(jié)點(diǎn)。3.1.1寬度優(yōu)先搜索33.1.1寬度優(yōu)先搜索寬度優(yōu)先搜索算法如下:1.令N為一個(gè)由初始狀態(tài)構(gòu)成的表；

2.若N為空退出，標(biāo)志失敗；

3.令n為N中第一個(gè)點(diǎn)，將n從N中刪除；

4.若n是目標(biāo)，則退出，標(biāo)態(tài)成功；

5.若n不是目標(biāo)，將n的后繼點(diǎn)加入到N表的尾部，轉(zhuǎn)2。

3.1.1寬度優(yōu)先搜索寬度優(yōu)先搜索算法如下:43.1.1寬度優(yōu)先搜索寬度優(yōu)先搜索的優(yōu)點(diǎn)是：若問(wèn)題有解，則可找出最優(yōu)解;寬度優(yōu)先搜索的缺點(diǎn)是:效率低，組合爆炸問(wèn)題難以解決。3.1.1寬度優(yōu)先搜索53.1.2深度優(yōu)先搜索在深度優(yōu)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的（即最深的）節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。3.1.2深度優(yōu)先搜索63.1.2深度優(yōu)先搜索深度優(yōu)先搜索算法如下:1.令N為一個(gè)由初始狀態(tài)構(gòu)成的表；2.若N為空退出，標(biāo)態(tài)失??；3.令n為N中第一個(gè)點(diǎn)，將n從N中刪除；4.若n是目標(biāo)，則退出，標(biāo)態(tài)成功；5.若n不是目標(biāo)，將n的后繼加入到N表的首部轉(zhuǎn)2。3.1.2深度優(yōu)先搜索深度優(yōu)先搜索算法如下:73.1.2深度優(yōu)先搜索

深度優(yōu)先搜索的優(yōu)點(diǎn)：節(jié)省大量時(shí)間和空間；深度優(yōu)先搜索的缺點(diǎn)：不一定能找到解。因?yàn)樵跓o(wú)限搜索樹的情況下，最壞的情況可能是不停機(jī)。3.1.2深度優(yōu)先搜索83.1.3分枝有界搜索

（Branch-and-Bound）

分枝有界搜索也是一種深度優(yōu)先搜索，但每個(gè)分支都規(guī)定了一個(gè)統(tǒng)一的搜索深度，搜索到這個(gè)深度后，如果沒(méi)有找到目標(biāo)便自動(dòng)退回到上一層，繼續(xù)搜索。3.1.3分枝有界搜索

（Branch-and-Bound93.1.3分枝有界搜索1.令N為一由初始狀態(tài)構(gòu)成的表；2.若N為空退出，標(biāo)志失??；3.令n為N中第一個(gè)點(diǎn)，將n從N中刪除；4.若n是目標(biāo)，則退出，標(biāo)態(tài)成功；5.若n深度=預(yù)先定好的一個(gè)界dmax，則轉(zhuǎn)2；6.若n不是目標(biāo)，將n的后繼加入到N表的首部轉(zhuǎn)2；3.1.3分枝有界搜索1.令N為一由初始狀態(tài)構(gòu)成的表；103.1.4迭代加深搜索

（Iterativedeepening）迭代加深搜索是在分枝有界搜索的基礎(chǔ)上，對(duì)dmax進(jìn)行迭代，即逐步加深。這是一種同時(shí)兼顧深度和廣度的搜索方法。在限定的深度內(nèi)，保證了對(duì)廣度節(jié)點(diǎn)的搜索，如果沒(méi)有找到解，再加深深度。3.1.4迭代加深搜索

（Iterativedeepen113.2啟發(fā)式搜索方法如果能夠找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大大提高。啟發(fā)式搜索就是基于這種想法,它是深度優(yōu)先的改進(jìn)。搜索時(shí)不是任取一個(gè)分枝，而是根據(jù)一些啟發(fā)式信息，選擇最佳一個(gè)分枝或幾個(gè)分枝往下搜索。3.2啟發(fā)式搜索方法如果能夠找到一種方法用于123.2.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)（1）人們善于利用一些線索來(lái)幫助自己選擇搜索方向，這些線索統(tǒng)稱為啟發(fā)式(Heuristics)信息。（2）現(xiàn)實(shí)問(wèn)題往往只需一個(gè)解，而不要求最優(yōu)解或全部解。（3）啟發(fā)式信息可以避免某些領(lǐng)域里的組合爆炸問(wèn)題。3.2.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)133.2.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：（1）表示為估計(jì)函數(shù)確定一個(gè)啟發(fā)式函數(shù)f(n),n

為被搜索的節(jié)點(diǎn),它把問(wèn)題狀態(tài)的描述映射成問(wèn)題解決的程度，通常這種程度用數(shù)值來(lái)表示，就是啟發(fā)式函數(shù)的值。這個(gè)值的大小用來(lái)決定最佳搜索路徑。3.2.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：143.2.1啟發(fā)式信息的表示（2）表示成規(guī)則如程序AM的一條啟發(fā)式規(guī)則為：如果存在一個(gè)有趣的二元函數(shù)f(x,y)，那么看看兩變?cè)嗤瑫r(shí)會(huì)發(fā)生什么？若f表示乘法：導(dǎo)致發(fā)現(xiàn)平方；若f表示集合并運(yùn)算：導(dǎo)致發(fā)現(xiàn)恒等函數(shù)；若f表示思考：導(dǎo)致發(fā)現(xiàn)反??；若f表示謀殺：導(dǎo)致發(fā)現(xiàn)自殺。3.2.1啟發(fā)式信息的表示（2）表示成規(guī)則153.2.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法啟發(fā)式函數(shù)是一種映射函數(shù)，它把對(duì)問(wèn)題狀態(tài)的描述映射成一種希望的程度。啟發(fā)式函數(shù)設(shè)計(jì)得好，對(duì)有效引導(dǎo)搜索過(guò)程有著重要的作用。非常簡(jiǎn)單的啟發(fā)式函數(shù)搜索路徑能夠作出非常令人滿意的估計(jì)。3.2.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法163.2.1啟發(fā)式信息的表示如何構(gòu)造啟發(fā)式函數(shù)？（1）啟發(fā)式函數(shù)能夠根據(jù)問(wèn)題的當(dāng)前狀態(tài)，確定用于繼續(xù)求解問(wèn)題的信息。這樣的啟發(fā)式函數(shù)能夠有效地幫助決定那些后繼節(jié)點(diǎn)應(yīng)被產(chǎn)生。3.2.1啟發(fā)式信息的表示如何構(gòu)造啟發(fā)式函數(shù)？173.2.1啟發(fā)式信息的表示

283

1

6475

例2.7八數(shù)碼問(wèn)題。

1

238

4765

a11a12a13a21a22a23a31a32a33

問(wèn)題空間為：S0

Sg

3.2.1啟發(fā)式信息的表示283例2183.2.1啟發(fā)式信息的表示各狀態(tài)間的轉(zhuǎn)換規(guī)則為：Pr1:空格上移↑

If□i，jandi≠1thenai-1,j←→□i，j

Pr2:空格下移↓

If□i，jandi≠3thenaI+1,j←→□i，j

3.2.1啟發(fā)式信息的表示各狀態(tài)間的轉(zhuǎn)換規(guī)則為：193.2.1啟發(fā)式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j3.2.1啟發(fā)式信息的表示20啟發(fā)式函數(shù)f1=數(shù)字錯(cuò)放位置的個(gè)數(shù)，f1=0，則達(dá)到目標(biāo)。2831647528316475283147652831476523184765283164752831476528316475啟發(fā)式函數(shù)f1=數(shù)字錯(cuò)放位置的個(gè)數(shù)，f1=0，則達(dá)到目標(biāo)。213.2.1啟發(fā)式信息的表示當(dāng)f1值相同時(shí)如何決定走步?

現(xiàn)在定義：f2=所有數(shù)字當(dāng)前位置以最短路徑走到正確位置的步數(shù)之和。在這個(gè)定義之下，各狀態(tài)的啟發(fā)式函數(shù)值為：數(shù)碼12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=43.2.1啟發(fā)式信息的表示當(dāng)f1值相同時(shí)如何決定走步223.2.1啟發(fā)式信息的表示數(shù)碼12345678F2(S2）=1+1+0+0+0+1+1+2=6F2(S3）=1+1+0+0+1+1+0+2=6F2(S4）=1+1+0+0+0+0+0+1=3F2(S5）=1+1+0+0+0+1+0+2=5F2(S6）=1+2+0+0+0+0+0+2=53.2.1啟發(fā)式信息的表示數(shù)碼12233.2.1啟發(fā)式信息的表示

(2)啟發(fā)式函數(shù)應(yīng)能夠估計(jì)出可能加速達(dá)到目標(biāo)的程度

這可以幫助確定當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，那些節(jié)點(diǎn)應(yīng)從搜索樹中刪除。啟發(fā)式函數(shù)對(duì)搜索樹(圖)的每一節(jié)點(diǎn)的真正優(yōu)點(diǎn)估計(jì)得愈精確,解題過(guò)程就愈少走彎路。3.2.1啟發(fā)式信息的表示(2)啟發(fā)式函數(shù)應(yīng)能夠估計(jì)出243.2.1啟發(fā)式信息的表示例2.8八皇后問(wèn)題(8-Queensproblem）

在8*8棋盤要求放下8個(gè)皇后，要求沒(méi)有一個(gè)皇后能夠攻擊其它皇后，即要使得在任何一行、一列或?qū)蔷€上都不存在兩個(gè)或兩個(gè)以上的皇后。3.2.1啟發(fā)式信息的表示例2.8八皇后問(wèn)題(8-Que253.2.1啟發(fā)式信息的表示求解這個(gè)問(wèn)題的過(guò)程為：

（a）定義狀態(tài)空間。設(shè)狀態(tài)空間的一點(diǎn)為：8*8矩陣。

（b）定義操作規(guī)則。按如下規(guī)則放置皇后：3.2.1啟發(fā)式信息的表示求解這個(gè)問(wèn)題的過(guò)程為：263.2.1啟發(fā)式信息的表示第一個(gè)皇后放第一行。第二個(gè)皇后放在第二行且不與第一個(gè)皇后在同一列或?qū)蔷€的空格上。

……

第i個(gè)皇后放在第i行且不與前面i–1個(gè)皇后在同一列或?qū)蔷€的空格上。

……3.2.1啟發(fā)式信息的表示第一個(gè)皇后放第一行。273.2.1啟發(fā)式信息的表示可使用如下啟發(fā)式函數(shù)：設(shè)x為當(dāng)前要放置Queen的空格f（x）=剩下未放行中能夠用來(lái)放Queen的空格數(shù)不難看出，f（x）愈大愈好，應(yīng)選擇f（x）最大的空格來(lái)放置皇后。3.2.1啟發(fā)式信息的表示可使用如下啟發(fā)式函數(shù)：28例如，在放置了三個(gè)Q后，第4個(gè)Q可放在第4行的A，B，C三個(gè)位置。

Q

Q

Q

A

BC

abc

bc

ab

bc

c

ac

abc

b

acb

ac

acabbc

例如，在放置了三個(gè)Q后，第4個(gè)Q可放在第4行的A，B，C三個(gè)293.2.1啟發(fā)式信息的表示a為第4行A處放了皇后剩下可放Q的位置；

b為第4行B處放了皇后剩下可放Q的位置；c為第4行C處放了皇后剩下可放Q的位置。按照以上定義，可求得：

f（A）=8，f（B）=9，f（C）=10。所以搜索可以從C對(duì)應(yīng)的空格放置一個(gè)皇后開始，其余的空格對(duì)應(yīng)的搜索樹可以刪除。3.2.1啟發(fā)式信息的表示a為第4行A處放了皇后剩下可放Q303.2.1啟發(fā)式信息的表示（c）定義搜索策略。第i個(gè)皇后放到第i行中的那個(gè)與前面i-l個(gè)皇后不在同一列或?qū)蔷€上且f（x）值最大的空格中。啟發(fā)式信息是某些領(lǐng)域里的知識(shí)信息，它能使計(jì)算機(jī)系統(tǒng)在這些知識(shí)信息提示以后可能采取的某些可能的動(dòng)作或避免某些不可能的動(dòng)作。3.2.1啟發(fā)式信息的表示（c）定義搜索策略。31搜索方向的選擇

搜索過(guò)程：在問(wèn)題空間中找出從開始狀態(tài)到目標(biāo)狀態(tài)的一條最好的或較好的路徑。這種搜索可按兩個(gè)方向進(jìn)行：

正向搜索：從初始狀態(tài)朝著目標(biāo)狀態(tài)方向搜索；逆向搜索：從目標(biāo)狀態(tài)朝著初始狀態(tài)方向搜索。將以上兩種搜索方法結(jié)合起來(lái)，就產(chǎn)生了雙向搜索

搜索方向的選擇搜索過(guò)程：在問(wèn)題空間中找出從開始狀態(tài)32搜索方向的選擇正向搜索和逆向搜索S0S0SgSg搜索方向的選擇正向搜索和33搜索方向的選擇(1)

朝分枝因子低的方向更有效。分子因子指從一點(diǎn)出發(fā)可以直接到達(dá)的平均結(jié)點(diǎn)數(shù)。朝著分枝因子低的方向搜索意味著朝著“收斂”的方向搜索，例如定理證明,一般是從公理或定理出發(fā)，推出新的定理。公理是有限的，而定理是大量的。搜索方向的選擇(1)

朝分枝因子低的方向更有效。34搜索方向的選擇(2)

由狀態(tài)少的一方出發(fā)，朝著大量的可識(shí)別的狀態(tài)的方向搜索

例如符號(hào)積分問(wèn)題,正向搜索意味著從被積函數(shù)出發(fā)，按照積分規(guī)則，尋找原函數(shù)。而逆向搜索，則要從大量的原函數(shù)的任意組合出發(fā)，通過(guò)積分規(guī)則，找出被積函數(shù)，這顯然要困難得多，我們?cè)谌斯ぱ菟惴e分問(wèn)題時(shí)決不會(huì)這么去做。搜索方向的選擇(2)

由狀態(tài)少的一方出發(fā)，朝著大量的可識(shí)別的35搜索方向的選擇

(3)依據(jù)用戶可接受的方向

特別是需要向用戶解釋推理過(guò)程時(shí)，順應(yīng)用戶的心理，選擇搜索方向會(huì)使系統(tǒng)顯得更自然一些。在建造專家系統(tǒng)時(shí)，向用戶解釋為什么系統(tǒng)會(huì)得出某個(gè)結(jié)論,這一步驟是必不可少的，所以尤其要考慮這個(gè)問(wèn)題。搜索方向的選擇(3)依據(jù)用戶可接受的方向363.2.2幾種最基本的搜索策略

下面主要介紹采用Best-first策略的幾個(gè)基本方法，這些方法構(gòu)成了許多數(shù)AI系統(tǒng)的構(gòu)架，其效率取決于問(wèn)題所在領(lǐng)域知識(shí)的利用與開發(fā)。由于這些方法的通用性，并且難于克服搜索過(guò)程的組合爆炸問(wèn)題，所以又稱為弱法(Weakmethod）。3.2.2幾種最基本的搜索策略下面主要介紹采用Best-373.2.2幾種最基本的搜索策略弱法主要包括：．最佳優(yōu)先法．生成測(cè)試法．爬山法．廣度優(yōu)先法．問(wèn)題歸約法．約束滿足法．手段目的分析法。3.2.2幾種最基本的搜索策略弱法主要包括：381．生成測(cè)試法

(Generate-and-test）

生成測(cè)試法的基本步驟為：

1.生成一個(gè)可能的解，此解是狀態(tài)空間一個(gè)點(diǎn)，或一條始于S0的路徑。

2.用生成的“解”與目標(biāo)比較。

3.達(dá)到目標(biāo)則停止，否則轉(zhuǎn)第一步。1．生成測(cè)試法

(Generate-and-test）391．生成測(cè)試法

(Generate-and-test）此方法屬于深度優(yōu)先搜索(depth-first-search）,因?yàn)橐a(chǎn)生一個(gè)完全的解后再判斷，若不是目標(biāo)又要生成下一個(gè)“解”。這種方法幾乎接近耗盡式搜索，因而效率低。于是人們考慮能否利用反饋信息以幫助決定生成什么樣的解，這種改進(jìn)就是下面要講的爬山法。1．生成測(cè)試法

(Generate-and-test）402．爬山法(Hill-climbing）

1生成第一個(gè)可能的解。若是目標(biāo)，則停止；否則轉(zhuǎn)下一步。2從當(dāng)前可能的解出發(fā)，生成新的可能解集。2.1用測(cè)試函數(shù)測(cè)試新的可能解集中的元素，若是解，則停止；否則轉(zhuǎn)2.2。

2.2若不是解，則將它與至今已測(cè)試過(guò)的“解”比較。若它最接近解，則保留作為最佳元素；若它不最接近解，則舍棄。

3以當(dāng)前最佳元素為起點(diǎn)，轉(zhuǎn)(２）。2．爬山法(Hill-climbing）1生成第一個(gè)可能412．爬山法(Hill-climbing）

爬山法在生成的元素中尋找最優(yōu)解，這種最優(yōu)是局部最優(yōu)。爬山法會(huì)產(chǎn)生下述問(wèn)題：

(1）找到的是局部最大值。(如左圖)(2）碰到平頂時(shí)無(wú)法處理。(如右圖)2．爬山法(Hill-climbing）爬山法在生成的元素422．爬山法(Hill-climbing）

(3）碰到山脊時(shí)無(wú)法處理。碰到山脊的克服辦法是：

(1)退回較大一步，即允許回朔。

(2)向前跨一大步。

(3)多設(shè)幾個(gè)初始點(diǎn)，從幾個(gè)初始點(diǎn)同時(shí)或先后進(jìn)行搜索。2．爬山法(Hill-climbing）(3）碰到山脊時(shí)無(wú)433．最佳優(yōu)先搜索

(Best-firstsearch)1生成第一個(gè)可能的解。若是目標(biāo)，則停止；否則轉(zhuǎn)下一步。

2從該可能的解出發(fā)，生成新的可能解集。

2.1用測(cè)試函數(shù)測(cè)試新的可能解集中的元素，若是解，則停止；否則轉(zhuǎn)a。

2.2若不是解，則將新生成的“解”集加入到原可能“解”集中。3從解集中挑選最好的元素作為起點(diǎn)，再轉(zhuǎn)２3．最佳優(yōu)先搜索

(Best-firstsearch)1444.模擬退火法

(simulatedAnnealing)

退火是冶金專家為了達(dá)到某些特種晶體結(jié)構(gòu)重復(fù)將金屬加熱或冷卻的過(guò)程,該過(guò)程的控制參數(shù)為溫度T。這種思想應(yīng)用于許多優(yōu)化問(wèn)題就產(chǎn)生了模擬退火算法,模擬退火法的基本思想是,在系統(tǒng)朝著能量減小的趨勢(shì)這樣一個(gè)變化過(guò)程中,偶爾允許系統(tǒng)跳到能量較高的狀態(tài)，以避開局部極小點(diǎn),最終穩(wěn)定到全局最小點(diǎn)。4.模擬退火法

(simulatedAnnealing)454.模擬退火法

(simulatedAnnealing)如圖所示，若使能量在C點(diǎn)突然增加h，就能跳過(guò)局部極小點(diǎn)B,而找到全局最小點(diǎn)A?，F(xiàn)在的問(wèn)題是何時(shí)增加能量？應(yīng)該增加多少能量？為此，柯克帕特里克(S.Kirkpatrick）提出了模擬退火算法。

B

AC4.模擬退火法

(simulatedAnnealing)463.3

隨機(jī)搜索

3.3隨機(jī)搜索