【文章內(nèi)容簡介】 對于寬度優(yōu)先 ， 選擇節(jié)點 i 的深度 d(i) 作為估價函數(shù) f(i) ；對于深度優(yōu)先 ， 選擇 1/d(i) 作為估價函數(shù) f(i) ；對于等代價搜索 ， 從起始節(jié)點 S 至節(jié)點 i 這段路徑的 代價 g(i) 作估價函數(shù)為 f(i) 。 有序搜索的有效性直接取決于估價函數(shù) f 的選擇 ， 如果選擇的 f 不合適 ， 有序搜索就可能失去一個最好的解甚至全部的解 。如果沒有適用的準確的希望量度 ， 那么 f 的選擇將涉及兩個方面的內(nèi)容： 一方面是考慮效率 、 時間和開銷；另一方面是保證有一個最優(yōu)的解或任意解 。 下面讓我們再次用八數(shù)碼難題的例子來說明圖搜索過程是如何應用估價函數(shù)排列節(jié)點的 。 我們考慮采用了簡單的 估價函數(shù) ： f(n) = d(n) + W(n) 其中 d(n) 是搜索樹中節(jié)點 n 的深度； W(n) 用來計算節(jié)點 n 對應于目標棋局錯放的棋子個數(shù) 。 例子：八數(shù)碼難題（ 8puzzle problem） 1 2 3 8 4 5 6 7 （目標狀態(tài)） 1 2 3 8 4 5 6 7 （初始狀態(tài)） 八數(shù)碼難題的有序搜索樹見下圖： 例如，起始節(jié)點棋局 S0 ，其在搜索樹中位于 0層，所以 d(S0)=0 而它與 Sg中棋子位置不同的個數(shù)是 4，即 W(S0)=4 ，所以有 f(S0) = 0+4=4 5 7 1 4 5 3 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 4） （ 6） （ 6） 2 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 6） （ 5） （ 5） 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 5） （ 7） 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 （ 6） （ 7） 6 1 2 3 8 4 （ 5） 5 6 7 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 （ 5） （ 7） 八數(shù)碼難題的有序搜索樹 1 2 3 8 4 6 （ 4） 上圖表示出利用這個估價函數(shù) f 把 GRAPHSEARCH應用于八數(shù)碼難題的結(jié)果 。 圖中的數(shù)字表示該節(jié)點的 f 值 ， 由 f 值我們能很容易確定節(jié)點的擴展順序 。 從圖可見 ， 這里所求得的解答路徑和用其它搜索方法找到的解答路徑相同 。 不過 ， 由于估價函數(shù)的使用明顯地減少了被擴展的節(jié)點數(shù) （ 如果估價函數(shù)定義為 f(n)=d(n) ， 那么就得到了寬度優(yōu)先搜索過程 ） 。 正確地選擇估價函數(shù)對確定搜索結(jié)果具有決定性的作用 。使用不能識別某些節(jié)點 “ 真實希望 ” 的估價函數(shù)會形成非最小代價路徑；而使用一個過多地估計了全部節(jié)點希望的估價函數(shù)（ 就像寬度優(yōu)先搜索方法得到的估價函數(shù)一樣 ） 又會擴展過多的節(jié)點 ， 降低求解效率 。 作業(yè) : 試比較寬度優(yōu)先 、 深度優(yōu)先 、 等代價搜索和有序搜索的主要區(qū)別 。 A*算法 A*算法的估價函數(shù)： 下面描述一特別的估價函數(shù)，該 估價函數(shù) f使得任意節(jié)點上函數(shù)值 f(n)能估算出從初始節(jié)點 S到節(jié)點 n的最小代價路徑的代價和從節(jié)點 n到某一目標節(jié)點的最小代價路徑的代價之總和 ，即 f(n)是約束地通過節(jié)點 n的一條最小代價路徑的代價的一個估計值。因此， OPEN表上具有最小 f值的那個節(jié)點就是下一步要擴展的節(jié)點。正式討論 A*算法之前，先介紹幾個記號： 令 k(ni， nj)表示任意兩個節(jié)點 ni和 nj之間最小代價路徑的 實際代價 (對于兩節(jié)點間沒有通路，函數(shù) k沒有定義 )。從節(jié)點 n到某個目標節(jié)點 ti，某條最小代價路徑的實際代價由 k(n， ti)給出。令 h*(n)表示目標節(jié)點集合 {ti}上所有 k(n， ti)中最小的一個，因此， h*(n)就是從節(jié)點 n到目標節(jié)點最小代價路徑的代價 ，而且 從 n到目標節(jié)點能夠獲得 h*(n)值的任一路徑就是一條從 n到某個目標節(jié)點的最佳路徑 (對于不能到達目標的節(jié)點 n，函數(shù) h*(n)沒意義 )。 通常我們想知道 從已知起始節(jié)點 S到任意節(jié)點 n的一條最佳路徑的代價 k(S， n)。為此，引進一個 新函數(shù) g*，這將使我們的記號得到某些簡化。對所有從 S開始可達到 n的路徑來說，函數(shù)g*定義為： g*(n)=k(S， n) 其次，我們定義函數(shù) f*，使得在任一節(jié)點 n上其 函數(shù)值 f*(n)就是 從節(jié)點 S到節(jié)點 n的一條最佳路徑的實際代價加上從節(jié)點 n到某目標節(jié)點的一條最佳路徑的代價之和 ，即 f*(n)=g*(n)+ h*(n) 因而 f*(n)的 值就是從初始節(jié)點 S開始約束地通過節(jié)點 n的一條最佳路徑的代價 ，我們希望估價函數(shù) f是 f*的一個估計，此估計由下式給出： f(n)=g(n)+h(n) 其中： g是 g*的估計； h是 h*的估計。對于 g(n)，一個明顯的選擇就是搜索樹中從 S到 n這段路徑的代價，這一代價可以由從 n到 S尋找指針時，把所遇到的各段弧線的代價加起來給出 (這條路徑就是從 S到 n的最小代價路徑 )， 顯然有 g(n)≥g*(n)。對于 h*(n)的估計 h(n)，依賴于有關(guān)問題的啟發(fā)信息，這類信息與八數(shù)碼難題中的函數(shù) W(n)所用的信息相似，因此把 h叫做啟發(fā)函數(shù) 。 一般地，在 f(n)=g(n)+h(n)中， g(n)的比重越大，搜索方式就越傾向于寬度優(yōu)先搜索； h(n)的比重越大，搜索方式就越傾向于深度優(yōu)先搜索 。 g(n)的作用一般不可忽略，因為它代表從初始節(jié)點到達目標節(jié)點的 總代價估值中實際已付出的部分 ， 體現(xiàn)了搜索的寬度優(yōu)先趨勢 ，這有利于搜索算法的 完備性 ，但影響算法搜索效率。當g(n)遠遠小于 h(n)時， g(n)可以忽略，則 f(n)=h(n)，這體現(xiàn)了搜索的深度優(yōu)先趨勢 ，有利于搜索 效率的提高 ，但影響搜索算法的完備性，可能找不到問題的解。 A算法和 A*算法的定義 定義 在一般圖搜索過程中，如果第 8步的重排 OPEN表是依據(jù) f(x) = g(x)+h(x) 進行的，則稱該過程為 A算法。 定義 在 A算法中，如果對所有的 x， h(x)≤h*(x)成立 ,則稱h(x)為 h*(x)的下界，它表示某種偏于保守的估計。 定義 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。當 h=0時， A*算法就變?yōu)橛行蛩阉魉惴ā? A*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義。 每個節(jié)點 n的估價函數(shù)值包含兩個分量：從起始節(jié)點到節(jié)點n的代價以及從節(jié)點 n到達目標節(jié)點的代價 。 A*算法步驟 (1) 把 S放入 OPEN表，記 f=h，令 CLOSED為空表。 (2) 重復下列過程，直至找到目標節(jié)點止。若 OPEN為空表，則宣告失敗。 (3)取 OPEN表中未設置過的具有 最小 f值 的節(jié)點為最佳節(jié)點BESTNODE，并把它放入 CLOSED表。 (4) 若 BESTNODE為一目標節(jié)點，則成功求得一解。 (5) 若 BESTNODE不是目標節(jié)點，則擴展之，產(chǎn)生后繼節(jié)點 SUCCSSOR。 (6) 對每個 SUCCSSOR進行下列過程： (a) 建立從 SUCCSSOR返回 BESTNODE的指針。 (b) 計算 g(SUC)=g(BES)+g(BES,SUC)。 (c) 如果 SUCCSSOR∈ OPEN，則稱此節(jié)點為 OLD，并把它添至 BESTNODE的后繼節(jié)點表中。 (d) 比較新舊路徑代價。如果 g(SUC)＜ g(OLD),則重新確定 OLD的父輩節(jié)點為 BESTNODE，記下較小代價 g(OLD),并修正 f(OLD)值。 (e) 若至 OLD節(jié)點的代價較低或一樣，則停止擴展節(jié)點。 (f) 若 SUCCSSOR不在 OPEN表中，則看其是否在CLOSED表中。 (g) 若 SUCCSSOR在 CLOSE表中，則轉(zhuǎn)向 c。 (h) 若 SUCCSSOR既不在 OPEN表中，又不在 CLOSED表中，則把它放入 OPEN表中，并添入 BESTNODE后裔表，然后轉(zhuǎn)向 (7) (7) 計算 f值 。 (8) GO LOOP 根據(jù)所描述的算法可畫出如下的 A*算法框圖（書 75頁圖 ） ? 對于許多比較復雜的系統(tǒng)和問題，如果采用前面討論過的搜索方法，有時會很難甚至無法使問題獲得解決，就需要應用一些功能更強大的推理技術(shù)來求解這種比較復雜的問題。 ? 第二章中討論過謂詞公式，某些推理規(guī)則以及置換合一等概念。在這個基礎上，我們能夠進一步研究消解原理。 消解原理 回顧： 原子公式 一些新概念： 文字 — 一個原子公式及其否定。 子句 — 由文字的析取組成的合式公式。 消解 — 可用于一定的子句公式的推理規(guī)則 ,又叫 歸結(jié) 。 例如 ：如果存在某個公式 E1∨E2 和另一公式～ E2∨E3 ，那么E1∨E3 在邏輯上成立 ，這就是消解過程， E1∨E3 稱 消解式 。 在說明消解過程之前，首先說明任一謂詞演算公式可以化成一個子句集，其變換過程由下列九個步驟組成： 子句集的求取 ? (1) 消去蘊涵符號 只應用 ∨ 和～符號，以～ A∨B 替換 A→B ? (2) 減少否定符號的轄域 把～緊鄰一個謂詞符號，并反復應用狄 摩根定律，如： 以～ A∨ ～ B代替～ (A∧B) 以～ A∧ ～ B代替～ (A∨B) 以 (? x){～ A}代替～ (? x)A 以 (? x){～ A}代替～ (? x)A 以 A代替～ (～ A) ? (3) 對變量標準化 在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元 (虛擬變量 )，它可以在該量詞轄域內(nèi)處處統(tǒng)一地被另一個沒有出現(xiàn)過的任意變量所代替，而不改變謂詞公式的邏輯真值。例如： (? x){ P(x) ? (? x)Q(x) } 標準化得到 (? x){ P(x) ? (? y)Q(y) } ? (4) 消去存在量詞 Skolem函數(shù) ：在公式 (? y)[(? x)P(x, y)]中，存在量詞是在全稱量詞的轄域內(nèi)，則所存在的 x可能依賴于 y值。 令這種依賴關(guān)系由函數(shù) g(y)所確定 ，它把每個 y值映射到存在的那個 x，這種函數(shù)叫做 Skolem函數(shù) 。 如果用 Skolem函數(shù)代替存在的 x，我們就可以消去全部存在量詞，并寫成： (? y)[P(g(y), y)] ? 從一個公式消去一個存在量詞的一般規(guī)則是 以一個 Skolem函數(shù)代替每個出現(xiàn)的存在量詞的量化變量 ，而 這個 Skolem函數(shù)的自變量就是由那些全稱量詞所約束的變量 ，這些全稱量詞的轄域要包括被消去的存在量詞的轄域。 Skolem函數(shù)所使用的函數(shù)符號必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號。 ? 如果要消去的 存在量詞不在任何一個全稱量詞的轄域內(nèi)，就用不含變量的 Skolem函數(shù)即常量來消去存在量詞量化的變量 。例如， (? x)P(x)化為 P(A)，其中常量符號 A用來表示我們知道的存在實體。 A必須是個新的常量符號，未曾在公式中其它地方使用過。又例如： (? z)(? y)(? x)P(x, y, z) 被 (? y)P(g(y), y, A) 代替，其中 g(y)為一 Skolem函數(shù)。 ? (5) 化為前束形 到這一步，已不留下任何存在量詞，把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為 前束形 ，前束形由前綴和母式組成，前綴由全稱量詞串組成，母式由沒有量詞的公式組成，即 前束形 = (前綴 ) (母 式 ) 全稱量詞串 無量詞公式 ? (6) 把母式化為合取范式 任何母式都可寫成 由一些謂詞公式和 (或 )謂詞公式的否定的析取的有限集組成的合取 。這種母式叫做 合取范式 。我們可以反復應用分配律。把任一母式化成合取范式。例如，把 A∨{B∧C} 化為 {A∨B}∧{A∨C} ? (7) 消去全稱量詞 到這一步， 所有余下的變量均被全稱量詞量化 。同時，全稱量化變量的次序也不重要，可以消去出現(xiàn)的全稱量詞 。