人工智能搜索問(wèn)題課件

第一章搜索問(wèn)題內(nèi)容： 狀態(tài)空間的搜索問(wèn)題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問(wèn)題： 如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。1第一章搜索問(wèn)題內(nèi)容：1搜索問(wèn)題（續(xù)1）S0Sg2搜索問(wèn)題（續(xù)1）S0Sg2搜索問(wèn)題（續(xù)2）討論的問(wèn)題：有哪些常用的搜索算法。問(wèn)題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。3搜索問(wèn)題（續(xù)2）討論的問(wèn)題：31.1回溯策略例：皇后問(wèn)題41.1回溯策略例：皇后問(wèn)題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ù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19一個(gè)遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12320一個(gè)遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

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

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(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一些深入的問(wèn)題失敗原因分析、多步回溯QQ27一些深入的問(wèn)題失敗原因分析、多步回溯QQ27一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)的利用 基本思想(以皇后問(wèn)題為例)： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ322328一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)的利用QQQQ31.2圖搜索策略問(wèn)題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過(guò)的路徑。

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

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

53A算法1,OPEN:=(s),f(s):=g(s)+h(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；54A算法（續(xù)） ADD(mj,OPEN),標(biāo)記mj到n的指…...…...…...…...…...mjmkmlnab55…...…...…...…...…...mjmkmlnab5Closed表Open表56Closed表Open表56一個(gè)A算法的例子定義評(píng)價(jià)函數(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一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)：2831h計(jì)算舉例 h(n)=42

831

64751234576

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

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：261A*條件舉例8數(shù)碼問(wèn)題28312A*算法的性質(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)。62A*算法的性質(zhì)A*算法的假設(shè)幾個(gè)等式62A*算法的性質(zhì)（續(xù)1）定理1.1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。63A*算法的性質(zhì)（續(xù)1）定理1.1：63A*算法的性質(zhì)（續(xù)2）引理1.1： 對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。64A*算法的性質(zhì)（續(xù)2）引理1.1：64A*算法的性質(zhì)（續(xù)3）引理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)65A*算法的性質(zhì)（續(xù)3）引理1.2：存在一個(gè)節(jié)點(diǎn)n，n在65A*算法的性質(zhì)（續(xù)3）定理1.2： 對(duì)無(wú)限圖，若從初始節(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)致矛盾。66A*算法的性質(zhì)（續(xù)3）定理1.2：引理1.1：A*如果不結(jié)束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)最小時(shí)才結(jié)束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴(kuò)展。得證。67A*算法的性質(zhì)（續(xù)4）推論1.1：由定理1.2，知A*A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。68A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)：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可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束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è)此時(shí)A*選擇n擴(kuò)展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。70A*算法的性質(zhì)（續(xù)6）推論1.2：由引理2.2知在A*結(jié)束前A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)A*算法A1和A2，若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)寫：如果h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外)，則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)71A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)AA*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說(shuō)，同一個(gè)節(jié)點(diǎn)無(wú)論被擴(kuò)展多少次，都只計(jì)算一次。72A*算法的性質(zhì)（續(xù)7）注意：72定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納（1）當(dāng)d(n)＝0時(shí)，即只有一個(gè)節(jié)點(diǎn)，顯然定理成立。（2）設(shè)d(n)≤k時(shí)定理成立。（歸納假設(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中。73定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納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時(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)(B)比較A、B兩式，有h1(n)≥h2(n)，與定理?xiàng)l件矛盾。故定理得證。74定理1.4的證明（續(xù)1）所以有：f1(n)≥f*(s)對(duì)h的評(píng)價(jià)方法平均分叉樹 設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個(gè)節(jié)點(diǎn)，則:

