第一章搜索問題內(nèi)容： 狀態(tài)空間搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問題： 怎樣利用知識，盡可能有效地找到問題解（最正確解）。1人工智能搜索問題第1頁搜索問題（續(xù)1）S0Sg2人工智能搜索問題第2頁搜索問題（續(xù)2）討論問題：有哪些慣用搜索算法。問題有解時能否找到解。找到解是最正確嗎？什么情況下能夠找到最正確解？求解效率怎樣。3人工智能搜索問題第3頁1.1回溯策略例：皇后問題4人工智能搜索問題第4頁()5人工智能搜索問題第5頁()Q((1,1))6人工智能搜索問題第6頁()QQ((1,1))((1,1)(2,3))7人工智能搜索問題第7頁()Q((1,1))((1,1)(2,3))8人工智能搜索問題第8頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9人工智能搜索問題第9頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10人工智能搜索問題第10頁()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11人工智能搜索問題第11頁()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12人工智能搜索問題第12頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13人工智能搜索問題第13頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14人工智能搜索問題第14頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))15人工智能搜索問題第15頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))16人工智能搜索問題第16頁()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))17人工智能搜索問題第17頁遞歸思想從前有座山……從前有座山……

從前有座山……18人工智能搜索問題第18頁遞歸思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19人工智能搜索問題第19頁一個遞歸例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12320人工智能搜索問題第20頁回溯搜索算法 BACKTRACK（DATA）

DATA：當(dāng)前狀態(tài)。 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。21人工智能搜索問題第21頁回溯搜索算法遞歸過程BACKTRACK(DATA)1, IFTERM(DATA)RETURNNIL;2, IFDEADEND(DATA)RETURNFAIL;3, RULES:=APPRULES(DATA);4, LOOP:IFNULL(RULES)RETURNFAIL;5, R:=FIRST(RULES);6, RULES:=TAIL(RULES);7, RDATA:=GEN(R,DATA);8, PATH:=BACKTRACK(RDATA);9, IFPATH=FAILGOLOOP;10, RETURNCONS(R,PATH);22人工智能搜索問題第22頁存在問題及處理方法處理方法：對搜索深度加以限制統(tǒng)計從初始狀態(tài)到當(dāng)前狀態(tài)路徑當(dāng)前狀態(tài)問題：深度問題死循環(huán)問題23人工智能搜索問題第23頁回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當(dāng)前狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)路徑 （以規(guī)則表形式表示） 或FAIL。24人工智能搜索問題第24頁回溯搜索算法11, DATA:=FIRST(DATALIST)2, IFMENBER(DATA,TAIL(DATALIST)) RETURNFAIL;

3, IFTERM(DATA)RETURNNIL;4, IFDEADEND(DATA)RETURNFAIL;5, IFLENGTH(DATALIST)>BOUND RETURNFAIL;6, RULES:=APPRULES(DATA);7,LOOP:IFNULL(RULES)RETURNFAIL;8, R:=FIRST(RULES);25人工智能搜索問題第25頁回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULES);10, RDATA:=GEN(R,DATA);11, RDATALIST:=CONS(RDATA,DATALIST);12, PATH:=BACKTRCK1(RDATALIST)13, IFPATH=FAILGOLOOP;14, RETURNCONS(R,PATH);26人工智能搜索問題第26頁一些深入問題失敗原因分析、多步回溯QQ27人工智能搜索問題第27頁一些深入問題（續(xù)）回溯搜索中知識利用 基本思想(以皇后問題為例)： 盡可能選取劃去對角線上位置數(shù)最少。QQQQ322328人工智能搜索問題第28頁1.2圖搜索策略問題引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)一條路徑。圖搜索：保留全部已經(jīng)搜索過路徑。

