人工智能搜索問題102

1、第一章第一章 搜索問題搜索問題 內(nèi)容：狀態(tài)空間的搜索問題。 搜索方式： 盲目搜索 啟發(fā)式搜索 關(guān)鍵問題：如何利用知識(shí)，盡可能有效地找到問題的解（最佳解）。1搜索問題（續(xù)搜索問題（續(xù)1）S0Sg2搜索問題（續(xù)搜索問題（續(xù)2） 討論的問題： 有哪些常用的搜索算法。 問題有解時(shí)能否找到解。 找到的解是最佳的嗎？ 什么情況下可以找到最佳解？ 求解的效率如何。31.1 回溯策略回溯策略 例：皇后問題QQQQ4( )5( )Q(1,1)6( )QQ(1,1)(1,1) (2,3)7( )Q(1,1)(1,1) (2,3)8( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)9( )QQ(1,1

2、)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)10( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)11( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)12( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)13( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)14( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2

3、)Q(1,2) (2,4)15( )(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)16( )(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)17遞歸的思想遞歸的思想從前有座山 從前有座山 從前有座山18遞歸的思想（續(xù)）遞歸的思想（續(xù)）當(dāng)前狀態(tài)目標(biāo)狀態(tài)g19一個(gè)遞歸的例子一個(gè)遞歸的例子int ListLenght(LIST *

4、pList)if (pList = NULL) return 0;else return ListLength(pList-next)+1;NULLpLIST12320回溯搜索算法回溯搜索算法BACKTRACK（DATA）DATA：當(dāng)前狀態(tài)。返回值：從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。21回溯搜索算法回溯搜索算法遞歸過程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);4, LOOP: IF NULL(RULES) RET

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

6、AIL。24回溯搜索算法回溯搜索算法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);25回溯搜索算法回溯搜索算法1（續(xù)）（續(xù)）9,RULES:=TA

7、IL(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);26一些深入的問題一些深入的問題 失敗原因分析、多步回溯QQ27一些深入問題（續(xù)）一些深入問題（續(xù)） 回溯搜索中知識(shí)的利用基本思想(以皇后問題為例)：盡可能選取劃去對角線上位置數(shù)最少的。QQQQ3 2 2 3281.2 圖搜索策略圖搜索策略 問題的引出 回溯搜索：只保留從初始狀態(tài)到當(dāng)前狀態(tài)的一條路徑。 圖搜

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

9、(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 EXIT(SUCCESS);6, EXPAND(n)mi, G:=ADD(mi, G);33一般的圖搜索算法（續(xù)）一般的圖搜索算法（續(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)按某種原則重新

10、排序；9, GO LOOP；34節(jié)點(diǎn)類型說明節(jié)點(diǎn)類型說明.mjmkml35修改指針舉例123456s36修改指針舉例（續(xù)1）123456s37123456修改指針舉例（續(xù)2）s38123456修改指針舉例（續(xù)3）s391.3 無信息圖搜索過程無信息圖搜索過程 深度優(yōu)先搜索 寬度優(yōu)先搜索40深度優(yōu)先搜索深度優(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, O

11、PEN), 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;412 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 5

12、2 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)42深度優(yōu)先搜索的性質(zhì)深度優(yōu)先搜索的性質(zhì) 一般不能保證找到最優(yōu)解 當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制 最壞情況時(shí)，搜索空間等同于窮舉 與回溯法的差別：圖搜索 是一個(gè)通用的與問題無關(guān)的方法43寬度優(yōu)先搜索寬度優(yōu)先搜索1, G:=G0(G0=s), OP

13、EN:=(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)記mj到n的指針;9, GO LOOP;442 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47

14、 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 5445寬度優(yōu)先搜索的性質(zhì)寬度優(yōu)先搜索的性質(zhì) 當(dāng)問題有解時(shí)，一定能找到解 當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解 方法與問題無關(guān)，具有通用性 效率較低 屬于圖搜索方法46漸進(jìn)式深度優(yōu)先搜索方法漸進(jìn)式深度優(yōu)先搜索

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

16、索算法，啟發(fā)式搜索算法A（A算法）算法） 評價(jià)函數(shù)的格式：f(n) = g(n) + h(n)f(n)：評價(jià)函數(shù)h(n)：啟發(fā)函數(shù)51符號的意義符號的意義 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)、f*(n)的估計(jì)值52A算法算法1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THE

17、N EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 計(jì)算f(n, mi):=g(n, mi)+h(mi);53A算法（續(xù)）算法（續(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ù) 幾個(gè)等式幾個(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)。62A*算法的性質(zhì)（續(xù)算法的性質(zhì)（續(xù)

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

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

20、在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由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ù)71A*算法的性質(zhì)（續(xù)算法的性質(zhì)（續(xù)7） 注意：注意： 在定理1.4中，評價(jià)指標(biāo)是“擴(kuò)展的節(jié)點(diǎn)數(shù)”，也就是說，同一個(gè)節(jié)點(diǎn)無論被擴(kuò)展多少次，都只計(jì)算一次。72定理定理1.4的證明的證明 使用數(shù)學(xué)歸納法，對節(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è)深度為k1的節(jié)