其中，b*稱為平均分叉樹。b*越小，說(shuō)明h效果越好。實(shí)驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問(wèn)題基本不隨問(wèn)題規(guī)模變化。75對(duì)h的評(píng)價(jià)方法平均分叉樹75對(duì)h的評(píng)價(jià)舉例例：8數(shù)碼問(wèn)題，隨機(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對(duì)h的評(píng)價(jià)舉例例：8數(shù)碼問(wèn)題，隨機(jī)產(chǎn)生若干初始狀態(tài)。76A*的復(fù)雜性一般來(lái)說(shuō)，A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)： abs(h(n)-h*(n))≤O(log(h*(n))) A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標(biāo)的距離成正比的。77A*的復(fù)雜性一般來(lái)說(shuō)，A*的算法復(fù)雜性是指數(shù)型的，可以證明，3，A*算法的改進(jìn)問(wèn)題的提出： 因A算法第6步對(duì)ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。783，A*算法的改進(jìn)問(wèn)題的提出：78s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子：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目標(biāo)631118一個(gè)例出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒(méi)有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G目標(biāo)63111880出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒(méi)有找到從初始節(jié)點(diǎn)到解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。81解決的途徑對(duì)h加以限制81改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性82改進(jìn)的條件可采納性不變82對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(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對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，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ò)展時(shí)，有g(shù)(n)=g*(n)。84h單調(diào)的性質(zhì)定理1.5：84定理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中。85定理1.5的證明設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)n＝s時(shí)，定理顯定理1.5的證明（續(xù)1）由單調(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中)86定理1.5的證明（續(xù)1）由單調(diào)限制條件，對(duì)P中任意節(jié)點(diǎn)ni有定理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定理1.5的證明（續(xù)2）重寫上式：f(nj+1)≤g*(h單調(diào)的性質(zhì)（續(xù)）定理1.6： 若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其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ù)碼問(wèn)題：h為“不在位”的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼節(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿足單調(diào)的條件。 90h單調(diào)的例子8數(shù)碼問(wèn)題：90對(duì)算法加以改進(jìn)一些結(jié)論：OPEN表上任以具有f(n)<f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。91對(duì)算法加以改進(jìn)一些結(jié)論：91改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(s)f值小于f*(s)的節(jié)點(diǎn)f值大于等于f*(s)的節(jié)點(diǎn)fm：到目前為止已擴(kuò)展節(jié)點(diǎn)的最大f值，用fm代替f*(s)92改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(修正過(guò)程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(shù)最小的節(jié)點(diǎn) ELSEn:=FIRST(OPEN), fm:=f(n);4,…,8:同過(guò)程A。93修正過(guò)程A1,OPEN:=(s),f(s)=g(s)+hs(10)A(1)B(5)C(8)G目標(biāo)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目標(biāo)631118前面的h的單調(diào)化方法如果令： f(n)=max(f(n的父節(jié)點(diǎn)),g(n)+h(n)) 則容易證明，這樣處理后的h是單調(diào)的。95h的單調(diào)化方法如果令：95IDA*算法(IterativeDeepeningA*)基本思想：回溯與A*的結(jié)合算法簡(jiǎn)介（非嚴(yán)格地） 1，設(shè)初始值f0； 2，集合S＝NULL； 3，用回溯法求解問(wèn)題，如果節(jié)點(diǎn)n的f值大于f0，則將該節(jié)點(diǎn)放入集合S中，并回溯； 4，如果在3中找到了解，則結(jié)束； 5，如果3以失敗結(jié)束，則f0＝S中節(jié)點(diǎn)的最小f值； 6，返回到2。96IDA*算法(IterativeDeepeningA*)知識(shí)的靈活應(yīng)用例：如何轉(zhuǎn)動(dòng)，使得每個(gè)扇區(qū)數(shù)字和為12。13551441332523123122552342543433分析：陰影部分?jǐn)?shù)字和：48直徑部分?jǐn)?shù)字和：24轉(zhuǎn)45°改變陰影部分轉(zhuǎn)90°改變直徑部分但不改變陰影部分轉(zhuǎn)180°改變扇區(qū)部分但不改變陰影部分也不改變直徑部分97知識(shí)的靈活應(yīng)用例：如何轉(zhuǎn)動(dòng)，使得每個(gè)扇區(qū)數(shù)字和為12。1354，其他的搜索算法爬山法（局部搜索算法）984，其他的搜索算法爬山法（局部搜索算法）98其他的搜索算法（續(xù)1）隨機(jī)搜索算法動(dòng)態(tài)規(guī)劃算法 如果對(duì)于任何n，當(dāng)h(n)=0時(shí)，A*算法就成為了動(dòng)態(tài)規(guī)劃算法。99其他的搜索算法（續(xù)1）隨機(jī)搜索算法99動(dòng)態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段100動(dòng)態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段1005，搜索算法實(shí)用舉例漢字識(shí)別后處理一個(gè)例子我錢線載哦栽哉裁劣綏 優(yōu)仍們仿倫奶砧犯扔妨 要耍密窮安壁駐努窯垂 扳報(bào)叔嵌奴振技寂敘蔽 奮夯杏蠶香脊秀吞吝番 精猜指潔括治捐活冶桔 種神襯祥科鐘拌樣拎補(bǔ)

