清華大學《人工智能導論》課程電子教案(一)課件

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

1、單擊此處編輯母版標題樣式,,,*,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,第一章 產(chǎn)生式系統(tǒng),,1943,年,Post,首先在一種計算形式體系中提出,,60,年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu),,形式上很簡單，但在一定意義上模仿了人類思考的過程,,,,,1,,1.1,產(chǎn)生式系統(tǒng)的基本組成,,組成三要素：,,,一個綜合數(shù)據(jù)庫,——,存放信息,,一組產(chǎn)生式規(guī)則,——,知識,,一個控制系統(tǒng),——,規(guī)則的解釋或執(zhí)行程序 （控制策略） （推理引擎）,,2,,規(guī)則的一般形式,,

2、IF <,前提,> THEN <,結(jié)論,>,,IF <,條件,> THEN <,行動,>,,或者簡寫為：,,,<,前提,>,－,> <,結(jié)論,>,,<,條件,>,－,> <,行動,>,,3,,1.2,產(chǎn)生式系統(tǒng)的基本過程,,過程,PRODUCTION,,1,，,DATA←,初始數(shù)據(jù)庫,,2，,until DATA,滿足結(jié)束條件，,do,,3,，,{,,4,，,在規(guī)則集中選擇一條可應用于,DATA,的規(guī)則,R,,5,，,DATA ←R,應用到,DATA,得到的結(jié)果,,6,，,},,4,,一個簡單的例子,,問題：設(shè)字符轉(zhuǎn)換規(guī)則,,,A∧B→C,,A∧C→D,,B∧C→G,,B∧E→

3、F,,D→E,,,已知：,A,，,B,,,求：,F,,5,,一個簡單的例子（續(xù),1,）,,一、綜合數(shù)據(jù)庫,,,{x},，,其中,x,為字符,,二、規(guī)則集,,,,1，IF A∧B THEN C,,2，IF A∧C THEN D,,3，IF B∧C THEN G,,4，IF B∧E THEN F,,5，IF D THEN E,,6,,一個簡單的例子（續(xù),2,）,,三、控制策略,,順序排隊,,四、初始條件,,,{A,，,B},,五、結(jié)束條件,,,F∈{x},,7,,求解過程,數(shù)據(jù)庫 可觸發(fā)規(guī)則 被觸發(fā)規(guī)則,A，B,（1）,（1）,A，B，C,（,2,）

4、（,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 A∧B THEN C 2，IF A∧C THEN D,,3，IF B∧C THEN G 4，IF B∧E THEN F,,5，IF D THEN E,,8,,1 .3,問題表示舉例,,例,1,：傳教士與野人問題（,M-C,問題）,,問題,：,N,個傳教士，,N,個野人，一條船，可同時乘坐,k,個人，要求在任何時刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。,,問：

5、如何過河。,,,以,N=3,，,k=2,為例求解。,,,9,,M-C,問題（續(xù),1,）,,,,初始 目標,,,L R L R,,m 3 0 m 0 3,,c 3 0 c 0 3,,B 1 0 B 0

6、 1,,10,,M-C,問題（續(xù),2,）,,1,，綜合數(shù)據(jù)庫,,（,m, c, b),，,,,其中：,0≤m, c≤3, b ∈{0, 1},,2,，,初始狀態(tài),,（,3,，,3,，,1,）,,3,，目標狀態(tài)（結(jié)束狀態(tài)）,,（,0,，,0,，,0,）,,,11,,M-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)

7、THEN (m, c-2, 0),,12,,M-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,，,控制策略：（略）,,13,,M-C,問題（第二種方法）,,4,，規(guī)則集：,,,,IF (m, c, 1) AND 1 ≤i+j≤2 THEN (m-i, c-j, 0),,IF (m, c, 0) A

8、ND 1 ≤i+j≤2 THEN (m+i, c+j, 1),,,14,,猴子摘香蕉問題,,,,,,,,c a b,,15,,猴子摘香蕉問題（續(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),,（,x,1

9、,, x,2,, x,3,, x,4,, 1,）,,,其中,x,1,～,x,4,為變量。,,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,

