第一章 搜索問(wèn)題1

1、編輯ppt啟發(fā)式圖搜索過(guò)程啟發(fā)式圖搜索過(guò)程n利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的n啟發(fā)信息的強(qiáng)度n強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解n弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解n希望n引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率編輯ppt啟發(fā)能力的強(qiáng)弱n比較不同搜索方法的效果可用啟發(fā)能力的強(qiáng)弱來(lái)度量n在大多數(shù)實(shí)際問(wèn)題中，人們感興趣的是n使路徑的耗散值和求得路徑所需搜索的耗散值兩者的某種組合最小n更一般的情況是考慮搜索方法對(duì)求解所有可能遇見(jiàn)的問(wèn)題，其平均的組合耗散值最小n搜索空間（代價(jià)）小n如果搜索方法1的平均

2、組合耗散值比方法2的平均組合耗散值低，則認(rèn)為方法1比方法2有更強(qiáng)的啟發(fā)能力編輯ppt基本思想n優(yōu)先擴(kuò)展有希望的結(jié)點(diǎn)n要對(duì)OPEN表進(jìn)行排序n這就需要有一種方法來(lái)計(jì)算待擴(kuò)展結(jié)點(diǎn)有希望通向目標(biāo)結(jié)點(diǎn)的不同程度n一種最常用的方法是定義一個(gè)評(píng)價(jià)函數(shù)f（Evaluation function）對(duì)各個(gè)子結(jié)點(diǎn)進(jìn)行計(jì)算，其目的就是用來(lái)估算出“有希望”的結(jié)點(diǎn)來(lái)n通常可以參考的原則有：n一個(gè)結(jié)點(diǎn)處在最佳路徑上的概率n求出任意一個(gè)結(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)集之間的距離度量或差異度量n根據(jù)格局（博弈問(wèn)題）或狀態(tài)的特點(diǎn)來(lái)打分編輯ppt啟發(fā)式搜索算法啟發(fā)式搜索算法An簡(jiǎn)稱為A算法n是一種典型的啟發(fā)式搜索算法n其基本思想是n定義一個(gè)評(píng)價(jià)

3、函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的結(jié)點(diǎn)來(lái)擴(kuò)展n評(píng)價(jià)函數(shù)的形式如下：nf(n)g(n)h(n)nn是被評(píng)價(jià)的結(jié)點(diǎn)編輯pptng*(n)n表示從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的最短路徑的耗散值nh*(n)n表示從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值nf*(n)=g*(n)+h*(n)n表示從初始結(jié)點(diǎn)s經(jīng)過(guò)結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值n而f(n)、g(n)和h(n)則分別表示是對(duì)f*(n)、g*(n)和h*(n)三個(gè)函數(shù)值的的估計(jì)值nOPEN:（s），），f（s）:g（s）+h（s）;nLOOP：IF OPEN（ ）THEN EXIT（FAIL）；）；nn:FIRST（OPEN）；）；

4、nIF GOAL（n）THEN EXIT（SUCCESS）；）；nREMOVE（n，OPEN），），ADD（n，CLOSED）；）；nEXPAND（n）mi，計(jì)算，計(jì)算f（n，mi）g（n，mi）+h（mi）；）；g（n，mi）是從）是從s通過(guò)通過(guò)n到到mi的耗散值，的耗散值，f（n，mi）是從）是從s通過(guò)通過(guò)n、mi到到目標(biāo)結(jié)點(diǎn)耗散值的估計(jì)。目標(biāo)結(jié)點(diǎn)耗散值的估計(jì)。nADD（mj，OPEN），標(biāo)記），標(biāo)記mi到到n的指針。的指針。nIF f（n，mk）f（mk）THEN f（mk）:f（n，mk），標(biāo)記），標(biāo)記mk到到n的指針；比較的指針；比較f（n，mk）和）和f（mk），），f（mk）是擴(kuò)

