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