10、x, x, 1, 1),,,其中,x, y, z, w,為變量,,18,,1.4,產(chǎn)生式系統(tǒng)的特點,,數(shù)據(jù)驅(qū)動,,知識的無序性,,控制系統(tǒng)與問題無關(guān),,數(shù)據(jù)、知識和控制相互獨立,,,19,,1.5,產(chǎn)生式系統(tǒng)的類型,,正向、逆向、雙向產(chǎn)生式系統(tǒng),,可交換的產(chǎn)生式系統(tǒng),,可分解的產(chǎn)生式系統(tǒng),,,20,,第二章 產(chǎn)生式系統(tǒng)的搜索策略,,內(nèi)容：,,狀態(tài)空間的搜索問題。,,搜索方式：,,盲目搜索,,啟發(fā)式搜索,,關(guān)鍵問題：,,如何利用知識，盡可能有效地找到問題的解（最佳解）。,,21,,產(chǎn)生式系統(tǒng)的搜索策略（續(xù),1,）,,S,0,S,g,,22,,產(chǎn)生式系統(tǒng)的搜索策略（續(xù),2,）,,討論的問題：,,,

11、有哪些常用的搜索算法。,,問題有解時能否找到解。,,找到的解是最佳的嗎？,,什么情況下可以找到最佳解？,,求解的效率如何。,,23,,2.1,回溯策略,,例：皇后問題,,,24,,( ),,25,,( ),Q,((1,1)),,26,,( ),Q,Q,((1,1)),((1,1) (2,3)),,27,,( ),Q,((1,1)),((1,1) (2,3)),,28,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),,29,,( ),Q,Q,((1,1)),((1,1) (2,3)),((1,1) (2,4)),Q,((1,1) (2,4) (3.2))

12、,,30,,( ),Q,Q,((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)

13、 (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,

14、2) (2,4) (3,1) (4,3)),,37,,遞歸的思想,,,當前狀態(tài),目標狀態(tài),g,,38,,一個遞歸的例子,,int,,ListLenght(LIST,*,pList,),,{,,if (,pList,== NULL) return 0;,,else return,ListLength(pList,->next)+1;,,},NULL,pLIST,1,2,3,,39,,回溯搜索算法,,,BACKTRACK,（,DATA,）,,,,,DATA,：,當前狀態(tài)。,,返回值：從當前狀態(tài)到目標狀態(tài)的路徑,,（以規(guī)則表的形式表示）,,或,FAIL,。,,40,,回溯搜索算法,遞歸過程,BACK

15、TRACK(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);

16、,,41,,存在問題及解決辦法,,解決辦法：,,對搜索深度加以限制,,記錄從初始狀態(tài)到當前狀態(tài)的路徑,,當前狀態(tài),問題：,,深度問題,,死循環(huán)問題,,42,,回溯搜索算法,1,,BACKTRACK1,（,DATALIST,）,,,,,DATALIST,：,從初始到當前的狀態(tài)表（逆向）,,返回值：從當前狀態(tài)到目標狀態(tài)的路徑,,（以規(guī)則表的形式表示）,,或,FAIL,。,,,43,,回溯搜索算法,1,,1, DATA:=FIRST(DATALIST),,2, IF MENBER(DATA, TAIL(DATALIST)),,RETURN FAIL;,,,3, IF TERM(DATA) RE

17、TURN 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:=

18、BACKTRCK1(RDATALIST),,13, IF PATH=FAIL GO LOOP;,,14, RETURN CONS(R, PATH);,,45,,一些深入的問題,,失敗原因分析、多步回溯,,Q,Q,,46,,一些深入問題（續(xù)）,,回溯搜索中知識的利用,,基本思想,(,以皇后問題為例,),：,,盡可能選取劃去對角線上位置數(shù)最少的。,Q,,Q,Q,,Q,3 2 2 3,,47,,2.2,圖搜索策略,,問題的引出,,,回溯搜索：只保留

19、從初始狀態(tài)到當前狀態(tài)的一條路徑。,,圖搜索：保留所有已經(jīng)搜索過的路徑。,,,,48,,一些基本概念,,節(jié)點深度：,,根節(jié)點深度,=0,,,其它節(jié)點深度,=,父節(jié)點深度,+1,0,1,2,3,,49,,一些基本概念（續(xù),1,）,,路徑,,設(shè)一節(jié)點序列為,(n,0,, n,1,,…,,n,k,),，,對于,i=1,…,k,，,若節(jié)點,n,i-1,具有一個后繼節(jié)點,n,i,，,則該序列稱為從,n,0,到,n,k,的路徑。,,路徑的耗散值,,一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用,C(n,i,,,n,j,),表示從,n,i,到,n,j,的路徑的耗散值。,,50,,一些基本概念（續(xù)

