D-啟發(fā)式搜索-人工智能(AI)課件

啟發(fā)式（有信息）搜索

Heuristic(Informed)Search

(我們試著做一些聰明的選擇)

R&N:Chap.4,Sect.4.1–3

1啟發(fā)式（有信息）搜索

Heuristic(Informed啟發(fā)函數(shù)h(N)0估計從狀態(tài)（N）到目標(biāo)狀態(tài)的耗散

其值與當(dāng)前的搜索樹無關(guān)；僅取決于狀態(tài)STATE(N)和目標(biāo)測試GOAL?

Example:

h1(N)=不在位的牌數(shù)=6

[為什么它是對目標(biāo)距離的一個估計呢？]啟發(fā)函數(shù)

HeuristicFunction14752638STATE(N)64715283Goalstate2啟發(fā)函數(shù)h(N)0估計從狀態(tài)（N）到目標(biāo)狀態(tài)的耗散h1(N)=不在位的牌數(shù)=6h2(N)=每個數(shù)碼牌與其目標(biāo)位置的 (Manhattan)距離和

=2+3+0+1+3+0+3+1=13h3(N)=sumofpermutationinversions

=n5+n8+n4+n2+n1+n7+n3+n6

=4+6+3

+1

+0

+2

+0+0

=16OtherExamples14752638STATE(N)64715283Goalstate3OtherExamples14752638STATE(N)8-Puzzle4553343442120343f(N)=h(N)=不在位數(shù)碼牌的個數(shù)白色為空位48-Puzzle4553343442120343f(N)=0+41+51+51+33+33+43+43+24+15+25+02+32+42+38-Puzzlef(N)=g(N)+h(N)

式中

h(N)=不在位數(shù)碼牌的個數(shù)50+41+51+51+33+33+43+43+24+15+25664421205538-Puzzlef(N)=h(N)=S

數(shù)碼牌與其目標(biāo)位置的距離65664421205538-Puzzlef(N)=h(N最佳優(yōu)先效率

Best-First

Efficiencyf(N)=h(N)=與目標(biāo)的直線距離Local-minimumproblem7最佳優(yōu)先效率

Best-FirstEfficienc什么是我們能證明的？如果狀態(tài)空間是無限的，通常搜索是不完備的如果狀態(tài)空間是有限的，但不丟棄那些重復(fù)訪問的狀態(tài)的話，通常搜索也是不完備的如果狀態(tài)空間是有限的，并丟棄那些重復(fù)訪問的狀態(tài)，那么搜索是完備的，但通常不是最優(yōu)的8什么是我們能證明的？如果狀態(tài)空間是無限的，通常搜索是不完備的可采納的啟發(fā)

AdmissibleHeuristic

令h*(N)為從節(jié)點(diǎn)N到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑的耗散

啟發(fā)式函數(shù)h(N)是可納的，若：

0h(N)h*(N)可納的啟發(fā)式函數(shù)總是最優(yōu)的！G為目標(biāo)節(jié)點(diǎn)

h(G)=09可采納的啟發(fā)

AdmissibleHeuristic令hh1(N)=不在位數(shù)碼牌的個數(shù)=6

是

???h2(N)=sumofthe(Manhattan)distancesof

everytiletoitsgoalposition

=2+3+0+1+3+0+3+1=13

isadmissibleh3(N)=sumofpermutationinversions

=4+6+3+1+0+2+0+0=16

isnotadmissible8-PuzzleHeuristics14752638STATE(N)64715283Goalstate108-PuzzleHeuristics14752638STAh1(N)=不在位數(shù)碼牌的個數(shù)=6

是可納的h2(N)=每個數(shù)碼牌與其目標(biāo)位置的 (Manhattan)距離和

=2+3+0+1+3+0+3+1=13

是???h3(N)=sumofpermutationinversions

=4+6+3+1+0+2+0+0=16

isnotadmissible

8-PuzzleHeuristics14752638STATE(N)64715283Goalstate118-PuzzleHeuristics14752638STAh1(N)=不在位數(shù)碼牌的個數(shù)=6

是可納的h2(N)=每個數(shù)碼牌與其目標(biāo)位置的 (Manhattan)距離和

=2+3+0+1+3+0+3+1=13

是可納的h3(N)=sumofpermutationinversions

=4+6+3+1+0+2+0+0=16

isnotadmissible

8-PuzzleHeuristics14752638STATE(N)64715283Goalstate128-PuzzleHeuristics14752638STAh1(N)=不在位數(shù)碼牌的個數(shù)=6

是可納的h2(N)=每個數(shù)碼牌與其目標(biāo)位置的

(Manhattan)距離和

=2+3+0+1+3+0+3+1=13

是可納的h3(N)=sumofpermutationinversions

=4+6+3+1+0+2+0+0=16

isnotadmissible

8-PuzzleHeuristics14752638STATE(N)64715283Goalstate138-PuzzleHeuristics14752638STA怎樣構(gòu)造一個可納的h？一個可納的啟發(fā)函數(shù)通?？煽醋魇且粋€松弛問題（通過去除一些約束限制得到）的最優(yōu)解的耗散在機(jī)器人導(dǎo)航中:曼哈頓距離對應(yīng)于去除障礙物的限制歐幾里得距離對應(yīng)于去除障礙物的限制及機(jī)器人只能在格子內(nèi)移動的約束詳情在本課稍后敘述14怎樣構(gòu)造一個可納的h？一個可納的啟發(fā)函數(shù)通?？煽醋魇且粋€A*搜索

(AI中被最廣泛應(yīng)用的算法)f(N)=g(N)+h(N),其中:g(N)=從起始節(jié)點(diǎn)到節(jié)點(diǎn)N的路徑耗散h(N)=可納啟發(fā)函數(shù)

對于所有的弧:c(N,N’)

>0

采用

SEARCH#2搜索算法（節(jié)點(diǎn)擴(kuò)展時目標(biāo)測試）最佳優(yōu)先（Best-first）搜索于是被稱為A*search15A*搜索

(AI中被最廣泛應(yīng)用的算法)f(N)=g(N結(jié)論1

A*完備最優(yōu)

[即使不丟棄重復(fù)訪問的節(jié)點(diǎn)，以上結(jié)論也是成立的]16結(jié)論1 A*完備最優(yōu)16時間限制問題當(dāng)一個問題無解時，如果該問題的狀態(tài)空間是無限的或者不限制重復(fù)訪問的次數(shù)，那么A*將不停的永遠(yuǎn)運(yùn)行下去。其他的一些情況，也可能使A*花費(fèi)大量的時間才會停止。因此，實際應(yīng)用中，對A*將會給定一個時間的限制。如果在時間限制內(nèi)沒有找到解，則停止運(yùn)行。這樣的話，將沒有辦法知道該問題是否無解，或者是否需要更多的時間就能找到解當(dāng)AI系統(tǒng)“小”且一次只是解決一個搜索問題時，以上的問題不會成為太大的問題，不必過慮.但是當(dāng)AI系統(tǒng)變得很大，需要同時解決許多個搜索問題，其中一些是無解問題的時候，該如何定義相應(yīng)的時間限制呢？有興趣的同學(xué)可以進(jìn)一步閱讀相關(guān)文獻(xiàn)……（如MotionPlanning...）17時間限制問題當(dāng)一個問題無解時，如果該問題的狀態(tài)空間是無限的或8-Puzzle0+41+51+51+33+33+43+43+24+15+25+02+32+42+3f(N)=g(N)+h(N)

式中h(N)=不在位的數(shù)碼牌個數(shù)188-Puzzle0+41+51+51+33+33+43+43RobotNavigation19RobotNavigation19RobotNavigation02115877347676328645233365244355465645f(N)=h(N),其中h(N)=與目標(biāo)的Manhattan距離(不是A*)20RobotNavigation02115877347676RobotNavigation02115877347676328645233365244355465645f(N)=h(N),其中h(N)=與目標(biāo)的Manhattan距離(不是A*)7021RobotNavigation02115877347676RobotNavigationf(N)=g(N)+h(N),式中h(N)=與目標(biāo)的Manhattan距離(A*)021158773476763286452333652443554656457+06+16+18+17+07+26+17+26+18+17+28+37+26+36+35+45+44+54+53+63+62+78+37+47+46+55+66+35+62+73+84+75+64+73+84+73+83+82+92+93+102+93+82+91+101+100+110+1122RobotNavigationf(N)=g(N)+h(最佳優(yōu)先搜索（貪婪搜索）

Best-FirstSearch評價函數(shù)f將搜索樹的每一個節(jié)點(diǎn)N映射為一個實際的數(shù)值

f(N)0

最佳優(yōu)先搜索按照節(jié)點(diǎn)的f值升序排列邊緣隊列

23最佳優(yōu)先搜索（貪婪搜索）

Best-FirstSearchA*搜索f(N)=g(N)+h(N),其中:g(N)=從起始節(jié)點(diǎn)到節(jié)點(diǎn)N的路徑耗散h(N)=可納啟發(fā)函數(shù)

對于所有的弧:c(N,N’)

>0

采用

SEARCH#2搜索算法（節(jié)點(diǎn)擴(kuò)展時目標(biāo)測試）最佳優(yōu)先（Best-first）搜索于是被稱為A*search24A*搜索f(N)=g(N)+h(N),其中:24結(jié)論1

A*完備最優(yōu)

[即使不丟棄重復(fù)訪問的節(jié)點(diǎn)，以上結(jié)論也是成立的]25結(jié)論1 A*完備最優(yōu)25如何處理可重復(fù)訪問狀態(tài)?c=1100212h=1000901 此處的啟發(fā)函數(shù)h無疑是可納的26如何處理可重復(fù)訪問狀態(tài)?c=1100212h=100c=1100212h=10009011044+90f=1+1002+1?如果因為該新節(jié)點(diǎn)的狀態(tài)是重復(fù)訪問的，就將它丟棄的話，那么搜索算法下一個就將擴(kuò)展目標(biāo)節(jié)點(diǎn)，因此返回一個非最優(yōu)解如何處理可重復(fù)訪問狀態(tài)?27c=1100212h=10009011044+90f110021210009011044+901+1002+12+90102相反的，如果不因為狀態(tài)的重復(fù)訪問而丟棄新節(jié)點(diǎn)，那么搜索算法將會找到最優(yōu)解，并停止如何處理可重復(fù)訪問狀態(tài)?28110021210009011044+901+1002+12但是... 如果不丟棄那些重復(fù)訪問狀態(tài)的節(jié)點(diǎn)，搜索樹可能會達(dá)到指數(shù)級的訪問狀態(tài)數(shù)量121112111+11+12+12+12+12是... 如果不丟棄那些重復(fù)訪問狀態(tài)的節(jié)點(diǎn)，搜索樹可能會如果新路徑耗散之前的路徑耗散，那么丟棄該重復(fù)訪問狀態(tài)的節(jié)點(diǎn)對A*不會產(chǎn)生負(fù)面影響

[因此，實際上如果一個節(jié)點(diǎn)的重復(fù)訪問狀態(tài)是已經(jīng)被其祖先節(jié)點(diǎn)訪問過的話，可以將其丟棄]A*仍然是最優(yōu)的，但狀態(tài)仍可能會被多次訪問

[搜索樹可能會變得龐大，達(dá)到訪問狀態(tài)的指數(shù)級]幸運(yùn)的是，對于許多可納函數(shù)，是所謂一致可納的，這使得算法在處理重復(fù)訪問狀態(tài)上變得非常高效30如果新路徑耗散之前的路徑耗散，那么丟棄該重復(fù)訪問狀態(tài)的一致啟發(fā)函數(shù)

ConsistentHeuristic 一個啟發(fā)函數(shù)h是一致

(或單調(diào))的，若

1)對于每個節(jié)點(diǎn)N及其每一個子節(jié)點(diǎn)N’: h(N)c(N,N’)+h(N’)

2)對于每個目標(biāo)節(jié)點(diǎn)G: h(G)=0(三角形不等式)NN’h(N)h(N’)c(N,N’)一致啟發(fā)函數(shù)也是可納的直覺:一致啟發(fā)函數(shù)將會隨著搜索樹的深入變得越來越精確31一致啟發(fā)函數(shù)

ConsistentHeuristic 一個一致啟發(fā)函數(shù)也是可納的

可納啟發(fā)函數(shù)不一定是一致的，但許多的可納啟發(fā)函數(shù)是一致的一致性和可納性

AdmissibilityandConsistency32一致啟發(fā)函數(shù)也是可納的

一致性和可納性

Admissibil8-Puzzle1234567812345678STATE(N)goal

h1(N)=不在位的數(shù)碼牌個數(shù)h2(N)=與目標(biāo)位置的Manhattan距離的和都是一致的嗎?(為什么呢？)338-Puzzle1234567812345678STATE( 若啟發(fā)函數(shù)h是一致的，則只要A*擴(kuò)展一個節(jié)點(diǎn)，那一定是找到了到達(dá)該節(jié)點(diǎn)狀態(tài)的最優(yōu)路徑結(jié)論#234 若啟發(fā)函數(shù)h是一致的，則只要A*擴(kuò)展一個節(jié)點(diǎn)，那一定是找到證明(1/2)考慮節(jié)點(diǎn)N及其子節(jié)點(diǎn)N’

由于h是一致的:h(N)c(N,N’)+h(N’)

f(N)=g(N)+h(N)g(N)+c(N,N’)+h(N’)=f(N’)

因此，其它任何一條路徑都不可能使f更低NN’35證明(1/2)考慮節(jié)點(diǎn)N及其子節(jié)點(diǎn)N’

由于h是一致的:一致啟發(fā)函數(shù)下的狀態(tài)重復(fù)訪問當(dāng)一個節(jié)點(diǎn)被擴(kuò)展時，保存其狀態(tài)到CLOSED表中當(dāng)一個新的節(jié)點(diǎn)N生成時:如果STATE(N)已在CLOSED中，則丟棄N如果在邊緣里存在節(jié)點(diǎn)N’有STATE(N’)=STATE(N)，則丟棄其中f最大的一個（N或N’）36一致啟發(fā)函數(shù)下的狀態(tài)重復(fù)訪問當(dāng)一個節(jié)點(diǎn)被擴(kuò)展時，保存其狀態(tài)到是否采用一致啟發(fā)函數(shù)的A*

就是我們追求的全部?No!

有許多一致函數(shù)是毫無作用的37是否采用一致啟發(fā)函數(shù)的A*

就是我們追求的全部?No!3例如:h0它是一致的(因此也是可納的)!采用h0的A*其實就是代價一致搜索uniform-costsearch廣度優(yōu)先和代價一致搜索其實就是A*的特例38例如:h0它是一致的(因此也是可納的)!38啟發(fā)函數(shù)的精確度

HeuristicAccuracy

h1

和h2

為兩個一致啟發(fā)函數(shù)，對于所有的節(jié)點(diǎn)N有:

h1(N)h2(N) h2

被稱為比h1更精確（或更有啟發(fā)知識）h1(N)=不在位的數(shù)碼牌個數(shù)h2(N)=與目標(biāo)位置的曼哈頓距離和h2

比h1更精確14752638STATE(N)64715283Goalstate39啟發(fā)函數(shù)的精確度

HeuristicAccuracy h1結(jié)論#3令h2

比h1更精確令A(yù)1*為采用h1的A*

A2*為采用h2的A*只要有解，A2*擴(kuò)展的所有節(jié)點(diǎn)（除了可能某些節(jié)點(diǎn)f1(N)=f2(N)=C*(最優(yōu)解耗散)，都會被A1*所擴(kuò)展，即A2*不會比A1*擴(kuò)展更多的節(jié)點(diǎn)40結(jié)論#3令h2比h1更精確40證明C*=h*(initial-node)[最優(yōu)解的耗散]所有f(N)C*的節(jié)點(diǎn)N最終都會被擴(kuò)展；f(N)>

C*的節(jié)點(diǎn)N沒有一個會被擴(kuò)展所有h(N)C*g(N)的節(jié)點(diǎn)N最終都會被擴(kuò)展。因此，所有h2(N)C*g(N)的節(jié)點(diǎn)N都會被A2*擴(kuò)展，由于h1(N)h2(N)，所以節(jié)點(diǎn)N也一定會被A1*擴(kuò)展如果有多個節(jié)點(diǎn)N有f1(N)=f2(N)=C*(若問題有解則這些節(jié)點(diǎn)包含了最優(yōu)目標(biāo)節(jié)點(diǎn))，A1*andA2*可能按相同的次序擴(kuò)展這些節(jié)點(diǎn)（直到有一個目標(biāo)節(jié)點(diǎn)被擴(kuò)展），也可能按照不相同的次序擴(kuò)展41證明C*=h*(initial-node)[最優(yōu)解的耗有效分支因子

EffectiveBranchingFactor用來刻畫啟發(fā)函數(shù)的效能針對某具體問題，令N為A*擴(kuò)展的總節(jié)點(diǎn)數(shù)，d為解的深度有效分支因子b*由下式定義 n=1

+

b*

+

(b*)2

+...+

(b*)d

42有效分支因子

EffectiveBranchingFac實驗結(jié)果

(seeR&Nfordetails)8-puzzle:h1=不在位數(shù)碼牌個數(shù)h2=所有數(shù)碼牌與其目標(biāo)位置的曼哈頓距離和隨機(jī)產(chǎn)生許多問題實例有效分支因子的平均值

(及擴(kuò)展節(jié)點(diǎn)數(shù)):dIDSA1*A2*22.451.791.7962.731.341.30122.78(3,644,035)1.42(227)1.24(73)16--1.451.2520--1.471.2724--1.48(39,135)1.26(1,641)43實驗結(jié)果

(seeR&Nfordetails)8-pu通過對每一個節(jié)點(diǎn)求解松弛問題8數(shù)碼問題中，每個數(shù)碼牌與其目標(biāo)位置的曼哈頓距離和其實相當(dāng)于解決8個簡單的問題:即忽略了其他數(shù)碼牌的負(fù)面相互影響怎樣構(gòu)造一個好的啟發(fā)函數(shù)?147526386471528355di

是將數(shù)碼牌i移動到其目標(biāo)位置的最短路徑，移動的過程忽略了其他數(shù)碼牌的存在,e.g.,d5=2h2=Si=1,...8di44通過對每一個節(jié)點(diǎn)求解松弛問題怎樣構(gòu)造一個好的啟發(fā)函數(shù)?147考慮如下兩個稍復(fù)雜的松弛問題:能做得更好嗎?147526386471528332144123d1234=將數(shù)碼牌1,2,3,和4移動到對應(yīng)的目標(biāo)位置的最短路徑的長度，（在不考慮其它的數(shù)碼牌的情況下）67587568d5678

h=d1234+d5678

[兩個子問題]如何計算d1234

和d5678?45考慮如下兩個稍復(fù)雜的松弛問題:能做得更好嗎?14752638考慮如下兩個稍復(fù)雜的松弛問題:能做得更好嗎?147526386471528332144123d1234=將數(shù)碼牌1,2,3,和4移動到對應(yīng)的目標(biāo)位置的最短路徑的長度，（在不考慮其它的數(shù)碼牌的情況下）67587568d5678

h=d1234+d5678

[兩個子問題]這些距離被預(yù)先計算出來并保存在模式數(shù)據(jù)庫中

[每個子問題將生成一個有著3024個節(jié)點(diǎn)/狀態(tài)的圖]這樣的方法使15-and24-puzzle問題的解決速度加快了幾個數(shù)量級(seeR&Np87)46考慮如下兩個稍復(fù)雜的松弛問題:能做得更好嗎?14752638完備性和最優(yōu)性采用一致啟發(fā)函數(shù)的A*有著很好的特性:完備，最優(yōu)，無需重復(fù)訪問狀態(tài)理論上的完備性不意味著“實際”的完備，比如需要很長的時間才能得到一個解（如前所述時間因此，如果不能設(shè)計出精確的一致啟發(fā)函數(shù)，不如設(shè)法找一個非可納的啟發(fā)函數(shù)，即使無法保證其完備性和最優(yōu)性，卻能在實際應(yīng)用中做得不錯，這樣的思路反而更好47完備性和最優(yōu)性采用一致啟發(fā)函數(shù)的A*有著很好的特性:完備迭代深入的A*搜索

IterativeDeepeningA*(IDA*)思想:通過對f的值設(shè)置一個截至范圍，以減少所需的內(nèi)存一致啟發(fā)函數(shù)hIDA*算法:將截至值設(shè)定為f(initial-node)重復(fù):執(zhí)行深度優(yōu)先搜索，擴(kuò)展所有f(N)cutoff的節(jié)點(diǎn)重新設(shè)定截至值cutoff＝未擴(kuò)展節(jié)點(diǎn)（葉節(jié)點(diǎn)）中的最小f值48迭代深入的A*搜索

IterativeDeepening8-Puzzle46f(N)=g(N)+h(N)withh(N)=numberofmisplacedtilesCutoff=4498-Puzzle46f(N)=g(N)+h(N)C8-Puzzle446Cutoff=46f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles508-Puzzle446Cutoff=46f(N)=g(N8-Puzzle446Cutoff=465f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles518-Puzzle446Cutoff=465f(N)=g(8-Puzzle446Cutoff=4655f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles528-Puzzle446Cutoff=4655f(N)=g48-Puzzle46Cutoff=46556f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles5348-Puzzle46Cutoff=46556f(N)=8-Puzzle46Cutoff=5f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles548-Puzzle46Cutoff=5f(N)=g(N)8-Puzzle446Cutoff=56f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles558-Puzzle446Cutoff=56f(N)=g(N8-Puzzle446Cutoff=565f(N)=g(N)+h(N)withh(N)=numberofmisplacedtiles56