【正文】 ｝的子句消解得到空子句，那么 L在邏輯上遵循 S。 57 含有變量的消解式 消解式求法 為了對含有變量的子句使用消解規(guī)則，必須找到一個置換，作用于父輩子句使其含有互補文字。 52 例 將下列謂詞演算公式化為一個子句集 (? x)｛ P(x)→ ｛ (? y)［ P(y)→P(f(x,y)) ］ ∧ ～ (? y)［ Q(x,y)→P(y) ］｝｝ 53 說明 并不是所有問題的謂詞公式化為子句集都需要上述 9個步驟。所得公式稱為前束形。合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個量詞有其自己唯一的啞元。 （ 2）子句：由文字的析取組成的公式 (一個原子公式和原子公式的否定都叫做文字 )。 40 A*算法 A*算法描述參考教材。這個定義包含了g(n)≥g*(n) 。 35 例：八數(shù)碼難題 采用了簡單的估價函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點 n的深度； W(n)用來計算對應(yīng)于節(jié)點 n的數(shù)據(jù)庫中錯放的棋子個數(shù)。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點。 (4) 把節(jié)點 i從 OPEN表中移出，并把它放入CLOSED的擴展節(jié)點表中。 尼爾遜 (Nilsson)曾提出一個有序搜索的基本算法。然后，搜索就可能沿著某個被認(rèn)為是最有希望的邊緣區(qū)段向外擴展。 教學(xué)難點：估價函數(shù)的設(shè)計、 A*算法原理。 思考題 ：有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的最短途徑嗎？ 20 定義 寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠不會終止 )。 10 寬度優(yōu)先搜索算法 (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答 )。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標(biāo)節(jié)點。對已在CLOSED表上的每個 M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。 (4) 選擇 OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進 CLOSED表中。第三章 搜索推理技術(shù) 教學(xué)內(nèi)容 ? 早期搜索推理技術(shù)，如圖搜索策略和消解原理； ? 高級搜索推理技術(shù)，如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理。 (3) LOOP：若 OPEN表是空表，則失敗退出。對已經(jīng)在 OPEN或 CLOSED表上的每一個 M成員，確定是否需要更改通到 n的指針方向。當(dāng)搜索樹不再剩有未被擴展的端節(jié)點時，過程就以失敗告終(某些節(jié)點最終可能沒有后繼節(jié)點，所以 OPEN表可能最后變成空表 )。 9 特點 這種搜索是逐層進行的；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。 11 寬度優(yōu)先搜索方法分析： 寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實際是將 OPEN表作為“先進先出”的隊列進行操作。 18 19 含有深度界限的深度優(yōu)先搜索算法 請同學(xué)們課后自學(xué)，并回答課后思考題。 教學(xué)重點：啟發(fā)式搜索策略、啟發(fā)信息和有序搜索。一個比較靈活 (但代價也較大 )的利用啟發(fā)信息的方法是應(yīng)用某些準(zhǔn)則來重新排列每一步 OPEN表中所有節(jié)點的順序。這種搜索方法叫做有序搜索(ordered search)或最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。結(jié)果有幾個節(jié)點合格，當(dāng)其中有一個為目標(biāo)節(jié)點時，則選擇此目標(biāo)節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點 i。如果新的 f值較小，則 (i) 以此新值取代舊值。如果沒有適用的準(zhǔn)確的希望量度，那么 f的選擇將涉及兩個方面的內(nèi)容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。對于g(n)來說，一個明顯的選擇就是搜索樹中從 S到n這段路徑的代價，這一代價可以由從 n到 S尋找指針時，把所遇到的各段弧線的代價加起來給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價路徑 )。當(dāng) h=0時， A*算法就變?yōu)橛行蛩阉魉惴ā? 42 消解原理的基礎(chǔ)知識： （ 1）謂詞公式、某些推理規(guī)則以及置換合一等概念。例如： 以～ A∨ ～ B代替～ (A∧B) 以～ A∧ ～ B代替～ (A∨B) 以 A代替～ (～ A) 以 (?)｛～ A｝代替～ (? x)A 以 (? x)｛～ A｝代替～ (? x)A 45 提問 ： 設(shè)有公式 (? x)(? y)｛ (? y)P(x,y)→ (? x)Q(x,y)｝，在經(jīng)過對變量標(biāo)準(zhǔn)化后得到公式為： A． (? x)(? y)｛ (? y)P(x,y)→( ? y)Q(y,y)｝ B． (? x)(? y)｛ (? x)P(x,x)→( ? x)Q(x,y)｝ C． (? x)(? y)｛ (? z)P(x,z)→( ? q)Q(q,y)｝ D． (? x)(? y)｛ (? z)P(x,z)→( ? q)Q(q,z)｝ E． (? x)(? y)｛ (? z)P(q,z)→( ? q)Q(q,z)｝ 46 (3) 對變量標(biāo)準(zhǔn)化 在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元 (虛構(gòu)變量 )，它可以在該轄域內(nèi)處處統(tǒng)一地被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。 49 (5) 化為前束形 把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。 (9) 更換變量名稱 可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。 說明： 對合并、重言式、鏈?zhǔn)?(三段論 )請同學(xué)們自行閱讀?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句 NIL。 64 ? 例：儲蓄問題 前提：每個儲蓄錢的人都獲得利息。 66 ? 規(guī)則演繹系統(tǒng)的定義： 基于規(guī)則的問題求解系統(tǒng)運用下述規(guī)則來建立： If→Then 其中， If部分可能由幾個 if組成，而 Then部分可能由一個或一個以上的 then組成。具體變換步驟與前述化為子句形類似。假設(shè)有一條規(guī)則 L=W，根據(jù)此規(guī)則及事實表達式 F(L)，可以推出表達式 F(W)。 結(jié)論： 當(dāng)正向演繹系統(tǒng)產(chǎn)生一個含有以目標(biāo)節(jié)點作為終止的解圖時，此系統(tǒng)就成功地終止。 77 規(guī)則雙向演繹系統(tǒng) 特點和局限性 正向演繹系統(tǒng)能夠處理任意形式的 if表達式，但被限制在 then表達式為由文字析取組成的一些表達式。只有當(dāng)求得這樣的一個證明時，證明過程才算成功地終止。 教學(xué)要求：掌握產(chǎn)生式系統(tǒng)的組成結(jié)構(gòu)，通過實踐掌握產(chǎn)生式系統(tǒng)的設(shè)計和工作過程。執(zhí)行產(chǎn)生式規(guī)則的操作會引起總數(shù)據(jù)庫的變化，這就使其他產(chǎn)生式規(guī)則的條件可能被滿足。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。 一般策略：先提供一批事實（數(shù)據(jù)）到總數(shù)據(jù)庫中。 92 雙向推理的推理策略是同時從目標(biāo)向事實推理和從事實向目標(biāo)推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標(biāo)的匹配。與每個任務(wù)有關(guān)的有兩件事，即提出該任務(wù)的理由和表示對該任務(wù)是有用的證據(jù)總權(quán)的評價。整個系統(tǒng)由一組稱為知識資源 (KS)的獨立模塊和一塊黑板組成。而在該假設(shè)最后導(dǎo)致不相容時，再考慮參加競爭的另一假設(shè)。這個系數(shù)被稱為可信度 (也有一些專家系統(tǒng)，如 MYCIN和EXPERT等，取可信度的范圍為 1到 +1)。 105 ? 例：有以下規(guī)則： 如果 啟動器發(fā)生刺耳的噪聲那么這個啟動器壞的可能性是 。按這種方法由一組規(guī)則支持的事實的可信度，可用以下方法求得，首先把各個證據(jù)的可信度轉(zhuǎn)換成可信性比例 r。 教學(xué)方法：課堂教學(xué)。 113 (Truth Maintenane System,TMS) 這是一個已經(jīng)實現(xiàn)的非單調(diào)推