人工智能課件2

人工智能及其應用第二章知識表示與推理人工智能及其應用第二章知識表示與推理目錄知識表示的一般方法圖搜索策略一般搜索與推理技術A*算法消解原理規(guī)則演繹系統(tǒng)產(chǎn)生式系統(tǒng)系統(tǒng)組織技術目錄知識表示的一般方法2.1知識表示的一般方法每種以符號和邏輯為基礎的智能系統(tǒng)，其問題求解方法都需要某種對解答的搜索。在搜索之前，必須先用某種方法或某幾種方法的混合來表示問題。對同一問題可以有不同的表示方法，問題表示的優(yōu)劣，對求解結果及求解工程量的影響甚大。問題求解大多采用試控搜索的方法，即通過在某個可能的解空間內(nèi)尋找一個解來求解問題。使用行之有效的知識表示方法解決所面臨的問題。2.1知識表示的一般方法每種以符號和邏輯為基礎的智能系統(tǒng)，2.1.1

狀態(tài)空間法一種基于解答空間的問題表示和求解方法，是以狀態(tài)和操作符為基礎的。方法：從某個初始狀態(tài)開始，每次加一個操作符，遞增地建立起操作符的試驗序列，直到達到目標狀態(tài)為止。由于狀態(tài)空間法需要擴展過多的節(jié)點，容易出現(xiàn)“組合爆炸”，因而只適用于表示比較簡單的問題。2.1.1狀態(tài)空間法一種基于解答空間的問題表示和求解方法，2.1.1狀態(tài)空間法狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。矢量形式：式中每個元素為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài)，如：操作符：使問題從一種狀態(tài)描述變化為另一種狀態(tài)描述的運算。操作符可為走步、過程、規(guī)則、數(shù)學算子、運算符號或邏輯符號等。2.1.1狀態(tài)空間法狀態(tài)：描述某類不同事物間的差別而引入的2.1.1狀態(tài)空間法三數(shù)碼難題（3PuzzleProblem）2.1.1狀態(tài)空間法三數(shù)碼難題（3PuzzleProbl2.1.1狀態(tài)空間法對一個問題的狀態(tài)描述，必須確定

3

件事：1.該狀態(tài)描述的方式，特別是初始狀態(tài)描述；2.算符集合及其對狀態(tài)描述的作用；3.目標狀態(tài)描述的特性。2.1.1狀態(tài)空間法對一個問題的狀態(tài)描述，必須確定3件事2.1.1狀態(tài)空間法狀態(tài)圖示法：是一個表示該問題全部可能狀態(tài)及其關系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。S：

初始狀態(tài)集合；F：

操作符集合；G：目標狀態(tài)集合。2.1.1狀態(tài)空間法狀態(tài)圖示法：是一個表示該問題全部可能狀2.1.1狀態(tài)空間法有向圖

(directedgraph)圖：由節(jié)點（不一定是有限的節(jié)點）的集合構成。有向圖：是指圖中的一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。路徑某個節(jié)點序列（）當j=2，3，……，k時，如果對于每一個都有一個后繼節(jié)點存在，那么就把這個節(jié)點序列叫做從節(jié)點至節(jié)點

的長度為k的路徑。2.1.1狀態(tài)空間法有向圖(directedgraph)2.1.1狀態(tài)空間法尋求一種狀態(tài)變換為另一種狀態(tài)的某個算符序列問題等價于尋求圖的某一路徑問題。代價從節(jié)點指向節(jié)點的那段弧線的指定數(shù)值/費用。用表示。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。最優(yōu)化問題，即找到兩節(jié)點間具有最小代價的路徑。2.1.1狀態(tài)空間法尋求一種狀態(tài)變換為另一種狀態(tài)的某個算符序2.1.1狀態(tài)空間法問題求解：即求某指定節(jié)點S（初始狀態(tài)）與另一節(jié)點T（目標狀態(tài)）之間的一條路徑。求得節(jié)點S與節(jié)點集合中任一節(jié)點之間的距離。求得節(jié)點集合中任一節(jié)點與節(jié)點集合中任一節(jié)點之間的路徑。112.1.1狀態(tài)空間法問題求解：即求某指定節(jié)點S（初始狀態(tài)）與2.1.1狀態(tài)空間法猴子和香蕉問題2.1.1狀態(tài)空間法猴子和香蕉問題2.1.1狀態(tài)空間法用一個四元表列（W，x，Y，z））來表示問題狀態(tài)。操作（算符）：1.goto（U）表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為:2.pushbox（V）猴子把箱子推到水平位置V，即有:2.1.1狀態(tài)空間法用一個四元表列（W，x，Y，z））來表示2.1.1狀態(tài)空間法3.climbbox猴子爬上箱頂，即有：4.grasp猴子摘到香蕉，即有：該初始狀態(tài)變換為目標狀態(tài)的操作序列為：