5、展）是擴(kuò)展n之前計(jì)算的耗散值。之前計(jì)算的耗散值。nIF f（n，m1）f（m1）THEN f（m1）:f（n，m1），標(biāo)記），標(biāo)記m1到到n的指針，的指針，ADD（m1，OPEN）；）；當(dāng)當(dāng)f（n，m1）f（m1）時(shí)，把）時(shí)，把m1重放回重放回OPEN中，中，不必考慮修改到其子結(jié)點(diǎn)的指針。不必考慮修改到其子結(jié)點(diǎn)的指針。nOPEN中的結(jié)點(diǎn)按中的結(jié)點(diǎn)按f值從小到大排序；值從小到大排序；nGO LOOP；編輯pptA算法說(shuō)明n由一般的圖搜索算法改變而成n在算法的第7步，按照f(shuō)值從小到大對(duì)OPEN表中的結(jié)點(diǎn)進(jìn)行排序，體現(xiàn)了A算法的含義n計(jì)算f(n)、g(n)和h(n)ng(n)根據(jù)已經(jīng)搜索的結(jié)果，按照

6、從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的路徑，計(jì)算這條路徑的耗散值就可以了nh(n)與問(wèn)題有關(guān)的，需要根據(jù)具體的問(wèn)題來(lái)定義nh(n)通常稱為啟發(fā)函數(shù)nA算法的結(jié)束條件n從OPEN中取出第一結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則算法成功結(jié)束n只要目標(biāo)結(jié)點(diǎn)一出現(xiàn)就立即結(jié)束擴(kuò)展擴(kuò)展n后新生成的子結(jié)點(diǎn)后新生成的子結(jié)點(diǎn)m1（mj）、）、m2（mk）、）、m3（ml）f(m1)=g(m1)+h(m1)f(n，m2)=g(n，m2)+h(m2)f(n，m3)=g(n，m3)+h(m3)編輯pptA算法舉例算法舉例八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題n在在3 33 3九宮格棋盤(pán)上，擺有九宮格棋盤(pán)上，擺有8 8個(gè)將牌，個(gè)將牌，分別刻有數(shù)字分別刻有數(shù)字

7、1-81-8，棋盤(pán)中留有一個(gè)，棋盤(pán)中留有一個(gè)空格，允許其周?chē)膶⑴葡蚩崭褚苿?dòng)?？崭瘢试S其周?chē)膶⑴葡蚩崭褚苿?dòng)。給定一種初始布局和目標(biāo)布局，找出給定一種初始布局和目標(biāo)布局，找出一個(gè)合法的走步序列。一個(gè)合法的走步序列。編輯ppt八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題n設(shè)評(píng)價(jià)函數(shù)設(shè)評(píng)價(jià)函數(shù)f(n)形式如下：形式如下：f(n)=d(n)+W(n)其中其中d(n)代表結(jié)點(diǎn)的深度，取代表結(jié)點(diǎn)的深度，取g(n)=d(n)表示討表示討論單位耗散的情況；取論單位耗散的情況；取h(n)=W(n)表示表示不在位不在位的將牌個(gè)數(shù)作為啟發(fā)函數(shù)的度量，這時(shí)的將牌個(gè)數(shù)作為啟發(fā)函數(shù)的度量，這時(shí)f(n)可可估計(jì)出通向目標(biāo)結(jié)點(diǎn)的希望程度。估計(jì)出

