《人工智能導(dǎo)論課程電子教案》由會員分享，可在線閱讀，更多相關(guān)《人工智能導(dǎo)論課程電子教案（143頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、第一章 產(chǎn)生式系統(tǒng)l1943年P(guān)ost首先在一種計(jì)算形式體系中提出l60年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu)l形式上很簡單，但在一定意義上模仿了人類思考的過程11.1 產(chǎn)生式系統(tǒng)的基本組成l組成三要素：一個(gè)綜合數(shù)據(jù)庫存放信息一組產(chǎn)生式規(guī)則知識一個(gè)控制系統(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ī)則集中選擇一條可應(yīng)用于DATA 的規(guī)則R5，DATA R應(yīng)用到DATA得到的結(jié)果6，4一個(gè)簡單的例子l問

2、題：設(shè)字符轉(zhuǎn)換規(guī)則ABCACDBCGBEFDE已知：A，B求：F5一個(gè)簡單的例子（續(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一個(gè)簡單的例子（續(xù)2）三、控制策略順序排隊(duì)四、初始條件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 THE

3、N D3，IF BC THEN G 4，IF BE THEN F5，IF D THEN E81.3 問題表示舉例例1：傳教士與野人問題（M-C問題）問題：N個(gè)傳教士，N個(gè)野人，一條船，可同時(shí)乘坐k個(gè)人，要求在任何時(shí)刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。問：如何過河。以N=3，k=2為例求解。9M-C問題（續(xù)1）初始 目標(biāo) 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，目標(biāo)狀態(tài)（結(jié)束狀態(tài)）（0，0，0）11M-C問題（續(xù)3）4，規(guī)則集I

4、F(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)I

5、F(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:I

6、F (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)的特點(diǎn)l數(shù)據(jù)驅(qū)動(dòng)l知識的無序性l控制系統(tǒng)與問題無關(guān)l數(shù)據(jù)、知識和控制相互獨(dú)立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）S0Sg

7、22產(chǎn)生式系統(tǒng)的搜索策略（續(xù)2）l討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。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,

8、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

9、(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)37遞歸的思想當(dāng)前狀態(tài)目標(biāo)狀態(tài)g38一個(gè)遞歸的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLength(pList-next)+1;NULLpLIST12339回溯搜索算法BACKTRACK（DATA）DATA：當(dāng)前狀態(tài)。返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。40回溯搜索算法遞歸過程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADE

10、ND(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)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)l問題：深度問題死循環(huán)問題42回溯搜索算法1BACKTRACK1（DATALIST）DATAL

11、IST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(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回

12、溯搜索算法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)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有

13、已經(jīng)搜索過的路徑。48一些基本概念l節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+1012349一些基本概念（續(xù)1）l路徑設(shè)一節(jié)點(diǎn)序列為(n0,n1,nk)，對于i=1,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。l路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。50一些基本概念（續(xù)1）l擴(kuò)展一個(gè)節(jié)點(diǎn)生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。51一般的圖搜索算法1,G=G0(G0=s),OPEN:=(s);2,CLOSED:=();3,LOOP:IF

14、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,標(biāo)記和修改指針：ADD(mj,OPEN),并標(biāo)記mj到n的指針；計(jì)算是否要修改mk、ml到n的指針；計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GO LOOP；53節(jié)點(diǎn)類型說明.mjmkml54修改指針舉例123456s55修改指針舉例（續(xù)1）123456s56123456修

15、改指針舉例（續(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 目標(biāo)在mi中 THEN EXIT(SUCCESS);9,ADD(

16、mj,OPEN),并標(biāo)記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

17、52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標(biāo)61深度優(yōu)先搜索的性質(zhì)l一般不能保證找到最優(yōu)解l當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制l最壞情況時(shí)，搜索空間等同于窮舉l與回溯法的差別：圖搜索l是一個(gè)通用的與問題無關(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,EXP

18、AND(n)mi,G:=ADD(mi,G);7,IF 目標(biāo)在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并標(biāo)記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

19、 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 5464寬度優(yōu)先搜索的性質(zhì)l當(dāng)問題有解時(shí)，一定能找到解l當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解l方法與問題無關(guān)，具有通用性l效率較低l屬于圖搜索方法65漸進(jìn)式深度優(yōu)先搜索方法l目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。l思想首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。662.4 啟發(fā)式圖搜索l利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。l啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可

20、能可以找到最優(yōu)解67希望：l引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。68基本思想l定義一個(gè)評價(jià)函數(shù)f，對當(dāng)前的搜索狀態(tài)進(jìn)行評估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展。691，啟發(fā)式搜索算法A（A算法）l評價(jià)函數(shù)的格式：f(n)=g(n)+h(n)f(n)：評價(jià)函數(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)的估計(jì)值71A算法1,OPEN:=(s),f(s):=g(

21、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,計(jì)算f(n,mi):=g(n,mi)+h(mi);72A算法（續(xù)）ADD(mj,OPEN),標(biāo)記mj到n的指針；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),標(biāo)記mk到n的指針；IF f(n,ml)其中為大于0的常數(shù)l幾個(gè)等式 f*(s)=f*(t)=h*(s)=g*(t)=f*(n)其中s是初始節(jié)點(diǎn)，t是

22、目標(biāo)節(jié)點(diǎn)，n是s到t的最佳路徑上的節(jié)點(diǎn)。81A*算法的性質(zhì)（續(xù)1）定理1：對有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。82A*算法的性質(zhì)（續(xù)2）引理2.1：對無限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)f*(s)。83A*算法的性質(zhì)（續(xù)3）引理2.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)84A*算法的性質(zhì)（續(xù)3）定理2：對無限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)

