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

啟發(fā)式圖搜索過(guò)程利用知識(shí)來(lái)引導(dǎo)搜索，到達(dá)減少搜索范圍，降低問(wèn)題復(fù)雜度的目的啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解希望引入啟發(fā)知識(shí)，在保證找到最正確解的情況下，盡可能減少搜索范圍，提高搜索效率編輯ppt啟發(fā)能力的強(qiáng)弱比較不同搜索方法的效果可用啟發(fā)能力的強(qiáng)弱來(lái)度量在大多數(shù)實(shí)際問(wèn)題中，人們感興趣的是使路徑的耗散值和求得路徑所需搜索的耗散值兩者的某種組合最小更一般的情況是考慮搜索方法對(duì)求解所有可能遇見(jiàn)的問(wèn)題，其平均的組合耗散值最小搜索空間〔代價(jià)〕小如果搜索方法1的平均組合耗散值比方法2的平均組合耗散值低，那么認(rèn)為方法1比方法2有更強(qiáng)的啟發(fā)能力編輯ppt根本思想優(yōu)先擴(kuò)展有希望的結(jié)點(diǎn)要對(duì)OPEN表進(jìn)行排序這就需要有一種方法來(lái)計(jì)算待擴(kuò)展結(jié)點(diǎn)有希望通向目標(biāo)結(jié)點(diǎn)的不同程度一種最常用的方法是定義一個(gè)評(píng)價(jià)函數(shù)f〔Evaluationfunction〕對(duì)各個(gè)子結(jié)點(diǎn)進(jìn)行計(jì)算，其目的就是用來(lái)估算出“有希望〞的結(jié)點(diǎn)來(lái)通?？梢詤⒖嫉脑敲从校阂粋€(gè)結(jié)點(diǎn)處在最正確路徑上的概率求出任意一個(gè)結(jié)點(diǎn)與目標(biāo)結(jié)點(diǎn)集之間的距離度量或差異度量根據(jù)格局〔博弈問(wèn)題〕或狀態(tài)的特點(diǎn)來(lái)打分編輯ppt啟發(fā)式搜索算法A簡(jiǎn)稱(chēng)為A算法是一種典型的啟發(fā)式搜索算法其根本思想是定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的結(jié)點(diǎn)來(lái)擴(kuò)展評(píng)價(jià)函數(shù)的形式如下：f(n)＝g(n)＋h(n)n是被評(píng)價(jià)的結(jié)點(diǎn)編輯pptg*(n)表示從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的最短路徑的耗散值h*(n)表示從結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值f*(n)=g*(n)+h*(n)表示從初始結(jié)點(diǎn)s經(jīng)過(guò)結(jié)點(diǎn)n到目標(biāo)結(jié)點(diǎn)g的最短路徑的耗散值而f(n)、g(n)和h(n)那么分別表示是對(duì)f*(n)、g*(n)和h*(n)三個(gè)函數(shù)值的的估計(jì)值編輯ppt①OPEN:＝〔s〕，f〔s〕:＝g〔s〕+h〔s〕;②LOOP：IFOPEN＝〔〕THENEXIT〔FAIL〕；③n:＝FIRST〔OPEN〕；④IFGOAL〔n〕THENEXIT〔SUCCESS〕；⑤REMOVE〔n，OPEN〕，ADD〔n，CLOSED〕；