29人工智能搜索問題第29頁一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012330人工智能搜索問題第30頁一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點(diǎn)ni-1含有一個后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk路徑。路徑耗散值 一條路徑耗散值等于連接這條路徑各節(jié)點(diǎn)間全部耗散值總和。用C(ni,nj)表示從ni到nj路徑耗散值。31人工智能搜索問題第31頁一些基本概念（續(xù)1）擴(kuò)展一個節(jié)點(diǎn) 生成出該節(jié)點(diǎn)全部后繼節(jié)點(diǎn)，并給出它們之間耗散值。這一過程稱為“擴(kuò)展一個節(jié)點(diǎn)”。32人工智能搜索問題第32頁普通圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IFOPEN=()THENEXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)THENEXIT(SUCCESS);6,EXPAND(n)→{mi},G:=ADD(mi,G);33人工智能搜索問題第33頁普通圖搜索算法（續(xù)）7,標(biāo)識和修改指針： ADD(mj,OPEN),并標(biāo)識mj到n指針； 計算是否要修改mk、ml到n指針； 計算是否要修改ml到其后繼節(jié)點(diǎn)指針；8,對OPEN中節(jié)點(diǎn)按某種標(biāo)準(zhǔn)重新排序；9,GOLOOP；34人工智能搜索問題第34頁節(jié)點(diǎn)類型說明…...…...…...…...…...mjmkml35人工智能搜索問題第35頁修改指針舉例123456s36人工智能搜索問題第36頁修改指針舉例（續(xù)1）123456s37人工智能搜索問題第37頁123456修改指針舉例（續(xù)2）s38人工智能搜索問題第38頁123456修改指針舉例（續(xù)3）s39人工智能搜索問題第39頁1.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索40人工智能搜索問題第40頁深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)識mj到n指針;10,GOLOOP;41人工智能搜索問題第41頁231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)42人工智能搜索問題第42頁深度優(yōu)先搜索性質(zhì)普通不能確保找到最優(yōu)解當(dāng)深度限制不合理時，可能找不到解，能夠?qū)⑺惴ǜ臑榭勺兩疃认拗谱顗那闆r時，搜索空間等同于窮舉與回溯法差異：圖搜索是一個通用與問題無關(guān)方法43人工智能搜索問題第43頁寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標(biāo)識mj到n指針;9,GOLOOP;44人工智能搜索問題第44頁23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)823418765445人工智能搜索問題第45頁寬度優(yōu)先搜索性質(zhì)當(dāng)問題有解時，一定能找到解當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，含有通用性效率較低屬于圖搜索方法46人工智能搜索問題第46頁漸進(jìn)式深度優(yōu)先搜索方法目標(biāo)處理寬度優(yōu)先方法空間問題和回溯方法不能找到最優(yōu)解問題。思想 首先給回溯法一個比較小深度限制，然后逐步增加深度限制，直到找到解或找遍所以分支為止。47人工智能搜索問題第47頁1.4啟發(fā)式圖搜索利用知識來引導(dǎo)搜索，到達(dá)降低搜索范圍，降低問題復(fù)雜度目標(biāo)。啟發(fā)信息強(qiáng)度強(qiáng)：降低搜索工作量，但可能造成找不到最 優(yōu)解弱：普通造成工作量加大，極限情況下變?yōu)?盲目搜索，但可能能夠找到最優(yōu)解48人工智能搜索問題第48頁希望：引入啟發(fā)知識，在確保找到最正確解情況下，盡可能降低搜索范圍，提升搜索效率。49人工智能搜索問題第49頁基本思想定義一個評價函數(shù)f，對當(dāng)前搜索狀態(tài)進(jìn)行評定，找出一個最有希望節(jié)點(diǎn)來擴(kuò)展。50人工智能搜索問題第50頁1，啟發(fā)式搜索算法A（A算法）評價函數(shù)格式： f(n)=g(n)+h(n) f(n)：評價函數(shù) h(n)：啟發(fā)函數(shù)51人工智能搜索問題第51頁符號意義g*(n)：從s到n最短路徑耗散值h*(n)：從n到g最短路徑耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g最短路徑耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)預(yù)計值52人工智能搜索問題第52頁A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},

計算f(n,mi):=g(n,mi)+h(mi);

53人工智能搜索問題第53頁A算法（續(xù)） ADD(mj,OPEN),標(biāo)識mj到n指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標(biāo)識mk到n指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標(biāo)識ml到n指針, ADD(ml,OPEN);7,OPEN中節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；54人工智能搜索問題第54頁…...…...…...…...…...mjmkmlnab55人工智能搜索問題第55頁Closed表Open表56人工智能搜索問題第56頁一個A算法例子定義評價函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”將牌數(shù)

