【正文】 W（ Pi） ←i 為出現(xiàn)相同關(guān)鍵字提。 對(duì)相同關(guān)鍵字的處理，算法附加了三個(gè)數(shù)組空間：每一記錄的鏈指針空間L（ i）， 鏈?zhǔn)字羔樋臻g Q，鏈當(dāng)前指針空間 W。其中，很可能出現(xiàn) Pi=Pj (i≠j), 這說(shuō)明 Ri和 Rj被其它規(guī)則依賴(lài)的條數(shù)相同。 Pi對(duì)應(yīng)于 Ri，相當(dāng)于 Ri 被 依賴(lài)次數(shù) Pi。 B5: 一遍掃描 Pi（ i=1， 2, ...， N)，求 Pmax。 然后轉(zhuǎn)B2。 然后轉(zhuǎn) B5。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） B1: [初始化 ]，有 N條規(guī)則，置 P1至 PN皆為 1。 枚舉計(jì)數(shù)：如果規(guī)則 Ri被規(guī)則 Rj依賴(lài) (j=1， 2, ..., N)，則Pi=pi+1（ Pi初值賦 1) 。相同數(shù)據(jù)落在同一數(shù)組元素中， 用計(jì)數(shù)方式可知有幾個(gè)。 顯然 Pi=50，對(duì)應(yīng) D(50)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 2 規(guī)則排序算法 排序算法原則 映射排列：是一個(gè)基于地址計(jì)算的排序。這些規(guī)則有可能還與未完成的其它語(yǔ)句有關(guān)。 靜態(tài)規(guī)則排列：亦是在原文分析、原文譯文轉(zhuǎn)換、譯文生成之前， 對(duì)規(guī)則集中已有 的規(guī)則按優(yōu)先次序排列。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 2 規(guī)則排序算法 排序算法原則 依賴(lài)規(guī)則：如果 Ri的結(jié)論部份包含有 Rj的條件部份，則Rj是一個(gè)依賴(lài)規(guī)則，即 Rj 依 賴(lài)規(guī)則 Ri，或稱(chēng) Ri是一個(gè)被依賴(lài)規(guī)則。 對(duì)相同 IF部分的規(guī)則繼續(xù)用它的各自 THEN部分作為其它可以匹配的 IF前提條件 , 遞歸地構(gòu)造 , 如發(fā)現(xiàn)兩個(gè)推理圖上分別有節(jié)點(diǎn)在 THENTHEN表上是矛盾的 , 則檢測(cè)出沖突規(guī)則 , 人工予以解決。 (2) 對(duì)于沖突規(guī)則 , 構(gòu)造 IFIF表 , 對(duì)規(guī)則集內(nèi)有相同的 IF 規(guī)則子句構(gòu)造規(guī)則樹(shù) , 形成推理圖。 (4) 從屬規(guī)則 : 兩個(gè)規(guī)則有相同的結(jié)果 , 但其中一個(gè)包含有多余的約束條件。 也有可能由多條規(guī)則鏈形成沖突規(guī)則集 。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 1 規(guī)則不一致原因及解決方法 主要的不一致規(guī)則種類(lèi) (1) 循環(huán)規(guī)則 : 由數(shù)個(gè)規(guī)則的前提和結(jié)論形成一個(gè)循環(huán)鏈 , 最終由末尾規(guī)則的結(jié)果 子句推出起始規(guī)則的前提部分 。但隨著時(shí)間的推移 , 新的規(guī)則不斷加入 , 規(guī)則集合越來(lái)越大 , 內(nèi)容也越來(lái)越豐富 , 這時(shí)規(guī)則間的相互影響和相互聯(lián)系就隨之變得復(fù)雜。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 1 規(guī)則不一致原因及解決方法 規(guī)則集中存在的不一致是影響系統(tǒng)性能的重要因素之一。 (3) 當(dāng)檢索到一個(gè)與新問(wèn)題部分相似的過(guò)去問(wèn)題的求解事例時(shí) , 程序能提取相似部 分解過(guò)程 , 還能組織部分搜索、銜接新的解過(guò)程。 一般要考慮以下 幾點(diǎn) : (1) 當(dāng)檢索沒(méi)有類(lèi)比啟發(fā)信息時(shí) , 程序能轉(zhuǎn)向常規(guī)搜索方法。 此外 , 還可設(shè)置相似度閥值， 檢索采用直接映射式方法。 相似程度越高 , 度量方法恰當(dāng) , 相似問(wèn)題的檢索俞易獲得。 這是一個(gè)很有意義的研究課題。 第二是只記問(wèn)題的最終解。 為了給相似問(wèn)題的求解提供有用信息 , 就要確定保存搜索過(guò)程中的哪些有用特征信息。 求解一個(gè)復(fù)雜問(wèn)題時(shí) , 經(jīng)常面臨龐大的搜索。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 類(lèi)比搜索方法實(shí)施的關(guān)鍵技術(shù)在于生成求解事例、相似性度量和檢索、 以及指導(dǎo)求 解。 AND/OR圖的啟發(fā)式搜索算法 AO*是通過(guò)評(píng)價(jià)函數(shù) f(n)=h(n)來(lái)引導(dǎo)搜索過(guò)程 , 適用于分解得到的子問(wèn)題不存在相互作用的情況。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 用 AND/OR圖算法求解問(wèn)題時(shí) , 求解過(guò)程就是對(duì)一個(gè)隱含的 AND/OR圖進(jìn)行搜索。 隨著求解次數(shù)的增加 , 求解事例將不斷積累 , 類(lèi)比的資料增多 (啟發(fā)信息增多 ), 從而使求解問(wèn)題 的效率不斷提高。 當(dāng)沒(méi)有檢索到一個(gè)與新問(wèn)題相似的過(guò)去問(wèn)題的求解事例時(shí) , 則使用 A*或 AO*等算法進(jìn)行 , 并在獲得解時(shí)將求解過(guò)程作為一個(gè)求 解事例存儲(chǔ)在事例庫(kù)中。 過(guò)去問(wèn)題與新問(wèn)題的相似性越高 , 求解過(guò)程需要的搜索就越少。 具體地說(shuō) , 就是在新問(wèn)題的求解過(guò)程中 , 對(duì)過(guò)去問(wèn)題的求解事例中記錄的成功搜索路徑上每個(gè)操作的依據(jù)條件重新測(cè)試 . 如果依據(jù)條件仍滿足 , 則算法根隨成功的求解路徑。類(lèi)比搜索方法在每次求解一個(gè)新問(wèn)題時(shí) , 不是直接去搜索給定的狀態(tài)空間 , 而是首先在求解事例庫(kù)中檢索 , 查找與該問(wèn)題相似的過(guò)去問(wèn)題的求解事例。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類(lèi)比搜索方法探討 方法探討 基于上述幾點(diǎn) , 需要建立一個(gè)類(lèi)比的啟發(fā)式搜索求解模型。 (2) 如何定義和判斷兩個(gè)問(wèn)題的求解情況是相似的 , 如何高效的進(jìn)行檢索。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類(lèi)比搜索方法探討 方法探討 類(lèi)比搜索方法把類(lèi)比推理技術(shù)與狀態(tài)空間的啟發(fā)式搜索相結(jié)合 , 實(shí)際上是對(duì)人類(lèi)求 解問(wèn)題、積累經(jīng)驗(yàn)和增加求解問(wèn)題能力的一種模擬。 (3) 在擴(kuò)展節(jié)點(diǎn)的過(guò)程中 , 決定那些節(jié)點(diǎn)可從搜索樹(shù)上刪除。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類(lèi)比搜索方法探討 方法探討 AO*、 A及其它算法在問(wèn)題的求解過(guò)程中利用與該問(wèn)題相關(guān)的啟發(fā)信息來(lái)幫助搜索 , 啟發(fā)信息通常被用于三種情況 : (1) 幫助確定擴(kuò)展節(jié)點(diǎn)。 即 , 利用類(lèi)比獲得與新問(wèn)題相似的過(guò)去問(wèn)題的求解過(guò)程 , 作為啟發(fā)信息來(lái)指導(dǎo)新問(wèn)題的求解 , 這樣可以縮小搜索范圍 , 降低問(wèn)題求解的復(fù)雜性。 人類(lèi)求解問(wèn)題的一個(gè)重要特點(diǎn) , 就是常常利用以前求解相同 或相似問(wèn)題的經(jīng)驗(yàn)來(lái)指導(dǎo)新問(wèn)題的求解。 此外 , 搜索算法一般執(zhí)行一次性搜索 , 將同一問(wèn)題的多次搜索視為彼此獨(dú)立、毫無(wú)相關(guān)的過(guò)程。 其次由于 k 連接符 連接的有關(guān)子節(jié)點(diǎn) , 對(duì)于父節(jié)點(diǎn)能解與否以及耗散值都有影響 , 因而不能象 A算法那樣優(yōu)先擴(kuò)展其中具有最小耗散值的節(jié)點(diǎn)。 當(dāng) h(n)≡0時(shí) , AO*成寬度優(yōu)先算法。中的一個(gè)非終節(jié)點(diǎn)擴(kuò)展值得研究 : 一般可以選一個(gè)最可能導(dǎo)致該局部解圖耗散值發(fā)生較大變化的那個(gè)節(jié)點(diǎn)先擴(kuò)展 , 因?yàn)檫x這個(gè)節(jié)點(diǎn)先擴(kuò)展 , 會(huì)促使及時(shí)修改局部解圖的標(biāo)記。 (2) 在 A6中擴(kuò)展節(jié)點(diǎn) n時(shí) , 若不存在后繼節(jié)點(diǎn) (即限入死胡同 ), 則可在 A11中對(duì) m(即 n) 賦一個(gè)高的 q值 , 這個(gè)高的 q值會(huì)依次傳遞到 s, 使得含有節(jié)點(diǎn) n的子圖具有高的 q(s), 從而排除了被當(dāng)作后選局部解圖的可能性。 A7～ A12, 完成自下而上的耗散值修正、連接符標(biāo)記和節(jié)點(diǎn)的能解標(biāo)記。 若該連接符的所有子節(jié)點(diǎn)都是能解的 , 則 m也標(biāo)上能解 . A12: IF M(m, SOLVED)∨ (q(m)≠q0(m)) THEN ADD(ma, S)。 這個(gè) m的子節(jié)點(diǎn) mc應(yīng)不在 S中 . A11: (1) 修改 m的耗散值 q(m): 對(duì) m指向節(jié)點(diǎn)集 {n1i, n2i, …, nki} 的每一個(gè)連接符 i分別計(jì)算 qi, qi(m)=Ci+q(n1i)+…+q(nki), q(m):=min qi(m)。 把 n的子節(jié)點(diǎn)添加到 G中 , 對(duì) G中未出現(xiàn)的子節(jié)點(diǎn) 計(jì)算耗散值 , 若有終節(jié)點(diǎn)則加能解標(biāo)記 . A7: S:={n}。中的任一非終節(jié)點(diǎn) 。 根據(jù)連接符標(biāo)記 (指針 )找出一個(gè)待擴(kuò)展的局部解圖 G39。開(kāi)始時(shí)圖 G只包含 s, 耗散值估計(jì)為 h(s), 若 s是終節(jié)點(diǎn) , 則標(biāo)記能解 . A2: Until s已標(biāo)記上 SOLVED, do: A3: begin A4: G39。 定義 8 若啟發(fā)式估價(jià)函數(shù) h滿足單調(diào)限制 , 即對(duì)AND/OR圖中任意節(jié)點(diǎn) n及其適用于 n的任一 k連接符 , 有 h(n)≤Ck+h(n1)+…+h(nk) 其中 , Ck為 k連接符的耗散值 , n1,n2,…,nk 是應(yīng)用 k 連接符于節(jié)點(diǎn) n所得的全部后繼節(jié)點(diǎn)。 令函數(shù)h*(n)表示從 AND/OR圖中的節(jié)點(diǎn) n 到一可解的葉節(jié)點(diǎn)集合的最佳 解圖的耗散值 。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) 定義 定義 6 從 AND/OR圖任意節(jié)點(diǎn) n到一立即可解的葉節(jié)點(diǎn)集合 N的解圖耗散值 k(n,N) 可遞歸地定義為： (1) 若節(jié)點(diǎn) n是集合 N中的元素 , 則 k(n,N)=0。由節(jié)點(diǎn) n、 k連接符、節(jié)點(diǎn) {n1,n2, …, nk } 以及從{n1, n2, …, nk} 中的每個(gè)節(jié)點(diǎn)到集合 N的解圖組成。是由單一節(jié)點(diǎn) n組成的 。是 G的子圖 。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) 定義 定義 5 設(shè) AND/OR圖 G, 則從節(jié)點(diǎn) n到一立即可解的葉節(jié)點(diǎn)集合 N的一解圖 G39。 如果確定某個(gè)節(jié)點(diǎn)是可解節(jié)點(diǎn) , 則不可 解的后裔節(jié)點(diǎn)不再有用 , 可從搜索圖中刪去 。 (4) 選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn) , 反復(fù)執(zhí)行 (2)和 (3), 直至找到可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。 (2) 應(yīng)用分解或等價(jià)變換算符對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。 下面分析 AND/OR圖 AO*搜索算法 , 作一些改進(jìn)探討 。 定義 3 可解節(jié)點(diǎn) 在 AND/OR圖中 , 滿足下列條件之一者為可解節(jié)點(diǎn) : (1) 它是一個(gè)終止節(jié)點(diǎn) . (2) 它是一個(gè) OR節(jié)點(diǎn) , 且子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn) . (3) 它是一個(gè) AND節(jié)點(diǎn) , 且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 4 AND/OR圖搜索算法 定義 2 OR圖及 OR圖算法把 一個(gè)復(fù)雜問(wèn)題利用同構(gòu)或同態(tài)的等價(jià)變換 , 使之成為若干個(gè)較容易求解的新問(wèn)題。 定義 1 AND圖及 AND圖算法把 一個(gè)復(fù)雜的問(wèn)題分解成若干個(gè)較為簡(jiǎn)單的子問(wèn)題 , 每個(gè)子問(wèn)題又可繼續(xù)分解為更為簡(jiǎn)單的子問(wèn)題 , 重復(fù)此過(guò)程 , 直到不需要再分解或者不能再分解為止。 但對(duì)于復(fù)雜的問(wèn)題 , 它們并不是唯一的途徑 , 若利用它們直接求解往往還比較困難。 那么等價(jià)問(wèn)題的搜索過(guò)程A1,A2,…,An 是完備的 ,則搜索過(guò)程 A也是完備的。 那么各子問(wèn)題的搜索過(guò)程A1,A2,…,An 是完備的 , 則搜索過(guò)程 A也是完備的。 當(dāng) v↑, 強(qiáng)調(diào)歷史信息 , 搜索過(guò)程沿橫向掃描 , 有利于完 備性 , 但降低了搜索效率。g(x)+w 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) 討論 (1) 啟發(fā)式搜索算法在大問(wèn)題中一般優(yōu)于非啟發(fā)式搜索算法 , 因此 ,有效地分析利用啟發(fā)信息尤為重要。 否則放入 OPEN2中。 若知道感興趣集且啟發(fā)式搜索算法恰當(dāng)?shù)貞?yīng)用感興趣集 , 則肯定可以改善算法的搜索效率。 這兩個(gè)結(jié)論都是在 h(x)滿足單調(diào)限制時(shí)才成立 . 對(duì)于第 2個(gè)結(jié)論 , 當(dāng) h(x)不滿足單調(diào) 限制時(shí) , 有可能某個(gè)要擴(kuò)展的節(jié)點(diǎn)比以前擴(kuò)展的節(jié)點(diǎn)具有較小的 f值 . 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 改進(jìn) 3 引入感興趣集的算法 : 這一改進(jìn)的思路是這樣的 , 問(wèn)題求解時(shí) , 人們往往知道最佳路徑上有關(guān)節(jié)點(diǎn)的某些啟發(fā)信息。 若把上式改寫(xiě) h(xi)≤h(xj)+c(xi,xj), 可看出節(jié)點(diǎn)xi到目標(biāo)節(jié)點(diǎn)的估價(jià)不會(huì)