8、通向目標(biāo)結(jié)點(diǎn)的希望程度。n比較上面兩個(gè)圖，發(fā)現(xiàn)比較上面兩個(gè)圖，發(fā)現(xiàn)1、2、6和和8四個(gè)將牌不四個(gè)將牌不在目標(biāo)狀態(tài)的位置上，所以初始狀態(tài)的在目標(biāo)狀態(tài)的位置上，所以初始狀態(tài)的不在不在位的將牌數(shù)位的將牌數(shù)就是就是4，也就是初始狀態(tài)的，也就是初始狀態(tài)的h值。值。編輯ppt八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題括弧中的數(shù)字是該結(jié)括弧中的數(shù)字是該結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值點(diǎn)的評(píng)價(jià)函數(shù)值f f。圓圈中的值，表示結(jié)圓圈中的值，表示結(jié)點(diǎn)的擴(kuò)展順序。點(diǎn)的擴(kuò)展順序。在出現(xiàn)相同的在出現(xiàn)相同的f f值時(shí)，值時(shí)，可以任意選擇其中的可以任意選擇其中的一個(gè)結(jié)點(diǎn)首先擴(kuò)展。一個(gè)結(jié)點(diǎn)首先擴(kuò)展。編輯ppt八數(shù)碼問(wèn)題八數(shù)碼問(wèn)題 搜索過(guò)程的搜索過(guò)程的OPENOPE

9、N表和表和CLOSEDCLOSED表表編輯ppt爬山法爬山法n過(guò)程過(guò)程Hill-climbingn:=s；s為初始結(jié)點(diǎn)為初始結(jié)點(diǎn)LOOP：IF GOAL（n）THEN EXIT (SUCCESS)；EXPAND（n）mi，計(jì)算，計(jì)算h(mi)，nextn:=m(min h(mi)的結(jié)點(diǎn)的結(jié)點(diǎn))；IF h(n)，其中為大于0的常數(shù)n幾個(gè)等式nf*(s) = f*(t) = h*(s) = g*(t) = f*(n)n其中s是初始結(jié)點(diǎn)，t是目標(biāo)結(jié)點(diǎn)，n是s到t的最佳路徑上的結(jié)點(diǎn)編輯pptA*算法的性質(zhì)（續(xù)）n定理1.1：對(duì)有限圖，如果從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。nA*

10、是A的特例n對(duì)有限圖，如果有解，A*一定能在找到到達(dá)目標(biāo)的路徑結(jié)束n無(wú)限圖呢？編輯pptA*算法的性質(zhì)（續(xù)）n引理1.1 ：對(duì)無(wú)限圖，若有從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t的路徑，則A*不能結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)f*(s)。編輯pptA*算法的性質(zhì)（續(xù)）n引理1.2：A*結(jié)束前，OPEN表中必存在f(n)f*(s)。存在一個(gè)結(jié)點(diǎn)n，n在最佳路徑上。f(n) = g(n) + h(n) = g*(n)+h(n) g*(n)+h*(n) = f*(n) = f*(s)編輯pptA*算法的性質(zhì)（續(xù)）n定理1.2：對(duì)無(wú)限圖，若從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t有路徑存在，則A

11、*一定成功結(jié)束。引理1.1：A*如果不結(jié)束，則OPEN中所有的n有f(n) f*(s)引理1.2：在A*結(jié)束前，必存在結(jié)點(diǎn)n，使得f(n) f*(s)所以，如果A*不結(jié)束，將導(dǎo)致矛盾。只說(shuō)明能結(jié)束，未必最優(yōu)編輯pptA*算法的性質(zhì)（續(xù)）n推論1.1：OPEN表上任一具有f(n)f*(s)的結(jié)點(diǎn)n，最終都將被A*選作擴(kuò)展的結(jié)點(diǎn)。由定理1.2，知A*一定結(jié)束由A*的結(jié)束條件，OPEN表中f(t)最小時(shí)才結(jié)束而f(t) f*(t) f*(s)所以f(n) f*(s)n由引理1.2知結(jié)束前OPEN中存在f(n)f*(s)的結(jié)點(diǎn)n，所以f(n) f*(s) h1(n)，則在具有一條從s到t的路徑的隱含圖

