人工智能搜索問題課件

第一章搜索問題內(nèi)容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關鍵問題： 如何利用知識，盡可能有效地找到問題的解（最佳解）。1第一章搜索問題內(nèi)容：1搜索問題（續(xù)1）S0Sg2搜索問題（續(xù)1）S0Sg2搜索問題（續(xù)2）討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。3搜索問題（續(xù)2）討論的問題：31.1回溯策略例：皇后問題41.1回溯策略例：皇后問題4()5()5()Q((1,1))6()Q((1,1))6()QQ((1,1))((1,1)(2,3))7()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))8()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))9()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))10()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))11()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))12()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))13()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))14()((1,1))((1,1)(2,3))((1,1)()((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()((1,1))((1,1)(2,3))((1,1)()((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()((1,1))((1,1)(2,3))((1,1)()((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()((1,1))((1,1)(2,3))((1,1)遞歸的思想從前有座山……從前有座山……

從前有座山……18遞歸的思想從前有座山……從前有座山……遞歸的思想（續(xù)）當前狀態(tài)目標狀態(tài)g19遞歸的思想（續(xù)）當前狀態(tài)目標狀態(tài)g19一個遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12320一個遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：當前狀態(tài)。 返回值：從當前狀態(tài)到目標狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。21回溯搜索算法 BACKTRACK（DATA）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回溯搜索算法遞歸過程BACKTRACK(DATA)22存在問題及解決辦法解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當前狀態(tài)的路徑當前狀態(tài)問題：深度問題死循環(huán)問題23存在問題及解決辦法解決辦法：當前狀態(tài)問題：23回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當前的狀態(tài)表（逆向） 返回值：從當前狀態(tài)到目標狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。24回溯搜索算法1BACKTRACK1（DATALIST）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回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法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回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULE一些深入的問題失敗原因分析、多步回溯QQ27一些深入的問題失敗原因分析、多步回溯QQ27一些深入問題（續(xù)）回溯搜索中知識的利用 基本思想(以皇后問題為例)： 盡可能選取劃去對角線上位置數(shù)最少的。QQQQ322328一些深入問題（續(xù)）回溯搜索中知識的利用QQQQ31.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

291.2圖搜索策略問題的引出29一些基本概念節(jié)點深度： 根節(jié)點深度=0 其它節(jié)點深度=父節(jié)點深度+1012330一些基本概念節(jié)點深度：012330一些基本概念（續(xù)1）路徑 設一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。31一些基本概念（續(xù)1）路徑31一些基本概念（續(xù)1）擴展一個節(jié)點 生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。32一些基本概念（續(xù)1）擴展一個節(jié)點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一般的圖搜索算法1,G=G0(G0=s),OPEN:=一般的圖搜索算法（續(xù)）7,標記和修改指針： ADD(mj,OPEN),并標記mj到n的指針； 計算是否要修改mk、ml到n的指針； 計算是否要修改ml到其后繼節(jié)點的指針；8,對OPEN中的節(jié)點按某種原則重新排序；9,GOLOOP；34一般的圖搜索算法（續(xù)）7,標記和修改指針：34節(jié)點類型說明…...…...…...…...…...mjmkml35節(jié)點類型說明…...…...…...…...…...mjmk修改指針舉例123456s36修改指針舉例123456s36修改指針舉例（續(xù)1）123456s37修改指針舉例（續(xù)1）123456s37123456修改指針舉例（續(xù)2）s38123456修改指針舉例（續(xù)2）s38123456修改指針舉例（續(xù)3）s39123456修改指針舉例（續(xù)3）s391.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索401.3無信息圖搜索過程深度優(yōu)先搜索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目標在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標記mj到n的指針;10,GOLOOP;41深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標4223232832深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關的方法43深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解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目標在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標記mj到n的指針;9,GOLOOP;44寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標82341876544523232832寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關，具有通用性效率較低屬于圖搜索方法46寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解46漸進式深度優(yōu)先搜索方法目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。思想 首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。47漸進式深度優(yōu)先搜索方法目的471.4啟發(fā)式圖搜索利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最 優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解481.4啟發(fā)式圖搜索利用知識來引導搜索，達到減少搜索范圍，降希望：引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。49希望：49基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。50基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一1，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式： f(n)=g(n)+h(n) f(n)：評價函數(shù) h(n)：啟發(fā)函數(shù)511，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式：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)的估計值52符號的意義g*(n)：從s到n的最短路徑的耗散值52A算法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);

53A算法1,OPEN:=(s),f(s):=g(s)+h(A算法（續(xù)） ADD(mj,OPEN),標記mj到n的指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標記mk到n的指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點按f值從小到大排序；8,GOLOOP；54A算法（續(xù)） ADD(mj,OPEN),標記mj到n的指…...…...…...…...…...mjmkmlnab55…...…...…...…...…...mjmkmlnab5Closed表Open表56Closed表Open表56一個A算法的例子定義評價函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點到當前節(jié)點的耗散值 h(n)為當前節(jié)點“不在位”的將牌數(shù)

283164751238476557一個A算法的例子定義評價函數(shù)：2831h計算舉例 h(n)=42

831

64751234576

858h計算舉例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目標1234565928328328322，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。602，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：261A*條件舉例8數(shù)碼問題28312A*算法的性質(zhì)A*算法的假設

設ni、nj是任意兩個節(jié)點，有：C(ni,nj)>其中為大于0的常數(shù)幾個等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點，t是目標節(jié)點，n是s到t的最佳路徑上的節(jié)點。62A*算法的性質(zhì)A*算法的假設幾個等式62A*算法的性質(zhì)（續(xù)1）定理1.1： 對有限圖，如果從初始節(jié)點s到目標節(jié)點t有路徑存在，則算法A一定成功結束。63A*算法的性質(zhì)（續(xù)1）定理1.1：63A*算法的性質(zhì)（續(xù)2）引理1.1： 對無限圖，若有從初始節(jié)點s到目標節(jié)點t的路徑，則A*不結束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)>f*(s)。64A*算法的性質(zhì)（續(xù)2）引理1.1：64A*算法的性質(zhì)（續(xù)3）引理1.2： A*結束前，OPEN表中必存在f(n)≤f*(s)。存在一個節(jié)點n，n在最佳路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)65A*算法的性質(zhì)（續(xù)3）引理1.2：存在一個節(jié)點n，n在65A*算法的性質(zhì)（續(xù)3）定理1.2： 對無限圖，若從初始節(jié)點s到目標節(jié)點t有路徑存在，則A*一定成功結束。引理1.1：A*如果不結束，則OPEN中所有的n有f(n)>f*(s)引理1.2：在A*結束前，必存在節(jié)點n，使得f(n)≤f*(s)所以，如果A*不結束，將導致矛盾。66A*算法的性質(zhì)（續(xù)3）定理1.2：引理1.1：A*如果不結束A*算法的性質(zhì)（續(xù)4）推論1.1： OPEN表上任一具有f(n)<f*(s)的節(jié)點n，最終都將被A*選作擴展的節(jié)點。

由定理1.2，知A*一定結束，由A*的結束條件，OPEN表中f(t)最小時才結束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴展。得證。67A*算法的性質(zhì)（續(xù)4）推論1.1：由定理1.2，知A*A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點s到目標節(jié)點t有路徑，則A*必能找到最佳解結束。68A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)：68可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結束設找到的路徑s→t不是最佳的（t為目標）則：f(t)=g(t)>f*(s)由引理1.2知結束前OPEN中存在f(n)≤f*(s)的節(jié)點n，所以f(n)≤f*(s)<f(t)因此A*應選擇n擴展，而不是t。與假設A*選擇t結束矛盾。得證。注意：A*的結束條件69可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結束A*算法的性質(zhì)（續(xù)6）推論1.2： A*選作擴展的任一節(jié)點n，有f(n)≤f*(s)。由引理2.2知在A*結束前，OPEN中存在節(jié)點n’，f(n’)≤f*(s)設此時A*選擇n擴展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。70A*算法的性質(zhì)（續(xù)6）推論1.2：由引理2.2知在A*結束前A*算法的性質(zhì)（續(xù)7）定理1.4：設對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對所有非目標節(jié)點有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n)>h1(n)(目標節(jié)點除外)，則A1擴展的節(jié)點數(shù)≥A2擴展的節(jié)點數(shù)71A*算法的性質(zhì)（續(xù)7）定理1.4：設對同一個問題定義了兩個AA*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評價指標是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只計算一次。72A*算法的性質(zhì)（續(xù)7）注意：72定理1.4的證明使用數(shù)學歸納法，對節(jié)點的深度進行歸納（1）當d(n)＝0時，即只有一個節(jié)點，顯然定理成立。（2）設d(n)≤k時定理成立。（歸納假設）（3）當d(n)=k+1時，用反證法。設存在一個深度為k＋1的節(jié)點n，被A2擴展，但沒有被A1擴展。而由假設，A1擴展了n的父節(jié)點，即n已經(jīng)被生成了。因此當A1結束時，n將被保留在OPEN中。73定理1.4的證明使用數(shù)學歸納法，對節(jié)點的深度進行歸納73定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2擴展了n，有f2(n)≤f*(s)即：h2(n)≤f*(s)–g2(n)(A)由于d(n)=k時，A2擴展的節(jié)點A1一定擴展，有g1(n)≤g2(n)(因為A2的路A1均走到了)所以：h1(n)≥f*(s)-g1(n)≥f*(s)–g2(n)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理條件矛盾。故定理得證。74定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)對h的評價方法平均分叉樹 設共擴展了d層節(jié)點，共搜索了N個節(jié)點，則:

其中，b*稱為平均分叉樹。b*越小，說明h效果越好。實驗表明，b*是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。75對h的評價方法平均分叉樹75對h的評價舉例例：8數(shù)碼問題，隨機產(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對h的評價舉例例：8數(shù)碼問題，隨機產(chǎn)生若干初始狀態(tài)。76A*的復雜性一般來說，A*的算法復雜性是指數(shù)型的，可以證明，當且僅當以下條件成立時： abs(h(n)-h*(n))≤O(log(h*(n))) A*的算法復雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標的距離成正比的。77A*的復雜性一般來說，A*的算法復雜性是指數(shù)型的，可以證明，3，A*算法的改進問題的提出： 因A算法第6步對ml類節(jié)點可能要重新放回到OPEN表中，因此可能會導致多次重復擴展同一個節(jié)點，導致搜索效率下降。783，A*算法的改進問題的提出：78s(10)A(1)B(5)C(8)G目標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)79s(10)A(1)B(5)C(8)G目標631118一個例出現(xiàn)多次擴展節(jié)點的原因在前面的擴展中，并沒有找到從初始節(jié)點到當前節(jié)點的最短路徑，如節(jié)點A。s(10)A(1)B(5)C(8)G目標63111880出現(xiàn)多次擴展節(jié)點的原因在前面的擴展中，并沒有找到從初始節(jié)點到解決的途徑對h加以限制能否對h增加適當?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑。對算法加以改進能否對算法加以改進，避免或減少節(jié)點的多次擴展。81解決的途徑對h加以限制81改進的條件可采納性不變不多擴展節(jié)點不增加算法的復雜性82改進的條件可采納性不變82對h加以限制定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj，其中nj是ni的子節(jié)點，滿足 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對h加以限制定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj，h單調(diào)的性質(zhì)定理1.5： 若h(n)是單調(diào)的，則A*擴展了節(jié)點n之后，就已經(jīng)找到了到達節(jié)點n的最佳路徑。 即：當A*選n擴展時，有g(n)=g*(n)。84h單調(diào)的性質(zhì)定理1.5：84定理1.5的證明設n是A*擴展的任一節(jié)點。當n＝s時，定理顯然成立。下面考察n≠s的情況。設P＝(n0=s,n1,n2,…,nk=n)是s到n的最佳路徑P中一定有節(jié)點在CLOSED中，設P中最后一個出現(xiàn)在CLOSED中的節(jié)點為nj，則nj+1在OPEN中。85定理1.5的證明設n是A*擴展的任一節(jié)點。當n＝s時，定理顯定理1.5的證明（續(xù)1）由單調(diào)限制條件，對P中任意節(jié)點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應用上不等式，有：g*(nj+1)+h(nj+1)≤g*(nk)+h(nk)即：f(nj+1)≤g*(n)+h(n)

注意：(nj在CLOSED中，nj+1在OPEN中)86定理1.5的證明（續(xù)1）由單調(diào)限制條件，對P中任意節(jié)點ni有定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(n)+h(n)另一方面，A*選n擴展，必有：

f(n)=g(n)+h(n)≤f(nj+1)比較兩式，有：g(n)≤g*(n)但已知g*(n)是最佳路徑的耗散值，所以只有：g(n)=g*(n)。得證。87定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(h單調(diào)的性質(zhì)（續(xù)）定理1.6： 若h(n)是單調(diào)的，則由A*所擴展的節(jié)點序列其f值是非遞減的。即f(ni)≤f(nj)。

88h單調(diào)的性質(zhì)（續(xù)）定理1.6：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定理1.6的證明由單調(diào)限制條件，有：=f(ni)-g(nih單調(diào)的例子8數(shù)碼問題：h為“不在位”的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼節(jié)點)-1 h(t)=0 c(ni,nj)=1滿足單調(diào)的條件。 90h單調(diào)的例子8數(shù)碼問題：90對算法加以改進一些結論：OPEN表上任以具有f(n)<f*(s)的節(jié)點定會被擴展。A*選作擴展的任一節(jié)點，定有f(n)≤f*(s)。91對算法加以改進一些結論：91改進的出發(fā)點OPEN=(…………)f*(s)f值小于f*(s)的節(jié)點f值大于等于f*(s)的節(jié)點fm：到目前為止已擴展節(jié)點的最大f值，用fm代替f*(s)92改進的出發(fā)點OPEN=(…………)f*(修正過程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IFOPEN=()THENEXIT(FAIL);3,NEST:={ni|f(ni)<fm} IFNEST≠()THENn:=NEST中g最小的節(jié)點 ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同過程A。93修正過程A1,OPEN:=(s),f(s)=g(s)+hs(10)A(1)B(5)C(8)G目標631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)94s(10)A(1)B(5)C(8)G目標631118前面的h的單調(diào)化方法如果令： f(n)=max(f(n的父節(jié)點),g(n)+h(n)) 則容易證明，這樣處理后的h是單調(diào)的。95h的單調(diào)化方法如果令：95IDA*算法(IterativeDeepeningA*)基本思想：回溯與A*的結合算法簡介（非嚴格地） 1，設初始值f0； 2，集合S＝NULL； 3，用回溯法求解問題，如果節(jié)點n的f值大于f0，則將該節(jié)點放入集合S中，并回溯； 4，如果在3中找到了解，則結束； 5，如果3以失敗結束，則f0＝S中節(jié)點的最小f值； 6，返回到2。96IDA*算法(IterativeDeepeningA*)知識的靈活應用例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為12。13551441332523123122552342543433分析：陰影部分數(shù)字和：48直徑部分數(shù)字和：24轉(zhuǎn)45°改變陰影部分轉(zhuǎn)90°改變直徑部分但不改變陰影部分轉(zhuǎn)180°改變扇區(qū)部分但不改變陰影部分也不改變直徑部分97知識的靈活應用例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為12。1354，其他的搜索算法爬山法（局部搜索算法）984，其他的搜索算法爬山法（局部搜索算法）98其他的搜索算法（續(xù)1）隨機搜索算法動態(tài)規(guī)劃算法 如果對于任何n，當h(n)=0時，A*算法就成為了動態(tài)規(guī)劃算法。99其他的搜索算法（續(xù)1）隨機搜索算法99動態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段100動態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段1005，搜索算法實用舉例漢字識別后處理一個例子我錢線載哦栽哉裁劣綏 優(yōu)仍們仿倫奶砧犯扔妨 要耍密窮安壁駐努窯垂 扳報叔嵌奴振技寂敘蔽 奮夯杏蠶香脊秀吞吝番 精猜指潔括治捐活冶桔 種神襯祥科鐘拌樣拎補

1015，搜索算法實用舉例漢字識別后處理101漢字識別后處理二元語法時：為常量用識別信度代替問題變?yōu)榍笞畲?02漢字識別后處理二元語法時：為常量用識別信度代替問題變?yōu)榍笞畲蟮谝徽滤阉鲉栴}內(nèi)容： 狀態(tài)空間的搜索問題。搜索方式：盲目搜索啟發(fā)式搜索關鍵問題： 如何利用知識，盡可能有效地找到問題的解（最佳解）。103第一章搜索問題內(nèi)容：1搜索問題（續(xù)1）S0Sg104搜索問題（續(xù)1）S0Sg2搜索問題（續(xù)2）討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。105搜索問題（續(xù)2）討論的問題：31.1回溯策略例：皇后問題1061.1回溯策略例：皇后問題4()107()5()Q((1,1))108()Q((1,1))6()QQ((1,1))((1,1)(2,3))109()QQ((1,1))((1,1)(2,3))7()Q((1,1))((1,1)(2,3))110()Q((1,1))((1,1)(2,3))8()QQ((1,1))((1,1)(2,3))((1,1)(2,4))111()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))112()QQ((1,1))((1,1)(2,3))((1,1()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))113()QQ((1,1))((1,1)(2,3))((1,1()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))114()Q((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))115()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))116()((1,1))((1,1)(2,3))((1,1)()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))117()((1,1))((1,1)(2,3))((1,1)()((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))118()((1,1))((1,1)(2,3))((1,1)()((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))119()((1,1))((1,1)(2,3))((1,1)遞歸的思想從前有座山……從前有座山……

從前有座山……120遞歸的思想從前有座山……從前有座山……遞歸的思想（續(xù)）當前狀態(tài)目標狀態(tài)g121遞歸的思想（續(xù)）當前狀態(tài)目標狀態(tài)g19一個遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST123122一個遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

DATA：當前狀態(tài)。 返回值：從當前狀態(tài)到目標狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。123回溯搜索算法 BACKTRACK（DATA）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);124回溯搜索算法遞歸過程BACKTRACK(DATA)22存在問題及解決辦法解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當前狀態(tài)的路徑當前狀態(tài)問題：深度問題死循環(huán)問題125存在問題及解決辦法解決辦法：當前狀態(tài)問題：23回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當前的狀態(tài)表（逆向） 返回值：從當前狀態(tài)到目標狀態(tài)的路徑 （以規(guī)則表的形式表示） 或FAIL。126回溯搜索算法1BACKTRACK1（DATALIST）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);127回溯搜索算法11, DATA:=FIRST(DATALIS回溯搜索算法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);128回溯搜索算法1（續(xù)）9, RULES:=TAIL(RULE一些深入的問題失敗原因分析、多步回溯QQ129一些深入的問題失敗原因分析、多步回溯QQ27一些深入問題（續(xù)）回溯搜索中知識的利用 基本思想(以皇后問題為例)： 盡可能選取劃去對角線上位置數(shù)最少的。QQQQ3223130一些深入問題（續(xù)）回溯搜索中知識的利用QQQQ31.2圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。

1311.2圖搜索策略問題的引出29一些基本概念節(jié)點深度： 根節(jié)點深度=0 其它節(jié)點深度=父節(jié)點深度+10123132一些基本概念節(jié)點深度：012330一些基本概念（續(xù)1）路徑 設一節(jié)點序列為(n0,n1,…,nk)，對于i=1,…,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。133一些基本概念（續(xù)1）路徑31一些基本概念（續(xù)1）擴展一個節(jié)點 生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。134一些基本概念（續(xù)1）擴展一個節(jié)點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);135一般的圖搜索算法1,G=G0(G0=s),OPEN:=一般的圖搜索算法（續(xù)）7,標記和修改指針： ADD(mj,OPEN),并標記mj到n的指針； 計算是否要修改mk、ml到n的指針； 計算是否要修改ml到其后繼節(jié)點的指針；8,對OPEN中的節(jié)點按某種原則重新排序；9,GOLOOP；136一般的圖搜索算法（續(xù)）7,標記和修改指針：34節(jié)點類型說明…...…...…...…...…...mjmkml137節(jié)點類型說明…...…...…...…...…...mjmk修改指針舉例123456s138修改指針舉例123456s36修改指針舉例（續(xù)1）123456s139修改指針舉例（續(xù)1）123456s37123456修改指針舉例（續(xù)2）s140123456修改指針舉例（續(xù)2）s38123456修改指針舉例（續(xù)3）s141123456修改指針舉例（續(xù)3）s391.3無信息圖搜索過程深度優(yōu)先搜索寬度優(yōu)先搜索1421.3無信息圖搜索過程深度優(yōu)先搜索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目標在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標記mj到n的指針;10,GOLOOP;143深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關的方法145深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解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目標在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標記mj到n的指針;9,GOLOOP;146寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標823418765414723232832寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關，具有通用性效率較低屬于圖搜索方法148寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解46漸進式深度優(yōu)先搜索方法目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。思想 首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。149漸進式深度優(yōu)先搜索方法目的471.4啟發(fā)式圖搜索利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最 優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解1501.4啟發(fā)式圖搜索利用知識來引導搜索，達到減少搜索范圍，降希望：引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。151希望：49基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。152基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一1，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式： f(n)=g(n)+h(n) f(n)：評價函數(shù) h(n)：啟發(fā)函數(shù)1531，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式：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)的估計值154符號的意義g*(n)：從s到n的最短路徑的耗散值52A算法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);

