第一章搜索問題內容： 狀態空間搜索問題。搜索方式：盲目搜索啟發式搜索關鍵問題： 怎樣利用知識，盡可能有效地找到問題解（最正確解）。1人工智能搜索問題第1頁搜索問題（續1）S0Sg2人工智能搜索問題第2頁搜索問題（續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頁遞歸思想（續）當前狀態目標狀態g19人工智能搜索問題第19頁一個遞歸例子intListLenght(LIST*pList){ if(pList==NULL)return0; elsereturnListLength(pList->next)+1;}NULLpLIST12320人工智能搜索問題第20頁回溯搜索算法 BACKTRACK（DATA）

DATA：當前狀態。 返回值：從當前狀態到目標狀態路徑 （以規則表形式表示） 或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頁存在問題及處理方法處理方法：對搜索深度加以限制統計從初始狀態到當前狀態路徑當前狀態問題：深度問題死循環問題23人工智能搜索問題第23頁回溯搜索算法1BACKTRACK1（DATALIST）

DATALIST：從初始到當前狀態表（逆向） 返回值：從當前狀態到目標狀態路徑 （以規則表形式表示） 或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（續）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頁一些深入問題（續）回溯搜索中知識利用 基本思想(以皇后問題為例)： 盡可能選取劃去對角線上位置數最少。QQQQ322328人工智能搜索問題第28頁1.2圖搜索策略問題引出回溯搜索：只保留從初始狀態到當前狀態一條路徑。圖搜索：保留全部已經搜索過路徑。

29人工智能搜索問題第29頁一些基本概念節點深度： 根節點深度=0 其它節點深度=父節點深度+1012330人工智能搜索問題第30頁一些基本概念（續1）路徑 設一節點序列為(n0,n1,…,nk)，對于i=1,…,k，若節點ni-1含有一個后繼節點ni，則該序列稱為從n0到nk路徑。路徑耗散值 一條路徑耗散值等于連接這條路徑各節點間全部耗散值總和。用C(ni,nj)表示從ni到nj路徑耗散值。31人工智能搜索問題第31頁一些基本概念（續1）擴展一個節點 生成出該節點全部后繼節點，并給出它們之間耗散值。這一過程稱為“擴展一個節點”。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頁普通圖搜索算法（續）7,標識和修改指針： ADD(mj,OPEN),并標識mj到n指針； 計算是否要修改mk、ml到n指針； 計算是否要修改ml到其后繼節點指針；8,對OPEN中節點按某種標準重新排序；9,GOLOOP；34人工智能搜索問題第34頁節點類型說明…...…...…...…...…...mjmkml35人工智能搜索問題第35頁修改指針舉例123456s36人工智能搜索問題第36頁修改指針舉例（續1）123456s37人工智能搜索問題第37頁123456修改指針舉例（續2）s38人工智能搜索問題第38頁123456修改指針舉例（續3）s39人工智能搜索問題第39頁1.3無信息圖搜索過程深度優先搜索寬度優先搜索40人工智能搜索問題第40頁深度優先搜索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人工智能搜索問題第41頁231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標42人工智能搜索問題第42頁深度優先搜索性質普通不能確保找到最優解當深度限制不合理時，可能找不到解，能夠將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法差異：圖搜索是一個通用與問題無關方法43人工智能搜索問題第43頁寬度優先搜索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人工智能搜索問題第44頁23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標823418765445人工智能搜索問題第45頁寬度優先搜索性質當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優解方法與問題無關，含有通用性效率較低屬于圖搜索方法46人工智能搜索問題第46頁漸進式深度優先搜索方法目標處理寬度優先方法空間問題和回溯方法不能找到最優解問題。思想 首先給回溯法一個比較小深度限制，然后逐步增加深度限制，直到找到解或找遍所以分支為止。47人工智能搜索問題第47頁1.4啟發式圖搜索利用知識來引導搜索，到達降低搜索范圍，降低問題復雜度目標。啟發信息強度強：降低搜索工作量，但可能造成找不到最 優解弱：普通造成工作量加大，極限情況下變為 盲目搜索，但可能能夠找到最優解48人工智能搜索問題第48頁希望：引入啟發知識，在確保找到最正確解情況下，盡可能降低搜索范圍，提升搜索效率。49人工智能搜索問題第49頁基本思想定義一個評價函數f，對當前搜索狀態進行評定，找出一個最有希望節點來擴展。50人工智能搜索問題第50頁1，啟發式搜索算法A（A算法）評價函數格式： f(n)=g(n)+h(n) f(n)：評價函數 h(n)：啟發函數51人工智能搜索問題第51頁符號意義g*(n)：從s到n最短路徑耗散值h*(n)：從n到g最短路徑耗散值f*(n)=g*(n)+h*(n)：從s經過n到g最短路徑耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)預計值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算法（續） 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中節點按f值從小到大排序；8,GOLOOP；54人工智能搜索問題第54頁…...…...…...…...…...mjmkmlnab55人工智能搜索問題第55頁Closed表Open表56人工智能搜索問題第56頁一個A算法例子定義評價函數： f(n)=g(n)+h(n) g(n)為從初始節點到當前節點耗散值 h(n)為當前節點“不在位”將牌數

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)目標12345659人工智能搜索問題第59頁2，最正確圖搜索算法A*（A*算法）在A算法中，假如滿足條件： h(n)≤h*(n) 則A算法稱為A*算法。60人工智能搜索問題第60頁A*條件舉例8數碼問題h1(n)=“不在位”將牌數h2(n)=將牌“不在位”距離和2