20、,1,）,,擴展一個節(jié)點,,生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為,“,擴展一個節(jié)點,”,。,,51,,一般的圖搜索算法,,1, G=G,0,(G,0,=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)→{m,i,}, G:=ADD(m,i,, G);,,,52,,一般的圖搜

21、索算法（續(xù)）,,7,,標記和修改指針：,,,ADD(m,j,, OPEN),,并標記,m,j,到,n,的指針；,,計算是否要修改,m,k,、,m,l,到,n,的指針；,,計算是否要修改,m,l,到其后繼節(jié)點的指針；,,8,,,對,OPEN,中的節(jié)點按,某種原則,重新排序；,,9, GO LOOP,；,,53,,節(jié)點類型說明,,,…...,…...,…...,…...,…...,m,j,m,k,m,l,,54,,修改指針舉例,1,2,3,4,5,6,s,,55,,修改指針舉例（續(xù),1,）,1,2,3,4,5,6,s,,56,,1,2,3,4,5,6,修改指針舉例（續(xù),2,）,s,,57,,1,2

22、,3,4,5,6,修改指針舉例（續(xù),3,）,s,,58,,2.3,無信息圖搜索過程,,深度優(yōu)先搜索,,寬度優(yōu)先搜索,,,59,,深度優(yōu)先搜索,,1, G:=G,0,(G,0,=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) →{m,i,},

23、G:=ADD(m,i,, G);,,8, IF,目標在,{m,i,},中,THEN EXIT(SUCCESS);,,9,,ADD(m,j,, OPEN),,并標記,m,j,到,n,的指針,;,,10, GO LOOP;,,60,,2 3,,1 8 4,,7 6 5,,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,1 6 4,,7 5,2

24、 8 3,,1 4,,7 6 5,2 8 3,,1 6 4,,7 5,2 8 3,,1 6 4,,7 5,2 8 3,,7 1 4,,6 5,,8 3,,2 1 4,,7 6 5,2 8,,1 4 3,,7 6 5,2 8 3,,1 4 5,,7 6,1 2 3,,7 8 4,,6 5,1 2 3,,8 4,,7 6 5,2 8 3,,6 4,,1 7 5,2 8 3,,1 6,,

25、7 5 4,8 3,,2 1 4,,7 6 5,2 8 3,,7 1 4,,6 5,2 8,,1 4 3,,7 6 5,2 8 3,,1 4 5,,7 6,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,,8 4,,7 6 5,目標,,61,,深度優(yōu)先搜索的性質(zhì),,一般不能保證找到最優(yōu)解,,當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制,,最壞情況時，搜索空間等同于窮舉,,與回溯法的差別：圖搜索,,是一個通用的與問題無

26、關(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) →{m,i,}, G:=ADD(m,i,, G);,,7, IF,目標在,{m,i,},中,THEN EXIT(SUCCESS);,,8,,ADD(OPEN,,m,j,),,,并標記,m,j

27、,到,n,的指針,;,,9, GO LOOP;,,63,,2 3,,1 8 4,,7 6 5,,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,1 6 4,,7 5,2 8 3,,1 4,,7 6 5,2 8 3,,1 6 4,,7 5,2 8 3,,1 6 4,,7 5,2

28、 8 3,,7 1 4,,6 5,,8 3,,2 1 4,,7 6 5,2 8,,1 4 3,,7 6 5,2 8 3,,1 4 5,,7 6,1 2 3,,7 8 4,,6 5,1 2 3,,8 4,,7 6 5,1,2,5,6,7,3,1 2 3,,8 4,,7 6 5,目標,8,2 3 4,,1 8,,7 6 5,4,,64,,寬度優(yōu)先搜索的性質(zhì),,當問題有解時，一定能找到解,,當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解,

