【正文】 配置（ 333）。 它能有效地說明如何由問題歸約法求得問題的解答。應(yīng)用一系列相似的推理，子問題 1和子問題 3也可被歸約為本原問題，如圖 。 ? 將原始難題歸約（簡化）為下列子難題：移動圓盤 A和 B至柱子 2的雙圓盤難題，如圖 (a)所示。因此，首先應(yīng)該把圓盤 A和 B移到柱子 2上。 問題歸約法 ? 解題過程： 將原始問題歸約為一個較簡單問題集合，要把所有圓盤都移至柱子 3，我們必須首先把圓盤 C移至柱子 3；而且在移動圓盤 C至柱子 3之前，要求柱子 3必須是空的。要求把所有圓盤都移到柱子 3上，每次只許移動一個，而且只能先搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。在每個圓盤的中心有一個孔，所以圓盤可以堆疊在柱子上。 ? 問題歸約的實質(zhì)：從目標 (要解決的問題 )出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。對該問題的某個具體子集的解答就意味著對原始問題的一個解答。現(xiàn)在有 3 ? 個適用的操作，即 goto(U)， ? pushbox(V)和 climbbox(若 U=b)。在這一表示中，目標 ? 狀態(tài)的集合可由任何最后元素為 1的 ? 表列來描述。 狀態(tài)空間法 ? 對于規(guī)則 (2)，只有當(dāng)算符 pushbox(V) ? 的先決條件，即猴子與箱子在同一位 ? 置上而且猴子不在箱頂上這些條件得 ? 到滿足時，算符 pushbox(V)才是適用 ? 的。 狀態(tài)空間法 ? 狀態(tài)圖示法 這個問題中的操作 (算符 )如下： (3) climbbox猴子爬上箱頂，即有 ? (W， 0， W， z) ?(W， 1， W， z) ()在應(yīng)用算符 climbbox時也必須注意到，猴子和箱子應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上 。 ? (2) pushbox(V)猴子把箱子推到水平位置 V，即有 ? (W， 0， W， z) ?(V， 0， V， z) () ? 應(yīng)當(dāng)注意的是，要應(yīng)用算符 pushbox(V)， 就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。那么這只猴子怎樣才能摘到香蕉呢 ?圖 、香蕉和箱子在房間內(nèi)的相對位置。 推銷員旅行問題 ? 總數(shù)據(jù)庫：到目前為止所訪問的城市； ? 規(guī)則對應(yīng)于決策：即下一步走向城市Ａ，下一步走向城市Ｂ， … ，下一步走向城市Ｅ，一條規(guī)則必須能把某個數(shù)據(jù)庫變?yōu)橐粋€合法數(shù)據(jù)庫，否則不適應(yīng)這個數(shù)據(jù)庫； ? 任一以Ａ為起點和終點，并出現(xiàn)所有其它城市的總數(shù)據(jù)庫，都滿足終止條件． 狀態(tài)空間法 ? 狀態(tài)圖示法 例 2 猴子和香蕉問題 (monkey and banana problem) 在一個房間內(nèi)有一只猴子 (可把這只猴子看做一個機器人 )、一個箱子和一束香蕉。 一個控制策略 ：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時，就停止計算。用規(guī)則來改變數(shù)據(jù)庫就象用算符來改變狀態(tài)一樣。 一套規(guī)則 ：它對數(shù)據(jù)庫進行操作運算。 一個總數(shù)據(jù)庫 (global database)：它含有與具體任務(wù)有關(guān)的信息；隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能小得像數(shù)字矩陣那樣簡單，或許大得如檢索文件結(jié)構(gòu)那么復(fù)雜。 ? 各種問題都可以用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來求解。許多似乎很難的問題，當(dāng)表示適當(dāng)時就可能具有小而簡單的狀態(tài)空間。 ? 問題的表示對求解工作量有很大的影響。 此外，引入后繼節(jié)點算符的概念是方便的。 狀態(tài)空間法 ? 狀態(tài)圖示法 ? 一個圖可由顯式說明也可由隱式說明。 隱式表示 ：節(jié)點的無限集合 {si}作為起始節(jié)點是已知的。 顯式表示 ：各節(jié)點及其具有代價的弧線由一張表明確給出。 ? 代價 ：用 c(ni,nj)來表示從節(jié)點 ni指向節(jié)點 nj的那段弧線的代價。 后繼節(jié)點 (descendant node)與 父輩節(jié)點 (parent node)：如果某條弧線從節(jié)點 ni指向節(jié)點 nj，那么節(jié)點 nj就叫做節(jié)點 ni的后繼節(jié)點或后裔，而節(jié)點 ni叫做節(jié)點 nj的父輩節(jié)點或祖先。 狀態(tài)空間法 ? 狀態(tài)圖示法 為 了對狀態(tài)空間圖有更深入的了解，這里介紹一下圖論中的幾個術(shù)語和圖的正式表示法。對于最優(yōu)化問題找到任一目標狀態(tài)是不夠的，必須按某個準則實現(xiàn)最優(yōu)化路徑。 狀態(tài)空間法 ? ? 狀態(tài)空間法：從某個初始狀態(tài)開始，每次加一個操作符，遞增的建立起操作符的試驗序列，直到達到目標狀態(tài)為止。圖中繪出了兩種棋局，即初始棋局和目標棋局，它們對應(yīng)于該下棋問題的初始狀態(tài)和目標狀態(tài)。由 15個編有 1至 15并放在 4 4方格棋盤上的可走動的棋子組成?？砂褷顟B(tài)空間記為三元狀態(tài) (S， F， G)。操 作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運算符號或邏輯符號等。 (1)狀態(tài)（ state） (2)算符（ operator） (3)狀態(tài)空間方法 狀態(tài)空間法 問題狀態(tài)描述 狀態(tài) (state)：為描述某類不同事物間的差別而引入的一組最少變量 q0， q1， ? ， qn的有序集合，其矢量形式如下： Q=[q0,q1,?,q n]T 式中每個元素 qi(i=0,1,n)為集合的分量 ,稱為狀態(tài)變量 ,給定每個分量的一 組值就得到一個具體的狀態(tài) ,如 Qk=[q0k,q1k,?,q nk]T 式中每個元素 qi(i=0,1， ? ， n)為集合的分量，稱為狀態(tài)變量。 ? 狀態(tài)空間法 ：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。 ? 在分析了人工智能研究中運用的問題求解方法之后，就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。包括怎樣使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序結(jié)構(gòu)等知識。 ? 控制 有關(guān)問題的求解步驟、技巧性知識，告訴怎么做一件事。如雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的。 人工智能系統(tǒng)所關(guān)心的知識 ? 事實 有關(guān)問題環(huán)境的一些事物的知識，常以“ ? 是 ? ”的形式出現(xiàn)。 知識表示的基本概念 ? 知識表示 ：研究用機器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。第二章 知識表示 本章主要討論知識表示問題，介紹 7種知識表示方法：狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法、框架表示、本體技術(shù)、過程表示。 掌握狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法的要點及其之間的關(guān)系，了解框架表示、本體技術(shù)、過程表示。 ? 知識表示可看成是一組描述事物的約定，以把人類知識表示成機器能處理的數(shù)據(jù)結(jié)構(gòu)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實、客觀事實等。 ? 規(guī)則 有關(guān)問題中與事物的行動、動作相聯(lián)系的因果關(guān)系知識，是動態(tài)的，常以“如果 ? 那么 ? ”形式出現(xiàn)。 ? 元知識 有關(guān)知識的知識，是知識庫中的高層知識。 狀態(tài)空間法 ? 問題求解 ? 問題求解 (problem solving)是個大課題，它涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關(guān)過程的核心概念。也就是說，這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。 狀態(tài)空間法 (1) 問題的表示：如果描述方法不對，對問題求解會帶來很大的困難； (2) 求解的方法：采用試探搜索方法。 算符 ：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。 問題的狀態(tài)空間 (state space)：是一個表示該問題全部可能狀態(tài)及其關(guān)系 的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合 S、操作符 集合 F以及目標狀態(tài)集合 G。 狀態(tài)空間法 ? 讓我們先用數(shù)碼難題 (puzzle problem)來說明狀態(tài)空間表示的概念。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進空格，這也可以理解為移動空格。 如何把初始棋局變換為目標棋局呢？問題的解答就是某個合適的棋子走步序列，如 左移棋子 12，下移棋子 15，右移棋子 4， … 等等。 ? 尋找狀態(tài)空間的全部過程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及此后檢驗這些新的狀態(tài)描述，看是否達到了該目標狀態(tài)。 P26 ? 完成目標狀態(tài)的三件事： ? １狀態(tài)描述方式，特別是初始狀態(tài)描述； ? ２操作符集合及其對狀態(tài)描述的作用； ? ３目標狀態(tài)的特性。 節(jié)點 (node)： 圖形上的匯合點，用來表示狀態(tài)、事件和時間關(guān)系的匯合，也可用來指示通路的匯合； 弧線 (arc)： 節(jié)點間的連接線； 有向圖 (directed graph)： 一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。 狀態(tài)空間法 ? 狀態(tài)圖示法 路徑 ：某個節(jié)點序列 (ni1,ni2,…,n ik)當(dāng) j=2， 3， … ， k時，如果對于每一個 ni，j1都有一個后繼節(jié)點 nij存在，那么就把這個節(jié)點序列叫做從節(jié)點 ni1至節(jié)點nik的長度為 k的路徑。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連接弧線的代價。后繼節(jié)點算符 Γ 也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價。顯然，顯式說明對于大型的圖是不切實際的，而對于具有無限節(jié)點集合的圖則是不可能的。后繼節(jié)點算符 Γ 也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價把后繼算符應(yīng)用于 {si}的成員和它們的后繼節(jié)點以及這些后繼節(jié)點的后繼節(jié)點，如此無限制地進行下去，最后使得由 Γ 和 {si}所規(guī)定的隱式圖變?yōu)轱@示圖。人們顯然希望有較小的狀態(tài)空間表示。 狀態(tài)空間法 ? 狀態(tài)圖示法 ? 根據(jù)問題狀態(tài)、操作符和目標條件選擇各種表示，是高效率問題求解必須的。 狀態(tài)空間法 ? 狀態(tài)圖示法 （ Production System） ? ? 每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時所完成的動作。 ? 控制策略由控制系統(tǒng)選擇和確定。香蕉掛在天花板下方，但猴子的高度不足以碰到它。 ? 猴子和香蕉 ... 用一個四元表列 (W,X,Y,Z)來表示這個問題 ? 的狀態(tài)， 其中 W－猴子的水平位置 X－當(dāng)猴子在箱子頂上時取 X=1；否則取 X=0