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

　　

【正文】 果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (4) 如果節(jié)點 n不可擴展，則作下列工作： ① 標(biāo)記節(jié)點 n為不可解節(jié)點； ② 應(yīng)用不可解標(biāo)記過程對節(jié)點 n的先輩中不可解解的節(jié)點進(jìn)行標(biāo)記 。如果初始解節(jié)點 S0也被標(biāo)記為不可解節(jié)點 ， 則搜索失敗 ， 表明原始問題無解 ，退出搜索過程；如果不能確定 S0為不可解節(jié)點 ， 則從 Open表中刪去具有不可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步 。 65 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例 : 設(shè)有下圖所示的與 /或樹，節(jié)點按標(biāo)注順序進(jìn)行擴展，其中表有 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é)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定 3號節(jié)點是否可節(jié)。 (6) 擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 1號節(jié)點為可解節(jié)點。 (4) 擴展節(jié)點 A，由于 A是端節(jié)點，因此不可擴展。調(diào)用不可解標(biāo)記過程 … 。 (5) 擴展 4號節(jié)點，生成 t2節(jié)點和 B節(jié)點。由于 t2為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號節(jié)點為可解，但不能標(biāo)記 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é)點 。 若有 ， 則標(biāo)記這些終止節(jié)點為可解節(jié)點 ， 并用可解標(biāo)記過程對其父節(jié)點及先輩節(jié)點中的可解解節(jié)點進(jìn)行標(biāo)記 。如果初始解節(jié)點 S0能夠被標(biāo)記為可解節(jié)點 ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點 ， 則從 Open表中刪去具有可解先輩的節(jié)點 。 ③ 轉(zhuǎn)第 (2)步。 (5)如果節(jié)點 n不可擴展，則作下列工作： ① 標(biāo)記節(jié)點 n為不可解節(jié)點； ② 應(yīng)用不可解標(biāo)記過程對節(jié)點 n的先輩中不可解解的節(jié)點進(jìn)行標(biāo)記 。 如果初始解節(jié)點 S0也被標(biāo)記為不可解節(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é)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，不能確定 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é)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號節(jié)點為可解，再往上又可標(biāo)記 1號節(jié)點為可解。 (3)擴展 5號節(jié)點，生成 t3節(jié)點和 C節(jié)點。由于 t3為終止節(jié)點，則標(biāo)記它為可解節(jié)點，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 3號節(jié)點為可解節(jié)點，但不能標(biāo)記 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 圖 表達(dá)式 Q∨ R=P P R Q 圖 表達(dá)式 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 圖 一個命題演算表達(dá)式 集合的與 /或樹 ?h為真嗎？ ?b不再為真時 h還會為真嗎？ ?為了證明 X為真，最短的推理序列是什么？ 74 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例子： 這是謂詞演算的例子 ,闡述的是一個目標(biāo)驅(qū)動的圖搜索。要證明為真的目標(biāo)是一含變量的謂詞演算表達(dá)式。斷言集是對一只狗 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 深入討論 是一只訓(xùn)練過的狗。 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). 目標(biāo)是 : ?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:=