29、,方法與問題無關(guān)，具有通用性,,效率較低,,屬于圖搜索方法,,,65,,漸進式深度優(yōu)先搜索方法,,目的,,解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。,,思想,,首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。,,66,,2.4,啟發(fā)式圖搜索,,利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。,,啟發(fā)信息的強度,,強：降低搜索工作量，但可能導致找不到最 優(yōu)解,,弱：一般導致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解,,67,,希望：,,,引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能

30、減少搜索范圍，提高搜索效率。,,,68,,基本思想,,定義一個評價函數(shù),f,，,對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。,,,69,,1,，啟發(fā)式搜索算法,A,（,A,算法）,,評價函數(shù)的格式：,,,,f(n) = g(n) + h(n),,,f(n),：,評價函數(shù),,,h(n),：,啟發(fā)函數(shù),,70,,符號的意義,,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

31、),、,f*(n),的估計值,,,71,,A,算法,,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),→{m,i,},,,,計算,f(n, m,i,):=g(n, m,i,)+h(m,i,);,,,,72,,A,算法（續(xù)）,,,ADD(m,j,, OPEN),,標記,m,j,到,n,的指針；,,

32、,IF f(n,,m,k,)<,f(m,k,) THEN,f(m,k,):=f(n,,m,k,),,,,標記,m,k,到,n,的指針；,,,IF f(n, m,l,)

33、) = g(n) + h(n),,g(n),為從初始節(jié)點到當前節(jié)點的耗散值,,,h(n),為當前節(jié)點,“,不在位,”,的將牌數(shù),,,2 8 3,,1 6 4,,7 5,,1 2 3,,8 4,,7 6 5,,,76,,h,計算舉例,,h(n) =4,2,,8,3,,1,,6,4,,7 5,1 2 3,4,,5,7 6,,8,,77,,2 8 3,,1 6 4,,7 5,2 8 3,,1 4,,7 6 5,2 8

34、 3,,1 6 4,,7 5,2 8 3,,1 6 4,,7 5,2 3,,1 8 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,1 4,,7 6 5,2 8 3,,7 1 4,,6 5,,8 3,,2 1 4,,7 6 5,,2 3,,1 8 4,,7 6 5,2 3,,1 8 4,,7 6 5,1 2 3,,8 4,,7 6 5,1 2 3,,8

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

36、 5,1 2 3,4,,5,7 6,,8,將牌,1,：,1,,將牌,2,：,1,,將牌,6,：,1,,將牌,8,：,2,,80,,A*,算法的性質(zhì),,A*,算法的假設(shè),,,設(shè),n,i,、,n,j,是任意兩個節(jié)點，有：,,,C(n,i,,,n,j,) >,?,,,其中,?,為大于,0,的常數(shù),幾個等式,,,f*(s) = f*(t) = h*(s) = g*(t) = f*(n),,,其中,s,是初始節(jié)點，,t,是目標節(jié)點，,n,是,s,到,t,的最佳路徑上的節(jié)點。,,81,,A*,算法的性質(zhì)（續(xù),1,）,,定理,1,：,,對有限圖，如果從初始節(jié)點,s,到目標節(jié)點,t,有路

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

38、,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é)束，將導致矛盾。,,85,,A*,算法的性質(zhì)（續(xù),4,）,,推論,2.1,：,,,OPEN,表上任一具有,f(n)

39、,,f(t) ≥,f*(t),＝,f*(s),,,所以,f(n) f*(s),,由引理,2.2,知結(jié)束前,OPEN,中存在,f(n)≤f*(s),的,節(jié)點,n,，,所以,,,f(n) ≤ f*(s) < f(t),,因此,A*,

40、應選擇,n,擴展，而不是,t,。,與假設(shè),A*,選擇,t,結(jié)束矛盾。得證。,,注意,：,A*,的結(jié)束條件,,88,,A*,算法的性質(zhì)（續(xù),6,）,,推論,3.1,：,,,A*,選作擴展的任一節(jié)點,n,，有,f(n)≤f*(s),。,由引理,2.2,知在,A*,結(jié)束前，,OPEN,中存在節(jié)點,n’,，,f(n’)≤f*(s),,設(shè)此時,A*,選擇,n,擴展。,,如果,n,＝,n’,，則,f(n)≤f*(s),，,得證。,,如果,n≠ n’,，,由于,A*,選擇,n,擴展，而不是,n’,，,所以有,f(n) ≤ f(n’)≤f*(s),。,得證。,,89,,A*,算法的性質(zhì)（續(xù),7,）,,定理,4