831

64751234576

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

設ni、nj是任意兩個節點，有：C(ni,nj)>

其中為大于0常數幾個等式f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節點，t是目標節點，n是s到t最正確路徑上節點。62人工智能搜索問題第62頁A*算法性質（續1）定理1.1： 對有限圖，假如從初始節點s到目標節點t有路徑存在，則算法A一定成功結束。63人工智能搜索問題第63頁A*算法性質（續2）引理1.1： 對無限圖，若有從初始節點s到目標節點t路徑，則A*不結束時，在OPEN表中即使最小一個f值也將增到任意大，或有f(n)>f*(s)。64人工智能搜索問題第64頁A*算法性質（續3）引理1.2： A*結束前，OPEN表中必存在f(n)≤f*(s)。存在一個節點n，n在最正確路徑上。f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n)=f*(s)65人工智能搜索問題第65頁A*算法性質（續3）定理1.2： 對無限圖，若從初始節點s到目標節點t有路徑存在，則A*一定成功結束。引理1.1：A*假如不結束，則OPEN中全部n有f(n)>f*(s)引理1.2：在A*結束前，必存在節點n，使得f(n)≤f*(s)所以，假如A*不結束，將造成矛盾。66人工智能搜索問題第66頁A*算法性質（續4）推論1.1： OPEN表上任一含有f(n)<f*(s)節點n，最終都將被A*選作擴展節點。

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

在定理1.4中，評價指標是“擴展節點數”，也就是說，同一個節點不論被擴展多少次，都只計算一次。72人工智能搜索問題第72頁定理1.4證實使用數學歸納法，對節點深度進行歸納（1）當d(n)＝0時，即只有一個節點，顯然定理成立。（2）設d(n)≤k時定理成立。（歸納假設）（3）當d(n)=k+1時，用反證法。設存在一個深度為k＋1節點n，被A2擴展，但沒有被A1擴展。而由假設，A1擴展了n父節點，即n已經被生成了。所以當A1結束時，n將被保留在OPEN中。73人工智能搜索問題第73頁定理1.4證實（續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擴展節點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人工智能搜索問題第74頁對h評價方法平均分叉樹 設共擴展了d層節點，共搜索了N個節點，則:

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

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