【正文】 該問(wèn)題的狀態(tài)空間是： {{S0}， { P 01， P 10， P 11， P 02， P 20， Q01， Q 10， Q 11， Q 02， Q 20}， {S31}}。隱式狀態(tài)空間圖也稱(chēng)為是 狀態(tài)空間圖的隱式表示或隱式圖 。 例 （ 4） （ 3）隱式圖搜索 初始狀態(tài) S＝（ 0， 1， 2， 3， 5， 6， 4， 7， 8 ）滿(mǎn)足條件 X0 =0，故可以使用第 0組的四條規(guī)則： 如果選擇規(guī)則 R1，則狀態(tài)轉(zhuǎn)換為： S1＝（ 2， 1， 0， 3， 5， 6， 4， 7，8) R 2R 4R 1R 3 1 2 3 8 5 7 4 6 1 3 8 2 5 7 4 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 8 5 7 4 62023/4/2 人工智能 31 例 旅行商問(wèn)題 (TSP)(1) 設(shè)有 n個(gè)互相可直達(dá)的城市 ， 某推銷(xiāo)商準(zhǔn)備從其中的 A城出發(fā) ， 周游各城市一遍 ， 最后又回到 A城 。即沒(méi)遍歷完時(shí)，在城市序列中添加一個(gè)沒(méi)有到過(guò)的城市。要求將 A、B移至三號(hào)桿，每次只可移動(dòng)一個(gè)盤(pán)子，任何時(shí)刻 B不能在 A上。盲目搜索與問(wèn)題無(wú)關(guān)，具有通用性。 2023/4/2 人工智能 38 節(jié)點(diǎn) 父節(jié)點(diǎn)編號(hào) 編號(hào) 節(jié)點(diǎn) 父節(jié)點(diǎn)編號(hào) OPEN表 CLOSED表 2023/4/2 人工智能 39 狀態(tài)空間圖的盲目搜索 廣度優(yōu)先搜索 深度優(yōu)先搜索 2023/4/2 人工智能 40 廣度優(yōu)先搜索（ 1） ? 廣度優(yōu)先搜索（ A?ed）基本思想： 廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹(shù)中的出現(xiàn)位置 一層一 層向下的搜索過(guò)程。 廣度優(yōu)先搜索（ 2） 2023/4/2 人工智能 42 例 1 2 3 8 5 7 4 6 1 1 2 3 8 5 6 7 4 8 1 3 8 2 5 7 4 6 10 1 2 3 8 4 5 7 6 7 1 2 3 8 4 5 7 6 6 1 3 8 2 5 7 4 6 11 1 2 3 8 4 5 7 6 2 1 2 3 8 5 7 4 6 3 1 2 3 8 4 5 7 6 4 1 2 3 7 8 5 4 6 12 2 3 1 8 5 7 4 6 13 1 2 3 8 4 7 6 5 14 1 2 3 4 5 8 7 6 15 1 2 8 5 3 7 4 6 17 1 3 5 8 2 7 4 6 18 8 1 3 2 5 7 4 6 19 1 2 3 7 8 5 4 6 20 2 3 1 8 5 7 4 6 21 1 2 8 4 3 7 6 5 22 1 2 3 8 5 7 4 6 5 1 2 3 8 4 7 6 5 23 八數(shù)碼廣度優(yōu)先搜索 1 2 8 5 3 7 4 6 9 16 1 2 3 8 5 6 7 4 2023/4/2 人工智能 43 廣度優(yōu)先搜索 廣度優(yōu)先搜索的特點(diǎn)： ?廣度優(yōu)先中 OPEN表 是一個(gè) 隊(duì)列 ， CLOSED表 是一個(gè) 順序表 ，表中各節(jié)點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最大。 ?缺點(diǎn)搜索 效率低 。 例 1 2 3 8 5 7 4 6 1 1 2 3 8 4 5 7 6 3 1 2 3 8 4 5 7 6 1 2 3 8 4 5 7 6 1 2 3 8 5 7 4 6 1 2 3 8 4 5 7 6 1 2 3 8 4 7 6 5 4 1 2 8 4 3 7 6 5 1 2 3 8 5 7 4 6 2 1 2 3 8 4 7 6 5 5 2023/4/2 人工智能 46 深度優(yōu)先搜索 深度優(yōu)先搜索的特點(diǎn) ： ?OPEN表為一個(gè) 堆棧 。由于解的路徑長(zhǎng)度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出 dm的值是比較困難的。 當(dāng) ⊿ d =1時(shí)，算法開(kāi)始蛻變?yōu)?廣度優(yōu)先搜索 算法。 (3) 步 3 取 OPEN表中第一個(gè)節(jié)點(diǎn) N放在 CLOSED表中；并冠以編號(hào) n； 步 4 若節(jié)點(diǎn) N為目標(biāo)節(jié)點(diǎn)，成功退出。 步 6 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 步 7 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針?lè)湃隣PEN表首部， 置 d（ Ni ）＝ d（ N）＋ 1 ，轉(zhuǎn)步 2。 啟發(fā)函數(shù)可以是： （ 1）一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度； （ 2）一個(gè)節(jié)點(diǎn)處在最佳路徑上的概率； （ 3）根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。 2023/4/2 人工智能 60 啟發(fā)式搜索算法 （ 4） 基本思想： 局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索，在 OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，對(duì)其中 新生成的每個(gè)子節(jié)點(diǎn) x計(jì)算啟發(fā)函數(shù) ，從 全部子節(jié)點(diǎn) 中選出 最優(yōu)節(jié)點(diǎn) 進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn)， 局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)別僅在 步 6： 步 6 否則，擴(kuò)展 N，計(jì)算 N的每個(gè)子節(jié)點(diǎn) x的函數(shù)值，并將 N的所有子節(jié)點(diǎn) x配以指向節(jié)點(diǎn) N的指針后，將 全部子節(jié)點(diǎn) 按啟發(fā)函數(shù)值升序排列后放入 OPEN表的首部，轉(zhuǎn)步 2。將兩者同時(shí)考慮，用于指導(dǎo)搜索的算法稱(chēng)為 A算法和 A*算法 。 啟發(fā)式搜索的 A算法和 A*算法（ 3） 代價(jià) g（ x） 的計(jì)算 g（ x） 表示從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) x的代價(jià)： g（ S0 ）＝ 0 g（ xj ）＝ g（ xi ）＋ c（ xi， xj） 其中， c（ xi， xj） 表示父節(jié)點(diǎn) xi到子節(jié)點(diǎn) xj的代價(jià) A D C E B 4 6 4 3 3 2 3 2 3 4 6 2 3 4 4 6 3 2 C1 B1 D1 D2 E1 C2 E2 D3 C3 B2 E4 E3 6 B3 2023/4/2 人工智能 64 啟發(fā)式搜索的 A算法和 A*算法（ 4） 對(duì)估價(jià)函數(shù) f（ x） ＝ g（ x）＋ h（ x） 令其中的 h（ x） =0時(shí)，這時(shí)得到的是 代價(jià)樹(shù) 的 非啟發(fā)式搜索算法。 步 5 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 啟發(fā)式搜索的 A算法和 A*算法（ 6） 步 6 否則，擴(kuò)展 N，生成一組子節(jié)點(diǎn) xi，計(jì)算 f（ xi ） ，并對(duì)這組節(jié)點(diǎn) xi作如下處理： 1）若 xi是 N的 先輩節(jié)點(diǎn) ，則 刪除 之。 2023/4/2 人工智能 67 2023/4/2 人工智能 68 啟發(fā)式搜索的 A算法和 A*算法（ 7） 對(duì) 步 6的 1）的說(shuō)明： ABCDS0（ a ）（ b ）S0BACD 啟發(fā)式搜索的 A算法和 A*算法（ 8） 對(duì)步 6的 2）的說(shuō)明： （ b ）S0BACABCDS0（ a ）ABCDS0（ c ）D2023/4/2 人工智能 69 啟發(fā)式搜索的 A算法和 A*算法（ 9） ? 樹(shù)式搜索例 ? 對(duì)于 已存在于 OPEN表中的節(jié)點(diǎn) （如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點(diǎn)在 OPEN表中的原返回指針，使其沿原路徑返回。 S0 過(guò)去生成 P的路徑 現(xiàn)在生成 P的路徑 過(guò)去對(duì) Ps的 最優(yōu)路徑 Ps P m n k n之前已是某一節(jié)點(diǎn) m的后繼，所以需要做如同（ 2）同樣的處理，如圖右部所示。 g（ x）：對(duì)某一確定的節(jié)點(diǎn)，是確定的值。 例 A算法在重排九宮問(wèn)題中的應(yīng)用。 在正中方格上有將牌得 1分，否則得 0分。在河的左岸有五個(gè)修道士、五個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過(guò)河去，但受到以下條件的限制： （ 1）修道士和野人都會(huì)劃船，但船一次 最多 只能 運(yùn)三個(gè)人； （ 2）在任何岸邊及船上 野人數(shù)目 都 不得超過(guò)修道士 ，否則修道士就會(huì)被野人吃掉。問(wèn)題的狀態(tài)可以用一個(gè)三元數(shù)組來(lái)描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 初始狀態(tài) 為：（ 5， 5， 1） 終止?fàn)顟B(tài) 為：（ 0， 0， 0） 合法的操作只有使?fàn)顟B(tài)如下轉(zhuǎn)換： 從平衡狀態(tài)（ m=c）轉(zhuǎn)換為修道士扎堆（ m=0或 m=5） 從平衡狀態(tài)（ m=c）轉(zhuǎn)換為平衡狀態(tài)（ m=c） 從扎堆狀態(tài) （ m=0或 m=5）轉(zhuǎn)換為平衡狀態(tài)（ m=c） 2023/4/2 人工智能 85 啟發(fā)式搜索的 A算法和 A*算法（ 25） 定義啟發(fā)函數(shù)，若滿(mǎn)足 h（ n） ≤h *（ n），即滿(mǎn)足 A*條件的。 2023/4/2 人工智能 86 啟發(fā)式搜索的 A算法和 A*算法（ 26） ? 先考慮船在左岸的情況： ? 如果不考慮限制條件，至少需要 [（ m+c3） /2]*2+1 化簡(jiǎn)后為： [（ m+c3） /2]*2+1大于等于 m+n2 ? 再考慮船在右岸的情況： ? 同樣不考慮限制條件。 A*算法在游戲中的應(yīng)用（ 2） ? 如果游戲僅僅要求出從點(diǎn) A到達(dá)點(diǎn) B的一條最短路徑的話，那么使用 A*算法，將 h(x)設(shè)計(jì)為對(duì)A點(diǎn)到 B點(diǎn)的最短路徑的估計(jì)就可以完成此任務(wù)；然而，真實(shí)游戲中往往還要考慮路上的障礙物、或者在從點(diǎn) A到點(diǎn) B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。 2023/4/2 人工智能 93 與或圖表示及搜索技術(shù) 與或圖表示 與或樹(shù)的盲目搜索 與或樹(shù)的啟發(fā)式搜索 與或圖表示（ 1） ? 與或圖的概念來(lái)源于問(wèn)題求解中的分解和變換 ? 一個(gè)復(fù)雜的問(wèn)題 P常?？梢苑纸鉃榕c之等價(jià)的一組子問(wèn)題 P1， P2 ， ? Pn， 當(dāng)這些問(wèn)題全部可解時(shí)，問(wèn)題可解；任何一個(gè)子問(wèn)題無(wú)解時(shí)，都將導(dǎo)致原問(wèn)題 P無(wú)解。 與或圖表示（ 2） 例 猴子摘香蕉問(wèn)題 房間內(nèi)有一只猴子位于 A處，有一只箱子位于 B處，還有一架梯子位于 C處， A到 B的距離與 A到 C是距離相同，梯子和箱子的重量相同。D180。 D180。 ：證明 AD＝ A′D ′ Q13 180。 ：證明 BD＝ B′D′ 180。 Q21 Q22 Q23 Q21 39。 有 3號(hào)桿， 1號(hào)桿自上而下串著從小到大的 n個(gè)金盤(pán)，要把 1號(hào)桿上的 n個(gè)金盤(pán)移到 3號(hào)桿上。 ? 無(wú)子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為 端節(jié)點(diǎn) 。 2023/4/2 人工智能 104 與或圖表示（ 8） 與或圖也可以用三元組表示： （ Q0 , F , Qn） Q0表示初始問(wèn)題 F表示問(wèn)題變換規(guī)則集 Qn表示 本原問(wèn)題集 與或圖表示（ 9） 節(jié)點(diǎn)的可解性判別： （ 1）終止節(jié)點(diǎn)是可解節(jié)點(diǎn)； （ 2）一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其全部子節(jié)點(diǎn)可解； （ 3）一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)