41、,：設(shè)對同一個問題定義了兩個,A*,算法,A,1,和,A,2,，若,A,2,比,A,1,有較多的啟發(fā)信息，即對所有非目標節(jié)點有,h,2,(n) > h,1,(n),，,則在具有一條從,s,到,t,的路徑的隱含圖上，搜索結(jié)束時，由,A,2,所擴展的每一個節(jié)點，也必定由,A,1,所擴展，即,A,1,擴展的節(jié)點數(shù)至少和,A,2,一樣多。,,簡寫：如果,h,2,(n),>,h,1,(n) (,目標節(jié)點除外,),，則,A,1,擴展的節(jié)點數(shù),≥,A,2,擴展的節(jié)點數(shù),,90,,A*,算法的性質(zhì)（續(xù),7,）,,注意：,,,在定理,4,中，評價指標是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只

42、計算一次。,,91,,定理,4,的證明,,使用數(shù)學歸納法，對節(jié)點的深度進行歸納,,（,1,）當,d(n),＝,0,時，即只有一個節(jié)點，顯然定理成立。,,（,2,）設(shè),d(n)≤k,時定理成立。（歸納假設(shè)）,,（,3,）當,d(n)=k+1,時，用反證法。,,設(shè)存在一個深度為,k,＋,1,的節(jié)點,n,，被,A,2,擴展，但沒有被,A,1,擴展。而由假設(shè)，,A,1,擴展了,n,的父節(jié)點，即,n,已經(jīng)被生成了。因此當,A,1,結(jié)束時，,n,將被保留在,OPEN,中。,,92,,定理,4,的證明（續(xù),1,）,,所以有：,f,1,(n) ≥ f*(s),,,即：,g,1,(n)+h,1,(n) ≥ f*

43、(s),,所以：,h,1,(n) ≥ f*(s) - g,1,(n),,另一方面，由于,A,2,擴展了,n,，有,f2(n) ≤ f*(s),,即：,h,2,(n) ≤ f*(s) – g,2,(n) (A),,由于,d(n)=k,時，,A,2,擴展的節(jié)點,A,1,一定擴展，有,,,g,1,(n) ≤ g,2,(n) (,因為,A,2,的路,A,1,均走到了,),,所以：,h,1,(n) ≥ f*(s) - g,1,(n) ≥ f*(s) – g,2,(n) (B),,比較,A,、,B,兩式，有,h,1,(n) ≥ h,2,(n),，與,定理條

44、件矛盾。故定理得證。,,93,,對,h,的評價方法,,平均分叉樹,,設(shè)共擴展了,d,層節(jié)點，共搜索了,N,個節(jié)點，則,:,,,,,其中，,b*,稱為平均分叉樹。,,b*,越小，說明,h,效果越好。,,實驗表明，,b*,是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。,,94,,對,h,的評價舉例,,例：,8,數(shù)碼問題，隨機產(chǎn)生若干初始狀態(tài)。,,,使用,h,1,：,,,d=14, N=539, b*=1.44;,,d=20, N=7276,，,b*=1.47,；,,使用,h,2,：,,,d=14, N=113, b*=1.23;,,d=20, N=676, b*=1.27,

45、,,95,,A*,的復雜性,,一般來說，,A*,的算法復雜性是指數(shù)型的，可以證明，當且僅當以下條件成立時：,,,abs(h(n)-h*(n)) ≤ O(log(h*(n))),,A*,的算法復雜性才是非指數(shù)型的，但是通常情況下，,h,與,h*,的差別至少是和離目標的距離成正比的。,,96,,3,，,A*,算法的改進,,問題的提出：,,因,A,算法第,6,步對,m,l,類節(jié)點可能要重新放回到,OPEN,表中，因此可能會導致多次重復擴展同一個節(jié)點，導致搜索效率下降。,,97,,s(10),A(1),B(5),C(8),G,目標,6,3,1,1,1,8,一個例子：,OPEN表,CLOSED表,s

