人工智能導(dǎo)論第一章產(chǎn)生式系統(tǒng)

1、1l1943年P(guān)ost首先在一種計算形式體系中提出l60年代開始，成為專家系統(tǒng)的最基本的結(jié)構(gòu)l形式上很簡單，但在一定意義上模仿了人類思考的過程2l組成三要素：一個綜合數(shù)據(jù)庫存放信息一組產(chǎn)生式規(guī)則知識一個控制系統(tǒng)規(guī)則的解釋或執(zhí)行程序 （控制策略） （推理引擎）3lIF THEN lIF THEN l或者簡寫為： 4過程PRODUCTION1，DATA初始數(shù)據(jù)庫2，until DATA滿足結(jié)束條件，do3，4， 在規(guī)則集中選擇一條可應(yīng)用于DATA 的規(guī)則R5， DATA R應(yīng)用到DATA得到的結(jié)果6，5l問題：設(shè)字符轉(zhuǎn)換規(guī)則ABCACDBCGBEFDE已知：A，B求：F6一、綜合數(shù)據(jù)庫x，其中x為

2、字符二、規(guī)則集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E7三、控制策略順序排隊四、初始條件A，B五、結(jié)束條件Fx8數(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 E9例1：傳教士與野人問題（M-C問題）問題：N個傳教士

3、，N個野人，一條船，可同時乘坐k個人，要求在任何時刻，在河的兩岸，傳教士人數(shù)不能少于野人的人數(shù)。問：如何過河。以N=3，k=2為例求解。10 初始 目標(biāo) L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1111，綜合數(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）124，規(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)

4、 THEN (m-2, c, 0)IF (m, c, 1) THEN (m, c-2, 0)13IF (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，控制策略：（略）144，規(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)1

5、5 c a b161，綜合數(shù)據(jù)庫（M, B, Box, On, H）M：猴子的位置B：香蕉的位置Box：箱子的位置On=0：猴子在地板上On=1：猴子在箱子上H=0：猴子沒有抓到香蕉H=1：猴子抓到了香蕉172，初始狀態(tài)（c, a, b, 0, 0）3，結(jié)束狀態(tài)（x1, x2, x3, x4, 1）其中x1x4為變量。184，規(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:

6、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為變量19l數(shù)據(jù)驅(qū)動l知識的無序性l控制系統(tǒng)與問題無關(guān)l數(shù)據(jù)、知識和控制相互獨立20l正向、逆向、雙向產(chǎn)生式系統(tǒng)l可交換的產(chǎn)生式系統(tǒng)l可分解的產(chǎn)生式系統(tǒng)21l內(nèi)容：狀態(tài)空間的搜索問題。l搜索方式：盲目搜索啟發(fā)式搜索l關(guān)鍵問題：如何利用知識，盡可能有效地找到問題的解（最佳解）。22S0Sg23l討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。

7、24l例：皇后問題QQQQ25( )26( )Q(1,1)27( )QQ(1,1)(1,1) (2,3)28( )Q(1,1)(1,1) (2,3)29( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)30( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)31( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)32( )Q(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) (

8、2,4) (3.2)34( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)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)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)37( )(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,

9、1)Q(1,2) (2,4) (3,1) (4,3)38當(dāng)前狀態(tài)目標(biāo)狀態(tài)g39int ListLenght(LIST *pList)if (pList = NULL) return 0;else return ListLength(pList-next)+1;NULLpLIST12340BACKTRACK（DATA）DATA：當(dāng)前狀態(tài)。返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。41遞歸過程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRUL

10、ES(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);42l解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當(dāng)前狀態(tài)的路徑當(dāng)前狀態(tài)l問題：深度問題死循環(huán)問題43BACKTRACK1（DATALIST）DATALIST：從初始到當(dāng)前的狀態(tài)表（逆向）返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示

11、）或FAIL。441, 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);459,RULES:=TAIL(RULES);10,RDATA:=GEN(R, DA

12、TA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);46l失敗原因分析、多步回溯QQ47l回溯搜索中知識的利用基本思想(以皇后問題為例)：盡可能選取劃去對角線上位置數(shù)最少的。QQQQ3 2 2 348l問題的引出回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。圖搜索：保留所有已經(jīng)搜索過的路徑。49l節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+1012350l路徑設(shè)一節(jié)點序列為(n0, n1,nk)，對于i=1

13、,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。l路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。51l擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。521, 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 EX

14、IT(SUCCESS);6, EXPAND(n)mi, G:=ADD(mi, G);537, 標(biāo)記和修改指針：ADD(mj, OPEN), 并標(biāo)記mj到n的指針；計算是否要修改mk、ml到n的指針；計算是否要修改ml到其后繼節(jié)點的指針；8, 對OPEN中的節(jié)點按某種原則重新排序；9, GO LOOP；54.mjmkml55修改指針舉例123456s56修改指針舉例（續(xù)1）123456s57123456修改指針舉例（續(xù)2）s58123456修改指針舉例（續(xù)3）s59l深度優(yōu)先搜索l寬度優(yōu)先搜索601, G:=G0(G0=s), OPEN:=(s), CLOSED:=( );2, LOOP: IF

15、 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(mj, OPEN), 并標(biāo)記mj到n的指針;10, GO LOOP;612 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52

16、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目標(biāo)62l一般不能保證找到最優(yōu)解l當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制

17、l最壞情況時，搜索空間等同于窮舉l與回溯法的差別：圖搜索l是一個通用的與問題無關(guān)的方法63寬度優(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 目標(biāo)在mi中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并標(biāo)記m

18、j到n的指針;9, GO LOOP;642 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目標(biāo)82 3 41 8 7 6 5465l當(dāng)問題有解時，一定能找到解l當(dāng)問題為單位耗散值，且問題有解時，一定能找到最

19、優(yōu)解l方法與問題無關(guān)，具有通用性l效率較低l屬于圖搜索方法66l目的解決寬度優(yōu)先方法的空間問題和回溯方法不能找到最優(yōu)解的問題。l思想首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。67l利用知識來引導(dǎo)搜索，達到減少搜索范圍，降低問題復(fù)雜度的目的。l啟發(fā)信息的強度強：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解68l引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。69l定義一個評價函數(shù)f，對當(dāng)前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。70l評價函數(shù)的格式：f

20、(n) = g(n) + h(n)f(n)：評價函數(shù)h(n)：啟發(fā)函數(shù)71lg*(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)的估計值721, 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, CL

21、OSED);6, EXPAND(n) mi, 計算f(n, mi):=g(n, mi)+h(mi);73ADD(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幾個等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中s是初始節(jié)點，t是目標(biāo)節(jié)點，n是s到t的最佳路徑上的節(jié)點。82定理1：對有限圖，如果從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在，則算法A一定成功結(jié)束。83引理2.1 ：對無限圖，若有從初始節(jié)點s到目標(biāo)節(jié)點t的路徑，則A*不

22、結(jié)束時，在OPEN表中即使最小的一個f值也將增到任意大，或有f(n)f*(s)。84引理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)85定理2：對無限圖，若從初始節(jié)點s到目標(biāo)節(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é)束，將導(dǎo)致矛盾。86推論2.1：OPEN表上任一具有f(n)f*(s)

23、的節(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) (目標(biāo)節(jié)點除外)，則A1擴展的節(jié)點數(shù)A2擴展的節(jié)點數(shù)91l注意： 在定理4中，評價指標(biāo)是“擴展的節(jié)點數(shù)”，也就是說，同一個節(jié)點無論被擴展多少次，都只

24、計算一次。92l使用數(shù)學(xué)歸納法，對節(jié)點的深度進行歸納l（1）當(dāng)d(n)0時，即只有一個節(jié)點，顯然定理成立。l（2）設(shè)d(n)k時定理成立。（歸納假設(shè)）l（3）當(dāng)d(n)=k+1時，用反證法。l設(shè)存在一個深度為k1的節(jié)點n，被A2擴展，但沒有被A1擴展。而由假設(shè)，A1擴展了n的父節(jié)點，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時，n將被保留在OPEN中。93l所以有：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時，

25、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) ，與定理條件矛盾。故定理得證。94l平均分叉樹設(shè)共擴展了d層節(jié)點，共搜索了N個節(jié)點，則:其中，b*稱為平均分叉樹。lb*越小，說明h效果越好。l實驗表明，b*是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。*1*1)1(bbNd95例：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=1

26、4, N=113, b*=1.23;d=20, N=676,b*=1.2796l一般來說，A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時：abs(h(n)-h*(n) O(log(h*(n)A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下， h與h*的差別至少是和離目標(biāo)的距離成正比的。97l問題的提出：因A算法第6步對ml類節(jié)點可能要重新放回到OPEN表中，因此可能會導(dǎo)致多次重復(fù)擴展同一個節(jié)點，導(dǎo)致搜索效率下降。98s(10)A(1)B(5)C(8)G 目標(biāo)631118一個例子：OPEN表CLOSED表s(10)s(10)A(7) B(8) C(9)A(7) s(10)B(8) C

27、(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)99l在前面的擴展中，并沒有找到從初始節(jié)點到當(dāng)前節(jié)點的最短路徑，如節(jié)點A。s(10)A(1)B(5)C(8)G 目標(biāo)631118100l對h加以限制能否對h增加適當(dāng)?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑。l對算法加以改進能否對算法加以改進，避免或減少節(jié)點的多次擴展。101l可采納性不變l不多擴展節(jié)點l不增

28、加算法的復(fù)雜性102l定義：一個啟發(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)103l定理5：若h(n)是單調(diào)的，則A*擴展了節(jié)點n之后，就已經(jīng)找到了到達節(jié)點n的最佳路徑。即：當(dāng)A*選n擴展時，有g(shù)(n)=g*(n)。104l設(shè)n是A*擴展的任一節(jié)點。當(dāng)ns時，定理顯然成立。下面考察n s的情況。l設(shè)P(n0=s, n1, n2, , nk=n)是s到n的最佳路徑lP中一定有節(jié)點在CL

29、OSED中，設(shè)P中最后一個出現(xiàn)在CLOSED中的節(jié)點為nj，則nj+1在OPEN中。105l由單調(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應(yīng)用上不等式，有： g*(nj+1)+h(nj+1) g*(nk)+h(nk)l即：f(nj+1) g*(n)+h(n) 注意：(nj在CL

30、OSED中，nj+1在OPEN中)106l重寫上式：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)。得證。107l定理6：若h(n)是單調(diào)的，則由A*所擴展的節(jié)點序列其f值是非遞減的。即f(ni) f(nj)。 108l由單調(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

31、(ni)+C(ni, nj) f(ni)-g(ni) - f(nj)+ g(ni)+C(ni, nj) C(ni, nj) f(ni) - f(nj) 0，得證。109l8數(shù)碼問題：h為“不在位”的將牌數(shù) 1h(ni) - h(nj) = 0(nj為ni的后繼節(jié)點) -1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。110l一些結(jié)論：OPEN表上任以具有f(n) f*(s)的節(jié)點定會被擴展。A*選作擴展的任一節(jié)點，定有f(n)f*(s)。111OPEN = ( )f*(s)f值小于f*(s)的節(jié)點f值大于等于f*(s)的節(jié)點fm：到目前為止已擴展節(jié)點的最大f值，用fm代替f*(

32、s)1121, 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。113s(10)A(1)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

33、) B(2+5)10A(3+1) s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0) 114l如果令：f(n) = max(f(n的父節(jié)點), g(n)+h(n)則容易證明，這樣處理后的h是單調(diào)的。115l基本思想：回溯與A*的結(jié)合l算法簡介（非嚴格地）1，設(shè)初始值f0；2，集合SNULL；3，用回溯法求解問題，如果節(jié)點n的f值大于f0，則將該節(jié)點放入集合S中，并回溯；4，如果在3中找到了解，則結(jié)束；5，如果3以失敗結(jié)束，則f0S中節(jié)點的最小f值；6，返回到2。116例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為12。13551441332523123122552342543433分析：

34、 陰影部分數(shù)字和：48 直徑部分數(shù)字和：24 轉(zhuǎn)45改變陰影部分 轉(zhuǎn)90改變直徑部分 但不改變陰影部分 轉(zhuǎn)180改變扇區(qū)部分 但不改變陰影部分 也不改變直徑部分117l爬山法（局部搜索算法）118l隨機搜索算法l動態(tài)規(guī)劃算法如果對于任何n，當(dāng)h(n)=0時，A*算法就成為了動態(tài)規(guī)劃算法。119S0tS1S2S3SnW0W1,1W1,2W2,1W2,2W2,3W3,3W3,2W3,1Wn,1Wn,2Wn,3Wn+1120其中：Q(Wij)表示到點Wij的最佳路徑值 D(Wi-1,j, Wi,k)表示W(wǎng)i-1,j到Wi,k的距離0i00i)W,W(D)W(Qmin)W(Qj , ik , 1ik , 1ikj , i121l漢字識別后處理l一個例子我錢線載哦栽哉裁劣綏優(yōu)仍們仿倫奶砧犯扔妨要耍密窮安壁駐努窯垂扳報叔嵌奴振技寂敘蔽奮夯杏蠶香脊秀吞吝番精猜指潔括治捐活冶桔種神襯祥科鐘拌樣拎補 122niiiwwwPSP111).|()()()|()()|(OPSOPSPOSP二元語法時：niiiwwPSP11)|()()(OP為常量)|(SOP用識別信度代替問題變?yōu)榍髇iiiiwCFwwP11)()|(最大123目標(biāo)目標(biāo)初始節(jié)點sabc124l與或圖是一個超圖，節(jié)點間通過連接符連接。lK-連接符：.K個125k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N為終節(jié)點集 C