【正文】 又因為 g(xn)≥g*(xn) 所以有 g(xn)≥d*(xn) e 再因 h(xn)≥0, f(xn)≥g(xn) 故得到 f(xn)≥d*(xn) e 由于 A*算法不終止 , 隨著搜索的進行 , d*(xn)會無限增大 , 從而使f(xn)也無限增大。)≤f*(s).。到 x 最小耗散值路徑的耗散值g*(x)的估計值 , g(x)0。 3) 搜索過程中 , 如果同時出現(xiàn)了兩條到達某一節(jié)點的路徑 ,代價大的那條路徑即時刪去。 把它們放進 OPEN表中 , 依據(jù)初始節(jié)點到它們各自所付出的代價 大小進行排序 , 代價小的節(jié)點放在前面擴展 , 周而復始重復上述操作 , 直至找到目標節(jié)點為止。 這種方法搜索一旦進入某個分支 , 就將沿著該分支一直向下搜索。 從 OPEN表中取出一個節(jié)點 n, 將其 放入 CLOSED表中。 3 . 3 圖搜索算法 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3. 3 . 1 一般性圖搜索算法 步驟 1 G←S,OPEN←(S)。 YX5: 取頭條可用規(guī)則 Ri。 如果有好的選擇規(guī)則的知識可用 , 那么用這種知識來引導規(guī)則選取 , 就會減少盲目性 , 降低回溯次數(shù) , 甚至不回溯就能找到解 , 總之一般來說有利于提高效率。 回溯應發(fā)生在以下三種情況 : (1) 新生成的狀態(tài)在通向初始狀態(tài)的路徑上已出現(xiàn)過 。 第 3 章 產生式系統(tǒng)及其搜索方法 產生式系統(tǒng)的搜索 (控制 )策略 3 . 2 . 2 不可撤回方法 爬山法不僅適用于爬山問題 , 那些目標為極大值 , 搜索過程是不斷接近目標的單值問題都可應用這一方法。 非啟發(fā)式算法是按預定的控制策略進行搜索 , 在其過程中獲得的中間信息不用來改進控制策略。 要注意一般結 束條件應是所有分量數(shù)據(jù)庫都已滿足結束條件?？蓱玫囊?guī)則集合為 R1: if {a, b, c} then {a, b, c, ab} R2: if {a, b, c} then {a, b, c, bc} R3: if {a, b, c} then {a, b, c, ca} 顯然 , 這個產生式實例具有可交換性。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 1 產生式系統(tǒng) 3 . 1 . 3 產生式系統(tǒng)的類型 可交換的產生式系統(tǒng) 可交換式產生式系統(tǒng)的可交換性指幾條規(guī)則的應用可以任意交換次序而不影響求解。對問題表示的好壞 , 往往對求 解過程的效率有很大的影響。 建立了產生式系統(tǒng)描述之后 , 通過控制策略 , 可求得實現(xiàn)目標的一個規(guī)則序列 , 這就是所謂問題的解 , 這個解序列是根據(jù)控制系統(tǒng)記住搜索目標過程中用過的所有規(guī)則而構造出來的。 在研究人類進行問題求解過程時 , 完全可用一個產生式系統(tǒng)來模擬求解過程 , 及可作為描述搜索的一種有效方法。 當數(shù)據(jù)庫滿足結束條件時 , 系統(tǒng)就應停止運行 。人們可以根據(jù)問題的性質 , 用適當?shù)姆椒▉順嬙炀C合數(shù)據(jù)庫的信息。 它是智能軟件中使用最普遍、最典型的一種結構。 一個控制系統(tǒng)。如綜合數(shù)據(jù)庫代表當前狀態(tài) , 則應用規(guī)則后就使狀態(tài)發(fā)生轉換 , 生成新狀態(tài)。 產生式系統(tǒng)中控制策略的作用就是從初始狀態(tài)出發(fā) , 尋求一個滿足一定條件的問題狀態(tài)。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 1 產生式系統(tǒng) 3 . 1 . 1 產生式系統(tǒng)的組成部分 用產生式系統(tǒng)來求解問題 , 首先必須建立起問題的產生式系統(tǒng)描述 , 即規(guī)定出數(shù)據(jù)庫、規(guī)則集合及其控制策略。這樣建立起來的狀態(tài)空間圖 , 描述了問題所有可能出現(xiàn)的狀態(tài)及狀態(tài)和操作之間的關系 , 因而可以較直觀地看出問題的解路徑及其性質。 正向產生式系統(tǒng)是從初始狀態(tài)出發(fā)朝著目標狀態(tài)這個方向使用規(guī)則 , 即正推的方式工作 , 稱這些規(guī)則為 F規(guī)則 。(并能達到解 ), 當改變這些規(guī)則次序后 , 任然可求得解 , 即求得 D39。實際搜索時有可能去探索更多的路徑 , 往往導致效率降低。由此可見 , 高效率的控制策略需要有關被求解問題的足夠知識 , 這樣才能在搜索過程 減少盲目性 , 比較快的找到解路徑。 這是由于在搜索過程中如能有效利用局部知識 , 即使使用了一條不理想的規(guī)則 , 也不妨礙下一步選得另一條更合適的規(guī)則?；厮莘椒ú槐Ａ敉暾乃阉鳂浣Y構 , 只記住當前工作的一條路徑 , 回溯就是對這條路徑進行修正。因而應根據(jù)實際情況來規(guī)定搜索范圍 , 先設置適中的深度搜索 , 失敗時再逐步加深。 YX2: 搜索的狀態(tài)找不到可用規(guī)則 , 回溯到 YX0。 YX9: 記錄新狀態(tài) , 對新狀態(tài)遞規(guī)調用 YX1～ YX7。 進入循環(huán)。 但是 , 在問題大節(jié)點多 , 且目標節(jié)點距離初始節(jié)點較遠時將會產生許多無用節(jié)點 , 搜索效率低 , 還可能產生組合爆炸。 因此 , 深度優(yōu)先搜索法如果沒有啟發(fā)信息 , 很難有實用價值。 相同代價值的節(jié)點落在同一數(shù)組元素中 , 用計數(shù)方式 可知有幾個。 h(x)是從節(jié)點 x到目標節(jié)點 Sg的最優(yōu) 路徑的估計代價 , 它體現(xiàn)了問題的啟發(fā)性信息 , 其形式根據(jù)問題的特性確定。 不 管那種情況 , A*算法都在有限步內終止。)≤f*(S0) 至此 , 第一步證明結束 。)≤f*(s0) 此時 , A *算法一定會選擇 x39。到 xk的路徑 , 其費用不會比 A*2搜索樹從 S。 若把上式改寫 h(xi)≤h(xj)+c(xi,xj), 可看出節(jié)點xi到目標節(jié)點的估價不會超過 x i 到其子節(jié)點 xj邊代價加從 xj到目標節(jié)點的估價。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 3 典型的啟發(fā)式搜索算法分析與改進 討論 (1) 啟發(fā)式搜索算法在大問題中一般優(yōu)于非啟發(fā)式搜索算法 , 因此 ,有效地分析利用啟發(fā)信息尤為重要。 那么等價問題的搜索過程A1,A2,…,An 是完備的 ,則搜索過程 A也是完備的。 定義 3 可解節(jié)點 在 AND/OR圖中 , 滿足下列條件之一者為可解節(jié)點 : (1) 它是一個終止節(jié)點 . (2) 它是一個 OR節(jié)點 , 且子節(jié)點中至少有一個是可解節(jié)點 . (3) 它是一個 AND節(jié)點 , 且其子節(jié)點全部是可解節(jié)點。 如果確定某個節(jié)點是可解節(jié)點 , 則不可 解的后裔節(jié)點不再有用 , 可從搜索圖中刪去 。由節(jié)點 n、 k連接符、節(jié)點 {n1,n2, …, nk } 以及從{n1, n2, …, nk} 中的每個節(jié)點到集合 N的解圖組成。開始時圖 G只包含 s, 耗散值估計為 h(s), 若 s是終節(jié)點 , 則標記能解 . A2: Until s已標記上 SOLVED, do: A3: begin A4: G39。 這個 m的子節(jié)點 mc應不在 S中 . A11: (1) 修改 m的耗散值 q(m): 對 m指向節(jié)點集 {n1i, n2i, …, nki} 的每一個連接符 i分別計算 qi, qi(m)=Ci+q(n1i)+…+q(nki), q(m):=min qi(m)。中的一個非終節(jié)點擴展值得研究 : 一般可以選一個最可能導致該局部解圖耗散值發(fā)生較大變化的那個節(jié)點先擴展 , 因為選這個節(jié)點先擴展 , 會促使及時修改局部解圖的標記。 人類求解問題的一個重要特點 , 就是常常利用以前求解相同 或相似問題的經驗來指導新問題的求解。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 6 類比搜索方法探討 方法探討 類比搜索方法把類比推理技術與狀態(tài)空間的啟發(fā)式搜索相結合 , 實際上是對人類求 解問題、積累經驗和增加求解問題能力的一種模擬。 具體地說 , 就是在新問題的求解過程中 , 對過去問題的求解事例中記錄的成功搜索路徑上每個操作的依據(jù)條件重新測試 . 如果依據(jù)條件仍滿足 , 則算法根隨成功的求解路徑。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 7 討論 用 AND/OR圖算法求解問題時 , 求解過程就是對一個隱含的 AND/OR圖進行搜索。 為了給相似問題的求解提供有用信息 , 就要確定保存搜索過程中的哪些有用特征信息。 此外 , 還可設置相似度閥值， 檢索采用直接映射式方法。但隨著時間的推移 , 新的規(guī)則不斷加入 , 規(guī)則集合越來越大 , 內容也越來越豐富 , 這時規(guī)則間的相互影響和相互聯(lián)系就隨之變得復雜。 (2) 對于沖突規(guī)則 , 構造 IFIF表 , 對規(guī)則集內有相同的 IF 規(guī)則子句構造規(guī)則樹 , 形成推理圖。這些規(guī)則有可能還與未完成的其它語句有關。 枚舉計數(shù)：如果規(guī)則 Ri被規(guī)則 Rj依賴 (j=1， 2, ..., N)，則Pi=pi+1（ Pi初值賦 1) 。 B5: 一遍掃描 Pi（ i=1， 2, ...， N)，求 Pmax。 W（ Pi） ←i 為出現(xiàn)相同關鍵字提。 Pi對應于 Ri，相當于 Ri 被 依賴次數(shù) Pi。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 4 產生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法描述與分析 靜態(tài)算法（上） B1: [初始化 ]，有 N條規(guī)則，置 P1至 PN皆為 1。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 4 產生式系統(tǒng)的規(guī)則問題 3 . 4 . 2 規(guī)則排序算法 排序算法原則 映射排列：是一個基于地址計算的排序。 對相同 IF部分的規(guī)則繼續(xù)用它的各自 THEN部分作為其它可以匹配的 IF前提條件 , 遞歸地構造 , 如發(fā)現(xiàn)兩個推理圖上分別有節(jié)點在 THENTHEN表上是矛盾的 , 則檢測出沖突規(guī)則 , 人工予以解決。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 4 產生式系統(tǒng)的規(guī)則問題 3 . 4 . 1 規(guī)則不一致原因及解決方法 主要的不一致規(guī)則種類 (1) 循環(huán)規(guī)則 : 由數(shù)個規(guī)則的前提和結論形成一個循環(huán)鏈 , 最終由末尾規(guī)則的結果 子句推出起始規(guī)則的前提部分 。 一般要考慮以下 幾點 : (1) 當檢索沒有類比啟發(fā)信息時 , 程序能轉向常規(guī)搜索方法。 第二是只記問題的最終解。 AND/OR圖的啟發(fā)式搜索算法 AO*是通過評價函數(shù) f(n)=h(n)來引導搜索過程 , 適用于分解得到的子問題不存在相互作用的情況。 過去問題與新問題的相似性越高 , 求解過程需要的搜索就越少。 (2) 如何定義和判斷兩個問題的求解情況是相似的 , 如何高效的進行檢索。 即 , 利用類比獲得與新問題相似的過去問題的求解過程 , 作為啟發(fā)信息來指導新問題的求解 , 這樣可以縮小搜索范圍 , 降低問題求解的復雜性。 當 h(n)≡0時 , AO*成寬度優(yōu)先算法。 若該連接符的所有子節(jié)點都是能解的 , 則 m也標上能解 . A12: IF M(m, SOLVED)∨ (q(m)≠q0(m)) THEN ADD(ma, S)。 根據(jù)連接符標記 (指針 )找出一個待擴展的局部解圖 G39。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進 定義 定義 6 從 AND/OR圖任意節(jié)點 n到一立即可解的葉節(jié)點集合 N的解圖耗散值 k(n,N) 可遞歸地定義為： (1) 若節(jié)點 n是集合 N中的元素 , 則 k(n,N)=0。 第 3 章 產生式系統(tǒng)及其搜索方法 3 . 3 圖搜索算法 3 . 3 . 5 AO*搜索算法分析與改進 定義 定義 5 設 AND/OR圖 G, 則從節(jié)點 n到一立即可解的葉節(jié)點集合 N的一解圖 G39。 下面分析 AND/OR圖 AO*搜索算法 , 作一些改進探討 。 但對于復雜的問題 , 它們并不是唯一的途徑 , 若利用它們直接求解往往還比較困難。g(x)+w 這兩個結論都是在 h(x)滿足單調限制時才成立 . 對于第 2個結論 ,