【正文】 到終局的與或樹搜索而得到最好的一步棋是不可能的，比如曾有人估計，西洋跳棋完整的博弈樹約有 10的 40次方個節(jié)點(diǎn)。 我們假定 MAX先走，處于奇數(shù)深度級的節(jié)點(diǎn)都對應(yīng)下一步由 MAX走，這些節(jié)點(diǎn)稱為 MAX節(jié)點(diǎn)，相應(yīng)地偶數(shù)級為 MIN節(jié)點(diǎn)。雙方輪流地擴(kuò)展節(jié)點(diǎn)。 (2) 在博弈樹中， 或 節(jié)點(diǎn)和 與 節(jié)點(diǎn)是逐層交替出現(xiàn)的。 2022/8/21 78 ? 這樣，如果站在某一方 (如 MAX方，即 MAX要取勝 )，把上述博弈過程用圖表示出來，則得到的是一棵 與或樹 。此時，如果我們站在 MAX方的立場上，則可供 MAX方選擇的若干行動方案之間是 或 關(guān)系，因?yàn)橹鲃訖?quán)操在 MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由 MAX方自已決定。 2022/8/21 77 ? 在博弈過程中，任何一方都希望自己取得勝利。 (3) 任何一方在采取行動前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的“碰運(yùn)氣”因素。 博弈有很多種，我們討論最簡單的“二人零和、全信息、非偶然”博弈，其特征如下： (1) 對壘的 MAX、 MIN雙方輪流采取行動，博弈的結(jié)果只有三種情況： MAX方勝， MIN方敗； MIN方勝，MAX方敗；和局。 AO*算法在一些特殊場合可以簡化，可以進(jìn)行改進(jìn)，提高算法的性能，暫時不對這些展開討論。由于我們曾經(jīng)假設(shè) h是單調(diào)限制的，費(fèi)用的修正只可能是費(fèi)用的增大。修正費(fèi)用 q(n)是從 n到一組終節(jié)點(diǎn)的一個最佳解圖費(fèi)用的一個修正估計。從剛被擴(kuò)展的節(jié)點(diǎn)開始，此過程修正其費(fèi)用值 (利用其后繼節(jié)點(diǎn)最新計算的費(fèi)用 )，并把外向連接符標(biāo)記到被估計為達(dá)到終節(jié)點(diǎn)的最好路徑上。對這個最好的局部解圖的非終葉節(jié)點(diǎn)之一進(jìn)行擴(kuò)展，并把某個費(fèi)用賦給它的后繼節(jié)點(diǎn)。首先，一個自上而下的圖生長運(yùn)算 (第 4至第 6步 )，通過跟蹤有標(biāo)記的連接符尋找最好的局部解圖。 2022/8/21 73 ? (12) 如果 m已標(biāo)記為 SOLVED，或者 m的修正費(fèi)用不同于它的前一道費(fèi)用，則把 m的所有那樣的父輩節(jié)點(diǎn)都添加到S中去，這些父輩節(jié)點(diǎn)的通過某個有標(biāo)記連接符的后繼節(jié)點(diǎn)之一就是節(jié)點(diǎn) m。 (11) 根據(jù)以下步驟修改 m的費(fèi)用 q(m)：對于從 m指向節(jié)點(diǎn)集 {n1i,… ， nki}的每個連接符，計算 qi(m)=Ci+q(n1i)+…+q(nki) ? 式中， q(nji)(其中 j=1， 2， … ， k)或者通過這一內(nèi)循環(huán)在上述某道運(yùn)算中剛剛計算過，或者，這是第一道運(yùn)算，那么它們已在第 6步中計算過。 2022/8/21 72 ? (7) 建立一個正好包含節(jié)點(diǎn) n的單一節(jié)點(diǎn)集合 S。于未曾在 G中出現(xiàn)過的每一個后繼節(jié)點(diǎn) nj，相應(yīng)的費(fèi)用 q(nj)=h(nj)。 (5) select G’ 的任意一個非終葉節(jié)點(diǎn) n(將在以后說明如何選擇 )。如果 S為終節(jié)點(diǎn)，則標(biāo)記 S為 SOLVED。對于 n在終節(jié)點(diǎn)集合中的情況，若有h(n)=0，則單調(diào)限制意味著 h是 h*的一個下界，即對于所有的節(jié)點(diǎn) n，有 h(n)≤h*(n)。我們假設(shè) ? h(n)≤c+h(n1)+… ， +h(nk) ? 其中， c為連接符的費(fèi)用。正如圖搜索一樣 ,如果 h滿足一定的限制，則搜索過程語句是可能得到簡化的。 2022/8/21 70 *算法 ? 讓我們來描述一種具有啟發(fā)成分的估價函數(shù)的搜索過程，它可以被設(shè)計來用于與或圖。我們稱這樣的一個解圖為最佳解圖。因此，在圖 ，如果每個 k— 連接符的費(fèi)用為 k，兩個解圖的費(fèi)用分別為 8和 7。 在一個解圖費(fèi)用的定義中，我們可能要不止 — 次地計算解圖中某些連接符的值。中 )的費(fèi)用加上從 n的各后繼節(jié)點(diǎn)(在 G’中 )到 N的每個解圖費(fèi)用的總和。令該連接符的費(fèi)用為 Cn，于是我們可得 ? k(n,N)=Cn+k(n1,N)+…+k(ni,N) 2022/8/21 69 ? 從上式可以看出，從節(jié)點(diǎn) n到 N的一個解圖 G39。然后，連接符的費(fèi)用便可用來計算一個解圖的費(fèi)用。 2022/8/21 68 ? 象在普通圖中采用的弧線費(fèi)用葉一樣，在與或圖中給連接符指定一定的費(fèi)用往往是很有用的 (這些費(fèi)用模擬規(guī)則應(yīng)用的代價。是由單一節(jié)點(diǎn) n組成的；若有一個指向節(jié)點(diǎn) {n1， n2， ......，nk}的外向連接符 K，使得從每個 ni到 N有一個解圖，其中i=1， 2， …… ， k，則 G39。是 G的子圖。 設(shè)某個與或圖 G中，從節(jié)點(diǎn) n到一節(jié)點(diǎn)集合 N的一個解圖記作 G39。今后，我們就一直使用這種無環(huán)性假定。 2022/8/21 66 2022/8/21 67 ? 假設(shè)我們的與或圖中不包含環(huán)，即在與或圖中不存在這樣的節(jié)點(diǎn)，它的后繼節(jié)點(diǎn)同時又是它的祖先。圖 n。粗略地說，從一個與或圖的節(jié)點(diǎn) n到節(jié)點(diǎn)集合 N的一個解圖類似于一個普通圖中的一條路徑。在隱含圖中，與滿足產(chǎn)生式系統(tǒng)終止條件的數(shù)據(jù)庫相對應(yīng)的是一個終節(jié)點(diǎn)集合。每條產(chǎn)生式規(guī)則在隱含圖中都對應(yīng)于一個連接符。初始數(shù)據(jù)庫對應(yīng)于圖中一個特別的節(jié)點(diǎn)，叫做起始節(jié)點(diǎn)。在與或圖中，我們把沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)叫作葉節(jié)點(diǎn) (對于與或樹則叫做端節(jié)點(diǎn) )。 ? 在與或樹中，每個節(jié)點(diǎn)最多只有一個父輩節(jié)點(diǎn)。節(jié)點(diǎn) n4和 n5可以稱為一組與節(jié)點(diǎn)，而 n1可稱為或節(jié)點(diǎn)。有二個 1— 連接符指向其后繼節(jié)點(diǎn) n1，還有一個 2— 連接符指向其后繼節(jié)點(diǎn)集合 {n4， n5}。圖 。這些超弧線又叫做連接符。不過，我們?nèi)匀话堰@些結(jié)構(gòu)叫做與或圖，并在討論與或樹時繼續(xù)采用與節(jié)點(diǎn)和或節(jié)點(diǎn)等術(shù)語。在這種情況下，對于其中一個父輩節(jié)點(diǎn)來說它可以叫做或節(jié)點(diǎn)，而對另一個父輩節(jié)點(diǎn)它又可以叫做與節(jié)點(diǎn)。 2022/8/21 61 ? 我們所要討論的一般是與或圖，而不是與或樹這種特殊情況，因?yàn)閼?yīng)用不同序列的規(guī)則可能生成相同的數(shù)據(jù)庫。一種情況是由總數(shù)據(jù)庫標(biāo)記的一個父輩節(jié)點(diǎn)擁有一組與后繼節(jié)點(diǎn)，每一個后繼節(jié)點(diǎn)都用一個分量數(shù)據(jù)庫來標(biāo)記。 ? (7) GO LOOP 2022/8/21 58 A*算法框圖 2022/8/21 59 雙向搜索 ? 雙向搜索指從初始狀態(tài)開始的正向搜索到從目標(biāo)狀態(tài)開始的逆向搜索同時進(jìn)行，直至這兩條路徑在中途某處相交為止，正向推理是規(guī)則左邊的狀態(tài)與現(xiàn)有狀態(tài)相匹配，而右邊的狀態(tài)用于生成新的節(jié)點(diǎn)，直至達(dá)到目標(biāo)節(jié)點(diǎn)為止。 (g) 若 SUCCSSOR在 CLOSE表中，則轉(zhuǎn)向 c。 (e) 若至 OLD節(jié)點(diǎn)的代價較低或一樣，則停止擴(kuò)展節(jié)點(diǎn)。 (d) 比較新舊路徑代價。 (b) 計算 g(SUC)=g(BES)+g(BES,SUC)。 ? (5) 若 BESTNODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn) SUCCSSOR。 ? (3) 選取 OPEN表中未設(shè)置過的具有最小 f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn) BESTNODE，并把它放入 CLOSED表。 ? (2) 重復(fù)下列過程，直至找到目標(biāo)節(jié)點(diǎn)止。因此， f是根據(jù)需要找到一條最小代價路徑的觀點(diǎn)來估算節(jié)點(diǎn)的，所以，可考慮每個節(jié)點(diǎn) n的估價函數(shù)值為兩個分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn) n的代價以及從節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn)的代價。 A*算法是一種有序搜索算法，其特點(diǎn)在于對估價函數(shù)的定義上。 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 2022/8/21 55 ? A算法和 A*算法的定義 定義 1 在 GRAPHSEARCH過程中，如果第 8步的重排OPEN表是依據(jù) f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為 A算法。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信息相似。這個定義包含了g(n)≥g*(n)。 ? 我們希望估價函數(shù) f是 f*的一個估計，此估計可由下式給出： ? f(n)=g(n)+h(n) 其中： g是 g*的估計； h是 h*的估計。為此，引進(jìn)一個新函數(shù) g*，這將使我們的記號得到某些簡化。 ? 令 h*(n)表示整個目標(biāo)節(jié)點(diǎn)集合｛ ti｝上所有 k(n,ti)中最小的一個，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價路徑的代價，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個目標(biāo)節(jié)點(diǎn)的最佳路徑 (對于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù) h*沒有定義 )。令 k(ni， nj)表示任意兩個節(jié)點(diǎn) ni和 nj之間最小代價路徑的實(shí)際代價 (對于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn)，函數(shù) k沒有定義 )。因此， OPEN表上具有最小 f值的那個節(jié)點(diǎn)就是所估計的加有最少嚴(yán)格約束條件的節(jié)點(diǎn)，而且下一步要擴(kuò)展這個節(jié)點(diǎn)是合適的。使用不能識別某些節(jié)點(diǎn)真實(shí)希望的估價函數(shù)會形成非最小代價路徑；而使用一個過多地估計了全部節(jié)點(diǎn)希望的估價函數(shù) (就像寬度優(yōu)先搜索方法得到的估價函數(shù)一樣 )又會擴(kuò)展過多的節(jié)點(diǎn)。不過，估價函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點(diǎn)數(shù) (如果我們只用估價函數(shù) f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程 )。圖中圓圈內(nèi)的數(shù)字表示該節(jié)點(diǎn)的 f值，不帶圈的數(shù)字表示節(jié)點(diǎn)擴(kuò)展的順序。 2022/8/21 47 ? 因此，起始節(jié)點(diǎn)棋局 ?2 8 3 ?1 6 4 ?7 5 ? 的 f值等于 0+4=4。 2022/8/21 46 有序搜索例子 ? 下面讓我們再次用八數(shù)碼難題的例子來說明過程GRAPHSEARCH是如何應(yīng)用估價函數(shù)排列節(jié)點(diǎn)的。 有序搜索的有效性直接取決于 f的選擇，如果選擇的 f不合適，有序搜索就可能失去一個最好的解甚至全部的解。對于寬度優(yōu)先搜索，我們選擇 f(i)作為節(jié)點(diǎn) i的深度。值得提出的是，即使搜索空間是一般的搜索圖，其顯示子搜索圖總是一棵樹，因?yàn)楣?jié)點(diǎn) j從來沒有同時記錄過一個以上的父輩節(jié)點(diǎn)。具有最小估價函數(shù) f（ j）的節(jié)點(diǎn)被選作父輩節(jié)點(diǎn)。 ? (iii) 如果節(jié)點(diǎn) j在 CLOSED表中，則把它移回 OPEN表 ? (7) 轉(zhuǎn)向 (2)，即 GO TO(2)。如果新的 f值較小，則 ? (i) 以此新值取代舊值。從 j加一指向其父輩節(jié)點(diǎn) i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時記住一個解答路徑。對于 i的每一個后繼節(jié)點(diǎn) j： ? (a) 計算 f(j)。 ? (5) 如果 i是個目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個解。結(jié)果有幾個節(jié)點(diǎn)合格，當(dāng)其中有一個為目標(biāo)節(jié)點(diǎn)時，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個節(jié)點(diǎn)作為節(jié)點(diǎn) i。 ? (2) 如果 OPEN是個空表，則失敗退出，無解。被選為擴(kuò)展的節(jié)點(diǎn)，是估價函數(shù)最小的節(jié)點(diǎn)。 ? 尼爾遜（ Nilsson）曾提出一個有序搜索的基本算法?？梢娝偸沁x擇最有希望的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)。應(yīng)用某個算法 (例如等代價算法 )選擇 OPEN表上具有最小 f值的節(jié)點(diǎn)作為下一個要擴(kuò)展的節(jié)點(diǎn)。根據(jù)習(xí)慣， OPEN表上的節(jié)點(diǎn)按照它們 f函數(shù)值的遞增順序排列。 一般形式： f(n)=g(n)+h(n)， g(n)是從 s0到 n的實(shí)際代價，h(n)是從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn) sg的估計代價。 我們用符號 f來標(biāo)記估價函數(shù)，用 f(n)表示節(jié)點(diǎn) n的估價函數(shù)值。在狀態(tài)空間問題中， 一種方法 是估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離； 另一種方法 認(rèn)為，解答路徑包括被估價過的節(jié)點(diǎn)，并計算全條路徑的長度或難度。 ? 估價函數(shù)的任務(wù)就是估計 OPEN表中各節(jié)點(diǎn)的重要程度。這種搜索叫做 有序搜索 (ordered search)。 在本節(jié)中，我們只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個是下一步要擴(kuò)展的節(jié)點(diǎn)。 (2) 在擴(kuò)展一個節(jié)點(diǎn)的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點(diǎn)，以免盲目地同時生成所有可能的節(jié)點(diǎn)。 把利用啟發(fā)信息的搜索方法叫做 啟發(fā)性搜索方法 。人們就試圖找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會大為提高。 2022/8/21 36 圖 等代價搜索算法框圖 2022/8/21 37 啟發(fā)式搜索 ? 盲目搜索的不足：效率低，耗費(fèi)過多的計算空間與時間。提供回到節(jié)點(diǎn) i的指針。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第 (2)步。 (4) 如果節(jié)點(diǎn) i為目標(biāo)節(jié)點(diǎn)，則求得一個解。如果有幾個節(jié)點(diǎn)都合格，那么就要選擇一個目標(biāo)節(jié)點(diǎn)作為節(jié)點(diǎn) i(要是有目標(biāo)節(jié)點(diǎn)的話 )；否則，就從中選一個作為節(jié)點(diǎn) i。 (2) 如果 OPEN是個空表，則沒有解而失敗退出。如果此起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解 。 2022/8/21 34 ? 有如下一些記號： 起始節(jié)點(diǎn)記為 S； 從節(jié)點(diǎn) i到它的后繼節(jié)點(diǎn) j的連接弧線代價記為 c(i,j)； 從起始節(jié)點(diǎn) S到任一節(jié)點(diǎn) i的路徑代價記為 g(i)。搜索樹中每條連接弧線上的有關(guān)代價以及隨之而求得的具有最小代價的解答路徑，與許多這樣的廣義準(zhǔn)則相符合。從圖可見，深度優(yōu)先搜索過程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再