{goto(b),pushbox(c),climbbox,grasp}2.1.1狀態(tài)空間法3.climbbox猴子爬上箱頂，即有：人工智能課件22.1.2問題歸約法從目標（要解決的問題）出發(fā)，逆向推理，通過一系列變化把初始問題變換為子問題集合和子子問題集合，直至最后歸約為一個平凡的本原問題集合。這些本原問題的解可以直接得到，從而解決了初始問題。比狀態(tài)空間法更有效地表示問題。狀態(tài)空間法是問題歸約法的一種特例。問題歸約法的與或圖中包含與節(jié)點和或節(jié)點，而狀態(tài)空間法的狀態(tài)圖示法只含有或節(jié)點。2.1.2問題歸約法從目標（要解決的問題）出發(fā)，逆向推理2.1.2問題歸約法2.1.2問題歸約法2.1.2問題歸約法梵塔難題把所有的圓盤都移動到柱子3上。每次只能移動一個圓盤。只能先搬動柱子頂部的圓盤。不允許把較大的圓盤放在較小的圓盤上。2.1.2問題歸約法梵塔難題2.1.2問題歸約法2.1.2問題歸約法2.1.2問題歸約法原始的樊塔問題歸約為一個較為簡單的問題集合，其方法之一為：要把所有圓盤都移至柱子3，首先需把圓盤C移至柱子3，而且在移動圓盤C至柱子3之前，柱子3必須是空的。需把圓盤A和B移動至柱子2之后，才能移動圓盤C。把圓盤C從柱子1移至柱子3，并繼續(xù)解決難題的其余部分。2.1.2問題歸約法原始的樊塔問題歸約為一個較為簡單的問題2.1.2問題歸約法把原始難題歸約（簡化）為下列三個子難題移動圓盤A和B至柱子2的雙圓盤難題移動圓盤C至柱子3的單圓盤難題（本原問題）移動圓盤A和B至柱子3的雙圓盤難題2.1.2問題歸約法把原始難題歸約（簡化）為下列三個子難題2.1.2問題歸約法與或圖2.1.2問題歸約法與或圖2.1.2問題歸約法2.1.2問題歸約法2.1.2問題歸約法父節(jié)點，一個初始問題或是可分解為子問題的問題節(jié)點；子節(jié)點，一個初始問題或是子問題分解的子問題節(jié)點；或節(jié)點，只要解決某個問題就可解決其父輩問題的節(jié)點集合；與節(jié)點，只有解決所有子問題，才能解決其父輩問題的節(jié)點集合；弧線，是父輩節(jié)點指向子節(jié)點的圓弧連線；終葉節(jié)點，是對應于原問題的本原節(jié)點。2.1.2問題歸約法父節(jié)點，一個初始問題或是可分解為子問題的2.1.2問題歸約法可解節(jié)點1.終葉節(jié)點是可解節(jié)點（因為它們與本原問題相關連）。2.如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只有當其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。3.如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。不可解節(jié)點1.沒有后裔的非終葉節(jié)點為不可解節(jié)點。2.全部后裔為不可解的非終葉節(jié)點且含有為或后繼節(jié)點，此非終葉節(jié)點才是不可解的。3.后裔至少有一個為不可解的非終葉節(jié)點且含有與后繼節(jié)點，此非終葉節(jié)點才是不可解的。2.1.2問題歸約法可解節(jié)點2.1.2問題歸約法2.1.2問題歸約法2.1.2問題歸約法與或圖構成規(guī)則與或圖中所含起始節(jié)點對應于原始問題。終葉節(jié)點對應于本原問題的節(jié)點。將某一算符作用于問題A，其目的是把問題A變換為一個子問題集合；有向弧線自A指向后繼節(jié)點，表示所求得的子問題（或子問題集合）。一般對于代表兩個或兩個以上子問題集合的節(jié)點，有向弧線就需從此節(jié)點指向此子問題集合中的每個節(jié)點。2.1.2問題歸約法與或圖構成規(guī)則2.1.2問題歸約法樊塔問題與或圖2.1.2問題歸約法樊塔問題與或圖2.1.2問題歸約法樊塔問題狀態(tài)空間法2.1.2問題歸約法樊塔問題狀態(tài)空間法2.1.2問題歸約法猴子和香蕉問題與或圖2.1.2問題歸約法猴子和香蕉問題與或圖2.1.2問題歸約法2.1.2問題歸約法2.1.3謂詞邏輯法一種形式語言，能夠把數(shù)學中的邏輯論證符號化。采用謂詞合式公式和一階謂詞演算把要解決的問題變?yōu)橐粋€有待證明的問題，然后采用消解定理和消解反演來證明一個新語句是從已知的正確語句導出的，從而證明這個新語句也是正確的。常與其他方法混合使用，表示比較復雜的問題。2.1.3謂詞邏輯法一種形式語言，能夠把數(shù)學中的邏輯論證符2.1.4語義網(wǎng)絡法一種結構化表示方法。由節(jié)點和弧線或鏈線組成。節(jié)點：表示物體、概念和狀態(tài)。弧線：表示節(jié)點間的關系。語義網(wǎng)絡的解答是一個經(jīng)過推理和匹配而得到的具有明確結果的新的語義網(wǎng)絡?？杀硎径嘣P系，擴展后可表示更復雜的問題。2.1.4語義網(wǎng)絡法一種結構化表示方法。2.1.5框架一種結構化表示方法。通常由指定事物各個方面的槽組成，每個槽擁有若干個側面，而每個側面又擁有若干個值。大多數(shù)實用系統(tǒng)必須同時使用許多框架，可聯(lián)成一個框架系統(tǒng)。劇本是框架的一種特殊形式，使用一組槽來描述事件的發(fā)生序列，特別適用于描述順序性動作或事件。2.1.5框架一種結構化表示方法。2.1.6過程一種知識的過程式表示方法。將某一有關問題領域知識與這些使用方法一起，隱式地表示為一個問題求解過程。用程序來描述問題，具有很高的問題求解效率。由于知識隱含在程序中難以操作，適用范圍較窄。2.1.6過程一種知識的過程式表示方法。2.2圖搜索策略搜索過程既是一個問題求解的過程。搜索過程可采用適當?shù)乃阉骷夹g，如各種規(guī)則、過程和算法等推理技術，力求找到問題的解答。圖搜索策略可看成是一種在圖中尋找路徑的方法。圖搜索策略最終生成一個明確的搜索圖（圖G）和搜索樹（G的一個子集T）。2.2圖搜索策略搜索過程既是一個問題求解的過程。2.2圖搜索策略從某王姓家族的四代中找王A的后代且其壽命為X=57的人。2.2圖搜索策略從某王姓家族的四代中找王A的后代且其壽命為2.2圖搜索策略建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN的未擴展節(jié)點表中。建立一個叫做CLOSED的已擴展節(jié)點表，其初始為空表。LOOP：若OPEN表是空表，則失敗退出。選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n。若n為一目標節(jié)點，則有解并成功退出，此解是搜索圖G中沿著指針從n到S這條路徑而得到（指針將在第7步中設置）。2.2圖搜索策略建立一個只含有起始節(jié)點S的搜索圖G，把S2.2圖搜索策略擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。對那些未曾在G中出現(xiàn)過的（既未曾在OPEN表上或CLOSED表上出現(xiàn)過的）M成員設置一個通向n的指針，把M的這些成員加進OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。按某一任意方式或按某個探試值，重排OPEN表。GOLOOP

