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

單擊此處編輯母版標(biāo)題樣式,,,*,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,第一章 產(chǎn)生式系統(tǒng),,1943,年,Post,首先在一種計(jì)算形式體系中提出,,60,年代開(kāi)始，成為專家系統(tǒng)的最基本的結(jié)構(gòu),,形式上很簡(jiǎn)單，但在一定意義上模仿了人類思考的過(guò)程,,,,,1,,1.1,產(chǎn)生式系統(tǒng)的基本組成,,組成三要素：,,,一個(gè)綜合數(shù)據(jù)庫(kù),——,存放信息,,一組產(chǎn)生式規(guī)則,——,知識(shí),,一個(gè)控制系統(tǒng),——,規(guī)則的解釋或執(zhí)行程序 （控制策略） （推理引擎）,,2,,規(guī)則的一般形式,,IF <,前提,> THEN <,結(jié)論,>,,IF <,條件,> THEN <,行動(dòng),>,,或者簡(jiǎn)寫為：,,,<,前提,>,－,> <,結(jié)論,>,,<,條件,>,－,> <,行動(dòng),>,,3,,1.2,產(chǎn)生式系統(tǒng)的基本過(guò)程,,過(guò)程,PRODUCTION,,1,，,DATA←,初始數(shù)據(jù)庫(kù),,2，,until DATA,滿足結(jié)束條件，,do,,3,，,{,,4,，,在規(guī)則集中選擇一條可應(yīng)用于,DATA,的規(guī)則,R,,5,，,DATA ←R,應(yīng)用到,DATA,得到的結(jié)果,,6,，,},,4,,一個(gè)簡(jiǎn)單的例子,,問(wèn)題：設(shè)字符轉(zhuǎn)換規(guī)則,,,A∧B→C,,A∧C→D,,B∧C→G,,B∧E→F,,D→E,,,已知：,A,，,B,,,求：,F,,5,,一個(gè)簡(jiǎn)單的例子（續(xù),1,）,,一、綜合數(shù)據(jù)庫(kù),,,{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,,一個(gè)簡(jiǎn)單的例子（續(xù),2,）,,三、控制策略,,順序排隊(duì),,四、初始條件,,,{A,，,B},,五、結(jié)束條件,,,F∈{x},,7,,求解過(guò)程,數(shù)據(jù)庫(kù) 可觸發(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 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,問(wèn)題表示舉例,,例,1,：傳教士與野人問(wèn)題（,M-C,問(wèn)題）,,問(wèn)題,：,N,個(gè)傳教士，,N,個(gè)野人，一條船，可同時(shí)乘坐,k,個(gè)人，要求在任何時(shí)刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。,,問(wèn)：如何過(guò)河。,,,以,N=3,，,k=2,為例求解。,,,9,,M-C,問(wèn)題（續(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 1,,10,,M-C,問(wèn)題（續(xù),2,）,,1,，綜合數(shù)據(jù)庫(kù),,（,m, c, b),，,,,其中：,0≤m, c≤3, b ∈{0, 1},,2,，,初始狀態(tài),,（,3,，,3,，,1,）,,3,，目標(biāo)狀態(tài)（結(jié)束狀態(tài)）,,（,0,，,0,，,0,）,,,11,,M-C,問(wèn)題（續(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),,12,,M-C,問(wèn)題（續(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,問(wèn)題（第二種方法）,,4,，規(guī)則集：,,,,IF (m, c, 1) AND 1 ≤i+j≤2 THEN (m-i, c-j, 0),,IF (m, c, 0) AND 1 ≤i+j≤2 THEN (m+i, c+j, 1),,,14,,猴子摘香蕉問(wèn)題,,,,,,,,c a b,,15,,猴子摘香蕉問(wèn)題（續(xù),1,）,,1,，綜合數(shù)據(jù)庫(kù),,（,M, B, Box, On, H,）,,,M,：,猴子的位置,,,B,：,香蕉的位置,,,Box,：,箱子的位置,,,On=0,：,猴子在地板上,,,On=1,：,猴子在箱子上,,,H=0,：,猴子沒(méi)有抓到香蕉,,,H=1,：,猴子抓到了香蕉,,16,,猴子摘香蕉問(wèn)題（續(xù),2,）,,2,，初始狀態(tài),,（,c, a, b, 0, 0,）,,,3,，,結(jié)束狀態(tài),,（,x,1,, x,2,, x,3,, x,4,, 1,）,,,其中,x,1,～,x,4,為變量。,,17,,猴子摘香蕉問(wèn)題（續(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,為變量,,18,,1.4,產(chǎn)生式系統(tǒng)的特點(diǎn),,數(shù)據(jù)驅(qū)動(dòng),,知識(shí)的無(wú)序性,,控制系統(tǒng)與問(wèn)題無(wú)關(guān),,數(shù)據(jù)、知識(shí)和控制相互獨(dú)立,,,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)空間的搜索問(wèn)題。,,搜索方式：,,盲目搜索,,啟發(fā)式搜索,,關(guān)鍵問(wèn)題：,,如何利用知識(shí)，盡可能有效地找到問(wèn)題的解（最佳解）。,,21,,產(chǎn)生式系統(tǒng)的搜索策略（續(xù),1,）,,S,0,S,g,,22,,產(chǎn)生式系統(tǒng)的搜索策略（續(xù),2,）,,討論的問(wèn)題：,,,有哪些常用的搜索算法。,,問(wèn)題有解時(shí)能否找到解。,,找到的解是最佳的嗎？,,什么情況下可以找到最佳解？,,求解的效率如何。,,23,,2.1,回溯策略,,例：皇后問(wèn)題,,,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)),,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) (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,,遞歸的思想,,,當(dāng)前狀態(tài),目標(biāo)狀態(tài),g,,38,,一個(gè)遞歸的例子,,int,,ListLenght(LIST,*,pList,),,{,,if (,pList,== NULL) return 0;,,else return,ListLength(pList,->next)+1;,,},NULL,pLIST,1,2,3,,39,,回溯搜索算法,,,BACKTRACK,（,DATA,）,,,,,DATA,：,當(dāng)前狀態(tài)。,,返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑,,（以規(guī)則表的形式表示）,,或,FAIL,。,,40,,回溯搜索算法,遞歸過(guò)程,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,,存在問(wèn)題及解決辦法,,解決辦法：,,對(duì)搜索深度加以限制,,記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑,,當(dāng)前狀態(tài),問(wèn)題：,,深度問(wèn)題,,死循環(huán)問(wèn)題,,42,,回溯搜索算法,1,,BACKTRACK1,（,DATALIST,）,,,,,DATALIST,：,從初始到當(dāng)前的狀態(tài)表（逆向）,,返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑,,（以規(guī)則表的形式表示）,,或,FAIL,。,,,43,,回溯搜索算法,1,,1, 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,,一些深入的問(wèn)題,,失敗原因分析、多步回溯,,Q,Q,,46,,一些深入問(wèn)題（續(xù)）,,回溯搜索中知識(shí)的利用,,基本思想,(,以皇后問(wèn)題為例,),：,,盡可能選取劃去對(duì)角線上位置數(shù)最少的。,Q,,Q,Q,,Q,3 2 2 3,,47,,2.2,圖搜索策略,,問(wèn)題的引出,,,回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。,,圖搜索：保留所有已經(jīng)搜索過(guò)的路徑。,,,,48,,一些基本概念,,節(jié)點(diǎn)深度：,,根節(jié)點(diǎn)深度,=0,,,其它節(jié)點(diǎn)深度,=,父節(jié)點(diǎn)深度,+1,0,1,2,3,,49,,一些基本概念（續(xù),1,）,,路徑,,設(shè)一節(jié)點(diǎn)序列為,(n,0,, n,1,,…,,n,k,),，,對(duì)于,i=1,…,k,，,若節(jié)點(diǎn),n,i-1,具有一個(gè)后繼節(jié)點(diǎn),n,i,，,則該序列稱為從,n,0,到,n,k,的路徑。,,路徑的耗散值,,一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用,C(n,i,,,n,j,),表示從,n,i,到,n,j,的路徑的耗散值。,,50,,一些基本概念（續(xù),1,）,,擴(kuò)展一個(gè)節(jié)點(diǎn),,生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱為,“,擴(kuò)展一個(gè)節(jié)點(diǎn),”,。,,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,,一般的圖搜索算法（續(xù)）,,7,,標(biāo)記和修改指針：,,,ADD(m,j,, OPEN),,并標(biāo)記,m,j,到,n,的指針；,,計(jì)算是否要修改,m,k,、,m,l,到,n,的指針；,,計(jì)算是否要修改,m,l,到其后繼節(jié)點(diǎn)的指針；,,8,,,對(duì),OPEN,中的節(jié)點(diǎn)按,某種原則,重新排序；,,9, GO LOOP,；,,53,,節(jié)點(diǎn)類型說(shuō)明,,,…...,…...,…...,…...,…...,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,3,4,5,6,修改指針舉例（續(xù),3,）,s,,58,,2.3,無(wú)信息圖搜索過(guò)程,,深度優(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,}, G:=ADD(m,i,, G);,,8, IF,目標(biāo)在,{m,i,},中,THEN EXIT(SUCCESS);,,9,,ADD(m,j,, OPEN),,并標(biāo)記,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 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,,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,目標(biāo),,61,,深度優(yōu)先搜索的性質(zhì),,一般不能保證找到最優(yōu)解,,當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制,,最壞情況時(shí)，搜索空間等同于窮舉,,與回溯法的差別：圖搜索,,是一個(gè)通用的與問(wèn)題無(wú)關(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,目標(biāo)在,{m,i,},中,THEN EXIT(SUCCESS);,,8,,ADD(OPEN,,m,j,),,,并標(biāo)記,m,j,到,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 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,目標(biāo),8,2 3 4,,1 8,,7 6 5,4,,64,,寬度優(yōu)先搜索的性質(zhì),,當(dāng)問(wèn)題有解時(shí)，一定能找到解,,當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解,,方法與問(wèn)題無(wú)關(guān)，具有通用性,,效率較低,,屬于圖搜索方法,,,65,,漸進(jìn)式深度優(yōu)先搜索方法,,目的,,解決寬度優(yōu)先方法的空間問(wèn)題和回溯方法不能找到最優(yōu)解的問(wèn)題。,,思想,,首先給回溯法一個(gè)比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。,,66,,2.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)解,,67,,希望：,,,引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。,,,68,,基本思想,,定義一個(gè)評(píng)價(jià)函數(shù),f,，,對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。,,,69,,1,，啟發(fā)式搜索算法,A,（,A,算法）,,評(píng)價(jià)函數(shù)的格式：,,,,f(n) = g(n) + h(n),,,f(n),：,評(píng)價(jià)函數(shù),,,h(n),：,啟發(fā)函數(shù),,70,,符號(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ì)值,,,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,},,,,計(jì)算,f(n, m,i,):=g(n, m,i,)+h(m,i,);,,,,72,,A,算法（續(xù)）,,,ADD(m,j,, OPEN),,標(biāo)記,m,j,到,n,的指針；,,,IF f(n,,m,k,)<,f(m,k,) THEN,f(m,k,):=f(n,,m,k,),,,,標(biāo)記,m,k,到,n,的指針；,,,IF f(n, m,l,)<f(m,l,,) THEN f(m,l,):=f(n, m,l,),,,,標(biāo)記,m,l,到,n,的指針,,,,ADD(m,l,, OPEN);,,7, OPEN,中的節(jié)點(diǎn)按,f,值從小到大排序；,,8,, GO LOOP,；,,73,,,,…...,…...,…...,…...,…...,m,j,m,k,m,l,n,a,b,,74,,,,Closed,表,Open,表,,75,,一個(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ù),,,2 8 3,,1 6 4,,7 5,,1 2 3,,8 4,,7 6 5,,,76,,h,計(jì)算舉例,,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 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 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),目標(biāo),1,2,3,4,5,6,,78,,2,，最佳圖搜索算法,A*,（,A*,算法）,,在,A,算法中，如果滿足條件：,,,h(n)≤h*(n),,,則,A,算法稱為,A*,算法。,,,,79,,A*,條件舉例,,8,數(shù)碼問(wèn)題,,h1(n) =,“,不在位,”,的將牌數(shù),,h2(n) =,將牌,“,不在位,”,的距離和,2,,8,3,,1,,6,4,,7 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,是任意兩個(gè)節(jié)點(diǎn)，有：,,,C(n,i,,,n,j,) >,?,,,其中,?,為大于,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)。,,81,,A*,算法的性質(zhì)（續(xù),1,）,,定理,1,：,,對(duì)有限圖，如果從初始節(jié)點(diǎn),s,到目標(biāo)節(jié)點(diǎn),t,有路徑存在，則算法,A,一定成功結(jié)束。,,,,82,,A*,算法的性質(zhì)（續(xù),2,）,,引理,2.1,：,,對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn),s,到目標(biāo)節(jié)點(diǎn),t,的路徑，則,A*,不結(jié)束時(shí)，在,OPEN,表中即使最小的一個(gè),f,值也將增到任意大，或有,f(n)>f*(s),。,,83,,A*,算法的性質(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),,84,,A*,算法的性質(zhì)（續(xù),3,）,,定理,2,：,,對(duì)無(wú)限圖，若從初始節(jié)點(diǎn),s,到目標(biāo)節(jié)點(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)致矛盾。,,85,,A*,算法的性質(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),的,n,，,均被擴(kuò)展。得證。,,86,,A*,算法的性質(zhì)（續(xù),5,）,,定理,3 (,可采納性定理,),：,,若存在從初始節(jié)點(diǎn),s,到目標(biāo)節(jié)點(diǎn),t,有路徑，則,A*,必能找到最佳解結(jié)束。,,87,,可采納性的證明,,由,定理,1,、,2,知,A*,一定找到一條路徑結(jié)束,,設(shè)找到的路徑,s→ t,不是最佳的（,t,為目標(biāo)）,,則：,f(t) = g(t) > f*(s),,由引理,2.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é)束條件,,88,,A*,算法的性質(zhì)（續(xù),6,）,,推論,3.1,：,,,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),。,得證。,,89,,A*,算法的性質(zhì)（續(xù),7,）,,定理,4,：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè),A*,算法,A,1,和,A,2,，若,A,2,比,A,1,有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)有,h,2,(n) > h,1,(n),，,則在具有一條從,s,到,t,的路徑的隱含圖上，搜索結(jié)束時(shí)，由,A,2,所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由,A,1,所擴(kuò)展，即,A,1,擴(kuò)展的節(jié)點(diǎn)數(shù)至少和,A,2,一樣多。,,簡(jiǎn)寫：如果,h,2,(n),>,h,1,(n) (,目標(biāo)節(jié)點(diǎn)除外,),，則,A,1,擴(kuò)展的節(jié)點(diǎn)數(shù),≥,A,2,擴(kuò)展的節(jié)點(diǎn)數(shù),,90,,A*,算法的性質(zhì)（續(xù),7,）,,注意：,,,在定理,4,中，評(píng)價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說(shuō)，同一個(gè)節(jié)點(diǎn)無(wú)論被擴(kuò)展多少次，都只計(jì)算一次。,,91,,定理,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,，被,A,2,擴(kuò)展，但沒(méi)有被,A,1,擴(kuò)展。而由假設(shè)，,A,1,擴(kuò)展了,n,的父節(jié)點(diǎn)，即,n,已經(jīng)被生成了。因此當(dāng),A,1,結(jié)束時(shí)，,n,將被保留在,OPEN,中。,,92,,定理,4,的證明（續(xù),1,）,,所以有：,f,1,(n) ≥ f*(s),,,即：,g,1,(n)+h,1,(n) ≥ f*(s),,所以：,h,1,(n) ≥ f*(s) - g,1,(n),,另一方面，由于,A,2,擴(kuò)展了,n,，有,f2(n) ≤ f*(s),,即：,h,2,(n) ≤ f*(s) – g,2,(n) (A),,由于,d(n)=k,時(shí)，,A,2,擴(kuò)展的節(jié)點(diǎn),A,1,一定擴(kuò)展，有,,,g,1,(n) ≤ g,2,(n) (,因?yà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),，與,定理?xiàng)l件矛盾。故定理得證。,,93,,對(duì),h,的評(píng)價(jià)方法,,平均分叉樹(shù),,設(shè)共擴(kuò)展了,d,層節(jié)點(diǎn)，共搜索了,N,個(gè)節(jié)點(diǎn)，則,:,,,,,其中，,b*,稱為平均分叉樹(shù)。,,b*,越小，說(shuō)明,h,效果越好。,,實(shí)驗(yàn)表明，,b*,是一個(gè)比較穩(wěn)定的常數(shù)，同一問(wèn)題基本不隨問(wèn)題規(guī)模變化。,,94,,對(duì),h,的評(píng)價(jià)舉例,,例：,8,數(shù)碼問(wèn)題，隨機(jī)產(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,,,95,,A*,的復(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)的距離成正比的。,,96,,3,，,A*,算法的改進(jìn),,問(wèn)題的提出：,,因,A,算法第,6,步對(duì),m,l,類節(jié)點(diǎn)可能要重新放回到,OPEN,表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。,,97,,s(10),A(1),B(5),C(8),G,目標(biāo),6,3,1,1,1,8,一個(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)的原因,,在前面的擴(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),6,3,1,1,1,8,,99,,解決的途徑,,對(duì),h,加以限制,,能否對(duì),h,增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從,s,到該節(jié)點(diǎn)的最短路徑。,,對(duì)算法加以改進(jìn),,能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。,,100,,改進(jìn)的條件,,可采納性不變,,不多擴(kuò)展節(jié)點(diǎn),,不增加算法的復(fù)雜性,,,101,,對(duì),h,加以限制,,定義：一個(gè)啟發(fā)函數(shù),h,，,如果對(duì)所有節(jié)點(diǎn),n,i,和,n,j,，,其中,n,j,是,n,i,的子節(jié)點(diǎn)，滿足,,,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,是單調(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*,擴(kuò)展了節(jié)點(diǎn),n,之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn),n,的最佳路徑。,,即：當(dāng),A*,選,n,擴(kuò)展時(shí)，有,g(n)=g*(n),。,,103,,定理,5,的證明,,設(shè),n,是,A*,擴(kuò)展的任一節(jié)點(diǎn)。,當(dāng),n,＝,s,時(shí)，定理顯然成立。下面考察,n ≠s,的情況。,,設(shè),P,＝,(n,0,=s, n,1,, n,2,, …,,n,k,=n),是,s,到,n,的最佳路徑,,P,中一定有節(jié)點(diǎn)在,CLOSED,中，設(shè),P,中最后一個(gè)出現(xiàn)在,CLOSED,中的節(jié)點(diǎn)為,n,j,，則,n,j+1,在,OPEN,中,。,,104,,定理,5,的證明（續(xù),1,）,,由單調(diào)限制條件，對(duì),P,中任意節(jié)點(diǎn),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,),,從,i=j,到,i=k-1,應(yīng)用上不等式，有：,,,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,擴(kuò)展，必有：,,,f(n) = g(n)+h(n) ≤ f(n,j+1,),,比較兩式，有：,,,g(n) ≤ g*(n),,但已知,g*(n),是最佳路徑的耗散值，所以只有：,g(n) = g*(n),。,得證。,,106,,h,單調(diào)的性質(zhì)（續(xù)）,,定理,6,：,,若,h(n),是單調(diào)的，則由,A*,所擴(kuò)展的節(jié)點(diǎn)序列其,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(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ù)碼問(wèn)題：,,h,為,“,不在位,”,的將牌數(shù),,,1,,,h(n,i,) -,h(n,j,) = 0 (,n,j,為,n,i,的后繼節(jié)點(diǎn),),,-1,,h(t) = 0,,,c(n,i,,,n,j,) = 1,,,,滿足單調(diào)的條件。,,,109,,對(duì)算法加以改進(jìn),,一些結(jié)論：,,OPEN,表上任以具有,f(n) < f*(s),的節(jié)點(diǎn)定會(huì)被擴(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),,f,m,：,到目前為止已擴(kuò)展節(jié)點(diǎn)的最大,f,值，,用,f,m,代替,f*(s),,111,,修正過(guò)程,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,)<f,m,},,IF NEST ≠ ( ) THEN n:=NEST,中,g,最小的節(jié)點(diǎn),,,ELSE n:=FIRST(OPEN),,,f,m,:=f(n);,,4, …, 8:,同過(guò)程,A,。,,112,,s(10),A(1),B(5),C(8),G,目標(biāo),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é)點(diǎn),), g(n)+h(n)),,,則容易證明，這樣處理后的,h,是單調(diào)的。,,114,,IDA*,算法(,Iterative Deepening A*),,基本思想：回溯與,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,。,,115,,知識(shí)的靈活應(yīng)用,,例：如何轉(zhuǎn)動(dòng)，使得每個(gè)扇區(qū)數(shù)字和為,12,。,1,3,5,5,1,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,分析：,,陰影部分?jǐn)?shù)字和：,48,,,直徑部分?jǐn)?shù)字和：,24,,,轉(zhuǎn),45°,改變陰影部分,,轉(zhuǎn),90°,改變直徑部分,,但不改變陰影部分,,轉(zhuǎn),180°,改變扇區(qū)部分,,但不改變陰影部分,,也不改變直徑部分,,,,116,,4,，其他的搜索算法,,爬山法（局部搜索算法）,,,117,,其他的搜索算法（續(xù),1,）,,隨機(jī)搜索算法,,動(dòng)態(tài)規(guī)劃算法,,如果對(duì)于任何,n,，當(dāng),h(n)=0,時(shí)，,A*,算法就成為了動(dòng)態(tài)規(guī)劃算法。,,118,,動(dòng)態(tài)規(guī)劃,,,S,0,t,S,1,S,2,S,3,S,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,),表示到點(diǎn),W,ij,的最佳路徑值,,,D(W,i-1,j,,,W,i,k,),表示,W,i-1,j,到,W,i,k,的距離,,120,,5,，搜索算法實(shí)用舉例,,漢字識(shí)別后處理,,一個(gè)例子,,我錢線載哦栽哉裁劣綏,,優(yōu)仍們仿倫奶砧犯扔妨,,要耍密窮安壁駐努窯垂,,扳報(bào)叔嵌奴振技寂敘蔽,,奮夯杏蠶香脊秀吞吝番,,精猜指潔括治捐活冶桔,,種神襯祥科鐘拌樣拎補(bǔ),,,,121,,漢字識(shí)別后處理,,,二元語(yǔ)法時(shí)：,為常量,用識(shí)別信度代替,問(wèn)題變?yōu)榍?最大,,122,,第三章 與或圖的搜索,,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),s,a,,b,,c,,,123,,3.1,基本概念,,與或圖是一個(gè)超圖，節(jié)點(diǎn)間通過(guò)連接符連接。,,K-,連接符：,,…...,K,個(gè),,124,,耗散值的計(jì)算,,,k(n, N) = C,n,+k(n,1,, N)+…+,k(n,i,, N),,其中：,N,為終節(jié)點(diǎn)集,,,C,n,為連接符的耗散值,…...,i,個(gè),n,n,1,n,2,n,i,,125,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),解圖：,,126,,能解節(jié)點(diǎn),,終節(jié)點(diǎn)是能解節(jié)點(diǎn),,若非終節(jié)點(diǎn)有,“,或,”,子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時(shí)，該非終節(jié)點(diǎn)才能解。,,若非終節(jié)點(diǎn)有,“,與,”,子節(jié)點(diǎn)時(shí)，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時(shí)，該非終節(jié)點(diǎn)才能解。,,127,,不能解節(jié)點(diǎn),,沒(méi)有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。,,若非終節(jié)點(diǎn)有,“,或,”,子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時(shí)，該非終節(jié)點(diǎn)才不能解。,,若非終節(jié)點(diǎn)有,“,與,”,子節(jié)點(diǎn)時(shí)，當(dāng)至少有一個(gè)子節(jié)點(diǎn)不能解時(shí)，該非終節(jié)點(diǎn)才不能解。,,128,,普通圖的情況,,,f(n) = g(n) + h(n),,,對(duì),n,的評(píng)價(jià)實(shí)際是對(duì)從,s,到,n,這條路徑的評(píng)價(jià),n,s,,129,,與或圖,:,對(duì)局部圖的評(píng)價(jià),,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),a,b,c,,130,,兩個(gè)過(guò)程,,圖生成過(guò)程，即擴(kuò)展節(jié)點(diǎn),,從最優(yōu)的局部途中選擇一個(gè)節(jié)點(diǎn)擴(kuò)展,,計(jì)算耗散值的過(guò)程,,對(duì)當(dāng)前的局部圖新計(jì)算耗散值,,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,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,,132,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始節(jié)點(diǎn),n,0,n,1,(2),n,4,(1),n,5,(1),紅色：,4,,黃色：,3,,133,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始節(jié)點(diǎn),n,0,,n,4,(1),n,5,(1),紅色：,4,,黃色：,6,n,1,n,2,(4),n,3,(4),5,,134,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,紅色：,5,,黃色：,6,初始節(jié)點(diǎn),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,,135,,目標(biāo),目標(biāo),初始節(jié)點(diǎn),n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,紅色：,5,,黃色：,6,初始節(jié)點(diǎn),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,博弈樹(shù)搜索,,博弈問(wèn)題,,雙人,,一人一步,,雙方信息完備,,零和,,137,,分錢幣問(wèn)題,,,（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）,對(duì)方先走,我方必勝,,138,,中國(guó)象棋,,一盤棋平均走,50,步，總狀態(tài)數(shù)約為,10,的,161,次方。,,假設(shè),1,毫微秒走一步，約需,10,的,145,次方年。,,結(jié)論：不可能窮舉。,,,139,,1,，極小極大過(guò)程,,,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é)點(diǎn)的下界為,?。,,極小節(jié)點(diǎn)的上界為?。,,剪枝的條件：,,后輩節(jié)點(diǎn)的?值≤祖先節(jié)點(diǎn)的?值時(shí)， ?剪枝,,后輩節(jié)點(diǎn)的? 值≥祖先節(jié)點(diǎn)的?值時(shí)， ?剪枝,,簡(jiǎn)記為：,,極小≤極大，剪枝,,極大≥極小，剪枝,,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,,?,-?,剪枝的其他應(yīng)用,故障診斷,,,,,A B C D,,,風(fēng)險(xiǎn)投資,,,143,,