【正文】 索被看成相互關(guān)聯(lián)的過程 , 前面搜索積累的經(jīng)驗將有助于提高后 面搜索的效率。 即 , 利用類比獲得與新問題相似的過去問題的求解過程 , 作為啟發(fā)信息來指導(dǎo)新問題的求解 , 這樣可以縮小搜索范圍 , 降低問題求解的復(fù)雜性。 也就是說 , 如果算法設(shè)計恰當(dāng) , 可以自動獲得啟發(fā)信息。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類比搜索方法探討 方法探討 AO*、 A及其它算法在問題的求解過程中利用與該問題相關(guān)的啟發(fā)信息來幫助搜索 , 啟發(fā)信息通常被用于三種情況 : (1) 幫助確定擴展節(jié)點。 (2) 在擴展節(jié)點的過程中 , 幫助決定產(chǎn)生后繼節(jié)點。 (3) 在擴展節(jié)點的過程中 , 決定那些節(jié)點可從搜索樹上刪除。值得注意的是 , 啟發(fā)信息是一種局部信息 , 只在搜索路徑的每個節(jié)點上為選擇操作提供參考。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類比搜索方法探討 方法探討 類比搜索方法把類比推理技術(shù)與狀態(tài)空間的啟發(fā)式搜索相結(jié)合 , 實際上是對人類求 解問題、積累經(jīng)驗和增加求解問題能力的一種模擬。 要實現(xiàn)它 , 需要解決如下一些主要問題 : (1) 如何積累問題求解的經(jīng)驗 , 即在一個問題的求解過程中 , 需要記錄那些有用信息。 (2) 如何定義和判斷兩個問題的求解情況是相似的 , 如何高效的進行檢索。 (3) 如何有效地使用類比結(jié)論 , 即相似的過去問題的求解經(jīng)驗 , 作為特殊的啟發(fā)信息指導(dǎo)新問題的求解。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類比搜索方法探討 方法探討 基于上述幾點 , 需要建立一個類比的啟發(fā)式搜索求解模型。 它主要包括生成求解事例、檢索及指導(dǎo)求解三個推理過程。類比搜索方法在每次求解一個新問題時 , 不是直接去搜索給定的狀態(tài)空間 , 而是首先在求解事例庫中檢索 , 查找與該問題相似的過去問題的求解事例。 若存在相似問題的求解事例 , 則以此作為啟發(fā)信息 , 指導(dǎo)該問題的求解。 具體地說 , 就是在新問題的求解過程中 , 對過去問題的求解事例中記錄的成功搜索路徑上每個操作的依據(jù)條件重新測試 . 如果依據(jù)條件仍滿足 , 則算法根隨成功的求解路徑。 否則 , 對原求解過程進行改寫 , 形成的新問題求解過程作為一個新事例存儲在事例庫中 , 以便指導(dǎo)將來相似問題的求解。 過去問題與新問題的相似性越高 , 求解過程需要的搜索就越少。 在最理想的情況下 , 甚至不需要搜索。 當(dāng)沒有檢索到一個與新問題相似的過去問題的求解事例時 , 則使用 A*或 AO*等算法進行 , 并在獲得解時將求解過程作為一個求 解事例存儲在事例庫中。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類比搜索方法探討 方法探討 系統(tǒng)最初使用時 , 由于事例庫中缺少求解事例 , 只有使用 A*或 AO*等算法。 隨著求解次數(shù)的增加 , 求解事例將不斷積累 , 類比的資料增多 (啟發(fā)信息增多 ), 從而使求解問題 的效率不斷提高。 由此可知 , 類比搜索方法的特點是 : 類比啟發(fā)信息不僅包含了局部信息 , 而且提供了指導(dǎo)求解的搜索方向 , 這樣就可以將一個龐大空間的搜索壓縮為對一個或數(shù)個很小空間的搜索 , 極大地提高了求解效率。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 用 AND/OR圖算法求解問題時 , 求解過程就是對一個隱含的 AND/OR圖進行搜索。 初始數(shù)據(jù)庫對應(yīng)于AND/OR圖的根節(jié)點 , 規(guī)則對應(yīng)于 k連接符 , 結(jié)束條件的數(shù)據(jù)庫對應(yīng)于一組 終節(jié)點集合 ,搜索算法的任務(wù)就是找到從初始節(jié)點到一組終節(jié)點集的一個解圖。 AND/OR圖的啟發(fā)式搜索算法 AO*是通過評價函數(shù) f(n)=h(n)來引導(dǎo)搜索過程 , 適用于分解得到的子問題不存在相互作用的情況。若 S→N集存在解圖 , 當(dāng)h(n)≤h*(n)且 h(n) 滿足單調(diào)限制條件時 , AO*算法一定能找到最佳解圖 , 在這種情況下 , AO*具有可采納性。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 類比搜索方法實施的關(guān)鍵技術(shù)在于生成求解事例、相似性度量和檢索、 以及指導(dǎo)求 解。 生成求解事例就是積累問題的求解經(jīng)驗 , 其生成過程主要解決的問題是對于一個 求解事例需要記錄和保存問題求解過程中的那些特征信息 , 以及如何進行表示、 抽取和存儲 這些信息。 求解一個復(fù)雜問題時 , 經(jīng)常面臨龐大的搜索。 大量被搜索的節(jié)點中 , 有成功的、也有失敗的。 為了給相似問題的求解提供有用信息 , 就要確定保存搜索過程中的哪些有用特征信息。顯然 , 走兩個極端最簡單 : 第 一是記下整個搜索過程 。 第二是只記問題的最終解。 這兩個極端都不圓滿 , 具體地作法除了保留問題的最終解外 , 還應(yīng)該記錄有關(guān)選擇這 些操作的情境和依據(jù)條件。 這是一個很有意義的研究課題。 相似性的度量也是類比搜 索方法的一個關(guān)鍵問題。 相似程度越高 , 度量方法恰當(dāng) , 相似問題的檢索俞易獲得。 關(guān)于這方面 , 目前還是主要根據(jù)新、老問題的特征和關(guān)系來確定它們之間的相似性。 此外 , 還可設(shè)置相似度閥值， 檢索采用直接映射式方法。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 指導(dǎo)求解是類比搜索方法的控制程序 , 主要考慮靈活的處理策略。 一般要考慮以下 幾點 : (1) 當(dāng)檢索沒有類比啟發(fā)信息時 , 程序能轉(zhuǎn)向常規(guī)搜索方法。 (2) 當(dāng)檢索到一個與新問題完全相似的過去問題的求解事例時 , 程序能直接轉(zhuǎn)換解。 (3) 當(dāng)檢索到一個與新問題部分相似的過去問題的求解事例時 , 程序能提取相似部 分解過程 , 還能組織部分搜索、銜接新的解過程。 此外 , 應(yīng)有裁剪過去問題多余解過程 的功能。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 1 規(guī)則不一致原因及解決方法 規(guī)則集中存在的不一致是影響系統(tǒng)性能的重要因素之一。系統(tǒng)建立初期 , 由于規(guī)則集較小 , 內(nèi)容也比較簡單 , 設(shè)計人員能對每一條規(guī)則的條件和結(jié)論部分反復(fù)推敲和精心 構(gòu)造 , 這類問題容易防止。但隨著時間的推移 , 新的規(guī)則不斷加入 , 規(guī)則集合越來越大 , 內(nèi)容也越來越豐富 , 這時規(guī)則間的相互影響和相互聯(lián)系就隨之變得復(fù)雜。在此情況下 , 規(guī)則的不一致就將自然產(chǎn)生 , 當(dāng)然 , 對它的認識和解決也就顯得很重要。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 1 規(guī)則不一致原因及解決方法 主要的不一致規(guī)則種類 (1) 循環(huán)規(guī)則 : 由數(shù)個規(guī)則的前提和結(jié)論形成一個循環(huán)鏈 , 最終由末尾規(guī)則的結(jié)果 子句推出起始規(guī)則的前提部分 。 (2) 沖突規(guī)則 : 兩個規(guī)則的前提條件等價 , 但一個或多個結(jié)果子句有矛盾或者前提 子句有矛盾而結(jié)論部分完全等價 。 也有可能由多條規(guī)則鏈形成沖突規(guī)則集 。 (3) 冗余規(guī)則 : 兩個規(guī)則的前提條件等價 , 一個或多個子結(jié)果子句也等價 。 (4) 從屬規(guī)則 : 兩個規(guī)則有相同的結(jié)果 , 但其中一個包含有多余的約束條件。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 1 規(guī)則不一致原因及解決方法 不一致規(guī)則的檢查解決方法 (1) 對于循環(huán)規(guī)則 , 可構(gòu)造規(guī)則集的 IFTHEN圖 , 從起始規(guī)則的條件部分開始搜索 , 如果搜索過程中遇到的 THEN部分已在前面出現(xiàn) , 就可以 中斷搜索 , 規(guī)則集中包含的循環(huán)規(guī)則子集合需設(shè)計人員檢查 , 解決 。 (2) 對于沖突規(guī)則 , 構(gòu)造 IFIF表 , 對規(guī)則集內(nèi)有相同的 IF 規(guī)則子句構(gòu)造規(guī)則樹 , 形成推理圖。同時建立 THENTHEN表用以判斷是否有沖突規(guī)則出現(xiàn)。 對相同 IF部分的規(guī)則繼續(xù)用它的各自 THEN部分作為其它可以匹配的 IF前提條件 , 遞歸地構(gòu)造 , 如發(fā)現(xiàn)兩個推理圖上分別有節(jié)點在 THENTHEN表上是矛盾的 , 則檢測出沖突規(guī)則 , 人工予以解決。 (3) 對冗余規(guī)則和從屬規(guī)則的檢查類似于沖突規(guī)則鏈的方法 . 不同之處是前者在推理圖中的遍歷是試圖發(fā)現(xiàn)有 THEN部分等價的兩條規(guī)則。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法原則 依賴規(guī)則：如果 Ri的結(jié)論部份包含有 Rj的條件部份，則Rj是一個依賴規(guī)則，即 Rj 依 賴規(guī)則 Ri，或稱 Ri是一個被依賴規(guī)則。 優(yōu)先規(guī)則 : 如果 Ri被 Pi個其它規(guī)則所依賴次數(shù) pi越大 , Ri被援引的可能性越大。 靜態(tài)規(guī)則排列：亦是在原文分析、原文譯文轉(zhuǎn)換、譯文生成之前， 對規(guī)則集中已有 的規(guī)則按優(yōu)先次序排列。 動態(tài)規(guī)則排列：這相當(dāng)于自學(xué)習(xí)能力，即某些句子分析、轉(zhuǎn)換、生成時， 會增加一 條或幾條規(guī)則。這些規(guī)則有可能還與未完成的其它語句有關(guān)。因此， 在對其它語句和完成速度影晌不大的情況下，同時再排列規(guī)則稱之為動態(tài)規(guī)則排列。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法原則 映射排列：是一個基于地址計算的排序。例如，求出上述 Pi(i=1， 2, ...， N）的最大值后，若開辟一個數(shù)組 D（ Pmax） ,就可把數(shù)據(jù)送入數(shù)據(jù)值下標(biāo)相等的對應(yīng)元素中。 顯然 Pi=50，對應(yīng) D(50)。 Pj=500, 對應(yīng) D(500)。相同數(shù)據(jù)落在同一數(shù)組元素中， 用計數(shù)方式可知有幾個。由于數(shù)組元素是有序的， 50050， 數(shù)組元素的下標(biāo)自然把數(shù)據(jù)一次定好位置，最后只要按規(guī)定的方式調(diào)非零元秦，相同元素按計數(shù)值次數(shù)調(diào)動，排序即完成。 枚舉計數(shù)：如果規(guī)則 Ri被規(guī)則 Rj依賴 (j=1， 2, ..., N)，則Pi=pi+1（ Pi初值賦 1) 。 顯然，對于 N條規(guī)則，每一條都將確定與其它規(guī)則的依賴關(guān)系并計算，這一過程稱之為枚舉計數(shù)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） B1: [初始化 ]，有 N條規(guī)則，置 P1至 PN皆為 1。 B2:〔對 i循環(huán)〕對 i=N， N— 1， N2， … ， 2執(zhí)行 B3。 然后轉(zhuǎn) B5。 B3:〔對 j循環(huán)〕對 j=i1， i2， … ， 1執(zhí)行 B4。 然后轉(zhuǎn)B2。 B4:〔尋求 Ri被 Rj依賴次數(shù)〕若 Ri被 Rj依賴，Pi←Pi＋ 1；否則轉(zhuǎn) B3。 B5: 一遍掃描 Pi（ i=1， 2, ...， N)，求 Pmax。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） 靜態(tài)算法進行到這里，求出了任一規(guī)則 Ri被依賴次數(shù) Pi。 Pi對應(yīng)于 Ri，相當(dāng)于 Ri 被 依賴次數(shù) Pi。 Pi對應(yīng) Ri，相當(dāng)于 Ri的關(guān)鍵字。其中，很可能出現(xiàn) Pi=Pj (i≠j), 這說明 Ri和 Rj被其它規(guī)則依賴的條數(shù)相同。怎樣快速地按關(guān)鍵字 Pi(i=1， 2， ..., N) 大小把規(guī) 則快速地排列起來，并滿足動態(tài)需要，我們采用高效算法 —— 映射排序 算法初始按關(guān)鍵字值以映射關(guān)系作一次掃描，基本排定規(guī)則位置， Ri→Pi→D（ Pi）。 對相同關(guān)鍵字的處理，算法附加了三個數(shù)組空間：每一記錄的鏈指針空間L（ i）， 鏈?zhǔn)字羔樋臻g Q，鏈當(dāng)前指針空間 W。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） 關(guān)鍵字值 Pi與 D數(shù)組元素下標(biāo)映射關(guān)系有一次時 ,D(Pi)=1；這時 Q(Pi)←1，記錄了具 有這唯一對應(yīng)關(guān)系 Pi所在規(guī)則的地址 i，并作為最后排序調(diào)整位置的首地址。 W（ Pi） ←i 為出現(xiàn)相同關(guān)鍵字