【正文】 第 2章 基于圖的知識(shí)表示與圖搜索技術(shù) 2023/4/2 人工智能 2 第 2章 基于圖的知識(shí)表示與圖搜索技術(shù) 概述 狀態(tài)空間圖表示 狀態(tài)空間圖的盲目搜索 狀態(tài)空間圖的啟發(fā)式搜索 與或圖表示及搜索技術(shù) 博弈樹及搜索技術(shù) 2023/4/2 人工智能 3 概述 知識(shí)與問題求解框架 知識(shí)表示 圖搜索技術(shù) 2023/4/2 人工智能 4 知識(shí)與問題求解框架 (1) ? 心理學(xué) ：個(gè)體通過與環(huán)境相互作用后獲得的信息及其組織。 ? 費(fèi)根鮑姆 ：知識(shí)是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。 ? 博恩斯坦 （ Bernstein） ：知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過程組成的。 概括地說，知識(shí)是高度組織起來的信息集團(tuán)，是人們?cè)陂L(zhǎng)期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。 知識(shí)與問題求解框架 (2) （ 1）從應(yīng)用領(lǐng)域來劃分 ? 常識(shí)性知識(shí) ? 領(lǐng)域（專業(yè)）性知識(shí) （ 2）從在問題求解中的作用來劃分 ? 敘述性知識(shí) ? 過程性知識(shí) ? 控制性知識(shí) （ 3）從確定性來劃分 ? 確定性知識(shí) ? 非確定性知識(shí) （ 4）從知識(shí)的表現(xiàn)形式來劃分，可分為文字、符號(hào)、聲音、圖形、圖像等。 2023/4/2 人工智能 5 知識(shí)與問題求解框架 (3) ?問題： 是指事件或事物的已知或 當(dāng)前狀態(tài) 與 目標(biāo)狀態(tài) 之間有 差異。 ?問題求解： 是指在一定的控制策略下， 通過 一系列的 操作 或 運(yùn)算來 改變 問題的 狀態(tài) ，使之與目標(biāo)狀態(tài)接近或一致。 例如，李明在北京，他要去西安（辦事）。 又如，博弈問題。 ?問題的求解框架 （ 1） 敘述性知識(shí)： 描述問題的狀態(tài)有關(guān)的各種知識(shí)。 （ 2） 過程性知識(shí)： 描述狀態(tài)之間的變換關(guān)系的各種知識(shí)。 （ 3） 控制性知識(shí)： 描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識(shí)。 2023/4/2 人工智能 6 2023/4/2 人工智能 7 知識(shí)表示 (1) ?知識(shí)表示： 就是研究 在計(jì)算機(jī)中 如何用最合適的形式 表示 問題求解過程中所需要的各種知識(shí)，包括構(gòu)成問題求解框架的全部知識(shí)。 ?常用的知識(shí)表示形式 ? 狀態(tài)空間圖 ? 與或圖 ? 謂詞邏輯 ? 產(chǎn)生式 ? 框架 ? 語(yǔ)義網(wǎng)絡(luò) ? …… 知識(shí)表示 (2) 2023/4/2 人工智能 8 例 。 在一個(gè) 2n?2n的方格棋盤中，去掉對(duì)角的兩個(gè)方格，如圖（ a），問能否將它全部劃成若干 1?2的小長(zhǎng)方塊？ 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) 搜索，簡(jiǎn)單地說就是 “尋找 ”，目的是找到問題的解。在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是 從 圖中 初始節(jié)點(diǎn) 出發(fā)，沿著與之相連的邊 試探著 前進(jìn)， 尋找目標(biāo)節(jié)點(diǎn) 或 可解節(jié)點(diǎn) 的過程。 搜索過程中 經(jīng)過 （考察過） 的節(jié)點(diǎn)和邊 ，按原圖的連接關(guān)系，便會(huì) 構(gòu)成 一個(gè) 樹型 的有 向圖 ，稱為搜索樹。搜索樹是一個(gè)搜索過程的搜索軌跡，或稱之為 搜索空間。 圖搜索技術(shù) (2) 2023/4/2 人工智能 10 SgSo問 題 全 狀 態(tài) 空 間搜 索 空 間解 路 徑圖 22搜索空間示意圖 問題的狀態(tài)空間、搜索空間及解的示意圖： 圖搜索技術(shù) (3) 搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。 ?盲目搜索 ： 無向?qū)?的 搜索 ，也稱窮舉搜索。 ?啟發(fā)式搜索 ：利用 “啟發(fā)性信息 ”作為 導(dǎo)航 的搜索過程。 對(duì)于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所以在實(shí)際當(dāng)中往往是不可行的。啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。 2023/4/2 人工智能 11 2023/4/2 人工智能 12 狀態(tài)空間圖表示 狀態(tài)空間圖 隱式狀態(tài)空間圖 2023/4/2 人工智能 13 狀態(tài)空間圖（ 1） 狀態(tài)對(duì)應(yīng)敘述性知識(shí) ，描述一個(gè)問題在開始、結(jié)束或中間的某一時(shí)刻所處的 狀況 或 狀態(tài) 。通常引進(jìn)一組變量 ，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組 來表示狀態(tài)。 狀態(tài)在狀態(tài)圖中表示為 節(jié)點(diǎn) 。 12 nq q q， ， ，12()nq q q， ， ，2023/4/2 人工智能 14 狀態(tài)空間圖（ 2） 操作對(duì)應(yīng)過程性知識(shí) ，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。 ?描述一個(gè)操作要包含兩個(gè)部分 ? 條件 :指明被作用的狀態(tài)要滿足的約束條件 ? 動(dòng)作 :指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。 ?操作的表示形式可以是一個(gè)機(jī)械性的步驟、過程、規(guī)則或算子。 ?操作在狀態(tài)圖中表示為 邊 。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對(duì)、條件語(yǔ)句、規(guī)則、函數(shù)、過程等表示。 如：如果室內(nèi)溫度低于 26度，則關(guān)閉空調(diào)。 2023/4/2 人工智能 15 狀態(tài)空間圖（ 3） ?問題的 狀態(tài)空間圖 是一個(gè)描述該問題全部可能的 狀態(tài) 及相互 關(guān)系 的 圖 ，如考慮操作的代價(jià)，狀態(tài)空間圖就是一個(gè) 賦值有向圖 。 ?狀態(tài)空間常記為三元組： S： 初始狀態(tài)的集合 F： 操作的集合 G： 目標(biāo)狀態(tài)的集合。 ?由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。 S F G??， ， 狀態(tài)空間圖（ 4） ? 在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找 從初始狀態(tài) Qs出發(fā) 到達(dá) 目標(biāo)狀態(tài) Qg的 路徑 問題，也就是尋找操作序列的問題。 ? 狀態(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)錢幣問題（ 1） 三枚錢幣處于反、正、反狀態(tài)，每次只許翻動(dòng)一枚錢幣，問連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正或全反狀態(tài)。 初始狀態(tài) Qs 目標(biāo)狀態(tài)集合 {Q0, Q7} 例 翻轉(zhuǎn)錢幣問題（ 2） 引入一個(gè)三元組 (q0,q1,q2)來描述總狀態(tài) ， 錢幣正面為 0， 反面為 1， 全部可能的狀態(tài)為： Q0=(0,0,0) 。 Q1=(0,0,1)。 Q2=(0,1,0) Q3=(0,1,1) 。 Q4=(1,0,0)。 Q5=(1,0,1) Q6=(1,1,0) 。 Q7=(1,1,1)。 翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子 ， 即 F＝ {a, b, c} a:把錢幣 q0翻轉(zhuǎn)一次 b:把錢幣 q1翻轉(zhuǎn)一次 c:把錢幣 q2翻轉(zhuǎn)一次 問題的狀態(tài)空間為 {Q5}, {a, b, c}， {Q0 Q7} 2023/4/2 人工智能 18 例 翻轉(zhuǎn)錢幣問題（ 4） 問題的狀態(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 bcc cbc ccb 2023/4/2 人工智能 20 例 （ 1） 在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條件的限制： （ 1）修道士和野人都會(huì)劃船，但船一次 最多 只能 運(yùn)兩個(gè)人 ； （ 2）在任何岸邊 野人數(shù)目 都 不得超過修道士 ，否則修道士就會(huì)被野人吃掉。 假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。 2023/4/2 人工智能 21 例 （ 2） 問題的狀態(tài) 可以用一個(gè)三元數(shù)組來描述： S＝ (m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 右岸的狀態(tài)不必標(biāo)出，因?yàn)椋? 右岸的修道士數(shù) m’ ＝ 3－ m 右岸的野人數(shù) c’ ＝ 3－ c 右岸的船數(shù) b’ ＝ 1－ b 2023/4/2 人工智能 22 例 （ 3） 狀態(tài) m, c, b 狀態(tài) m, c, b 狀態(tài) m, c, b 狀態(tài) m, c, b S0 3 3 1 S8 1 3 1 S16 3 3 0 S24 1 3 0 S1 3 2 1 S9 1 2 1 S17 3 2 0 S25 1 2 0 S2 3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0 S3 3 0 1 S11 1 0 1 S19 3 0 0 S27 1 0 0 S4 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0 S5 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0 S6 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0 S7 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0 2023/4/2 人工智能 23 例 （ 4） F＝ {p01, p10,p11,p02,p20,q01,q10,q11, q02,q20} q20 b=0, (m=0,c=2)或 (m=1,c=1) b=1, m=m+2 q02 b=0, m=0或 3, c≤ 2 b=1, c=c+2 q11 b=0, m=c, c≤ 2 b=1, m=m+1, c=c+1 q10 b=0, (m=0,c=1)或 (m=2,c=2) b=1, m=m+1 q01 b=0, m=0或 3, c≤ 2 b=1, c=c+1 p20 b=1, (m=3,c=1)或 (m=2,c=2) b=0, m=m2 p02 b=1, m=0或 3, c≥2 b=0, c=c2 p11 b=1, m=c, c≥1 b=0, m=m1, c=c1 p10 b=1, (m=3,c=2)或 (m=1,c=1) b=0, m=m1 p01 b=1, m=0或 3, c≥1 b=0, c=c1 操作符 條 件 動(dòng) 作 例 （ 5） 給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是：