23、點(diǎn)t有路徑存在，則A*一定成功結(jié)束。引理2.1：A*如果不結(jié)束，則OPEN中所有的n有f(n)f*(s)引理2.2：在A*結(jié)束前，必存在節(jié)點(diǎn)n，使得 f(n)f*(s)所以，如果A*不結(jié)束，將導(dǎo)致矛盾。85A*算法的性質(zhì)（續(xù)4）推論2.1：OPEN表上任一具有f(n)f*(s)的節(jié)點(diǎn)n，最終都將被A*選作擴(kuò)展的節(jié)點(diǎn)。由定理2，知A*一定結(jié)束，由A*的結(jié)束條件，OPEN表中f(t)最小時(shí)才結(jié)束。而 f(t)f*(t)f*(s)所以f(n)f*(s)l由引理2.2知結(jié)束前OPEN中存在f(n)f*(s)的節(jié)點(diǎn)n，所以 f(n)f*(s)h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，

24、由A2所擴(kuò)展的每一個(gè)節(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ù)90A*算法的性質(zhì)（續(xù)7）l注意：在定理4中，評價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說，同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次，都只計(jì)算一次。91定理4的證明l使用數(shù)學(xué)歸納法，對節(jié)點(diǎn)的深度進(jìn)行歸納l（1）當(dāng)d(n)0時(shí)，即只有一個(gè)節(jié)點(diǎn)，顯然定理成立。l（2）設(shè)d(n)k時(shí)定理成立。（歸納假設(shè)）l（3）當(dāng)d(n)=k+1時(shí)，用反證法。l設(shè)存在一個(gè)深度為k1的節(jié)點(diǎn)n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父節(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)

25、A1結(jié)束時(shí)，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擴(kuò)展了n，有f2(n)f*(s)l即：h2(n)f*(s)g2(n)(A)l由于d(n)=k時(shí)，A2擴(kuò)展的節(jié)點(diǎn)A1一定擴(kuò)展，有 g1(n)g2(n)(因?yàn)锳2的路A1均走到了)l所以：h1(n)f*(s)-g1(n)f*(s)g2(n)(B)l比較A、B兩式，有 h1(n)h2(n)，與定理?xiàng)l件矛盾。故定理得證。93對h的評價(jià)方法l平均分叉樹設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個(gè)節(jié)點(diǎn)，則:其中，b*稱為平均分叉樹

26、。lb*越小，說明h效果越好。l實(shí)驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。94對h的評價(jià)舉例例：8數(shù)碼問題，隨機(jī)產(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*的復(fù)雜性l一般來說，A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)：abs(h(n)-h*(n)O(log(h*(n)A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下，h與h*的差別至少是和離目標(biāo)的距離成正比的。963，A*算法的改進(jìn)l問題的提出：因

27、A算法第6步對ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。97s(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)98出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因l在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)

28、點(diǎn)A。s(10)A(1)B(5)C(8)G 目標(biāo)63111899解決的途徑l對h加以限制能否對h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。l對算法加以改進(jìn)能否對算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。100改進(jìn)的條件l可采納性不變l不多擴(kuò)展節(jié)點(diǎn)l不增加算法的復(fù)雜性101對h加以限制l定義：一個(gè)啟發(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)102h單調(diào)的性質(zhì)l定理5：若h(n)是單

29、調(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)。103定理5的證明l設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)ns時(shí)，定理顯然成立。下面考察n s的情況。l設(shè)P(n0=s,n1,n2,nk=n)是s到n的最佳路徑lP中一定有節(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的節(jié)點(diǎn)為nj，則nj+1在OPEN中。104定理5的證明（續(xù)1）l由單調(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)l由于ni、ni+1在最佳路徑上，所以：g*(n

30、i+1)=g*(ni)+C(ni,ni+1)l帶入上式有：g*(ni)+h(ni)g*(ni+1)+h(ni+1)l從i=j到i=k-1應(yīng)用上不等式，有：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擴(kuò)展，必有：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

31、)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其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é)點(diǎn))-1 h(t)=0c(ni,nj)=1 滿足單調(diào)的條件。109對算法加以改進(jìn)l一些結(jié)論