46、(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é)點的原因,,在前面的擴展中，并沒有找到從初始節(jié)點到當前節(jié)點的最短路徑，如節(jié)點,A,。,,s(10),A(1),B(5),C(8),G,目標,6,3,1,1,1,8,,99,,解決的途徑,,對,h,加以

47、限制,,能否對,h,增加適當?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從,s,到該節(jié)點的最短路徑。,,對算法加以改進,,能否對算法加以改進，避免或減少節(jié)點的多次擴展。,,100,,改進的條件,,可采納性不變,,不多擴展節(jié)點,,不增加算法的復雜性,,,101,,對,h,加以限制,,定義：一個啟發(fā)函數(shù),h,，,如果對所有節(jié)點,n,i,和,n,j,，,其中,n,j,是,n,i,的子節(jié)點，滿足,,,h(n,i,) -,h(n,j,) ≤,c(n,i,,,n,j,),,h(t) = 0,,,或,,,h(n,i,) ≤,c(n,i,,,n,j,) +,h(n,j,),,h(t) = 0,,,則稱,h,是單

48、調(diào)的。,h(n,i,),n,i,n,j,h(n,j,),c(n,i,,n,j,),,102,,h,單調(diào)的性質(zhì),,定理,5,：,,若,h(n),是單調(diào)的，則,A*,擴展了節(jié)點,n,之后，就已經(jīng)找到了到達節(jié)點,n,的最佳路徑。,,即：當,A*,選,n,擴展時，有,g(n)=g*(n),。,,103,,定理,5,的證明,,設(shè),n,是,A*,擴展的任一節(jié)點。,當,n,＝,s,時，定理顯然成立。下面考察,n ≠s,的情況。,,設(shè),P,＝,(n,0,=s, n,1,, n,2,, …,,n,k,=n),是,s,到,n,的最佳路徑,,P,中一定有節(jié)點在,CLOSED,中，設(shè),P,中最后一個出現(xiàn)在,CLOSE

49、D,中的節(jié)點為,n,j,，則,n,j+1,在,OPEN,中,。,,104,,定理,5,的證明（續(xù),1,）,,由單調(diào)限制條件，對,P,中任意節(jié)點,n,i,有：,,,h(n,i,) ≤,C(n,i,, n,i+1,)+h(n,i+1,),,,g*(,n,i,),+h(n,i,) ≤,g*(,n,i,),+C(n,i,, n,i+1,)+h(n,i+1,),,由于,n,i,,、,n,i+1,在最佳路徑上，所以：,,,,g*(n,i+1,) = g*(,n,i,)+C(n,i,, n,i+1,),,帶入上式有：,,,g*(,n,i,)+h(n,i,) ≤ g*(n,i+1,)+h(n,i+1,),,從

50、,i=j,到,i=k-1,應用上不等式，有：,,,g*(n,j+1,)+h(n,j+1,) ≤ g*(,n,k,)+h(n,k,),,即：,f(n,j+1,) ≤ g*(n)+h(n),,,注意：,(,n,j,在,CLOSED,中，,n,j+1,在,OPEN,中,),,105,,定理,5,的證明（續(xù),2,）,,重寫上式：,f(n,j+1,) ≤ g*(n)+h(n),,另一方面，,A*,選,n,擴展，必有：,,,f(n) = g(n)+h(n) ≤ f(n,j+1,),,比較兩式，有：,,,g(n) ≤ g*(n),,但已知,g*(n),是最佳路徑的耗散值，所以只有：,g(n) = g*(n)