2.2圖搜索策略擴展節(jié)點n，同時生成不是n的祖先的那些后繼CLOSED中的節(jié)點是搜索樹中的非端節(jié)點OPEN中的節(jié)點是搜索樹上未被擴展的節(jié)點決定該過程是盲目搜索還是啟發(fā)式搜索CLOSED中的節(jié)點是搜索樹中的非端節(jié)點OPEN中的節(jié)點是搜2.2圖搜索策略將牌移入空格的順序：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標節(jié)點）。2.2圖搜索策略將牌移入空格的順序：人工智能課件22.3一般搜索與推理技術啟發(fā)式搜索：特點：運用啟發(fā)信息，引用某些準則或經(jīng)驗來重新排列OPEN表中節(jié)點的順序，使搜索沿著某個被認為最有希望的前沿區(qū)段擴展。關鍵點：正確選擇估價函數(shù)，以尋求最小代價路徑或解樹。方法：有序搜索（最好優(yōu)先搜索）最優(yōu)搜索A*算法AO*算法2.3一般搜索與推理技術啟發(fā)式搜索：2.3一般搜索與推理技術盲目搜索：“盲目”窮舉，不重排OPEN表寬度優(yōu)先搜索：搜索效率次之；深度優(yōu)先搜索：搜索效率較差；等代價搜索（有界深度優(yōu)先搜索）：具有一定的啟發(fā)性，搜索效率較高，但可能丟失某些解。2.3一般搜索與推理技術盲目搜索：“盲目”窮舉，不重排OP2.3一般搜索與推理技術高級求解系統(tǒng)規(guī)則演繹系統(tǒng)：采用if-then規(guī)則來求解問題。又分為正向、逆向和雙向規(guī)則演繹系統(tǒng)。產(chǎn)生式系統(tǒng)：由總數(shù)據(jù)庫、產(chǎn)生式規(guī)則和控制策略三部分組成，也分為正向、逆向和雙向推理三種形式。系統(tǒng)組織技術將一個大系統(tǒng)或復雜系統(tǒng)中的知識劃分為一組相對獨立的模塊，然后考慮各子模塊在求解時的合作問題。2.3一般搜索與推理技術高級求解系統(tǒng)2.4A*算法一種有序搜索算法，總是選擇估價函數(shù)值最小的節(jié)點作為擴展節(jié)點。定義：任一節(jié)點上函數(shù)值表示從節(jié)點S開始約束通過節(jié)點n的一條最佳路徑的代價。