1015，搜索算法實(shí)用舉例漢字識(shí)別后處理101漢字識(shí)別后處理二元語(yǔ)法時(shí)：為常量用識(shí)別信度代替問(wèn)題變?yōu)榍笞畲?02漢字識(shí)別后處理二元語(yǔ)法時(shí)：為常量用識(shí)別信度代替問(wèn)題變?yōu)榍笞畲蟮谝徽滤阉鲉?wèn)題內(nèi)容： 狀態(tài)空間的搜索問(wèn)題。搜索方式：盲目搜索啟發(fā)式搜索關(guān)鍵問(wèn)題： 如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。103第一章搜索問(wèn)題內(nèi)容：1搜索問(wèn)題（續(xù)1）S0Sg104搜索問(wèn)題（續(xù)1）S0Sg2搜索問(wèn)題（續(xù)2）討論的問(wèn)題：有哪些常用的搜索算法。問(wèn)題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。105搜索問(wèn)題（續(xù)2）討論的問(wèn)題：31.1回溯策略例：皇后問(wèn)題1061.1回溯策略例：皇后問(wèn)題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ù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g121遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19一個(gè)遞歸的例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST123122一個(gè)遞歸的例子intListLenght(LIST*pL回溯搜索算法 BACKTRACK（DATA）

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

DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向） 返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(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一些深入的問(wèn)題失敗原因分析、多步回溯QQ129一些深入的問(wèn)題失敗原因分析、多步回溯QQ27一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)的利用 基本思想(以皇后問(wèn)題為例)： 盡可能選取劃去對(duì)角線上位置數(shù)最少的。QQQQ3223130一些深入問(wèn)題（續(xù)）回溯搜索中知識(shí)的利用QQQQ31.2圖搜索策略問(wèn)題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過(guò)的路徑。

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

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

155A算法1,OPEN:=(s),f(s):=g(s)+h(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；156A算法（續(xù)） ADD(mj,OPEN),標(biāo)記mj到n的指…...…...…...…...…...mjmkmlnab157…...…...…...…...…...mjmkmlnab5Closed表Open表158Closed表Open表56一個(gè)A算法的例子定義評(píng)價(jià)函數(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ù)

2831647512384765159一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)：2831h計(jì)算舉例 h(n)=42

831

64751234576

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

831

64751234576

8將牌1：1將牌2：1將牌6：1將牌8：2163A*條件舉例8數(shù)碼問(wèn)題28312A*算法的性質(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)。164A*算法的性質(zhì)A*算法的假設(shè)幾個(gè)等式62A*算法的性質(zhì)（續(xù)1）定理1.1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。165A*算法的性質(zhì)（續(xù)1）定理1.1：63A*算法的性質(zhì)（續(xù)2）引理1.1： 對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。166A*算法的性質(zhì)（續(xù)2）引理1.1：64A*算法的性質(zhì)（續(xù)3）引理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)167A*算法的性質(zhì)（續(xù)3）引理1.2：存在一個(gè)節(jié)點(diǎn)n，n在65A*算法的性質(zhì)（續(xù)3）定理1.2： 對(duì)無(wú)限圖，若從初始節(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)致矛盾。168A*算法的性質(zhì)（續(xù)3）定理1.2：引理1.1：A*如果不結(jié)束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)最小時(shí)才結(jié)束。而f(t)≥f*(t)＝f*(s)所以f(n)<f*(s)的n，均被擴(kuò)展。得證。169A*算法的性質(zhì)（續(xù)4）推論1.1：由定理1.2，知A*A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。170A*算法的性質(zhì)（續(xù)5）定理1.3(可采納性定理)：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é)束條件171可采納性的證明由定理1.1、1.2知A*一定找到一條路徑結(jié)束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è)此時(shí)A*選擇n擴(kuò)展。如果n＝n’，則f(n)≤f*(s)，得證。如果n≠n’，由于A*選擇n擴(kuò)展，而不是n’，所以有f(n)≤f(n’)≤f*(s)。得證。172A*算法的性質(zhì)（續(xù)6）推論1.2：由引理2.2知在A*結(jié)束前A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)A*算法A1和A2，若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)寫：如果h2(n)>h1(n)(目標(biāo)節(jié)點(diǎn)除外)，則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)173A*算法的性質(zhì)（續(xù)7）定理1.4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)AA*算法的性質(zhì)（續(xù)7）注意：

在定理1.4中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說(shuō)，同一個(gè)節(jié)點(diǎn)無(wú)論被擴(kuò)展多少次，都只計(jì)算一次。174A*算法的性質(zhì)（續(xù)7）注意：72定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納（1）當(dāng)d(n)＝0時(shí)，即只有一個(gè)節(jié)點(diǎn)，顯然定理成立。（2）設(shè)d(n)≤k時(shí)定理成立。（歸納假設(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中。175定理1.4的證明使用數(shù)學(xué)歸納法，對(duì)節(jié)點(diǎn)的深度進(jìn)行歸納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)即：h