51、,。,得證。,,106,,h,單調(diào)的性質(zhì)（續(xù)）,,定理,6,：,,若,h(n),是單調(diào)的，則由,A*,所擴展的節(jié)點序列其,f,值是非遞減的。即,f(n,i,) ≤,f(n,j,),。,,,,107,,定理,6,的證明,,由,單調(diào)限制條件，有：,,,h(n,i,) –,h(n,j,) ≤,C(n,i,,,n,j,),=,f(n,i,)-g(n,i,),=,f(n,j,)-g(n,j,),,f(n,i,)-g(n,i,) -,f(n,j,)+g(n,j,) ≤,C(n,i,,,n,j,),=,g(n,i,)+C(n,i,,,n,j,),,f(n,i,)-,g(n,i,),-,f(n,j,)+,g(

52、n,i,),+C(n,i,,,n,j,),≤,C(n,i,,,n,j,),,,f(n,i,) -,f(n,j,),,≤ 0,，,得證。,,,108,,h,單調(diào)的例子,,8,數(shù)碼問題：,,h,為,“,不在位,”,的將牌數(shù),,,1,,,h(n,i,) -,h(n,j,) = 0 (,n,j,為,n,i,的后繼節(jié)點,),,-1,,h(t) = 0,,,c(n,i,,,n,j,) = 1,,,,滿足單調(diào)的條件。,,,109,,對算法加以改進,,一些結(jié)論：,,OPEN,表上任以具有,f(n) < f*(s),的節(jié)點定會被擴展。,,A*,選作擴展的任一節(jié)點，定有,f(n)≤f*(s),。,,

53、,110,,改進的出發(fā)點,,OPEN = ( … … … … ),f*(s),f,值小于,f*(s),的節(jié)點,,f,值大于等于,f*(s),的節(jié)點,,f,m,：,到目前為止已擴展節(jié)點的最大,f,值，,用,f,m,代替,f*(s),,111,,修正過程,A,,1, OPEN:=(s), f(s)=g(s)+h(s), f,m,:=0;,,2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);,,3, NEST:={,n,i,|f(n,i,)

54、,,,f,m,:=f(n);,,4, …, 8:,同過程,A,。,,112,,s(10),A(1),B(5),C(8),G,目標,6,3,1,1,1,8,前面的例子：,OPEN表,CLOSED表,f,m,s(0+10),s(0+10),10,A(6+1) B(3+5) C(1+8),s(0+10) C(1+8),10,A(6+1) B(2+5),s(0+10) C(1+8) B(2+5),10,A(3+1),s(0+10)C(1+8)B(2+5)A(3+1),10,G(11+0),,113,,h,的單調(diào)化方法,,如果令：,,,f(n) = max(f(n,的父節(jié)點,), g(n)+h(n)),

55、,,則容易證明，這樣處理后的,h,是單調(diào)的。,,114,,IDA*,算法(,Iterative Deepening A*),,基本思想：回溯與,A*,的結(jié)合,,算法簡介（非嚴格地）,,,1,，設(shè)初始值,f0,；,,,2,，,集合,S,＝,NULL,；,,,3,，,用回溯法求解問題，如果節(jié)點,n,的,f,值大于,f0,，,則將該節(jié)點放入集合,S,中，并回溯；,,,4,，如果在,3,中找到了解，則結(jié)束；,,,5,，如果,3,以失敗結(jié)束，則,f0,＝,S,中節(jié)點的最小,f,值；,,,6,，返回到,2,。,,115,,知識的靈活應用,,例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為,12,。,1,3,5,5,1,

56、4,4,1,3,3,2,5,2,3,1,2,3,1,2,2,5,5,2,3,4,2,5,4,3,4,3,3,分析：,,陰影部分數(shù)字和：,48,,,直徑部分數(shù)字和：,24,,,轉(zhuǎn),45°,改變陰影部分,,轉(zhuǎn),90°,改變直徑部分,,但不改變陰影部分,,轉(zhuǎn),180°,改變扇區(qū)部分,,但不改變陰影部分,,也不改變直徑部分,,,,116,,4,，其他的搜索算法,,爬山法（局部搜索算法）,,,117,,其他的搜索算法（續(xù),1,）,,隨機搜索算法,,動態(tài)規(guī)劃算法,,如果對于任何,n,，當,h(n)=0,時，,A*,算法就成為了動態(tài)規(guī)劃算法。,,118,,動態(tài)規(guī)劃,,,S,0,t,S,1,S,2,S,3,S

57、,n,……,……,……,W,0,W,1,1,W,1,2,W,2,1,W,2,2,W,2,3,W,3,3,W,3,2,W,3,1,W,n,1,W,n,2,W,n,3,W,n+1,,119,,,其中：,Q(W,ij,),表示到點,W,ij,的最佳路徑值,,,D(W,i-1,j,,,W,i,k,),表示,W,i-1,j,到,W,i,k,的距離,,120,,5,，搜索算法實用舉例,,漢字識別后處理,,一個例子,,我錢線載哦栽哉裁劣綏,,優(yōu)仍們仿倫奶砧犯扔妨,,要耍密窮安壁駐努窯垂,,扳報叔嵌奴振技寂敘蔽,,奮夯杏蠶香脊秀吞吝番,,精猜指潔括治捐活冶桔,,種神襯祥科鐘拌樣拎補,,,,121,,漢字識別后

58、處理,,,二元語法時：,為常量,用識別信度代替,問題變?yōu)榍?最大,,122,,第三章 與或圖的搜索,,,目標,目標,初始節(jié)點,s,a,,b,,c,,,123,,3.1,基本概念,,與或圖是一個超圖，節(jié)點間通過連接符連接。,,K-,連接符：,,…...,K,個,,124,,耗散值的計算,,,k(n, N) = C,n,+k(n,1,, N)+…+,k(n,i,, N),,其中：,N,為終節(jié)點集,,,C,n,為連接符的耗散值,…...,i,個,n,n,1,n,2,n,i,,125,,目標,目標,初始節(jié)點,解圖：,,126,,能解節(jié)點,,終節(jié)點是能解節(jié)點,,若非終節(jié)點有,“,或,”,子節(jié)點時，當且僅

