人工智能導論課程電子教案

第一章 產(chǎn)生式系統(tǒng)l1943年P(guān)ost首先在一種計算形式體系中提出l60年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu)l形式上很簡單，但在一定意義上模仿了人類思考的過程11.1 產(chǎn)生式系統(tǒng)的基本組成l組成三要素：一個綜合數(shù)據(jù)庫存放信息一組產(chǎn)生式規(guī)則知識一個控制系統(tǒng)規(guī)則的解釋或執(zhí)行程序 （控制策略）（推理引擎）2規(guī)則的一般形式lIF THEN lIF THEN l或者簡寫為：31.2 產(chǎn)生式系統(tǒng)的基本過程過程PRODUCTION1，DATA初始數(shù)據(jù)庫2，until DATA滿足結(jié)束條件，do3，4，在規(guī)則集中選擇一條可應用于DATA 的規(guī)則R5，DATA R應用到DATA得到的結(jié)果6，4一個簡單的例子l問題：設字符轉(zhuǎn)換規(guī)則ABCACDBCGBEFDE已知：A，B求：F5一個簡單的例子（續(xù)1）一、綜合數(shù)據(jù)庫x，其中x為字符二、規(guī)則集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E6一個簡單的例子（續(xù)2）三、控制策略順序排隊四、初始條件A，B五、結(jié)束條件Fx7求解過程數(shù)據(jù)庫可觸發(fā)規(guī)則被觸發(fā)規(guī)則A，B（1）（1）A，B，C（2）（3）（2）A，B，C，D（3）（5）（3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F(xiàn)1，IF AB THEN C 2，IF AC THEN D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E81.3 問題表示舉例例1：傳教士與野人問題（M-C問題）問題：N個傳教士，N個野人，一條船，可同時乘坐k個人，要求在任何時刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。問：如何過河。以N=3，k=2為例求解。9M-C問題（續(xù)1）初始 目標 L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 110M-C問題（續(xù)2）1，綜合數(shù)據(jù)庫 （m,c,b)，其中：0m,c3,b 0,12，初始狀態(tài) （3，3，1）3，目標狀態(tài)（結(jié)束狀態(tài)）（0，0，0）11M-C問題（續(xù)3）4，規(guī)則集IF(m,c,1)THEN(m-1,c,0)IF(m,c,1)THEN(m,c-1,0)IF(m,c,1)THEN(m-1,c-1,0)IF(m,c,1)THEN(m-2,c,0)IF(m,c,1)THEN(m,c-2,0)12M-C問題（續(xù)4）IF(m,c,0)THEN(m+1,c,1)IF(m,c,0)THEN(m,c+1,1)IF(m,c,0)THEN(m+1,c+1,1)IF(m,c,0)THEN(m+2,c,1)IF(m,c,0)THEN(m,c+2,1)5，控制策略：（略）13M-C問題（第二種方法）4，規(guī)則集：IF(m,c,1)AND 1 i+j2 THEN(m-i,c-j,0)IF(m,c,0)AND 1 i+j2 THEN(m+i,c+j,1)14猴子摘香蕉問題 c a b15猴子摘香蕉問題（續(xù)1）1，綜合數(shù)據(jù)庫（M,B,Box,On,H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子沒有抓到香蕉H=1：猴子抓到了香蕉16猴子摘香蕉問題（續(xù)2）2，初始狀態(tài)（c,a,b,0,0）3，結(jié)束狀態(tài)（x1,x2,x3,x4,1）其中x1x4為變量。17猴子摘香蕉問題（續(xù)3）4，規(guī)則集r1:IF (x,y,z,0,0)THEN (w,y,z,0,0)r2:IF (x,y,x,0,0)THEN (z,y,z,0,0)r3:IF (x,y,x,0,0)THEN (x,y,x,1,0)r4:IF (x,y,x,1,0)THEN (x,y,x,0,0)r5:IF (x,x,x,1,0)THEN (x,x,x,1,1)其中x,y,z,w為變量181.4 產(chǎn)生式系統(tǒng)的特點l數(shù)據(jù)驅(qū)動l知識的無序性l控制系統(tǒng)與問題無關(guān)l數(shù)據(jù)、知識和控制相互獨立191.5 產(chǎn)生式系統(tǒng)的類型l正向、逆向、雙向產(chǎn)生式系統(tǒng)l可交換的產(chǎn)生式系統(tǒng)l可分解的產(chǎn)生式系統(tǒng)20第二章 產(chǎn)生式系統(tǒng)的搜索策略l內(nèi)容：狀態(tài)空間的搜索問題。l搜索方式：盲目搜索啟發(fā)式搜索l關(guān)鍵問題：如何利用知識，盡可能有效地找到問題的解（最佳解）。21產(chǎn)生式系統(tǒng)的搜索策略（續(xù)1）S0Sg22產(chǎn)生式系統(tǒng)的搜索策略（續(xù)2）l討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。232.1 回溯策略l例：皇后問題24()25()Q(1,1)26()QQ(1,1)(1,1)(2,3)27()Q(1,1)(1,1)(2,3)28()QQ(1,1)(1,1)(2,3)(1,1)(2,4)29()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)30()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)31()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)32()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)33()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)34()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)35()(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)36()(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)37遞歸的思想當前狀態(tài)目標狀態(tài)g38一個遞歸的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST12339回溯搜索算法BACKTRACK（DATA）DATA：當前狀態(tài)。返回值：從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。40回溯搜索算法遞歸過程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);4,LOOP:IF NULL(RULES)RETURN FAIL;5,R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,RDATA:=GEN(R,DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R,PATH);41存在問題及解決辦法l解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當前狀態(tài)的路徑當前狀態(tài)l問題：深度問題死循環(huán)問題42回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：從初始到當前的狀態(tài)表（逆向）返回值：從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。43回溯搜索算法11,DATA:=FIRST(DATALIST)2,IF MENBER(DATA,TAIL(DATALIST)RETURN FAIL;3,IF TERM(DATA)RETURN NIL;4,IF DEADEND(DATA)RETURN FAIL;5,IF LENGTH(DATALIST)BOUND RETURN FAIL;6,RULES:=APPRULES(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);44回溯搜索算法1（續(xù)）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R,DATA);11,RDATALIST:=CONS(RDATA,DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R,PATH);45一些深入的問題l失敗原因分析、多步回溯QQ46一些深入問題（續(xù)）l回溯搜索中知識的利用基本思想(以皇后問題為例)：盡可能選取劃去對角線上位置數(shù)最少的。QQQQ3 2 2 3472.2 圖搜索策略l問題的引出回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。48一些基本概念l節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+1012349一些基本概念（續(xù)1）l路徑設一節(jié)點序列為(n0,n1,nk)，對于i=1,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。l路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。50一些基本概念（續(xù)1）l擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。51一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF OPEN=()THEN EXIT(FAIL);4,n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IF GOAL(n)THEN EXIT(SUCCESS);6,EXPAND(n)mi,G:=ADD(mi,G);52一般的圖搜索算法（續(xù)）7,標記和修改指針：ADD(mj,OPEN),并標記mj到n的指針；計算是否要修改mk、ml到n的指針；計算是否要修改ml到其后繼節(jié)點的指針；8,對OPEN中的節(jié)點按某種原則重新排序；9,GO LOOP；53節(jié)點類型說明.mjmkml54修改指針舉例123456s55修改指針舉例（續(xù)1）123456s56123456修改指針舉例（續(xù)2）s57123456修改指針舉例（續(xù)3）s582.3 無信息圖搜索過程l深度優(yōu)先搜索l寬度優(yōu)先搜索59深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IF DEPTH(n)Dm GO LOOP;7,EXPAND(n)mi,G:=ADD(mi,G);8,IF 目標在mi中 THEN EXIT(SUCCESS);9,ADD(mj,OPEN),并標記mj到n的指針;10,GO LOOP;602 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標61深度優(yōu)先搜索的性質(zhì)l一般不能保證找到最優(yōu)解l當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制l最壞情況時，搜索空間等同于窮舉l與回溯法的差別：圖搜索l是一個通用的與問題無關(guān)的方法62寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,G:=ADD(mi,G);7,IF 目標在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并標記mj到n的指針;9,GO LOOP;632 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標82 3 41 8 7 6 5464寬度優(yōu)先搜索的性質(zhì)l當問題有解時，一定能找到解l當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解l方法與問題無關(guān)，具有通用性l效率較低l屬于圖搜索方法65漸進式深度優(yōu)先搜索方法l目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。l思想首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。662.4 啟發(fā)式圖搜索l利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。l啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最 優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解67希望：l引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。68基本思想l定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。691，啟發(fā)式搜索算法A（A算法）l評價函數(shù)的格式：f(n)=g(n)+h(n)f(n)：評價函數(shù)h(n)：啟發(fā)函數(shù)70符號的意義lg*(n)：從s到n的最短路徑的耗散值lh*(n)：從n到g的最短路徑的耗散值lf*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑的耗散值lg(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值71A算法1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)mi,計算f(n,mi):=g(n,mi)+h(mi);72A算法（續(xù)）ADD(mj,OPEN),標記mj到n的指針；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),標記mk到n的指針；IF f(n,ml)其中為大于0的常數(shù)l幾個等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點，t是目標節(jié)點，n是s到t的最佳路徑上的節(jié)點。81A*算法的性質(zhì)（續(xù)1）定理1：對有限圖，如果從初始節(jié)點s到目標節(jié)點t有路徑存在，則算法A一定成功結(jié)束。82A*算法的性質(zhì)（續(xù)2）引理2.1：對無限圖，若有從初始節(jié)點s到目標節(jié)點t的路徑，則A*不結(jié)束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)f*(s)。83A*算法的性質(zhì)（續(xù)3）引理2.2：A*結(jié)束前，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)84A*算法的性質(zhì)（續(xù)3）定理2：對無限圖，若從初始節(jié)點s到目標節(jié)點t有路徑存在，則A*一定成功結(jié)束。引理2.1：A*如果不結(jié)束，則OPEN中所有的n有f(n)f*(s)引理2.2：在A*結(jié)束前，必存在節(jié)點n，使得 f(n)f*(s)所以，如果A*不結(jié)束，將導致矛盾。85A*算法的性質(zhì)（續(xù)4）推論2.1：OPEN表上任一具有f(n)f*(s)的節(jié)點n，最終都將被A*選作擴展的節(jié)點。由定理2，知A*一定結(jié)束，由A*的結(jié)束條件，OPEN表中f(t)最小時才結(jié)束。而 f(t)f*(t)f*(s)所以f(n)f*(s)l由引理2.2知結(jié)束前OPEN中存在f(n)f*(s)的節(jié)點n，所以 f(n)f*(s)h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n)h1(n)(目標節(jié)點除外)，則A1擴展的節(jié)點數(shù)A2擴展的節(jié)點數(shù)90A*算法的性質(zhì)（續(xù)7）l注意：在定理4中，評價指標是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只計算一次。91定理4的證明l使用數(shù)學歸納法，對節(jié)點的深度進行歸納l（1）當d(n)0時，即只有一個節(jié)點，顯然定理成立。l（2）設d(n)k時定理成立。（歸納假設）l（3）當d(n)=k+1時，用反證法。l設存在一個深度為k1的節(jié)點n，被A2擴展，但沒有被A1擴展。而由假設，A1擴展了n的父節(jié)點，即n已經(jīng)被生成了。因此當A1結(jié)束時，n將被保留在OPEN中。92定理4的證明（續(xù)1）l所以有：f1(n)f*(s)l 即：g1(n)+h1(n)f*(s)l所以：h1(n)f*(s)-g1(n)l另一方面，由于A2擴展了n，有f2(n)f*(s)l即：h2(n)f*(s)g2(n)(A)l由于d(n)=k時，A2擴展的節(jié)點A1一定擴展，有 g1(n)g2(n)(因為A2的路A1均走到了)l所以：h1(n)f*(s)-g1(n)f*(s)g2(n)(B)l比較A、B兩式，有 h1(n)h2(n)，與定理條件矛盾。故定理得證。93對h的評價方法l平均分叉樹設共擴展了d層節(jié)點，共搜索了N個節(jié)點，則:其中，b*稱為平均分叉樹。lb*越小，說明h效果越好。l實驗表明，b*是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。94對h的評價舉例例：8數(shù)碼問題，隨機產(chǎn)生若干初始狀態(tài)。l使用h1：d=14,N=539,b*=1.44;d=20,N=7276，b*=1.47；l使用h2：d=14,N=113,b*=1.23;d=20,N=676,b*=1.2795A*的復雜性l一般來說，A*的算法復雜性是指數(shù)型的，可以證明，當且僅當以下條件成立時：abs(h(n)-h*(n)O(log(h*(n)A*的算法復雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標的距離成正比的。963，A*算法的改進l問題的提出：因A算法第6步對ml類節(jié)點可能要重新放回到OPEN表中，因此可能會導致多次重復擴展同一個節(jié)點，導致搜索效率下降。97s(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)98出現(xiàn)多次擴展節(jié)點的原因l在前面的擴展中，并沒有找到從初始節(jié)點到當前節(jié)點的最短路徑，如節(jié)點A。s(10)A(1)B(5)C(8)G 目標63111899解決的途徑l對h加以限制能否對h增加適當?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑。l對算法加以改進能否對算法加以改進，避免或減少節(jié)點的多次擴展。100改進的條件l可采納性不變l不多擴展節(jié)點l不增加算法的復雜性101對h加以限制l定義：一個啟發(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)102h單調(diào)的性質(zhì)l定理5：若h(n)是單調(diào)的，則A*擴展了節(jié)點n之后，就已經(jīng)找到了到達節(jié)點n的最佳路徑。即：當A*選n擴展時，有g(shù)(n)=g*(n)。103定理5的證明l設n是A*擴展的任一節(jié)點。當ns時，定理顯然成立。下面考察n s的情況。l設P(n0=s,n1,n2,nk=n)是s到n的最佳路徑lP中一定有節(jié)點在CLOSED中，設P中最后一個出現(xiàn)在CLOSED中的節(jié)點為nj，則nj+1在OPEN中。104定理5的證明（續(xù)1）l由單調(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)l由于ni、ni+1在最佳路徑上，所以：g*(ni+1)=g*(ni)+C(ni,ni+1)l帶入上式有：g*(ni)+h(ni)g*(ni+1)+h(ni+1)l從i=j到i=k-1應用上不等式，有：g*(nj+1)+h(nj+1)g*(nk)+h(nk)l即：f(nj+1)g*(n)+h(n)注意：(nj在CLOSED中，nj+1在OPEN中)105定理5的證明（續(xù)2）l重寫上式：f(nj+1)g*(n)+h(n)l另一方面，A*選n擴展，必有：f(n)=g(n)+h(n)f(nj+1)l比較兩式，有：g(n)g*(n)l但已知g*(n)是最佳路徑的耗散值，所以只有：g(n)=g*(n)。得證。106h單調(diào)的性質(zhì)（續(xù)）l定理6：若h(n)是單調(diào)的，則由A*所擴展的節(jié)點序列其f值是非遞減的。即f(ni)f(nj)。107定理6的證明l由單調(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，得證。108h單調(diào)的例子l8數(shù)碼問題：h為“不在位”的將牌數(shù) 1h(ni)-h(nj)=0(nj為ni的后繼節(jié)點)-1 h(t)=0c(ni,nj)=1 滿足單調(diào)的條件。109對算法加以改進l一些結(jié)論：OPEN表上任以具有f(n)f*(s)的節(jié)點定會被擴展。A*選作擴展的任一節(jié)點，定有f(n)f*(s)。110改進的出發(fā)點OPEN=()f*(s)f值小于f*(s)的節(jié)點f值大于等于f*(s)的節(jié)點fm：到目前為止已擴展節(jié)點的最大f值，用fm代替f*(s)111修正過程A1,OPEN:=(s),f(s)=g(s)+h(s),fm:=0;2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,NEST:=ni|f(ni)fmIF NEST ()THEN n:=NEST中g(shù)最小的節(jié)點 ELSE n:=FIRST(OPEN),fm:=f(n);4,8:同過程A。112s(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)113h的單調(diào)化方法l如果令：f(n)=max(f(n的父節(jié)點),g(n)+h(n)則容易證明，這樣處理后的h是單調(diào)的。114IDA*算法(Iterative Deepening A*)l基本思想：回溯與A*的結(jié)合l算法簡介（非嚴格地）1，設初始值f0；2，集合SNULL；3，用回溯法求解問題，如果節(jié)點n的f值大于f0，則將該節(jié)點放入集合S中，并回溯；4，如果在3中找到了解，則結(jié)束；5，如果3以失敗結(jié)束，則f0S中節(jié)點的最小f值；6，返回到2。115知識的靈活應用例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為12。13551441332523123122552342543433分析：陰影部分數(shù)字和：48 直徑部分數(shù)字和：24 轉(zhuǎn)45改變陰影部分 轉(zhuǎn)90改變直徑部分 但不改變陰影部分 轉(zhuǎn)180改變扇區(qū)部分 但不改變陰影部分 也不改變直徑部分1164，其他的搜索算法l爬山法（局部搜索算法）117其他的搜索算法（續(xù)1）l隨機搜索算法l動態(tài)規(guī)劃算法如果對于任何n，當h(n)=0時，A*算法就成為了動態(tài)規(guī)劃算法。118動態(tài)規(guī)劃S0tS1S2S3SnW0W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+1119其中：Q(Wij)表示到點Wij的最佳路徑值 D(Wi-1,j,Wi,k)表示W(wǎng)i-1,j到Wi,k的距離1205，搜索算法實用舉例l漢字識別后處理l一個例子我錢線載哦栽哉裁劣綏優(yōu)仍們仿倫奶砧犯扔妨要耍密窮安壁駐努窯垂扳報叔嵌奴振技寂敘蔽奮夯杏蠶香脊秀吞吝番精猜指潔括治捐活冶桔種神襯祥科鐘拌樣拎補 121漢字識別后處理二元語法時：為常量用識別信度代替問題變?yōu)榍笞畲?22第三章 與或圖的搜索目標目標初始節(jié)點sabc1233.1 基本概念l與或圖是一個超圖，節(jié)點間通過連接符連接。lK-連接符：.K個124耗散值的計算k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N為終節(jié)點集 Cn為連接符的耗散值.i個nn1n2ni125目標目標初始節(jié)點 解圖：126能解節(jié)點l終節(jié)點是能解節(jié)點l若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。l若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。127不能解節(jié)點l沒有后裔的非終節(jié)點是不能解節(jié)點。l若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。l若非終節(jié)點有“與”子節(jié)點時，當至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。128普通圖的情況f(n)=g(n)+h(n)對n的評價實際是對從s到n這條路徑的評價ns129與或圖:對局部圖的評價目標目標初始節(jié)點abc130兩個過程l圖生成過程，即擴展節(jié)點從最優(yōu)的局部途中選擇一個節(jié)點擴展l計算耗散值的過程對當前的局部圖新計算耗散值131AO*算法舉例其中：h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0設：K連接符的耗散值為K目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8132目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n1(2)n4(1)n5(1)紅色：4黃色：3133目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5134目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2135目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)211363.3 博弈樹搜索l博弈問題雙人一人一步雙方信息完備零和137分錢幣問題（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）對方先走我方必勝138中國象棋l一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。l假設1毫微秒走一步，約需10的145次方年。l結(jié)論：不可能窮舉。1391，極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011極大極小ab140-剪枝l極大節(jié)點的下界為。l極小節(jié)點的上界為。l剪枝的條件：后輩節(jié)點的值祖先節(jié)點的值時，剪枝后輩節(jié)點的 值祖先節(jié)點的值時，剪枝l簡記為：極小極大，剪枝極大極小，剪枝141-剪枝（續(xù)）05-333-3022-30-23541-30689-300-303305411-31661abcdefghijkmn142-剪枝的其他應用l故障診斷 A B C Dl風險投資143