【正文】 能 44 深度優(yōu)先搜索 (1) ?深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種一直向下的搜索過(guò)程，它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。 ?即使能求出解，它也不一定是最優(yōu)解。 步 5 若 N的深度 d（ N） ＞ dm（深度限制值）， 則標(biāo) N為待擴(kuò)展節(jié)點(diǎn)， 則轉(zhuǎn)步 2； 步 6 N無(wú)子節(jié)點(diǎn)，則轉(zhuǎn)步 2； 步 7 擴(kuò)展 N，將其所有子節(jié)點(diǎn) Ni配上指向 N的指針?lè)湃隣PEN首部 ， 置 d（ Ni ）＝ d（ N）＋ 1，轉(zhuǎn)步 2。 2023/4/2 人工智能 57 狀態(tài)空間圖的啟發(fā)式搜索 (3) 啟發(fā)式搜索算法 啟發(fā)式搜索的 A算法和 A*算法 A*算法在游戲中的應(yīng)用 2023/4/2 人工智能 58 啟發(fā)式搜索算法 （ 1） ?啟發(fā)式搜索 用啟發(fā)函數(shù)來(lái)導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再 增加啟發(fā)函數(shù)值 的 計(jì)算 與 傳播 過(guò)程，并且由 啟發(fā)函數(shù)值 來(lái) 確定 節(jié)點(diǎn)的 擴(kuò)展順序 。 2023/4/2 人工智能 63 啟發(fā)式搜索的 A算法和 A*算法（ 2） 1. A算法 估價(jià)函數(shù) f（ x） :為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途，將啟發(fā)函數(shù) h（ x）與代價(jià)函數(shù) g（ x）相結(jié)合，即初始節(jié)點(diǎn) S0到達(dá)節(jié)點(diǎn) x處已付出的 代價(jià)與 節(jié)點(diǎn) x 到達(dá)目標(biāo)節(jié)點(diǎn) Sg的 接近程度估計(jì)值總和 。 2）若 xi存在于 OPEN或 CLOSED表中，也 刪除 之，但表明此時(shí)存在兩條初始節(jié)點(diǎn) S0到 xi的路徑；如果 新路徑較 短 ，則 修改 xi節(jié)點(diǎn)的 返回指針 （指向 N），并修改 xi及其后裔節(jié)點(diǎn)和 f值；同時(shí)若 xi存在 于 CLOSED表中，則將其 移出放入 OPEN表 重新考察 。 Closed表中，說(shuō)明 P的后繼也在 n之前已經(jīng)生成，稱為Ps。 1 4 2 8 3 7 6 5 3 2 5 5 6 7 1 4 2 8 3 7 6 5 1 4 2 8 3 5 7 6 1 4 2 8 3 7 6 5 1 2 3 8 4 7 6 5 Sg 1 擴(kuò)展順序 f2(x)值 1 3 4 8 2 7 6 5 4 1 4 8 3 2 7 6 5 1 4 8 3 2 7 6 5 4 5 1 3 4 8 2 7 6 5 1 3 4 8 2 7 6 5 5 1 3 4 8 6 2 7 5 6 6 3 6 1 3 8 2 4 7 6 5 5 1 3 4 8 2 5 7 6 7 9 8 1 4 3 2 7 6 5 7 3 4 1 8 2 7 6 5 1 3 4 7 8 2 6 5 1 3 4 8 6 2 7 5 7 1 3 4 8 6 2 7 5 7 8 8 4 7 8 10 1 3 8 2 4 7 6 5 5 11 1 2 8 4 3 7 6 5 1 4 2 8 6 3 7 5 1 4 2 8 3 7 6 5 7 8 8 1 2 3 8 4 7 6 5 5 12 8 1 3 8 2 4 7 6 5 啟發(fā)式搜索的 A算法和 A*算法（ 15） 8 1 2 6 3 7 5 4 a 1 2 3 8 4 7 6 5 Sg 2 8 1 4 6 3 7 5 b 問(wèn)題 :是否對(duì)于所有的節(jié)點(diǎn) w(x)都能反映出從 x節(jié)點(diǎn) 變化到目標(biāo)節(jié)點(diǎn)的難易程度（到目標(biāo)的距離）？ w(a)=7 w(b)=6,從 w（ x）值看 a格局離目標(biāo)格局更遠(yuǎn)。 假定野人會(huì)服從任何一種過(guò)河安排，試規(guī)劃出一種確保修道士安全過(guò)河方案。船在右岸，需要一個(gè)人將船運(yùn)往左岸，因此，對(duì)于狀態(tài)（ m， c， 0），需要的擺渡數(shù)，相當(dāng)于船在左岸的（ m+1， c， 1）或（ m，c+1， 1），所以需要的最少擺渡數(shù)為： m+c+12+1=m+c ? 綜合條件，需要的最少擺渡數(shù)為 m+c2b。即一個(gè)問(wèn)題與一組子問(wèn)題的 與等價(jià) 。原來(lái)問(wèn)題可以分解為兩個(gè)子問(wèn)題： Q1：證明 Δ ABC ≌ Δ A′B′C′ Q2：證明 Δ BCD ≌ Δ B′C′D′ 原來(lái)問(wèn)題可以 分為兩個(gè)子問(wèn)題解決。 ：證明 BD＝ B′D ′ 問(wèn)題 Q2還可以再被分解為： Q21 ：證明 BC＝ B′C′ Q22 ：證明 CD＝ C′D′ Q23 ：證明 ∠ C＝ ∠ C ′ 或 Q21 180。 Q22 39。 ? 子節(jié)點(diǎn)為與關(guān)系，則該節(jié)點(diǎn)為 與節(jié)點(diǎn) 。 與或圖表示（ 10） 四邊形相等問(wèn)題分解樹(shù)： 1Q2Q1 1Q1 2Q1 3Q2 1Q2 2Q2 32023/4/2 人工智能 106 2023/4/2 人工智能 107 與或樹(shù)的盲目搜索（ 1） 與或樹(shù)搜索與狀態(tài)樹(shù)搜索的不同之處在于： （ 1）搜索過(guò)程中包含可解性標(biāo)記過(guò)程 。 ? 本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)稱為 終止節(jié)點(diǎn) 。 Q13 39。 ：證明 AB＝ A′B′ Q12 180。 分析：連接 BD， B180。 當(dāng)然，考慮更多的因素一定會(huì)增加代價(jià)計(jì)算量，所以，在實(shí)際當(dāng)中，使用 A*算法進(jìn)行游戲設(shè)計(jì)時(shí)，還需要在獲得戰(zhàn)術(shù)能力和所付出的計(jì)算量之間做出權(quán)衡。 對(duì)狀態(tài)（ 1， 1， 1），啟發(fā)函數(shù) 2不滿足 h（ n） ≤h* （ n） 提示：不考慮限制條件的運(yùn)送次數(shù)一定小于有限制條 件的運(yùn)送次數(shù)。 啟發(fā)式搜索的 A算法和 A*算法（ 23） 例 修道士和野人問(wèn)題。 估價(jià)函數(shù)定義探討 2023/4/2 人工智能 72 啟發(fā)式搜索的 A算法和 A*算法（ 12） 2023/4/2 人工智能 73 1 4 8 3 2 7 6 5 S0 1 2 3 8 4 7 6 5 Sg 估價(jià)函數(shù) f（ x）＝ g（ x）＋ h（ x） 因素 1 格局中將牌是否在家 g(x)用節(jié)點(diǎn)深度 d（ x）來(lái)衡量 如何定義？ h（ x）用 x的格局與目標(biāo)節(jié)點(diǎn)格局相比，不在家的 將牌數(shù)目 w(x)來(lái)衡量。 2023/4/2 人工智能 70 啟發(fā)式搜索的 A算法和 A*算法（ 10） ? 對(duì) 已存在于 CLOSED表的節(jié)點(diǎn) ，作與（ 2）同樣的處理，并將其移出 CLOSED表，放入 OPEN表中重新擴(kuò)展。 2023/4/2 人工智能 65 2023/4/2 人工智能 66 啟發(fā)式搜索的 A算法和 A*算法（ 5） 步 1 把附有 f（ S0 ） 的初始節(jié)點(diǎn) S0放入 OPEN表中； 步 2 若 OPEN表為空，則搜索失敗，退出； 步 3 否則，移出 OPEN表中第一個(gè)節(jié)點(diǎn) N放入 CLOSED表中，并冠以順序編號(hào) n； 步 4 若目標(biāo)節(jié)點(diǎn) Sg＝ N，則搜索成功，利用 CLOSED表中的返回指針找出 S0到 N的路徑即為所求解，退出。 在很多實(shí)際問(wèn)題中，已經(jīng)付出的實(shí)際代價(jià)是必須考慮的，如 TSP問(wèn)題等。 2023/4/2 人工智能 55 2023/4/2 人工智能 56 狀態(tài)空間圖的啟發(fā)式搜索 (2) 在實(shí)際設(shè)計(jì)過(guò)程中， 啟發(fā)函數(shù)是用來(lái)估計(jì)搜索樹(shù)節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為 h（ x） 。 ② 若有，則取出 CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到 OPEN表中，令 dm=dm+⊿ d。如下圖所示： S0S g 1圖 213 深度優(yōu)先搜索不具有完備性示意圖 2023/4/2 人工智能 47 （ Acd ） 為克服深度優(yōu)先搜索的不足，可以對(duì)其深度進(jìn)行限制 ?深度界限的選擇很重要 dm 若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效率。 ?廣度優(yōu)先搜索策略與問(wèn)題無(wú)關(guān)，具有通用性。CLOSED表中存放的就是一定搜索策略下的搜索樹(shù)。 2023/4/2 人工智能 32 補(bǔ)充例 二階梵塔問(wèn)題（ 1） 有三個(gè)桿，一號(hào)桿有 A、 B兩個(gè)金盤(pán)， A小于 B。類(lèi)似于這樣表示的狀態(tài)圖稱為 隱式狀態(tài)圖 ，或者說(shuō) 狀態(tài)圖 的 隱式表示 。 假定野人會(huì)服從任何一種過(guò)河安排，試規(guī)劃出一種確保修道士安全過(guò)河方案。 ? 狀態(tài)空間的解為三元組 Qs, a, Qg ? Qs ：某個(gè)初始狀態(tài) ? Qg ：某個(gè)目標(biāo)狀態(tài) ? a：把 Qs變換成 Qg的有限的操作序列 ? 狀態(tài)轉(zhuǎn)換圖 S1 S3 S2 … f1 f2 f3 f4 Qs Qg fn 2023/4/2 人工智能 16 2023/4/2 人工智能 17 例 翻轉(zhuǎn)錢(qián)幣問(wèn)題（ 1） 三枚錢(qián)幣處于反、正、反狀態(tài)，每次只許翻動(dòng)一枚錢(qián)幣，問(wèn)連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正或全反狀態(tài)。 ?操作的表示形式可以是一個(gè)機(jī)械性的步驟、過(guò)程、規(guī)則或算子。 ?啟發(fā)式搜索 ：利用 “啟發(fā)性信息 ”作為 導(dǎo)航 的搜索過(guò)程。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識(shí)表示 (1) ?知識(shí)表示： 就是研究 在計(jì)算機(jī)中 如何用最合適的形式 表示 問(wèn)題求解過(guò)程中所需要的各種知識(shí)，包括構(gòu)成問(wèn)題求解框架的全部知識(shí)。 知識(shí)與問(wèn)題求解框架 (2) （ 1）從應(yīng)用領(lǐng)域來(lái)劃分 ? 常識(shí)性知識(shí) ? 領(lǐng)域（專業(yè)）性知識(shí) （ 2）從在問(wèn)題求解中的作用來(lái)劃分 ? 敘述性知識(shí) ? 過(guò)程性知識(shí) ? 控制性知識(shí) （ 3）從確定性來(lái)劃分 ? 確定性知識(shí) ? 非確定性知識(shí) （ 4）從知識(shí)的表現(xiàn)形式來(lái)劃分，可分為文字、符號(hào)、聲音、圖形、圖像等。 概括地說(shuō)，知識(shí)是高度組織起來(lái)的信息集團(tuán)，是人們?cè)陂L(zhǎng)期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來(lái)的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。 （ 3） 控制性知識(shí)： 描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識(shí)。 ?盲目搜索 ： 無(wú)向?qū)?的 搜索 ，也稱窮舉搜索。 ?描述一個(gè)操作要包含兩個(gè)部分 ? 條件 :指明被作用的狀態(tài)要滿足的約束條件 ? 動(dòng)作 :指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問(wèn)題求解過(guò)程轉(zhuǎn)化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達(dá) 目標(biāo)狀態(tài) Qg的 路徑 問(wèn)題，也就是尋找操作序列的問(wèn)題。 翻動(dòng)錢(qián)幣的操作抽象為改變上述狀態(tài)的算子 ， 即 F＝ {a, b, c} a:把錢(qián)幣 q0翻轉(zhuǎn)一次 b:把錢(qián)幣 q1翻轉(zhuǎn)一次 c:把錢(qián)幣 q2翻轉(zhuǎn)一次 問(wèn)題的狀態(tài)空間為 {Q5}, {a, b, c}， {Q0 Q7} 2023/4/2 人工智能 18 例 翻轉(zhuǎn)錢(qián)幣問(wèn)題（ 4） 問(wèn)題的狀態(tài)空間為： 2023/4/2 人工智能 19 構(gòu)造狀態(tài)空間圖： 5 0 7{ } { } { }Q a b c Q Q??， ， ， ， ，cbbcQ1aQs= Q5bQ7= Qg 2aQ3cQ2aQ6baQ4Q0 = Qg 1c( 0 , 0 , 0 ) ( 1 , 0 , 0 )( 0 , 0 , 1 )( 1 , 0 , 1 )( 1 , 1 , 1 ) ( 0 , 1 , 1 )( 1 , 1 , 0 )( 0 , 1 , 0 )aab aba baa bbb