283164751238476557人工智能搜索問題第57頁h計算舉例 h(n)=42

831

64751234576

858人工智能搜索問題第58頁2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)12345659人工智能搜索問題第59頁2，最正確圖搜索算法A*（A*算法）在A算法中，假如滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。60人工智能搜索問題第60頁A*條件舉例8數(shù)碼問題h1(n)=“不在位”將牌數(shù)h2(n)=將牌“不在位”距離和2

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：261人工智能搜索問題第61頁A*算法性質(zhì)A*算法假設(shè)

設(shè)ni、nj是任意兩個節(jié)點(diǎn)，有：C(ni,nj)>

其中為大于0常數(shù)幾個等式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)。62人工智能搜索問題第62頁A*算法性質(zhì)（續(xù)1）定理1.1： 對有限圖，假如從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。63人工智能搜索問題第63頁A*算法性質(zhì)（續(xù)2）引理1.1： 對無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t路徑，則A*不結(jié)束時，在OPEN表中即使最小一個f值也將增到任意大，或有f(n)>f*(s)。64人工智能搜索問題第64頁A*算法性質(zhì)（續(xù)3）引理1.2： A*結(jié)束前，OPEN表中必存在f(n)≤f*(s)。存在一個節(jié)點(diǎn)n，n在最正確路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)65人工智能搜索問題第65頁A*算法性質(zhì)（續(xù)3）定理1.2： 對無限圖，若從初始節(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é)束，將造成矛盾。66人工智能搜索問題第66頁A*算法性質(zhì)（續(xù)4）推論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)最小時才結(jié)束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)n，均被擴(kuò)展。得證。67人工智能搜索問題第67頁A*算法性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最正確解結(jié)束。68人工智能搜索問題第68頁可采納性證實由定理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é)束條件69人工智能搜索問題第69頁A*算法性質(zhì)（續(xù)6）推論1.2： A*選作擴(kuò)展任一節(jié)點(diǎn)n，有f(n)≤f*(s)。由引理2.2知在A*結(jié)束前，OPEN中存在節(jié)點(diǎn)n’，f(n’)≤f*(s)設(shè)此時A*選擇n擴(kuò)展。假如n＝n’，則f(n)≤f*(s)，得證。假如n≠n’，因為A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。70人工智能搜索問題第70頁A*算法性質(zhì)（續(xù)7）定理1.4：設(shè)對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多啟發(fā)信息，即對全部非目標(biāo)節(jié)點(diǎn)有h2(n)>h1(n)，則在含有一條從s到t路徑隱含圖上，搜索結(jié)束時，由A2所擴(kuò)展每一個節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展節(jié)點(diǎn)數(shù)最少和A2一樣多。簡寫：假如h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外)，則A1擴(kuò)展節(jié)點(diǎn)數(shù)≥A2擴(kuò)展節(jié)點(diǎn)數(shù)71人工智能搜索問題第71頁A*算法性質(zhì)（續(xù)7）注意：

