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