155A算法1,OPEN:=(s),f(s):=g(s)+h(A算法（續(xù)） ADD(mj,OPEN),標記mj到n的指針； IFf(n,mk)<f(mk)THENf(mk):=f(n,mk),

標記mk到n的指針； IFf(n,ml)<f(ml,)THENf(ml):=f(n,ml), 標記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點按f值從小到大排序；8,GOLOOP；156A算法（續(xù)） ADD(mj,OPEN),標記mj到n的指…...…...…...…...…...mjmkmlnab157…...…...…...…...…...mjmkmlnab5Closed表Open表158Closed表Open表56一個A算法的例子定義評價函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點到當前節(jié)點的耗散值 h(n)為當前節(jié)點“不在位”的將牌數(shù)

2831647512384765159一個A算法的例子定義評價函數(shù)：2831h計算舉例 h(n)=42

831

64751234576

8160h計算舉例 h(n)=428312831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(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)目標12345616128328328322，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。1622，最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：A*條件舉例8數(shù)碼問題h1(n)=“不在位”的將牌數(shù)h2(n)=將牌“不在位”的距離和2

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：2163A*條件舉例8數(shù)碼問題28312A*算法的性質(zhì)A*算法的假設

設ni、nj是任意兩個節(jié)點，有：C(ni,nj)>其中為大于0的常數(shù)幾個等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點，t是目標節(jié)點，n是s到t的最佳路徑上的節(jié)點。164A*算法的性質(zhì)A*算法的假設幾個等式62A*算法的性質(zhì)（續(xù)1）定理1.1： 對有限圖，如果從初始節(jié)點s到目標節(jié)點t有路徑存在，則算法A一定成功結束。165A*算法的性質(zhì)（續(xù)1）定理1.1：63A*算法的性質(zhì)（續(xù)2）引理1.1： 對無限圖，若有從初始節(jié)點s到目標節(jié)點t的路徑，則A*不結束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)>f*(s)。166A*算法的性質(zhì)（續(xù)2）引理1.1：64A*算法的性質(zhì)（續(xù)3）引理1.2： A*結束前，OPEN表中必存在f(n)≤f*(s)。存在一個節(jié)點n，n在最佳路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)167A*算法的性質(zhì)（續(xù)3）引理1.2：存在一個節(jié)點n，n在65A*算法的性質(zhì)（續(xù)3）定理1.2： 對無限圖，若從初始節(jié)點s到目標節(jié)點t有路徑存在，則A*一定成功結束。引理1.1：A*如果不結束，則OPEN中所有的n有f(n)>f*(s)引理1.2：在A*結束前，必存在節(jié)點n，使得f(n)≤f*(s)所以，如果A*不結束，將導致矛盾。168A*算法的性質(zhì)（續(xù)3）定理1.2：引理1.1：A*如果不結束A*算法的性質(zhì)（續(xù)4）推論1.1： OPEN表上任一具有f(n)<f*(s)的節(jié)點n，最終都將被A*選作擴展的節(jié)點。

