【正文】 殊選擇規(guī)則的機(jī)理 。 一般來(lái)說(shuō) , 當(dāng)一個(gè)產(chǎn)生式系統(tǒng)對(duì)任何一個(gè)數(shù)據(jù)庫(kù) D都具有如下性質(zhì)時(shí) , 這樣一個(gè)產(chǎn)生式系 統(tǒng)是可交換的。一種較好的表示法會(huì)簡(jiǎn)化狀態(tài)空間和規(guī)則集表示 , 此外 , 高 效率的問(wèn)題求解過(guò)程與控制策略有關(guān) , 合適的控制策略可縮小狀態(tài)空間的搜索范圍 , 提高求解的效率。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 1 產(chǎn)生式系統(tǒng) 3 . 1 . 1 產(chǎn)生式系統(tǒng)的組成部分 在一般情況下 , 問(wèn)題可能有多個(gè)解的序列 , 但有時(shí)會(huì)要求得到有某些附加約束條件的解 , 例如要求步數(shù)最少、距離最短等。作為智能中的一種形式體系 , 它還具有以下優(yōu)點(diǎn) : (1) 適合于模擬強(qiáng)數(shù)據(jù)驅(qū)動(dòng)特點(diǎn)的智能行為。 還要使系統(tǒng)在求解過(guò)程中記住應(yīng)用過(guò)的規(guī)則序列 , 以便最終能給出解的路徑。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 1 產(chǎn)生式系統(tǒng) 3 . 1 . 1 產(chǎn)生式系統(tǒng)的組成部分 產(chǎn)生式規(guī)則的一般形式為 : 條件 ─→行動(dòng) 或 前提 ─→結(jié)論 即表示成為 : if┄┄ then┄┄ 的形式。為什么要采用產(chǎn)生式系統(tǒng)作為智能軟件的主要結(jié)構(gòu)呢 ? 這可以有 兩點(diǎn)理由 : (1) 用產(chǎn)生式系統(tǒng)結(jié)構(gòu)求解問(wèn)題的過(guò)程和人類求解問(wèn)題時(shí)的思維過(guò)程很相象 , 因而可以用它來(lái)模擬人類求解問(wèn)題時(shí)的思維過(guò)程 。 一組產(chǎn)生式規(guī)則 。一條產(chǎn)生式規(guī)則滿足了應(yīng)用的先決條件之后 , 就可對(duì)綜合數(shù)據(jù)庫(kù)進(jìn)行操作 , 使其發(fā)生變化。在建立產(chǎn)生式系統(tǒng)描述時(shí) , 還要給出初始狀態(tài)和目標(biāo)條件 , 具體說(shuō)明所求解的問(wèn)題。 這是由于產(chǎn)生式系統(tǒng)的各組成部分具有相對(duì)的獨(dú)立性 , 因而便于擴(kuò)展和修改。狀態(tài)空間圖是一個(gè)有向圖 , 其節(jié)點(diǎn)可表示問(wèn)題的各種狀態(tài) (綜合數(shù)據(jù)庫(kù) ), 節(jié)點(diǎn)之間的弧線代表一些操作 (產(chǎn)生式規(guī)則 ), 它們可把一種狀態(tài)導(dǎo)向另一種狀態(tài)。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 1 產(chǎn)生式系統(tǒng) 3 . 1 . 2 產(chǎn)生式系統(tǒng)的基本算法 ? E1: DATA←初始事實(shí)庫(kù) ? E2: until DATA 滿足結(jié)束條件以前 , do ? E3: begin ? E4: 在規(guī)則集中 ,選某一條可用于 DATA的規(guī)則 ? E5: DATA←規(guī)則應(yīng)用到 DATA得到的結(jié)果 ? E6: 結(jié)束 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 1 產(chǎn)生式系統(tǒng) 3 . 1 . 3 產(chǎn)生式系統(tǒng)的類型 正向、逆向、雙向產(chǎn)生式系統(tǒng) 用產(chǎn)生式系統(tǒng)求解某一問(wèn)題時(shí) , 如果按照規(guī)則使用的方式或者說(shuō)按推理方向來(lái)劃分的話 , 有正向、逆向和雙向產(chǎn)生式系統(tǒng)。 (3) 若對(duì) D應(yīng)用某一規(guī)則序列后得到的一個(gè)數(shù)據(jù)庫(kù) D39。 圖中只給出兩條達(dá)到目標(biāo)的路徑和一條失敗的路徑。對(duì)大多數(shù)的智能應(yīng)用問(wèn)題 , 所擁有的控制策略知識(shí)或信息并不足以使每次通過(guò)算法 E4時(shí) , 一下子就能選出最合適的 一條規(guī)則來(lái) , 因而產(chǎn)生式系統(tǒng)還必須把 E4擴(kuò)大成搜索 (推理 )算法 , 以至于基本算法的每 一循環(huán)中選一條規(guī)則試用 , 最終找出某一序列能產(chǎn)生一個(gè)滿足結(jié)束條件的數(shù)據(jù)庫(kù)為止。 接著再根據(jù)新?tīng)顟B(tài)繼續(xù)選取規(guī)則 , 搜索過(guò)程一直進(jìn)行 , 不必考慮撤回用過(guò)的規(guī)則。在這種情況下 , 需要有這樣的控制策略 : 先試一試某一條規(guī)則 , 如果以后發(fā)現(xiàn)這條規(guī)則不合適 , 則允許退回去 , 另選一條規(guī)則來(lái)試。 設(shè)置太深 , 有可能導(dǎo)致回溯次數(shù)巨增。否則搜索繼續(xù) 。 若生成的 新?tīng)顟B(tài) 已出現(xiàn)過(guò) , 回溯到Y(jié)X0。 步驟 3 LOOP: if OPEN=( ) then return FAIL。 所以 , 廣度優(yōu)先搜索法是完備的 , 是一種推理算法。 如果回溯 , 不難證明其平 均效率與廣度優(yōu)先搜索法相同。 dj=500, 對(duì)應(yīng) P(500)。到節(jié)點(diǎn) x已經(jīng)付出的代價(jià) 。 或者 OPEN表中的節(jié)點(diǎn)被取完在步驟 3結(jié)束。是其中最前面的一個(gè) , 則它必然滿足 f(x39。但是由性質(zhì) 2證明可知 , 在 A*算法結(jié)束之前 , OPEN表中存在著節(jié)點(diǎn) x‘ , 它應(yīng)該在最優(yōu)路徑上 , 且滿足 f(x39。 現(xiàn)僅證明 A*2擴(kuò)展的第 K代的任一節(jié)點(diǎn) xk也被 A*1擴(kuò)展 : 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法幾個(gè)重要性質(zhì) : 性質(zhì) 4 A*算法是最優(yōu)的 證明（接前頁(yè) ): 由假設(shè)可知 , A*2擴(kuò)展的前 K1代節(jié)點(diǎn) A*1也都擴(kuò)展了 , 因此 A1* 搜索樹(shù)中有一條從初始節(jié)點(diǎn) S。 c(xi,xj)是節(jié)點(diǎn) xi到其子節(jié)點(diǎn) xj的邊代價(jià)。 選擇 節(jié)點(diǎn)擴(kuò)展時(shí) , 首先擴(kuò)展OPEN2中的節(jié)點(diǎn) , 因?yàn)?OPEN2中含有感興趣集中的節(jié)點(diǎn) , 可能比 OPEN1中的節(jié)點(diǎn)更有希望在最佳路徑上 , 而且所擴(kuò)展的節(jié)點(diǎn)數(shù)目總不會(huì)多于原算法。 A=A1∩A2∩…∩An 根據(jù)啟發(fā)信息 , 可將原始的問(wèn)題進(jìn)行同構(gòu)或同態(tài)的等價(jià)變換 , 轉(zhuǎn)換為若干等價(jià)問(wèn)題。 這個(gè)變換圖是 OR圖 , 根據(jù)這個(gè)圖對(duì)新問(wèn)題求解 , 當(dāng)且僅當(dāng)新問(wèn) 題有一個(gè)可解 , 就得到原問(wèn)題的解的解過(guò)程是 AO圖算法。 下班可解或不可解的搜索過(guò)程都是至上而下的。 (3) 若節(jié)點(diǎn) n有一個(gè)指向節(jié)點(diǎn) {n1, n2, …, nk} 的 k連接符 , 使得從每個(gè)后繼節(jié)點(diǎn) ni到集合 N有一個(gè)解圖 (i=1, 2, …, k), 則 G39。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) AO*算法 A1: 建立一個(gè)搜索圖 G, G:=s,計(jì)算 q(s)=h(s), IF GOAL(s) THEN M(s,SOLVED)。 建立含 n的單一節(jié)點(diǎn)集合 S. A8: Until S 為空 , do 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) AO*算法 (接前頁(yè) ) A9: begin A10: REMOVE (m,S), mc∈ {S}。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) 分析與改進(jìn) (3) A5中怎樣選 G39。 每次求解問(wèn)題時(shí) , 面臨的都是全新的搜索圖 , 即使求解的是相同問(wèn)題 , 算法仍然從零開(kāi)始 , 這顯然與人類求解問(wèn)題的方式不符。值得注意的是 , 啟發(fā)信息是一種局部信息 , 只在搜索路徑的每個(gè)節(jié)點(diǎn)上為選擇操作提供參考。 若存在相似問(wèn)題的求解事例 , 則以此作為啟發(fā)信息 , 指導(dǎo)該問(wèn)題的求解。 由此可知 , 類比搜索方法的特點(diǎn)是 : 類比啟發(fā)信息不僅包含了局部信息 , 而且提供了指導(dǎo)求解的搜索方向 , 這樣就可以將一個(gè)龐大空間的搜索壓縮為對(duì)一個(gè)或數(shù)個(gè)很小空間的搜索 , 極大地提高了求解效率。 大量被搜索的節(jié)點(diǎn)中 , 有成功的、也有失敗的。 關(guān)于這方面 , 目前還是主要根據(jù)新、老問(wèn)題的特征和關(guān)系來(lái)確定它們之間的相似性。系統(tǒng)建立初期 , 由于規(guī)則集較小 , 內(nèi)容也比較簡(jiǎn)單 , 設(shè)計(jì)人員能對(duì)每一條規(guī)則的條件和結(jié)論部分反復(fù)推敲和精心 構(gòu)造 , 這類問(wèn)題容易防止。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 1 規(guī)則不一致原因及解決方法 不一致規(guī)則的檢查解決方法 (1) 對(duì)于循環(huán)規(guī)則 , 可構(gòu)造規(guī)則集的 IFTHEN圖 , 從起始規(guī)則的條件部分開(kāi)始搜索 , 如果搜索過(guò)程中遇到的 THEN部分已在前面出現(xiàn) , 就可以 中斷搜索 , 規(guī)則集中包含的循環(huán)規(guī)則子集合需設(shè)計(jì)人員檢查 , 解決 。 動(dòng)態(tài)規(guī)則排列：這相當(dāng)于自學(xué)習(xí)能力，即某些句子分析、轉(zhuǎn)換、生成時(shí)， 會(huì)增加一 條或幾條規(guī)則。由于數(shù)組元素是有序的， 50050， 數(shù)組元素的下標(biāo)自然把數(shù)據(jù)一次定好位置，最后只要按規(guī)定的方式調(diào)非零元秦，相同元素按計(jì)數(shù)值次數(shù)調(diào)動(dòng)，排序即完成。 B4:〔尋求 Ri被 Rj依賴次數(shù)〕若 Ri被 Rj依賴，Pi←Pi＋ 1；否則轉(zhuǎn) B3。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 4 產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） 關(guān)鍵字值 Pi與 D數(shù)組元素下標(biāo)映射關(guān)系有一次時(shí) ,D(Pi)=1；這時(shí) Q(Pi)←1，記錄了具 有這唯一對(duì)應(yīng)關(guān)系 Pi所在規(guī)則的地址 i，并作為最后排序調(diào)整位置的首地址。 Pi對(duì)應(yīng) Ri，相當(dāng)于 Ri的關(guān)鍵字。 B2:〔對(duì) i循環(huán)〕對(duì) i=N， N— 1， N2， … ， 2執(zhí)行 B3。例如，求出上述 Pi(i=1， 2, ...， N）的最大值后，若開(kāi)辟一個(gè)數(shù)組 D（ Pmax） ,就可把數(shù)據(jù)送入數(shù)據(jù)值下標(biāo)相等的對(duì)應(yīng)元素中。 (3) 對(duì)冗余規(guī)則和從屬規(guī)則的檢查類似于沖突規(guī)則鏈的方法 . 不同之處是前者在推理圖中的遍歷是試圖發(fā)現(xiàn)有 THEN部分等價(jià)的兩條規(guī)則。 (2) 沖突規(guī)則 : 兩個(gè)規(guī)則的前提條件等價(jià) , 但一個(gè)或多個(gè)結(jié)果子句有矛盾或者前提 子句有矛盾而結(jié)論部分完全等價(jià) 。 (2) 當(dāng)檢索到一個(gè)與新問(wèn)題完全相似的過(guò)去問(wèn)題的求解事例時(shí) , 程序能直接轉(zhuǎn)換解。 這兩個(gè)極端都不圓滿 , 具體地作法除了保留問(wèn)題的最終解外 , 還應(yīng)該記錄有關(guān)選擇這 些操作的情境和依據(jù)條件。若 S→N集存在解圖 , 當(dāng)h(n)≤h*(n)且 h(n) 滿足單調(diào)限制條件時(shí) , AO*算法一定能找到最佳解圖 , 在這種情況下 , AO*具有可采納性。 在最理想的情況下 , 甚至不需要搜索。 (3) 如何有效地使用類比結(jié)論 , 即相似的過(guò)去問(wèn)題的求解經(jīng)驗(yàn) , 作為特殊的啟發(fā)信息指導(dǎo)新問(wèn)題的求解。 也就是說(shuō) , 如果算法設(shè)計(jì)恰當(dāng) , 可以自動(dòng)獲得啟發(fā)信息。 (5) AO*中評(píng)價(jià)函數(shù)只考慮 h(n)分量 , 計(jì)算 g沒(méi)有必要也不可能。 m能解或修正的耗散值與原先估算 q0不同 , 則把 m的所有先輩節(jié)點(diǎn) ma添加到 S中 . A13: end A14: end 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) 分析與改進(jìn) 算法 AO*可以理解為兩個(gè)主要運(yùn)算 : A1～ A6, 完成自上而下的圖生成 , 通過(guò)有標(biāo)記的 連接符 , 尋找最好的局部解圖 , 然后對(duì)其中一個(gè)非終節(jié)點(diǎn)進(jìn)行擴(kuò)展 , 并對(duì)其后繼節(jié)點(diǎn)賦 給耗散值 。. A5: n:=G39。 (2) 否則 , 節(jié)點(diǎn) n 有一 個(gè)通到解圖中后繼節(jié)點(diǎn)集合 {n1,n2,…,ni} 的連接符 . 令該連接符的耗散值為Cn, 則 k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N) 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進(jìn) 定義 定義 7 AND/OR圖求解中 , 從起始節(jié)點(diǎn)到一可解葉節(jié)點(diǎn)集合具有最小耗散值的一個(gè)解 圖稱為最佳解圖。定義為 : (1) G39。 探討類比搜索方法 .為此 , 我們首先給出 AND/OR圖的一般搜索過(guò)程 : (1) 把原始問(wèn)題作為初始節(jié)點(diǎn) , 并作為當(dāng)前節(jié)點(diǎn)。 AND/OR 圖算法是用于表示問(wèn)題及其求解過(guò)程的又一 種形式化方法。h(x) 其中 , v、 w為權(quán)系數(shù)且 ≥0. 當(dāng) w↑, 強(qiáng)調(diào)啟發(fā)信息 , 搜索過(guò)程沿最有希望的方向進(jìn)行 , 效率肯定高 , 但降低了完備性 。 例如 , 在求城市 A到城市 B的最佳路徑時(shí) , 人們往往憑自己的經(jīng)驗(yàn)斷定所要求的最佳路徑必經(jīng)城市 C和城市 H, 這里我們稱 {C, H} 是感興 趣集合。 第 3 章 產(chǎn)生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進(jìn) A*算法的改進(jìn) 改進(jìn) 1 OPEN表中自始至終的排序 , 采用 節(jié)中介紹的映射方法。 h(x)值越大 , 表明它攜帶的啟發(fā)信息越多 , 搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少 , 搜索的效率越高。到節(jié)點(diǎn) xn的最短路徑長(zhǎng)度 , 則顯然有 g*(xn)≥d*(xn) e