【正文】 Technology, Nanjing University Artificial Intelligence Spring 基于遞歸的搜索 procedure member (item, list)。遞歸是為大小不定的數(shù)據(jù)結(jié)構(gòu)，如廣義表、樹、圖構(gòu)造的一個(gè)自然的控制，特別適合狀態(tài)空間搜索。 。 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。 day(saturday)∧ warm(saturday)= location(sam,park). ,則 Sam 就在展覽館中。 ?X[spaniel(X)∨(collie(X)∧trained(X))=gooddog(X)] ,則狗會(huì)和主人在一起。 Technology, Nanjing University Artificial Intelligence Spring 深入討論 是一只訓(xùn)練過的狗。 day (saturday). 。 collie (fred). 是 Fred 的主人。斷言集是對一只狗 Fred和它的主人 Sam之間關(guān)系的邏輯描述。 Technology, Nanjing University Artificial Intelligence Spring 例子： 這是謂詞演算的例子 ,闡述的是一個(gè)目標(biāo)驅(qū)動(dòng)的圖搜索。 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。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 71 Department of Computer Science amp。 (3)擴(kuò)展 5號節(jié)點(diǎn)，生成 t3節(jié)點(diǎn)和 C節(jié)點(diǎn)。 (5) 擴(kuò)展 4號節(jié)點(diǎn)，生成 t2節(jié)點(diǎn)和 B節(jié)點(diǎn)。 (6) 搜索成功，得到由 4號節(jié)點(diǎn)即 tt t3節(jié)點(diǎn)構(gòu)成的解樹。 (2)擴(kuò)展 3號節(jié)點(diǎn)，生成 t1節(jié)點(diǎn)和 5號節(jié)點(diǎn)。 Technology, Nanjing University Artificial Intelligence Spring 例： 若按有界深度優(yōu)先，且 設(shè) dm=4，則其節(jié)點(diǎn)擴(kuò)展順序?yàn)椋? 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的有界深度優(yōu)先搜索 1， 3， 5， 2， 4 70 Department of Computer Science amp。 ③ 轉(zhuǎn)第 (2)步。 (5)如果節(jié)點(diǎn) n不可擴(kuò)展，則作下列工作： ① 標(biāo)記節(jié)點(diǎn) n為不可解節(jié)點(diǎn)； ② 應(yīng)用不可解標(biāo)記過程對節(jié)點(diǎn) n的先輩中不可解解的節(jié)點(diǎn)進(jìn)行標(biāo)記 。如果初始解節(jié)點(diǎn) S0能夠被標(biāo)記為可解節(jié)點(diǎn) ， 就得到了解樹 ， 搜索成功 ， 退出搜索過程；如果不能確定 S0為可解節(jié)點(diǎn) ， 則從 Open表中刪去具有可解先輩的節(jié)點(diǎn) 。 Technology, Nanjing University Artificial Intelligence Spring 與 /或樹的深度優(yōu)先搜索也可以帶有深度限制 dm 搜索算法如下： (1)把初始節(jié)點(diǎn) S0放入 Open表中； (2)把 Open表第一個(gè)節(jié)點(diǎn)取出放入 Closed表，并記該節(jié)點(diǎn)為 n； (3)如果節(jié)點(diǎn) n的深度等于 dm，則轉(zhuǎn)第 (5)步的第 ① 點(diǎn)； (4)如果節(jié)點(diǎn) n可擴(kuò)展，則做下列工作： ① 擴(kuò)展節(jié)點(diǎn) n，將其子節(jié)點(diǎn)放入 Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； ② 考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn) 。 ?在擴(kuò)展節(jié)點(diǎn)時(shí)，與 /或樹的深度優(yōu)先搜索過程總是把剛生成的節(jié)點(diǎn)放在 Open表的首部。 67 Department of Computer Science amp。由于 t2為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 2號節(jié)點(diǎn)為可解，但不能標(biāo)記 1號節(jié)點(diǎn)為可解。調(diào)用不可解標(biāo)記過程 … 。由于 t3為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，可標(biāo)記 1號節(jié)點(diǎn)為可解節(jié)點(diǎn)。由于 t1為終止節(jié)點(diǎn)，則標(biāo)記它為可解節(jié)點(diǎn)，并應(yīng)用可解標(biāo)記過程，不能確定 3號節(jié)點(diǎn)是否可節(jié)。 (2) 擴(kuò)展 2號節(jié)點(diǎn)，生成 A節(jié)點(diǎn)和4號節(jié)點(diǎn)。 1 2 3 A 4 t1 5 t2 B t3 C 與 /或樹的廣度優(yōu)先搜索 66 Department of Computer Science amp。 65 Department of Computer Science amp。如果初始解節(jié)點(diǎn) S0也被標(biāo)記為不可解節(jié)點(diǎn) ， 則搜索失敗 ， 表明原始問題無解 ，退出搜索過程；如果不能確定 S0為不可解節(jié)點(diǎn) ， 則從 Open表中刪去具有不可解先輩的節(jié)點(diǎn) 。 ③ 轉(zhuǎn)第 (2)步。 若有 ， 則標(biāo)記這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn) ， 并用可解標(biāo)記過程對其父節(jié)點(diǎn)及先輩節(jié)點(diǎn)中的可解解節(jié)點(diǎn)進(jìn)行標(biāo)記 。 與 /或樹的廣度優(yōu)先和深度優(yōu)先搜索 1 2 3 A 4 t1 5 64 Department of Computer Science amp。 與 /或樹的一般搜索 1 2 3 A 4 t1 5 t2 B t3 C 搜索樹 63 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring ?是一個(gè)不斷尋找解樹的過程。 Technology, Nanjing University Artificial Intelligence Spring 三階梵塔問題的分解過程可用如下圖與 /或樹來表示 (1,1,1)→(3,3,3) (1,1,1)→(1,2,2) (1,2,2)→(3,2,2) (3,2,2)→(3,3,3) (1,1,1)→(1,1,3) (1,1,3)→(1,2,3) (1,2,3)→(1,2,2) (3,2,2)→(3,2,1) (3,2,1)→(3,3,1) (3,3,1)→(3,3,3) 在該與 /或樹中，有 7個(gè)終止節(jié)點(diǎn)，它們分別對應(yīng)著 7個(gè)原本問題。 即 (1, 2, 2)→(3, 2, 2) （ 3）把金片 A及 B移到 3號鋼針的雙金片移動(dòng)問題。 Technology, Nanjing University Artificial Intelligence Spring 利用問題歸約方法，原問題可分解為以下 三個(gè)子問題 ： （ 1）把金片 A及 B移到 2號鋼針上的雙金片移動(dòng)問題。要求把 1號鋼針上的 3個(gè)金片全部移到 3號鋼針上， 1 2 3 1 2 3 與 /或樹表示的例子 A B C 解： 用三元組 (i, j, k) 表示問題在任一時(shí)刻的狀態(tài)，用“ → ”表示狀態(tài)的轉(zhuǎn)換。 問題歸約求解過程 : 生成解樹，即證明原始節(jié)點(diǎn)是可解節(jié)點(diǎn)的過程 這一過程涉及到 與 /或樹 的搜索 59 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring P t t t 解樹 解樹： 由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（它對應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為 解樹 。 ? 對“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 Technology, Nanjing University Artificial Intelligence Spring 可用類似的方法定義： ? 不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 ? 對“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。 Technology, Nanjing University Artificial Intelligence Spring 可解節(jié)點(diǎn)： 在與 /或樹中，滿足以下三個(gè)條件之一： ? 任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。 Technology, Nanjing University Artificial Intelligence Spring P P1 P2 P3 與樹 (1)與樹 分解 P1 P2 P3 或樹 P (2) 或樹 等價(jià)變換 P P1 P2 P3 P12 P12 P31 P32 P33 與 /或樹 (3) 與 /或樹 與或樹 與或樹表示法 55 Department of Computer Science amp。 即變換所得到的子問題的“或”與原問題 P等價(jià)。 即分解所得到的子問題的 “ 與 ” 與原問題 P等價(jià)。 Technology, Nanjing University Artificial Intelligence Spring ?基本思想 當(dāng)一問題較復(fù)雜時(shí)，可通過 分解 或 變換 ，將其轉(zhuǎn)化為一系列較簡單的子問題，然后通過對這些子問題的求解來實(shí)現(xiàn)對原問題的求解。 Technology, Nanjing University Artificial Intelligence Spring 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8