由定理1.2，知A*一定結束，由A*的結束條件，OPEN表中f(t)最小時才結束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴展。得證。169A*算法的性質(zhì)（續(xù)4）推論1.1：由定理1.2，知A*A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點s到目標節(jié)點t有路徑，則A*必能找到最佳解結束。170A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)：68可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結束設找到的路徑s→t不是最佳的（t為目標）則：f(t)=g(t)>f*(s)由引理1.2知結束前OPEN中存在f(n)≤f*(s)的節(jié)點n，所以f(n)≤f*(s)<f(t)因此A*應選擇n擴展，而不是t。與假設A*選擇t結束矛盾。得證。注意：A*的結束條件171可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結束A*算法的性質(zhì)（續(xù)6）推論1.2： A*選作擴展的任一節(jié)點n，有f(n)≤f*(s)。由引理2.2知在A*結束前，OPEN中存在節(jié)點n’，f(n’)≤f*(s)設此時A*選擇n擴展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。172A*算法的性質(zhì)（續(xù)6）推論1.2：由引理2.2知在A*結束前A*算法的性質(zhì)（續(xù)7）定理1.4：設對同一個問題定義了兩個A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對所有非目標節(jié)點有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n)>h1(n)(目標節(jié)點除外)，則A1擴展的節(jié)點數(shù)≥A2擴展的節(jié)點數(shù)173A*算法的性質(zhì)（續(xù)7）定理1.4：設對同一個問題定義了兩個AA*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評價指標是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只計算一次。174A*算法的性質(zhì)（續(xù)7）注意：72定理1.4的證明使用數(shù)學歸納法，對節(jié)點的深度進行歸納（1）當d(n)＝0時，即只有一個節(jié)點，顯然定理成立。（2）設d(n)≤k時定理成立。（歸納假設）（3）當d(n)=k+1時，用反證法。設存在一個深度為k＋1的節(jié)點n，被A2擴展，但沒有被A1擴展。而由假設，A1擴展了n的父節(jié)點，即n已經(jīng)被生成了。因此當A1結束時，n將被保留在OPEN中。175定理1.4的證明使用數(shù)學歸納法，對節(jié)點的深度進行歸納73定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)即：g1(n)+h1(n)≥f*(s)所以：h1(n)≥f*(s)-g1(n)另一方面，由于A2擴展了n，有f2(n)≤f*(s)即：h