59、當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。,,若非終節(jié)點有,“,與,”,子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。,,127,,不能解節(jié)點,,沒有后裔的非終節(jié)點是不能解節(jié)點。,,若非終節(jié)點有,“,或,”,子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。,,若非終節(jié)點有,“,與,”,子節(jié)點時，當至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。,,128,,普通圖的情況,,,f(n) = g(n) + h(n),,,對,n,的評價實際是對從,s,到,n,這條路徑的評價,n,s,,129,,與或圖,:,對局部圖的評價,,,目標,目標,初始節(jié)點,a,b,c,,130,,兩個過程,

60、,圖生成過程，即擴展節(jié)點,,從最優(yōu)的局部途中選擇一個節(jié)點擴展,,計算耗散值的過程,,對當前的局部圖新計算耗散值,,131,,AO*,算法舉例,,,其中：,,,h(n,0,)=3,,h(n,1,)=2,,h(n,2,)=4,,h(n,3,)=4,,h(n,4,)=1,,h(n,5,)=1,,h(n,6,)=2,,h(n,7,)=0,,h(n,8,)=0,,,設(shè)：,K,連接符,,的耗散值為,K,,目標,目標,初始節(jié)點,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,132,,目標,目標,初始節(jié)點,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始

61、節(jié)點,n,0,n,1,(2),n,4,(1),n,5,(1),紅色：,4,,黃色：,3,,133,,目標,目標,初始節(jié)點,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始節(jié)點,n,0,,n,4,(1),n,5,(1),紅色：,4,,黃色：,6,n,1,n,2,(4),n,3,(4),5,,134,,目標,目標,初始節(jié)點,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,紅色：,5,,黃色：,6,初始節(jié)點,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,,1

62、35,,目標,目標,初始節(jié)點,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,紅色：,5,,黃色：,6,初始節(jié)點,n,0,,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,1,,136,,3.3,博弈樹搜索,,博弈問題,,雙人,,一人一步,,雙方信息完備,,零和,,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

63、,1,1）,（2,1,1,1,1,1）,對方先走,我方必勝,,138,,中國象棋,,一盤棋平均走,50,步，總狀態(tài)數(shù)約為,10,的,161,次方。,,假設(shè),1,毫微秒走一步，約需,10,的,145,次方年。,,結(jié)論：不可能窮舉。,,,139,,1,，極小極大過程,,,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,極大,極小,a,b,,140,,?,-?,剪枝,極大節(jié)點的下界為,?。,,極小節(jié)點的上界為?。,,剪枝的條件：,,后輩節(jié)點的?值≤祖先節(jié)點的?值時， ?剪枝,,后輩節(jié)點的? 值≥祖先節(jié)點的?值時， ?剪枝,,簡記為：,,極小≤極大，剪枝,,極大≥極小，剪枝,,141,,?,-?,剪枝（續(xù)）,,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,,142,,?,-?,剪枝的其他應用,故障診斷,,,,,A B C D,,,風險投資,,,143,,