在定理1.4中，評價指標(biāo)是“擴(kuò)展節(jié)點(diǎn)數(shù)”，也就是說，同一個節(jié)點(diǎn)不論被擴(kuò)展多少次，都只計算一次。72人工智能搜索問題第72頁定理1.4證實使用數(shù)學(xué)歸納法，對節(jié)點(diǎn)深度進(jìn)行歸納（1）當(dāng)d(n)＝0時，即只有一個節(jié)點(diǎn)，顯然定理成立。（2）設(shè)d(n)≤k時定理成立。（歸納假設(shè)）（3）當(dāng)d(n)=k+1時，用反證法。設(shè)存在一個深度為k＋1節(jié)點(diǎn)n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n父節(jié)點(diǎn)，即n已經(jīng)被生成了。所以當(dāng)A1結(jié)束時，n將被保留在OPEN中。73人工智能搜索問題第73頁定理1.4證實（續(xù)1）所以有：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)(A)由于d(n)=k時，A2擴(kuò)展節(jié)點(diǎn)A1一定擴(kuò)展，有g(shù)1(n)≤g2(n)(因為A2路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理條件矛盾。故定理得證。74人工智能搜索問題第74頁對h評價方法平均分叉樹 設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個節(jié)點(diǎn)，則:

其中，b*稱為平均分叉樹。b*越小，說明h效果越好。試驗表明，b*是一個比較穩(wěn)定常數(shù)，同一問題基本不隨問題規(guī)模改變。75人工智能搜索問題第75頁對h評價舉例例：8數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)。使用h1： d=14,N=539, b*=1.44;d=20,N=7276， b*=1.47；使用h2： d=14,N=113, b*=1.23; d=20,N=676, b*=1.2776人工智能搜索問題第76頁A*復(fù)雜性普通來說，A*算法復(fù)雜性是指數(shù)型，能夠證實，當(dāng)且僅當(dāng)以下條件成立時： abs(h(n)-h*(n))≤O(log(h*(n))) A*算法復(fù)雜性才是非指數(shù)型，不過通常情況下，h與h*差異最少是和離目標(biāo)距離成正比。77人工智能搜索問題第77頁3，A*算法改進(jìn)問題提出： 因A算法第6步對ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，所以可能會造成屢次重復(fù)擴(kuò)展同一個節(jié)點(diǎn)，造成搜索效率下降。78人工智能搜索問題第78頁s(10)A(1)B(5)C(8)G目標(biāo)631118一個例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)B(8)s(10)A(5)B(8)s(10)C(9)A(5)s(10)B(7)C(9)s(10)A(4)B(7)C(9)s(10)79人工智能搜索問題第79頁出現(xiàn)屢次擴(kuò)展節(jié)點(diǎn)原因在前面擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)63111880人工智能搜索問題第80頁處理路徑對h加以限制能否對h增加適當(dāng)限制，使得第一次擴(kuò)展一個節(jié)點(diǎn)時，就找到了從s到該節(jié)點(diǎn)最短路徑。對算法加以改進(jìn)能否對算法加以改進(jìn)，防止或降低節(jié)點(diǎn)屢次擴(kuò)展。81人工智能搜索問題第81頁改進(jìn)條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法復(fù)雜性82人工智能搜索問題第82頁對h加以限制定義：一個啟發(fā)函數(shù)h，假如對全部節(jié)點(diǎn)ni和nj，其中nj是ni子節(jié)點(diǎn)，滿足 h(ni)-h(nj)≤c(ni,nj) h(t)=0 或h(ni)≤c(ni,nj)+h(nj) h(t)=0則稱h是單調(diào)。h(ni)ninjh(nj)c(ni,nj)83人工智能搜索問題第83頁h單調(diào)性質(zhì)定理1.5： 若h(n)是單調(diào)，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了抵達(dá)節(jié)點(diǎn)n最正確路徑。 即：當(dāng)A*選n擴(kuò)展時，有g(shù)(n)=g*(n)。84人工智能搜索問題第84頁定理1.5證實設(shè)n是A*擴(kuò)展任一節(jié)點(diǎn)。當(dāng)n＝s時，定理顯然成立。下面考查n≠s情況。設(shè)P＝(n0=s,n1,n2,…,nk=n)是s到n最正確路徑P中一定有節(jié)點(diǎn)在CLOSED中，設(shè)P中最終一個出現(xiàn)在CLOSED中節(jié)點(diǎn)為nj，則nj+1在OPEN中。85人工智能搜索問題第85頁定理1.5證實（續(xù)1）由單調(diào)限制條件，對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中)86人工智能搜索問題第86頁定理1.5證實（續(xù)2）重寫上式：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)。得證。87人工智能搜索問題第87頁h單調(diào)性質(zhì)（續(xù)）定理1.6： 若h(n)是單調(diào)，則由A*所擴(kuò)展節(jié)點(diǎn)序列其f值是非遞減。即f(ni)≤f(nj)。

88人工智能搜索問題第88頁定理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，得證。89人工智能搜索問題第89頁h單調(diào)例子8數(shù)碼問題：h為“不在位”將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni后繼節(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿足單調(diào)條件。 90人工智能搜索問題第90頁對算法加以改進(jìn)一些結(jié)論：OPEN表上任以含有f(n)<f*(s)節(jié)點(diǎn)定會被擴(kuò)展。A*選作