【正文】 2023/4/2 人工智能 104 與或圖表示（ 8） 與或圖也可以用三元組表示： （ Q0 , F , Qn） Q0表示初始問題 F表示問題變換規(guī)則集 Qn表示 本原問題集 與或圖表示（ 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è)可解。 有 3號桿， 1號桿自上而下串著從小到大的 n個(gè)金盤，要把 1號桿上的 n個(gè)金盤移到 3號桿上。 ：證明 BD＝ B′D′ 180。 D180。 與或圖表示（ 2） 例 猴子摘香蕉問題 房間內(nèi)有一只猴子位于 A處，有一只箱子位于 B處，還有一架梯子位于 C處， A到 B的距離與 A到 C是距離相同，梯子和箱子的重量相同。 A*算法在游戲中的應(yīng)用（ 2） ? 如果游戲僅僅要求出從點(diǎn) A到達(dá)點(diǎn) B的一條最短路徑的話，那么使用 A*算法，將 h(x)設(shè)計(jì)為對A點(diǎn)到 B點(diǎn)的最短路徑的估計(jì)就可以完成此任務(wù)；然而，真實(shí)游戲中往往還要考慮路上的障礙物、或者在從點(diǎn) A到點(diǎn) B的途中避免被看到或被射擊到、以及敵方的位置和火力線等。問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述： 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ù)，若滿足 h（ n） ≤h *（ n），即滿足 A*條件的。 在正中方格上有將牌得 1分，否則得 0分。 g（ x）：對某一確定的節(jié)點(diǎn)，是確定的值。 2023/4/2 人工智能 67 2023/4/2 人工智能 68 啟發(fā)式搜索的 A算法和 A*算法（ 7） 對 步 6的 1）的說明： ABCDS0（ a ）（ b ）S0BACD 啟發(fā)式搜索的 A算法和 A*算法（ 8） 對步 6的 2）的說明： （ b ）S0BACABCDS0（ a ）ABCDS0（ c ）D2023/4/2 人工智能 69 啟發(fā)式搜索的 A算法和 A*算法（ 9） ? 樹式搜索例 ? 對于 已存在于 OPEN表中的節(jié)點(diǎn) （如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點(diǎn)的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點(diǎn)在 OPEN表中的原返回指針，使其沿原路徑返回。 啟發(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） 對估價(jià)函數(shù) f（ x） ＝ g（ x）＋ h（ x） 令其中的 h（ x） =0時(shí)，這時(shí)得到的是 代價(jià)樹 的 非啟發(fā)式搜索算法。 2023/4/2 人工智能 60 啟發(fā)式搜索算法 （ 4） 基本思想： 局部擇優(yōu)搜索是在啟發(fā)性知識導(dǎo)航下的深度優(yōu)先搜索，在 OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，對其中 新生成的每個(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。 步 6 若 N不可擴(kuò)展，則轉(zhuǎn)步 2； 步 7 否則，擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的返回指針放入OPEN表首部， 置 d（ Ni ）＝ d（ N）＋ 1 ，轉(zhuǎn)步 2。 當(dāng) ⊿ d =1時(shí)，算法開始蛻變?yōu)?廣度優(yōu)先搜索 算法。 例 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è) 堆棧 。 廣度優(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)按順序編號，正被考察的節(jié)點(diǎn)在表中編號最大。盲目搜索與問題無關(guān)，具有通用性。即沒遍歷完時(shí)，在城市序列中添加一個(gè)沒有到過的城市。隱式狀態(tài)空間圖也稱為是 狀態(tài)空間圖的隱式表示或隱式圖 。 Q5=(1,0,1) Q6=(1,1,0) 。 ?狀態(tài)空間常記為三元組： S： 初始狀態(tài)的集合 F： 操作的集合 G： 目標(biāo)狀態(tài)的集合。 狀態(tài)在狀態(tài)圖中表示為 節(jié)點(diǎn) 。搜索樹是一個(gè)搜索過程的搜索軌跡，或稱之為 搜索空間。 ?問題的求解框架 （ 1） 敘述性知識： 描述問題的狀態(tài)有關(guān)的各種知識。 ? 費(fèi)根鮑姆 ：知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。 ?問題求解： 是指在一定的控制策略下， 通過 一系列的 操作 或 運(yùn)算來 改變 問題的 狀態(tài) ，使之與目標(biāo)狀態(tài)接近或一致。 在一個(gè) 2n?2n的方格棋盤中，去掉對角的兩個(gè)方格，如圖（ a），問能否將它全部劃成若干 1?2的小長方塊？ 2 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 22 n2 n( b ) 同 構(gòu) 問 題2 n2 n( a ) 原 始 問 題QSQ1Qg ( c ) 同 態(tài) 問 題( 2 n2 , 2 n2 – 2 )( 2 n2 – 1 , 2 n2 – 3 )( 2 , 0 )( 0 , 0 )Q2 n2 2目標(biāo)狀態(tài) 初始狀態(tài) 可達(dá)狀態(tài) 同構(gòu)問題 同態(tài)問題 2023/4/2 人工智能 9 圖搜索技術(shù) (1) 搜索，簡單地說就是 “尋找 ”，目的是找到問題的解。啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。 Q1=(0,0,1)。 2023/4/2 人工智能 25 例 （ 6） S0 (3,3,1) S18 (3,1,0) p02 q02 S17 (3,2,0) p01 q01 S21 (2,2,0) p11 q11 S1 (3,2,1) q01 p01 p10 q10 S19 (3,0,0) q02 p02 S2 (3,1,1) q01 p01 S26 (1,1,0) q20 p20 S31 (0,0,0) q11 p11 S14 (0,1,1) p01 q01 p02 q02 S10 (1,1,1) p10 q10 S13 (0,2,1) q01 p01 S30 (0,1,0) p02 q02 S12 (0,3,1) p01 q01 S29 (0,2,0) p20 q20 S5 (2,2,1) q11 p11 ： 四條 S0到 S31長度相等的最短路徑，對應(yīng)的操作序列就是該問題的四個(gè)最優(yōu)解 2023/4/2 人工智能 26 隱式狀態(tài)空間圖 ?顯式狀態(tài)空間圖： 表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱為 顯式狀態(tài)空間圖 ，或稱為 狀態(tài)空間圖的顯示表示 。 要求為該推銷商規(guī)劃一條最短的旅行路線 。 （ 1） 有關(guān)狀態(tài)的知識： 用二元組 （ SA， SB） 表示狀態(tài) ， SA表示 A所在桿號 ， SB表示B所在桿號 。通過將 OPEN表設(shè)計(jì)為一個(gè)隊(duì)列來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在 OPEN表的后面，保證先生成的節(jié)點(diǎn)先考察 。 2023/4/2 人工智