21、點(diǎn)n，被A2擴(kuò)展，但沒有被A1擴(kuò)展。而由假設(shè)，A1擴(kuò)展了n的父節(jié)點(diǎn)，即n已經(jīng)被生成了。因此當(dāng)A1結(jié)束時(shí)，n將被保留在OPEN中。73定理定理1.4的證明（續(xù)的證明（續(xù)1） 所以有：f1(n) f*(s) 即：g1(n)+h1(n) f*(s) 所以： h1(n) f*(s) - g1(n) 另一方面，由于A2擴(kuò)展了n，有f2(n) f*(s) 即： h2(n) f*(s) g2(n) (A) 由于d(n)=k時(shí)，A2擴(kuò)展的節(jié)點(diǎn)A1一定擴(kuò)展，有 g1(n) g2(n) (因?yàn)锳2的路A1均走到了) 所以： h1(n) f*(s) - g1(n) f*(s) g2(n) (B) 比較A、B兩式，有

22、 h1(n) h2(n) ，與定理?xiàng)l件矛盾。故定理得證。74對對h的評價(jià)方法的評價(jià)方法 平均分叉樹設(shè)共擴(kuò)展了d層節(jié)點(diǎn)，共搜索了N個(gè)節(jié)點(diǎn)，則:其中，b*稱為平均分叉樹。 b*越小，說明h效果越好。 實(shí)驗(yàn)表明，b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。*1*1)1(bbNd75對對h的評價(jià)舉例的評價(jià)舉例例：8數(shù)碼問題，隨機(jī)產(chǎn)生若干初始狀態(tài)。 使用h1：d=14, N=539,b*=1.44; d=20, N=7276， b*=1.47； 使用h2：d=14, N=113, b*=1.23;d=20, N=676,b*=1.2776A*的復(fù)雜性的復(fù)雜性 一般來說，A*的算法復(fù)雜性是指數(shù)

23、型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)：abs(h(n)-h*(n) O(log(h*(n)A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下， h與h*的差別至少是和離目標(biāo)的距離成正比的。773，A*算法的改進(jìn)算法的改進(jìn) 問題的提出：因A算法第6步對ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。78s(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(1

24、2)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)79出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因 在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。s(10)A(1)B(5)C(8)G 目標(biāo)63111880解決的途徑解決的途徑 對h加以限制 能否對h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。 對算法加以改進(jìn) 能否對算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。81改進(jìn)的條件改進(jìn)的條件 可采納性不變 不多擴(kuò)展節(jié)點(diǎn) 不增

25、加算法的復(fù)雜性82對對h加以限制加以限制 定義：一個(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)83h單調(diào)的性質(zhì)單調(diào)的性質(zhì) 定理1.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(shù)(n)=g*(n)。84定理定理1.5的證明的證明 設(shè)n是A*擴(kuò)展的任一節(jié)點(diǎn)。當(dāng)ns時(shí)，定理顯然成立。下面考察n s的情況。 設(shè)P(n0=s, n

26、1, n2, , nk=n)是s到n的最佳路徑 P中一定有節(jié)點(diǎn)在CLOSED中，設(shè)P中最后一個(gè)出現(xiàn)在CLOSED中的節(jié)點(diǎn)為nj，則nj+1在OPEN中。85定理定理1.5的證明（續(xù)的證明（續(xù)1） 由單調(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) 由于ni 、ni+1在最佳路徑上，所以： g*(ni+1) = g*(ni)+C(ni, ni+1) 帶入上式有： g*(ni)+h(ni) g*(ni+1)+h(ni+1) 從i=j到i=k-1應(yīng)用上不等式，有： g*(nj+1)

27、+h(nj+1) g*(nk)+h(nk) 即：f(nj+1) g*(n)+h(n) 注意：(nj在CLOSED中，nj+1在OPEN中)86定理定理1.5的證明（續(xù)的證明（續(xù)2） 重寫上式：f(nj+1) g*(n)+h(n) 另一方面，A*選n擴(kuò)展，必有： f(n) = g(n)+h(n) f(nj+1) 比較兩式，有： g(n) g*(n) 但已知g*(n)是最佳路徑的耗散值，所以只有：g(n) = g*(n)。得證。87h單調(diào)的性質(zhì)（續(xù)）單調(diào)的性質(zhì)（續(xù)） 定理1.6：若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。即f(ni) f(nj)。 88定理定理1.6的證明的證明

28、 由單調(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，得證。89h單調(diào)的例子單調(diào)的例子 8數(shù)碼問題： h為“不在位”的將牌數(shù) 1h(ni) - h(nj) = 0(nj為ni的后繼節(jié)點(diǎn)) -1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。90對算法加以改進(jìn)對算法加以改進(jìn) 一些結(jié)論： OPEN表上任以具有f(n) f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。 A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)f*(s)。91改進(jìn)的出發(fā)點(diǎn)改進(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)92修正過程修正過程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