12、上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)結(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的結(jié)點(diǎn)數(shù)至少和A2一樣多。n簡(jiǎn)寫(xiě)：如果h2(n)h1(n) (目標(biāo)結(jié)點(diǎn)除外)，則A1擴(kuò)展的結(jié)點(diǎn)集合包含A2擴(kuò)展的結(jié)點(diǎn)集合編輯ppt定理1.4的證明n使用數(shù)學(xué)歸納法，對(duì)結(jié)點(diǎn)的深度進(jìn)行歸納n（1）當(dāng)d(n)0時(shí)，即只有一個(gè)結(jié)點(diǎn)，顯然定理成立。n（2）設(shè)d(n)k時(shí)定理成立。（歸納假設(shè)）n（3）當(dāng)d(n)=k+1時(shí)，用反證法。設(shè)存在一個(gè)深度為k1的結(jié)點(diǎn)n，被A2擴(kuò)展，但沒(méi)有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父結(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時(shí)，n將被保留在OPEN中。編輯ppt定理1.4的證明（續(xù)）所以有：f1(n)f*

13、(s) 即：g1(n)+h1(n)f*(s) 所以： h1(n)f*(s)-g1(n)由于A2擴(kuò)展了n，有f2(n)f*(s)即：h2(n)f*(s)g2(n)由于d(n)=k時(shí)，A2擴(kuò)展的結(jié)點(diǎn)A1一定擴(kuò)展，有 g1(n)g2(n) (因?yàn)锳2的路A1均走到了)所以：h1(n)f*(s)-g1(n)f*(s)g2(n)比較A、B兩式，有 h1(n)h2(n)，與定理?xiàng)l件矛盾。定理得證。編輯ppt定理1.4的說(shuō)明n針對(duì)同一個(gè)問(wèn)題n都是A*的nh2(n) h1(n)對(duì)任何非目標(biāo)結(jié)點(diǎn)成立n同一結(jié)點(diǎn)擴(kuò)展多次，只算一個(gè)n該定理的意義在于，在使用A*算法求解問(wèn)題時(shí)，定義的啟發(fā)函數(shù)h，在滿足A*的條件下，應(yīng)

14、盡可能地大一些，使其接近于h*，這樣才能使得搜索的效率高編輯ppt使用h(n)縮小搜索空間的例子編輯pptA*算法的改進(jìn)n在A算法的第六步，對(duì)于ml類(lèi)結(jié)點(diǎn)，存在重新放回到OPEN表的可能，因此一個(gè)結(jié)點(diǎn)有可能被反復(fù)擴(kuò)展多次。因此單純用擴(kuò)展的結(jié)點(diǎn)數(shù)并不能客觀地來(lái)評(píng)判搜索算法的好壞。因?yàn)榧幢闶菙U(kuò)展的結(jié)點(diǎn)數(shù)比較少，但如果很多結(jié)點(diǎn)被多次重復(fù)擴(kuò)展的話，搜索效率同樣是很低的n如果不使用啟發(fā)函數(shù)，則每個(gè)結(jié)點(diǎn)僅擴(kuò)展一次，雖然擴(kuò)展的結(jié)點(diǎn)數(shù)相同，但A*擴(kuò)展的次數(shù)多。如果對(duì)啟發(fā)函數(shù)施加一定的限制（后面說(shuō)的單調(diào)限制），則當(dāng)A*算法選某一個(gè)結(jié)點(diǎn)擴(kuò)展時(shí)，就已經(jīng)找到到該結(jié)點(diǎn)的最佳路徑（就不可能重復(fù)擴(kuò)展了）編輯ppth=14重