表示從節(jié)點S到節(jié)點n的一條最佳路徑的實際代價。

表示從節(jié)點n到某目標節(jié)點的一條最佳路徑的代價。2.4A*算法一種有序搜索算法，總是選擇估價函數(shù)值最小的節(jié)2.4A*算法希望估價函數(shù)是的一個估計。是的估計，表示用搜索算法找到的從節(jié)點S到節(jié)點n的最小代價路徑，并且是的估計，依賴于有關問題領域的啟發(fā)信息，因此又叫做啟發(fā)函數(shù)。2.4A*算法希望估價函數(shù)是的一個估計。2.4A*算法2.4A*算法2.5消解原理采用謂詞演算方法求解問題時，首先把要解決的問題表示為一個待證明的問題，然后采用消解原理和消解反演過程來證明該問題。消解原理：采用推理規(guī)則進行正向搜索，最終證明該問題（定理）成立。消解反演過程：采用反演方法來證明某個定理的否定是不成立的，從而證明該定理必定是成立的。2.5消解原理采用謂詞演算方法求解問題時，首先把要解決的問2.6產(chǎn)生式系統(tǒng)由Post于1943年提出的產(chǎn)生式規(guī)則而得名。美國紐厄爾和西蒙于1965年利用這個原理建立了一個人類的認知模型。斯坦福大學利用產(chǎn)生式系統(tǒng)結構設計出第一個專家系統(tǒng)DENDRAL。2.6產(chǎn)生式系統(tǒng)由Post于1943年提出的產(chǎn)生式規(guī)則而得2.6產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念（產(chǎn)生式條件和操作對）為基礎的系統(tǒng)。產(chǎn)生式系統(tǒng)中，論域被分為2部分：用事實表示靜態(tài)知識，如事物、事件和它們之間的關系；用產(chǎn)生式規(guī)則表示推理過程和行為。求解效率低和無法表示結構性知識，不適用于求解復雜系統(tǒng)。2.6產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概2.6.1產(chǎn)生式系統(tǒng)組成總數(shù)據(jù)庫：綜合數(shù)據(jù)庫，用于存放求解過程中各種當前信息的數(shù)據(jù)結構，如問題的初始狀態(tài)、事實或證據(jù)、中間推理結論和最后結果等。產(chǎn)生式規(guī)則：一個規(guī)則庫，用于存放與求解問題有關的某個領域知識的規(guī)則之集合及其交換規(guī)則。控制策略：一個推理機構，由一組程序組成，用來控制產(chǎn)生式系統(tǒng)的運行，決定問題求解過程的推理線路，實現(xiàn)對問題的求解。2.6.1產(chǎn)生式系統(tǒng)組成總數(shù)據(jù)庫：綜合數(shù)據(jù)庫，用于存放求解2.6.1產(chǎn)生式系統(tǒng)組成產(chǎn)生式規(guī)則是一個以“如果滿足某個條件，就應當采取某些操作”形式表示的語句，其基本形式為：IF前提THEN 結論如：IF某種動物是哺乳動物，并且吃肉THEN 這種動物被稱為食肉動物條件、前項操作、后項2.6.1產(chǎn)生式系統(tǒng)組成產(chǎn)生式規(guī)則是一個以“如果滿足某個條2.6.1產(chǎn)生式系統(tǒng)組成在產(chǎn)生式系統(tǒng)的執(zhí)行過程中，如果某條規(guī)則的條件滿足了，則系統(tǒng)的控制部分就可以執(zhí)行規(guī)則的操作部分，并且其結論作為新的事實存入總數(shù)據(jù)庫。控制策略產(chǎn)生式規(guī)則總數(shù)據(jù)庫2.6.1產(chǎn)生式系統(tǒng)組成在產(chǎn)生式系統(tǒng)的執(zhí)行過程中，如果某條2.6.1產(chǎn)生式系統(tǒng)組成控制策略的作用是說明下一步應該選用什么規(guī)則，如何應用規(guī)則。從選擇規(guī)則到執(zhí)行操作分為三步：匹配：把當前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。沖突解決：當有一條以上規(guī)則的條件部分和當前數(shù)據(jù)庫相匹配時，需要決定首先使用哪一條規(guī)則。其策略包括：專一性排序、規(guī)則排序、數(shù)據(jù)排序、規(guī)模排序和就近排序等。操作：執(zhí)行規(guī)則的操作部分，經(jīng)過操作后，