32、：OPEN表上任以具有f(n)f*(s)的節(jié)點(diǎn)定會被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)f*(s)。110改進(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)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é)點(diǎn) ELSE n:=FIRST(OPEN),fm:=f(n);4,8:同過程A。112s(10)A(1

33、)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)113h的單調(diào)化方法l如果令：f(n)=max(f(n的父節(jié)點(diǎn)),g(n)+h(n)則容易證明，這樣處理后的h是單調(diào)的。114IDA*算法(Iterative Deepening A*)l基本思想：回溯與A*的結(jié)合l算法簡介（非嚴(yán)格地）1，設(shè)初始值f0；2，集合SNULL；3，

34、用回溯法求解問題，如果節(jié)點(diǎn)n的f值大于f0，則將該節(jié)點(diǎn)放入集合S中，并回溯；4，如果在3中找到了解，則結(jié)束；5，如果3以失敗結(jié)束，則f0S中節(jié)點(diǎn)的最小f值；6，返回到2。115知識的靈活應(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ū)部分 但不改變陰影部分 也不改變直徑部分1164，其他的搜索算法l爬山法（局部搜索算法）117其他的搜索算法（續(xù)1）l隨機(jī)搜索算法l動(dòng)態(tài)規(guī)劃算法如果對于任何n，當(dāng)h(n)=0時(shí)，A*

35、算法就成為了動(dòng)態(tài)規(guī)劃算法。118動(dòng)態(tài)規(guī)劃S0tS1S2S3SnW0W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+1119其中：Q(Wij)表示到點(diǎn)Wij的最佳路徑值 D(Wi-1,j,Wi,k)表示W(wǎng)i-1,j到Wi,k的距離1205，搜索算法實(shí)用舉例l漢字識別后處理l一個(gè)例子我錢線載哦栽哉裁劣綏優(yōu)仍們仿倫奶砧犯扔妨要耍密窮安壁駐努窯垂扳報(bào)叔嵌奴振技寂敘蔽奮夯杏蠶香脊秀吞吝番精猜指潔括治捐活冶桔種神襯祥科鐘拌樣拎補(bǔ) 121漢字識別后處理二元語法時(shí)：為常量用識別信度代替問題變?yōu)榍笞畲?22第三章 與或圖的搜索目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc1233.1 基

36、本概念l與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過連接符連接。lK-連接符：.K個(gè)124耗散值的計(jì)算k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N為終節(jié)點(diǎn)集 Cn為連接符的耗散值.i個(gè)nn1n2ni125目標(biāo)目標(biāo)初始節(jié)點(diǎn) 解圖：126能解節(jié)點(diǎn)l終節(jié)點(diǎn)是能解節(jié)點(diǎn)l若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí)，該非終節(jié)點(diǎn)才能解。l若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。127不能解節(jié)點(diǎn)l沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。l若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解。l若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時(shí)，當(dāng)至少有一個(gè)子節(jié)點(diǎn)不能解時(shí)，該

37、非終節(jié)點(diǎn)才不能解。128普通圖的情況f(n)=g(n)+h(n)對n的評價(jià)實(shí)際是對從s到n這條路徑的評價(jià)ns129與或圖:對局部圖的評價(jià)目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc130兩個(gè)過程l圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展l計(jì)算耗散值的過程對當(dāng)前的局部圖新計(jì)算耗散值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設(shè)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8132目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n1(2)n4

38、(1)n5(1)紅色：4黃色：3133目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)n0n4(1)n5(1)紅色：4黃色：6n1n2(4)n3(4)5134目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2135目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)211363.3 博弈樹搜索l博弈問題雙人一人一步雙方信息完備零和137分錢幣問題（7）（6,1）（5,2）（

39、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假設(shè)1毫微秒走一步，約需10的145次方年。l結(jié)論：不可能窮舉。1391，極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011極大極小ab140-剪枝l極大節(jié)點(diǎn)的下界為。l極小節(jié)點(diǎn)的上界為。l剪枝的條件：后輩節(jié)點(diǎn)的值祖先節(jié)點(diǎn)的值時(shí)，剪枝后輩節(jié)點(diǎn)的 值祖先節(jié)點(diǎn)的值時(shí)，剪枝l簡記為：極小極大，剪枝極大極小，剪枝141-剪枝（續(xù)）05-333-3022-30-23541-30689-300-303305411-31661abcdefghijkmn142-剪枝的其他應(yīng)用l故障診斷 A B C Dl風(fēng)險(xiǎn)投資143