編輯ppt⑥EXPAND〔n〕→{mi}，計(jì)算f〔n，mi〕＝g〔n，mi〕+h〔mi〕；g〔n，mi〕是從s通過(guò)n到mi的耗散值，f〔n，mi〕是從s通過(guò)n、mi到目標(biāo)結(jié)點(diǎn)耗散值的估計(jì)?！DD〔mj，OPEN〕，標(biāo)記mi到n的指針?！Ff〔n，mk〕<f〔mk〕THENf〔mk〕:＝f〔n，mk〕，標(biāo)記mk到n的指針；比較f〔n，mk〕和f〔mk〕，f〔mk〕是擴(kuò)展n之前計(jì)算的耗散值。·IFf〔n，m1〕<f〔m1〕THENf〔m1〕:＝f〔n，m1〕，標(biāo)記m1到n的指針，ADD〔m1，OPEN〕；當(dāng)f〔n，m1〕<f〔m1〕時(shí)，把m1重放回OPEN中，不必考慮修改到其子結(jié)點(diǎn)的指針。⑦OPEN中的結(jié)點(diǎn)按f值從小到大排序；⑧GOLOOP；編輯pptA算法說(shuō)明由一般的圖搜索算法改變而成在算法的第7步，按照f(shuō)值從小到大對(duì)OPEN表中的結(jié)點(diǎn)進(jìn)行排序，表達(dá)了A算法的含義計(jì)算f(n)、g(n)和h(n)g(n)根據(jù)已經(jīng)搜索的結(jié)果，按照從初始結(jié)點(diǎn)s到結(jié)點(diǎn)n的路徑，計(jì)算這條路徑的耗散值就可以了h(n)與問(wèn)題有關(guān)的，需要根據(jù)具體的問(wèn)題來(lái)定義h(n)通常稱(chēng)為啟發(fā)函數(shù)A算法的結(jié)束條件從OPEN中取出第一結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，那么算法成功結(jié)束只要目標(biāo)結(jié)點(diǎn)一出現(xiàn)就立即結(jié)束編輯ppt擴(kuò)展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)題在3×3九宮格棋盤(pán)上，擺有8個(gè)將牌，分別刻有數(shù)字1-8，棋盤(pán)中留有一個(gè)空格，允許其周?chē)膶⑴葡蚩崭褚苿?dòng)。給定一種初始布局和目標(biāo)布局，找出一個(gè)合法的走步序列。編輯ppt八數(shù)碼問(wèn)題設(shè)評(píng)價(jià)函數(shù)f(n)形式如下：

f(n)=d(n)+W(n)

其中d(n)代表結(jié)點(diǎn)的深度，取g(n)=d(n)表示討論單位耗散的情況；取h(n)=W(n)表示"不在位"的將牌個(gè)數(shù)作為啟發(fā)函數(shù)的度量，這時(shí)f(n)可估計(jì)出通向目標(biāo)結(jié)點(diǎn)的希望程度。比較上面兩個(gè)圖，發(fā)現(xiàn)1、2、6和8四個(gè)將牌不在目標(biāo)狀態(tài)的位置上，所以初始狀態(tài)的"不在位的將牌數(shù)"就是4，也就是初始狀態(tài)的h值。編輯ppt八數(shù)碼問(wèn)題括弧中的數(shù)字是該結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值f。圓圈中的值，表示結(jié)點(diǎn)的擴(kuò)展順序。在出現(xiàn)相同的f值時(shí)，可以任意選擇其中的一個(gè)結(jié)點(diǎn)首先擴(kuò)展。編輯ppt八數(shù)碼問(wèn)題

搜索過(guò)程的OPEN表和CLOSED表編輯ppt爬山法過(guò)程Hill-climbing

①n:=s；s為初始結(jié)點(diǎn)

②LOOP：IFGOAL〔n〕THENEXIT(SUCCESS)；

③EXPAND〔n〕→{mi}，計(jì)算h(mi)，nextn:=m(minh(mi)的結(jié)點(diǎn))；

④IFh(n)<h(nextn)THENEXIT(FAIL);

⑤n:=nextn；

⑥GOLOOP；編輯ppt爬山法〔續(xù)〕H(n)表示目標(biāo)與當(dāng)前結(jié)點(diǎn)之間的距離?；蚍Q(chēng)為山頂與當(dāng)前位置n之間的高度差。用不言退，總是登向山頂。問(wèn)題：多峰山肩編輯ppt分支界限法分支界限法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的端結(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)為f(n)=g(n)。該算法的根本思想很簡(jiǎn)單，實(shí)際上是建立一個(gè)局部路徑〔或分支〕的隊(duì)列表，每次都選耗散值最小的那個(gè)分支上的端結(jié)點(diǎn)來(lái)擴(kuò)展，直到生成出含有目標(biāo)結(jié)點(diǎn)的路徑為止。編輯ppt分支界限法過(guò)程Branch-Bound