15、復(fù)擴(kuò)展的例子n為什么會(huì)出現(xiàn)這種現(xiàn)象？編輯ppt單調(diào)性條件n一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有結(jié)點(diǎn)ni和nj（nj是ni的子結(jié)點(diǎn)），都有h(ni)-h(nj)C(ni,nj)【或h(ni)C(ni,nj)h(nj)】且h(ti)0n則稱該h函數(shù)滿足單調(diào)限制條件n其意義是從ni到目標(biāo)結(jié)點(diǎn)，最佳路徑耗散值估計(jì)h(ni)不大于nj到目標(biāo)結(jié)點(diǎn)最佳路徑耗散值估計(jì)h(nj)與ni到nj孤線耗散值兩者之和h(ni)ninjh(nj)c(ni,nj)t編輯ppth單調(diào)的例子n8數(shù)碼問(wèn)題：nh為“不在位”的將牌數(shù) 1h(ni)-h(nj)= 0(nj為ni的后繼結(jié)點(diǎn)) -1 h(t) = 0c(ni, nj) = 1 滿

16、足單調(diào)的條件編輯ppth單調(diào)時(shí)的A*n定理1.5：若h(n)是單調(diào)的，則A*擴(kuò)展了結(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)結(jié)點(diǎn)n的最佳路徑。即：當(dāng)A*選n擴(kuò)展時(shí)，有g(shù)(n)=g*(n)。編輯ppt定理1.5的證明n設(shè)n是A*擴(kuò)展的任一結(jié)點(diǎn)。當(dāng)ns時(shí)，定理顯然成立。下面考察ns的情況。n設(shè)P(n0=s, n1, n2, , nk=n)是s到n的最佳路徑nP中一定有結(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的結(jié)點(diǎn)為nj，則nj+1在OPEN中。編輯ppt定理1.5的證明（續(xù)）n由單調(diào)限制條件，對(duì)P中任意結(jié)點(diǎn)ni有：h(ni)C(ni, ni+1)+h(ni+1)g*(ni)+h(ni)g*(ni

17、)+C(ni,ni+1)+h(ni+1)n由于ni 、ni+1在最佳路徑上，所以： g*(ni+1) = g*(ni)+C(ni, ni+1)n代入上式有： g*(ni)+h(ni) g*(ni+1)+h(ni+1)n從i=j到i=k-1應(yīng)用上不等式，有： g*(nj+1)+h(nj+1) g*(nk)+h(nk)n即：f(nj+1) g*(n)+h(n) 注意：(nj在CLOSED中，nj+1在OPEN中)編輯ppt定理1.5的證明（續(xù)）n重寫(xiě)上式：f(nj+1)g*(n)+h(n)n另一方面，A*選n擴(kuò)展，必有： f(n)=g(n)+h(n)f(nj+1) n比較兩式，有： g(n)g*(

18、n)n但已知g*(n)是最佳路徑的耗散值，所以只有：g(n)=g*(n)。n得證。編輯ppth單調(diào)時(shí)的A*（續(xù)）n定理1.6：若h(n)是單調(diào)的，則由A*所擴(kuò)展的結(jié)點(diǎn)序列其f值是非遞減的即 f(ni) f(nj)定理1.6的證明n由單調(diào)限制條件，有： h(ni) h(nj) C(ni,nj) =f(ni)-g(ni)=f(nj)-g(nj)f(ni)-g(ni) - f(nj)+g(nj) C(ni, nj)=g(ni)+C(ni,nj)f(ni)-g(ni)-f(nj)+g(ni)+C(ni,nj)C(ni,nj) f(ni) - f(nj) 0，得證。編輯ppth單調(diào)的好處n定理1.5和1

19、.6的意義n如果h滿足單調(diào)限制條件，應(yīng)用算法A*時(shí)，第6步可不必進(jìn)行結(jié)點(diǎn)的指針修正工作，因而改善了A*的效率n因h不滿足單調(diào)限制條件，在擴(kuò)展結(jié)點(diǎn)n時(shí)，有可能還沒(méi)有找到到達(dá)n的最佳路徑，因此該結(jié)點(diǎn)還會(huì)再次被放入OPEN中，從而造成了該結(jié)點(diǎn)被重復(fù)擴(kuò)展編輯ppt對(duì)算法加以改進(jìn)n定義一個(gè)單調(diào)的h并不是一件很容易的事n那么能否通過(guò)修改算法，來(lái)達(dá)到避免或者減少重復(fù)結(jié)點(diǎn)擴(kuò)展的問(wèn)題呢n在改進(jìn)A*算法的時(shí)候n一是要保持A*算法的可采納性n二是不能增加過(guò)多的計(jì)算工作量n由推論1.1我們知道，OPEN表上任一具有f(n) f*(s)的結(jié)點(diǎn)n定會(huì)被擴(kuò)展。由推論1.2我們知道，A*選作擴(kuò)展的任一結(jié)點(diǎn)，定有f(n)f*(

20、s)。這兩個(gè)推論正是我們改進(jìn)A*算法的理論基礎(chǔ)編輯ppt改進(jìn)算法的思路n必須擴(kuò)展的結(jié)點(diǎn)盡量不重復(fù)擴(kuò)展OPEN = ( )f*(s)f值小于f*(s)的結(jié)點(diǎn)f值大于等于f*(s)的結(jié)點(diǎn)fm：到目前為止已擴(kuò)展結(jié)點(diǎn)的最大f值，用fm代替f*(s)編輯ppt修正的A*算法OPEN:=(s), f(s)=g(s)+h(s), fm:=0;LOOP: IF OPEN=( ) THEN EXIT(FAIL);NEST:=ni|f(ni)fmIF NEST ( ) THENn:=NEST中g(shù)最小的結(jié)點(diǎn)ELSE n:=FIRST(OPEN), fm:=f(n);同過(guò)程A。編輯ppth=14修正的A*算法的例子O

21、PENfmCLOSED初始化：(s(0+20)1 (A(11+1) B(9+4) C(6+8) D(1+14)2 (A(7+1) B(5+4) C(2+8)3 (A(5+1) B(3+4)4 (A(4+1)5 (t(22+0)成功結(jié)束02020202020()(s(0+20)(s(0+20) D(1+14)(s(0+20) C(2+8) D(1+14)(s(0+20) B(3+4) C(2+8) D(1+14)(s(0+20) A(4+1) B(3+4) C(2+8) D(1+14)編輯pptA*算法應(yīng)用舉例n8數(shù)碼問(wèn)題n兩個(gè)hnW(n)nP(n)編輯pptA*算法應(yīng)用舉例n傳教士和野人問(wèn)題（

22、M-C問(wèn)題）編輯pptA*算法應(yīng)用舉例n迷宮問(wèn)題nh可定義為兩點(diǎn)間的Manhattan距離（city-block距離）nh(n)=| XG xn | + | YG yn |編輯ppt評(píng)價(jià)函數(shù)的啟發(fā)能力n一般來(lái)說(shuō)啟發(fā)能力強(qiáng)，則搜索效率較高。n有時(shí)選用不是h*(n)下界范圍的h(n)時(shí)，雖然會(huì)犧牲找到最佳解的性能，但可使啟發(fā)能力得到改善，從而有利于求解一些較難的問(wèn)題n例子n見(jiàn)教材P46編輯ppt評(píng)價(jià)函數(shù)的啟發(fā)能力n還有一個(gè)決定搜索算法啟發(fā)能力的因素是涉及到計(jì)算啟發(fā)函數(shù)的工作量n從被擴(kuò)展的結(jié)點(diǎn)數(shù)最少的角度看，hh*最優(yōu)，但這可能導(dǎo)致繁重的計(jì)算工作量n有時(shí)候一個(gè)不是h*下界范圍的h函數(shù)可能比起下界范圍的h函數(shù)更容易計(jì)算，而且被擴(kuò)展結(jié)點(diǎn)的總數(shù)可以減少，使啟發(fā)能力加倍得到改善，雖然犧牲了可采納性，但從啟發(fā)能力的角度看仍是可