【導讀】用搜索法對問題求解。狀態(tài)空間搜索的結(jié)構(gòu)。問題的狀態(tài)空間表示法。與/或樹的盲目搜索。一個問題可以形式化地定義為四個組成部分：。問題的解就是從初始狀態(tài)到目標狀態(tài)的路徑。問題求解器是否能終止運行,或是否會陷入一個死循環(huán)?怎樣才能最有效地降低搜索的復雜性?怎樣設(shè)計才能最有效地利用描述語言?狀態(tài)空間的理論是我們用來回答這些疑問最主要的工具。圖由結(jié)點集和連接結(jié)點對的弧或邊的集合組成。設(shè)有三根鋼針，它們的編號分別是1號、2號和3號。要求把這兩個金片全部移到另一根鋼針上，的位于小的上面。最短的路徑長度是?w表示猴子的水平位置；拿到香蕉時z取1，否則z取0。

　　

【正文】 果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (4) 如果節(jié)點 n不可擴展，則作下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 應用不可解標記過程對節(jié)點 n的先輩中不可解解的節(jié)點進行標記 。如果初始解節(jié)點 S0也被標記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ，退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步 。 65 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例 : 設(shè)有下圖所示的與 /或樹，節(jié)點按標注順序進行擴展，其中表有 t tt3的節(jié)點是終止節(jié)點， A、 B、 C為不可解的端節(jié)點。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的廣度優(yōu)先搜索 66 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的廣度優(yōu)先搜索 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和 3號節(jié)點。 (2) 擴展 2號節(jié)點，生成 A節(jié)點和4號節(jié)點。 (3) 擴展 3號節(jié)點，生成 t1節(jié)點和 5號節(jié)點。由于 t1為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，不能確定 3號節(jié)點是否可節(jié)。 (6) 擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 1號節(jié)點為可解節(jié)點。 (4) 擴展節(jié)點 A，由于 A是端節(jié)點，因此不可擴展。調(diào)用不可解標記過程 … 。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。由于 t2為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 2號節(jié)點為可解，但不能標記 1號節(jié)點為可解。 (7) 搜索成功，得到由 5號節(jié)點即 tt t3節(jié)點構(gòu)成的解樹。 67 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring ?與 /或樹的深度優(yōu)先搜索和與 /或樹的廣度優(yōu)先搜索過程基本相同 . ?其主要區(qū)別在于 Open表中節(jié)點的排列順序不同。 ?在擴展節(jié)點時，與 /或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點放在 Open表的首部。 ?深度優(yōu)先搜索 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的深度優(yōu)先搜索 68 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 與 /或樹的深度優(yōu)先搜索也可以帶有深度限制 dm 搜索算法如下： (1)把初始節(jié)點 S0放入 Open表中； (2)把 Open表第一個節(jié)點取出放入 Closed表，并記該節(jié)點為 n； (3)如果節(jié)點 n的深度等于 dm，則轉(zhuǎn)第 (5)步的第 ① 點； (4)如果節(jié)點 n可擴展，則做下列工作： ① 擴展節(jié)點 n，將其子節(jié)點放入 Open表的首部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針； ② 考察這些子節(jié)點中是否有終止節(jié)點 。 若有 ， 則標記這些終止節(jié)點為可解節(jié)點 ， 并用可解標記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進行標記 。如果初始解節(jié)點 S0能夠被標記為可解節(jié)點 ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (5)如果節(jié)點 n不可擴展，則作下列工作： ① 標記節(jié)點 n為不可解節(jié)點； ② 應用不可解標記過程對節(jié)點 n的先輩中不可解解的節(jié)點進行標記 。 如果初始解節(jié)點 S0也被標記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ，退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 69 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例： 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點擴展順序為？ 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 1， 3， 5， 2， 4 70 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 搜索過程為： (1) 先擴展 1號節(jié)點，生成 2號節(jié)點和3號節(jié)點。 (2)擴展 3號節(jié)點，生成 t1節(jié)點和 5號節(jié)點。由于 t1為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，不能確定 3號節(jié)點是否可解。 (6) 搜索成功，得到由 4號節(jié)點即 tt t3節(jié)點構(gòu)成的解樹。 (4) 擴展 2號節(jié)點，生成 A節(jié)點和 4號節(jié)點。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。由于 t2為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 2號節(jié)點為可解，再往上又可標記 1號節(jié)點為可解。 (3)擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標記它為可解節(jié)點，并應用可解標記過程，可標記 3號節(jié)點為可解節(jié)點，但不能標記 1號為可解。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 71 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 謂詞演算推理的與或樹表示法 命題演算中一個蘊含集 q = p r = p v = q s = r t = r s = u s t p q s u t v r 假設(shè)有下面的斷言集 : 72 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 與 /或樹 P R Q 圖 表達式 Q∨ R=P P R Q 圖 表達式 Q∧ R=P 73 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring a b c a∧b =d a∧c =e b∧d =f f=g a∧e =h g d e h f b c a 圖 一個命題演算表達式 集合的與 /或樹 ?h為真嗎？ ?b不再為真時 h還會為真嗎？ ?為了證明 X為真，最短的推理序列是什么？ 74 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例子： 這是謂詞演算的例子 ,闡述的是一個目標驅(qū)動的圖搜索。要證明為真的目標是一含變量的謂詞演算表達式。斷言集是對一只狗 Fred和它的主人 Sam之間關(guān)系的邏輯描述。 該例中的事實和規(guī)則如下 : 是一只長毛大牧羊犬。 collie (fred). 是 Fred 的主人。 master (fred,sam). 。 day (saturday). 。 ~(warm (saturday)). 75 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深入討論 是一只訓練過的狗。 trained (fred). 。 ?X[spaniel(X)∨(collie(X)∧trained(X))=gooddog(X)] ,則狗會和主人在一起。 ?X,Y,Z[gooddog(X)∧master(X,Y)∧location(Y,Z)=location(X,Z)] ,則 Sam 就在公園里。 day(saturday)∧ warm(saturday)= location(sam,park). ,則 Sam 就在展覽館中。 day(saturday)∧ ~ warm(saturday) =location(sam,museum). 目標是 : ?X location(fred,X) 也就是 :Fred在哪 ? 76 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深入討論 表示 FRED在展覽館的與 /或樹 LOCATION(X,Z) GOODDOG(X) NOT WARM(SATURDAY) DAY(SATRDAY) MASTER(FRED,SAM) TRAINED(X) COLLIE(X) LOCATION(Y,Z) MASTER(X,Y) TRAINED(FRED) COLLIE(FRED) SUBSTITUTIONS={FRED/X, SAM/Y, MUSEUM/Z} 77 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 基于遞歸的搜索 ? 遞歸 一個遞歸過程包括 : 。 。 對所有遞歸定義和遞歸算法都是必要的。遞歸是為大小不定的數(shù)據(jù)結(jié)構(gòu)，如廣義表、樹、圖構(gòu)造的一個自然的控制，特別適合狀態(tài)空間搜索。 78 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 基于遞歸的搜索 procedure member (item, list)。 begin if list is empty then return (fail) % terminating condition 1 else if item = first element of list then return (success) % terminating condition 2 else begin tail:=