①Q(mào)UEUE:=(s-s)，g(s)=0;

②LOOP：IFQUEUE=()THENEXIT(FAIL);

③PATH:=FIRST(QUEUE)，n:=LAST(PATH);

④IFGOAL(n)THENEXIT(SUCCESS);

⑤EXPAND(n)→{mi}，計(jì)算g(mi)=g(n，mi)，REMOVE〔s-n，QUEUE〕，ADD(s-mi，QUEUE);

⑥QUEUE中局部路徑g值最小者排在前面；

⑦GOLOOP；編輯ppt分支界限法〔最短路徑問(wèn)題〕八城市地圖示意圖分支界限搜索樹(shù)g=7編輯ppt動(dòng)態(tài)規(guī)劃法在A算法中，當(dāng)h(n)≡0時(shí)由于在A算法中，很多問(wèn)題的啟發(fā)函數(shù)h難于定義，因此動(dòng)態(tài)規(guī)劃算法是至今一直被經(jīng)常使用的算法動(dòng)態(tài)規(guī)劃法實(shí)際上是對(duì)分支界限法的改進(jìn)分支界限隊(duì)列中有冗余求s→t的最正確路徑時(shí)，對(duì)某一個(gè)中間結(jié)點(diǎn)I，只要考慮s到I中最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的，不必加以考慮編輯ppt動(dòng)態(tài)規(guī)劃法QUEUE:=(s-s),g(s)=0LOOP：IFQUEUE=()THENEXIT(FAIL)PATH:=FIRST(QUEUE)，n:=LAST(PATH)IFGOAL(n)THENEXIT(SUCCESS)EXPAND(n)→{mi},計(jì)算g(mi)=g(n,mi),REMOVE(s-n,QUEUE),ADD(s-mi,QUEUE);假設(shè)QUEUE中有多條到達(dá)某一公共結(jié)點(diǎn)的路徑，那么只保存耗散值最小的那條路徑，其余刪去，并重新排序，g值最小者排在前面GOLOOP編輯ppt動(dòng)態(tài)規(guī)劃法編輯pptA*算法當(dāng)在算法A的評(píng)價(jià)函數(shù)中，使用的啟發(fā)函數(shù)h(n)是處在h﹡〔n〕的下界范圍，即滿(mǎn)足h(n)≤h*(n)時(shí)，稱(chēng)為算法A﹡。對(duì)任意一個(gè)圖，當(dāng)s到目標(biāo)結(jié)點(diǎn)有一條路徑存在時(shí)，如果搜索算法總是在找到一條從s到目標(biāo)結(jié)點(diǎn)的最正確路徑上結(jié)束，那么稱(chēng)該搜索算法是可采納的。A﹡就具有可采納性〔admissibility〕。編輯pptA*算法的性質(zhì)A*算法的假設(shè)設(shè)ni、nj是任意兩個(gè)結(jié)點(diǎn)，有：C(ni,nj)>ε，其中ε為大于0的常數(shù)幾個(gè)等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始結(jié)點(diǎn)，t是目標(biāo)結(jié)點(diǎn)，n是s到t的最正確路徑上的結(jié)點(diǎn)編輯pptA*算法的性質(zhì)〔續(xù)〕定理1.1： 對(duì)有限圖，如果從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t有路徑存在，那么算法A一定成功結(jié)束。A*是A的特例對(duì)有限圖，如果有解，A*一定能在找到到達(dá)目標(biāo)的路徑結(jié)束無(wú)限圖呢？編輯pptA*算法的性質(zhì)〔續(xù)〕引理1.1： 對(duì)無(wú)限圖，假設(shè)有從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t的路徑，那么A*不能結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。編輯pptA*算法的性質(zhì)〔續(xù)〕引理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ù)〕定理1.2： 對(duì)無(wú)限圖，假設(shè)從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t有路徑存在，那么A*一定成功結(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ù)〕推論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，均被擴(kuò)展編輯pptA*算法的性質(zhì)〔續(xù)〕定理1.3(可采納性定理)： 假設(shè)存在從初始結(jié)點(diǎn)s到目標(biāo)結(jié)點(diǎn)t有路徑，那么A*必能找到最正確解結(jié)束。編輯pptA*可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束設(shè)找到的路徑s→t不是最正確的〔t為目標(biāo)〕那么： f(t)=g(t)>f*(s)由引理1.2知結(jié)束前OPEN中存在f(n)≤f*(s)的結(jié)點(diǎn)n，所以 f(n)≤f*(s)<f(t)因此A*應(yīng)選擇n擴(kuò)展，而不是t。與假設(shè)A*選擇t結(jié)束矛盾。得證。注意：A*的結(jié)束條件編輯pptA*算法的性質(zhì)〔續(xù)〕推論1.2： A*選作擴(kuò)展的任一結(jié)點(diǎn)n，有f(n)≤f*(s)由引理1.2知在A*結(jié)束前，OPEN中存在結(jié)點(diǎn)n’，f(n’)≤f*(s)設(shè)此時(shí)A*選擇n擴(kuò)展。如果n＝n’，那么f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。編輯ppt啟發(fā)函數(shù)與A*算法的關(guān)系應(yīng)用A*的過(guò)程中，如果選作擴(kuò)展的結(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)值f(n)=f*(n)，那么不會(huì)去擴(kuò)展多余的結(jié)點(diǎn)就可找到解可以想象到f(n)越接近于f*(n)，擴(kuò)展的結(jié)點(diǎn)數(shù)就會(huì)越少，即啟發(fā)函數(shù)中，應(yīng)用的啟發(fā)信息〔問(wèn)題知識(shí)〕愈多，擴(kuò)展的結(jié)點(diǎn)數(shù)就越少編輯pptA*算法的性質(zhì)〔續(xù)〕定理1.4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)A*算法A1和A2，假設(shè)A2比A1有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)結(jié)點(diǎn)有h2(n)>h1(n)，那么在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)結(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的結(jié)點(diǎn)數(shù)至少和A2一樣多。簡(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的證明使用數(shù)學(xué)歸納法，對(duì)結(jié)點(diǎn)的深度進(jìn)行歸納〔1〕當(dāng)d(n)＝0時(shí)，即只有一個(gè)結(jié)點(diǎn)，顯然定理成立?！?〕設(shè)d(n)≤k時(shí)定理成立?！矚w納假設(shè)〕〔3〕當(dāng)d(n)=k+1時(shí)，用反證法。 設(shè)存在一個(gè)深度為k＋1的結(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*(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ò)展，有g(shù)1(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ō)明針對(duì)同一個(gè)問(wèn)題都是A*的h2(n)>h1(n)對(duì)任何非目標(biāo)結(jié)點(diǎn)成立同一結(jié)點(diǎn)擴(kuò)展屢次，只算一個(gè)該定理的意義在于，在使用A*算法求解問(wèn)題時(shí)，定義的啟發(fā)函數(shù)h，在滿(mǎn)足A*的條件下，應(yīng)盡可能地大一些，使其接近于h*，這樣才能使得搜索的效率高編輯ppt使用h(n)縮小搜索空間的例子編輯pptA*算法的改進(jì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ò)展的話(huà)，搜索效率同樣是很低的如果不使用啟發(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重復(fù)擴(kuò)展的例子為什么會(huì)出現(xiàn)這種現(xiàn)象？編輯ppt單調(diào)性條件一個(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)＝0那么稱(chēng)該h函數(shù)滿(mǎn)足單調(diào)限制條件其意義是從ni到目標(biāo)結(jié)點(diǎn)，最正確路徑耗散值估計(jì)h(ni)不大于nj到目標(biāo)結(jié)點(diǎn)最正確路徑耗散值估計(jì)h(nj)與ni到nj孤線(xiàn)耗散值兩者之和h(ni)ninjh(nj)c(ni,nj)t編輯ppth單調(diào)的例子8數(shù)碼問(wèn)題：h為“不在位〞的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼結(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿(mǎn)足單調(diào)的條件 編輯ppth單調(diào)時(shí)的A*定理1.5： 假設(shè)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的證明設(shè)n是A*擴(kuò)展的任一結(jié)點(diǎn)。當(dāng)n＝s時(shí)，定理顯然成立。下面考察n≠s的情況。設(shè)P＝(n0=s,n1,n2,…,nk=n)是s到n的最正確路徑P中一定有結(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的結(jié)點(diǎn)為nj，那么nj+1在OPEN中。編輯ppt定理1.5的證明〔續(xù)〕由單調(diào)限制條件，對(duì)P中任意結(jié)點(diǎn)ni有： h(ni)≤C(ni,ni+1)+h(ni+1) g*(ni)+h(ni)≤g*(ni)+C(ni,ni+1)+h(ni+1)由于ni、ni+1在最正確路徑上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)代入上式有：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)從i=j到i=k-1應(yīng)用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)注意：(nj在CLOSED中，nj+1在OPEN中)編輯ppt定理1.5的證明〔續(xù)〕重寫(xiě)上式：f(nj+1)≤g*(n)+h(n)另一方面，A*選n擴(kuò)展，必有：f(n)=g(n)+h(n)≤f(nj+1)比較兩式，有：g(n)≤g*(n)但g*(n)是最正確路徑的耗散值，所以只有：g(n)=g*(n)。得證。編輯ppth單調(diào)時(shí)的A*〔續(xù)〕定理1.6： 假設(shè)h(n)是單調(diào)的，那么由A*所擴(kuò)展的結(jié)點(diǎn)序列其f值是非遞減的 即f(ni)≤f(nj)編輯ppt定理1.6的證明由單調(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)的好處定理1.5和1.6的意義如果h滿(mǎn)足單調(diào)限制條件，應(yīng)用算法A*時(shí)，第6步可不必進(jìn)行結(jié)點(diǎn)的指針修正工作，因而改善了A*的效率因h不滿(mǎn)足單調(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)定義一個(gè)單調(diào)的h并不是一件很容易的事那么能否通過(guò)修改算法，來(lái)到達(dá)防止或者減少重復(fù)結(jié)點(diǎn)擴(kuò)展的問(wèn)題呢在改進(jìn)A*算法的時(shí)候一是要保持A*算法的可采納性二是不能增加過(guò)多的計(jì)算工作量由推論1.1我們知道，OPEN表上任一具有f(n)<f*(s)的結(jié)點(diǎn)n定會(huì)被擴(kuò)展。由推論1.2我們知道，A*選作擴(kuò)展的任一結(jié)點(diǎn)，定有f(n)≤f*(s)。這兩個(gè)推論正是我們改進(jìn)A*算法的理論根底編輯ppt改進(jì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:IFOPEN=()THENEXIT(FAIL);③ NEST:={ni|f(ni)<fm} IFNEST≠()THEN n:=NEST中g(shù)最小的結(jié)點(diǎn) ELSE n:=FIRST(OPEN),fm:=f(n);④……⑧ 同過(guò)程A。編輯ppth=14修正的A*算法的例子OPENfmCLOSED初始化：(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)用舉例8數(shù)碼問(wèn)題兩個(gè)hW(n)P(n)編輯pptA*算法應(yīng)用舉例傳教士和野人問(wèn)題〔M-C問(wèn)題〕編輯pptA*算法應(yīng)用舉例迷宮問(wèn)題h可定義為兩點(diǎn)間的Manhattan距離〔city-block距離〕h(n)=|XG–xn|+|YG–yn|編輯ppt評(píng)價(jià)函數(shù)的啟發(fā)能力一般來(lái)說(shuō)啟發(fā)能力強(qiáng)，那么搜索效率較高。有時(shí)選用不是h*(n)下界范圍的h(n)時(shí)，雖然會(huì)犧牲找到最正確解的性能，但可使啟發(fā)能力得到改善，從而有利于求解一些較難的問(wèn)題例子見(jiàn)教材P46