知識表示3.狀態(tài)空間問題歸約表示法.pptVIP

2019/6/19,1,人工智能原理,第二講 知識表示 之 狀態(tài)空間/問題歸約表示,主講：王祖喜 華中科技大學(xué)圖像所,2019/6/19,2,知識的表示方法,謂詞邏輯法 狀態(tài)空間法 問題歸約法 語義網(wǎng)絡(luò)法 框架表示法 面向?qū)ο蟊硎?劇本(script)表示 過程(procedure)表示 小結(jié),2019/6/19,3,狀態(tài)空間法,問題求解(problem solving)是個大課題，它涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關(guān)過程的核心概念。在分析了人工智能研究中運(yùn)用的問題求解方法之后，就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。,2019/6/19,4,問題求解技術(shù)兩個主要的方面 問題的表示：如果描述方法不對，對問題求解會帶來很大的困難 求解的方法：采用試探搜索方法。,2019/6/19,5,狀態(tài)空間法三要點 狀態(tài)（state）：表示問題解法中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)； 算符（operator）：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段； 狀態(tài)空間方法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。,2019/6/19,6,1.問題狀態(tài)描述,要完成某個問題的狀態(tài)描述，必須確定三件事： 1.該狀態(tài)描述方式，特別是初始狀態(tài)描述； 2.操作符集合及其對狀態(tài)描述的作用； 3.目標(biāo)狀態(tài)描述的特性。,2019/6/19,7,定義 : 狀態(tài)(state)：為描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合，其矢量形式如下： 式中每個元素qi(i=0,1，n)為集合的分量，稱為狀態(tài)變量。,2019/6/19,8,給定每個變量的一組值就得到一個具體的狀態(tài)，如 Qk=q0k，q1k，. ，qnkT 它只是問題所有可能狀態(tài)的羅列，還必須描述這些狀態(tài)之間的可能變化。 所謂操作，或稱為算子是引起狀態(tài)中的某分量發(fā)生改變，從而使問題由一個具體狀態(tài)A變化為另一具體狀態(tài)B的作用。,2019/6/19,9,算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號或邏輯符號等。 問題的狀態(tài)空間(state space)：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S(初始狀態(tài)S0S)、操作符集合F以及目標(biāo)狀態(tài)集合G(GS)?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。 狀態(tài)空間可用有向圖來表示,2019/6/19,10,狀態(tài)空間的一個解 使一個有限的操作算子序列，它使初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)：S0-f1-S1-f2-.fk-G,2019/6/19,11,狀態(tài)空間表示詳釋,讓我們先用數(shù)碼難題(puzzle problem)來說明狀態(tài)空間表示的概念。由15個編有1至15并放在44方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進(jìn)空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即初始棋局和目標(biāo)棋局，它們對應(yīng)于該下棋問題的初始狀態(tài)和目標(biāo)狀態(tài)。 如何把初始棋局變換為目標(biāo)棋局呢？問題的解答就是某個合適的棋子走步序列，如“左移棋子12，下移棋子15，右移棋子4，“等等。,2019/6/19,12,（a）初始棋局 （b）目標(biāo)棋局 十五數(shù)碼難題,2019/6/19,13,總狀態(tài)為16!20922789888000 由于棋盤的對稱性，實際狀態(tài)數(shù)減半 上、下、左、右移動四種操作,2019/6/19,14,十五數(shù)碼難題最直接的求解方法是嘗試各種不同的走步，直到偶然得到該目標(biāo)棋局為止。這種嘗試本質(zhì)上涉及某種試探搜索。從初始棋局開始，試探(對于一般問題實際上是由計算機(jī)進(jìn)行計算和執(zhí)行的)由每一合法走步得到的各種新棋局，然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達(dá)到目標(biāo)棋局為止。把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間設(shè)想為一幅由各種狀態(tài)對應(yīng)的節(jié)點組成的圖。這種圖稱為狀態(tài)圖。圖中每個節(jié)點標(biāo)有它所代表的棋局。首先把適用的算符用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止。 部分狀態(tài)圖為：,2019/6/19,15,2019/6/19,16,我們一般用狀態(tài)空間法這一術(shù)語來表示下述方法： 從某個初始狀態(tài)開始，每次加一個操作符，遞增地建立起操作符的試驗序列，直到目標(biāo)狀態(tài)為止。 尋找狀態(tài)空間的全部過程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及此后檢驗這些新的狀態(tài)描述，看其是否描述了該目標(biāo)。這種檢驗往往只是查看某個狀態(tài)是否與給定的 目標(biāo)狀態(tài)描述相匹配。,2019/6/19,17,要完成某個問題的狀態(tài)描述，必須確定三件事： 1.該狀態(tài)描述方式，特別是初始狀態(tài)描述； 2.操作符集合及其對狀態(tài)描述的作用； 3.目標(biāo)狀態(tài)描述的特性。,2019/6/19,18,2.狀態(tài)圖示法,圖論中的幾個術(shù)語 節(jié)點(node)：圖形上的匯合點，用來表示狀態(tài)、事件和時 間關(guān)系的匯合，也可用來指示通路的匯合； 弧線(arc)：節(jié)點間的連接線； 有向圖(directed graph)：一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。,2019/6/19,19,后繼節(jié)點(descendant node)與父輩節(jié)點(parent node)：如果某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni的后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj的父輩節(jié)點或祖先。 路徑：某個節(jié)點序列(ni1,ni2,nik)當(dāng)j=2，3，k時，如果對于每一個ni,j-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。 代價：用c(ni,nj)來表示從節(jié)點ni指向節(jié)點nj的那段弧線的代價。,2019/6/19,20,如果從節(jié)點ni至節(jié)點nj存在有一條路徑，那么就稱節(jié)點nj 是從節(jié)點ni可達(dá)到的節(jié)點。 兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。最小者稱為最小代價的路徑。,2019/6/19,21,顯式表示：各節(jié)點及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連接弧線的代價。 隱式表示：節(jié)點的無限集合si作為起始節(jié)點是已知的。后繼節(jié)點算符也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價。,2019/6/19,22,圖的顯式和隱式表示,一個圖可由顯式說明也可由隱式說明。顯然，顯式說明對于大型的圖是不切實際的，而對于具有無限節(jié)點集合的圖則是不可能的。 此外，引入后繼節(jié)點算符的概念是方便的。后繼節(jié)點算符也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價(用我們的狀態(tài)空間術(shù)語來說，后繼算符是由適用于已知狀態(tài)描述的算符集合所確定的)。把后繼算符應(yīng)用于si的成員和它們的后繼節(jié)點以及這些后繼節(jié)點的后繼節(jié)點，如此無限制地進(jìn)行下去，最后使得由和si所規(guī)定的隱式圖變?yōu)轱@示圖。把后繼算符應(yīng)用于節(jié)點的過程，就是擴(kuò)展一個節(jié)點的過程。,2019/6/19,23,因此，搜索某個狀態(tài)空間以求得算符序列的一個解答的過程，就對應(yīng)于使隱式圖足夠大一部分變?yōu)轱@式以便包含目標(biāo)的過程。這樣的搜索圖是狀態(tài)空間問題求解的主要基礎(chǔ)。 問題的表示對求解工作量有很大的影響。人們顯然希望有較小的狀態(tài)空間表示。許多似乎很難的問題，當(dāng)表示適當(dāng)時就可能具有小而簡單的狀態(tài)空間。,2019/6/19,24,3.狀態(tài)空間表示舉例,各種問題都可用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來求解。 如果能夠用一種不同的表示方法來求解用一問題，也不必感到驚訝。 產(chǎn)生式系統(tǒng)（Production System） 是描述搜索過程的方法。,2019/6/19,25,一個產(chǎn)生式系統(tǒng)由下面三部分組成： 一個總數(shù)據(jù)庫(global database)：它含有與具體任務(wù)有關(guān)的信息；隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能小得像數(shù)字矩陣那樣簡單，或許大得如檢索文件結(jié)構(gòu)那么復(fù)雜。 一套規(guī)則：它對數(shù)據(jù)庫進(jìn)行操作運(yùn)算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時所完成的動作。應(yīng)用規(guī)則來改變數(shù)據(jù)庫，就象應(yīng)用算符來改變狀態(tài)一樣 一個控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時，就停止計算?？刂撇呗杂煽刂葡到y(tǒng)選擇和確定。,2019/6/19,26,狀態(tài)空間表示舉例,猴子和香蕉問題(monkey and banana problem) 在一個房間內(nèi)有一只猴子(可把這只猴子看做一個機(jī)器人)、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢?圖中表示出猴子、香蕉和箱子在房間內(nèi)的相對位置。,猴子和香蕉問題,2019/6/19,27,用一個四元表列(W,x,Y,z)來表示這個問題的狀態(tài)， 其中 W猴子的水平位置 X當(dāng)猴子在箱子頂上時取X=1；否則取X=0 Y箱子的水平位置 Z當(dāng)猴子摘到香蕉時取Z=1；否則取Z=0,2019/6/19,28,這個問題中的操作(算符)如下： (1) goto(U)猴子走到水平位置U，或者用產(chǎn)生式規(guī)則表示為 (W，0，Y，z) (U，0，Y，z) 即應(yīng)用操作goto(U)，能把狀態(tài)(W，0，Y，z)變換為狀態(tài)(U，0，Y，z)。 (2) pushbox(V)猴子把箱子推到水平位置V，即有 (W，0，W，z) (V，0，V，z) 應(yīng)當(dāng)注意的是，要應(yīng)用算符pushbox(V)，就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強(qiáng)加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件。,2019/6/19,29,(3) climbbox猴子爬上箱頂，即有 (W，0，W，z) (W，1，W，z) 在應(yīng)用算符climbbox時也必須注意到，猴子和箱子應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上 。 (4) grasp猴子摘到香蕉，即有 (c,1,c,0) (c,1,c,1) 其中，c是香蕉正下方的地板位置，在應(yīng)用算符grasp時，要求猴子和箱子都在位置c上，并且猴子已在箱子頂上。,2019/6/19,30,應(yīng)當(dāng)說明的是，在這種情況下，算符(操作)的適用性及作用均由產(chǎn)生式規(guī)則表示。例如，對于規(guī)則(2)，只有當(dāng)算符pushbox(V)的先決條件，即猴子與箱子在同一位置上而且猴子不在箱頂上這些條件得到滿足時，算符pushbox(V)才是適用的。這一操作算符的作用是猴子把箱子推到位置V。在這一表示中，目標(biāo)狀態(tài)的集合可由任何最后元素為1的表列來描述。,2019/6/19,31,令初始狀態(tài)為(a,0,b,0)。這時，goto(U)是唯一適用的操作，并導(dǎo)致下一狀態(tài)(U,0,b,0)?，F(xiàn)在有3個適用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。 把所有適用的操作繼續(xù)應(yīng)用于每個狀態(tài)，我們就能夠得到狀態(tài)空間圖。從圖不難看出，把該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為 goto(b),pushbox(c),climbbox,grasp,2019/6/19,32,猴子和香蕉問題的狀態(tài)空間圖,2019/6/19,33,問題歸約法,問題歸約(problem reduction)是另一種問題描述與求解方法。 先把問題分解為子問題和子-子問題，然后解決較小的問題。 對該問題的某個具體子集的解答就意味著對原始問題的一個解答。,2019/6/19,34,1. 問題歸約描述,問題歸約表示的組成部分： 一個初始問題描述； 一套把問題變換為子問題的操作符； 一套本原問題描述。 其中的每一個問題是不證明的，自然成立的，如公理、已知的實事等（本原問題集） 問題歸約的實質(zhì)：從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。,2019/6/19,35,梵塔難題,有3個柱子(1，2和3)和3個不同尺寸的圓盤（A，B和C）。在每個圓盤的中心有一個孔，所以圓盤可以堆疊在柱子上。最初，3個圓盤都堆在柱子1上：最大的圓盤C在底部，最小的圓盤A在頂部。要求把所有圓盤都移到柱子3上，每次只許移動一個，而且只能先搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。這個問題的初始配置和目標(biāo)配置如圖所示。,圖 梵塔問題,2019/6/19,36,解題過程： 將原始問題歸約為一個較簡單問題集合，要把所有圓盤都移至柱子3，我們必須首先把圓盤C移至柱子3；而且在移動圓盤C至柱子3之前，要求柱子3必須是空的。只有在移開圓盤A和B之后，才能移動圓盤C；而且圓盤A和B最好不要移至柱子3就不能把圓盤C移至柱子3。因此，首先應(yīng)該把圓盤A和B移到柱子2上。然后才能夠進(jìn)行關(guān)鍵的一步，把圓盤C從柱子1移至柱子3，并繼續(xù)解決難題的其余部分。 將原始難題歸約（簡化）為下列子難題：移動圓盤A和B至柱子2的雙圓盤難題，如圖(a)所示。,2019/6/19,37,把原始難題歸約（簡化）為以下三個子難題： 移動圓盤A和B至柱子2的雙圓盤難題；如圖(a)所示 移動圓盤C至柱子3的單圓盤難題 ；如圖(b)所示 移動圓盤A和B至柱子3雙圓盤難題；如圖(c)所示,2019/6/19,38,圖 2.7 梵塔問題解答(a),圖 2.8 梵塔問題解答(b),圖 2.9 梵塔問題解答(c),2019/6/19,39,梵塔問題歸約圖：子問題2可作為本原問題考慮，因為它的解只包含一步移動。應(yīng)用一系列相似的推理，子問題1和子問題3也可被歸約為本原問題，如圖2.10所示。這種圖式結(jié)構(gòu)，叫做與或圖(AND/OR graph)。 它能有效地說明如何由問題歸約法求得問題的解答。,圖 2.10 梵塔問題歸約圖,2019/6/19,40,把一個問題描述變換為一個歸約或后繼問題描述的集合，這是由問題歸約算符進(jìn)行的。變換所得所有后繼問題的解就意味著父輩問題的一個解。 所有問題歸約的目的是最終產(chǎn)生具有明顯解答的本原問題。這些問題可能是能夠由狀態(tài)空間搜索中走動一步來解決的問題，或者可能是別的具有已知解答的更復(fù)雜的問題。,2019/6/19,41,2. 與或圖表示,一般地，我們用一個類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，這種結(jié)構(gòu)圖叫做問題歸約圖，或叫與或圖。如下圖所示:,圖 2.13 子問題集合,圖 2.14 與或圖,2019/6/19,42,一些關(guān)于與或圖的術(shù)語： 父節(jié)點、子（后繼）節(jié)點、弧線、起始節(jié)點。 終葉節(jié)點：對應(yīng)于原問題的本原節(jié)點。 或節(jié)點：只要解決某個問題就可解決其父輩問題的節(jié)點集合，如（M，N，H）。 與節(jié)點：只有解決所有子問題，才能解決其父輩問題的節(jié)點集合，如（B,C)和（D,E,F）各個結(jié)點之間用一端小圓弧連接標(biāo)記。 與或圖：由與節(jié)點及或節(jié)點組成的結(jié)構(gòu)圖。,2019/6/19,43,可解節(jié)點的一般定義 (1) 終葉節(jié)點是可解節(jié)點(因為它們與本原問題相關(guān)連)。 (2) 如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只要當(dāng)其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。 (3) 如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當(dāng)其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。,2019/6/19,44,不可解節(jié)點的一般定義: (1) 沒有后裔的非終葉節(jié)點為不可解節(jié)點。 (2) 如果某個非終葉節(jié)點含有或后繼節(jié)點，那么只有當(dāng)其全部后裔為不可解時，此非終葉節(jié)點才是不可解的。 (3) 如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只要當(dāng)其后裔至少有一個為不可解時，此非終葉節(jié)點才是不可解的。,2019/6/19,45,圖2.15 中，終葉節(jié)點用字母t表示，有解節(jié)點用小原點表示，而解圖用粗線分支表示。,圖 2.15 與或圖例子,2019/6/19,46,與或圖構(gòu)成規(guī)則,(1) 與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含起始節(jié)點對應(yīng)于原始問題。 (2) 對應(yīng)于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔。 (3) 對于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向弧線自A 指向后繼節(jié)點表示所求得的子問題集合。 (4) 一般對于代表兩個或兩個以上子問題集合的每個節(jié)點，有向弧線從此節(jié)點指向此子問題集合中的各個節(jié)點。由于只有當(dāng)集合中所有的項都有解時，這個子問題的集合才能獲得解答，所以這些子問題節(jié)點叫做與節(jié)點。 (5) 在特殊情況下，當(dāng)只有一個算符可應(yīng)用于問題A，而且這個算符產(chǎn)生具有一個以上子問題的某個集合時，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡化。 因此，代表子問題集合的中間或節(jié)點可以被略去，如右圖所示。,圖 2.16 與或樹,2019/6/19,47,3. 問題歸約機(jī)理,關(guān)鍵算符 對于許多狀態(tài)空間的搜索問題，要推測一個狀態(tài)空間算符的特性并不是太困難的。也就是說，盡管尋求某個解答中整個算符序列的問題是困難的，但是規(guī)定這些算符中的一個卻往往是容易的。當(dāng)應(yīng)用該算符中的一個被認(rèn)為是問題求解的決定性步驟時，尋找這樣一個算符的可能性就增加了。例如，對我們前面討論過的梵塔問題，“移動圓盤C至柱子3“這個算符可被選為問題求解的決定性步驟(見圖2.9)，我們把這種具有決定性作用的算符叫做關(guān)鍵算符。,2019/6/19,48,當(dāng)某個關(guān)鍵算符被決定時，它可被用來辨別問題歸約過程中的路標(biāo)。假設(shè)F中的某個f是由三元狀態(tài)(S，F(xiàn)，G)表示的問題的關(guān)鍵算符。既然我們認(rèn)為f必定要應(yīng)用，所以(S，F(xiàn)，G)表示第一個后裔問題是一個對應(yīng)于尋找一條通向某一f適用的狀態(tài)的路徑問題。令Gf表示f適用的所有狀態(tài)的集合。由此，我們設(shè)立了一個由(S，F(xiàn)，Gf)描述的子問題。一旦這個子問題獲得解決，規(guī)定一個狀態(tài)gGf,我們就能夠設(shè)立由(g,F,f(g)表示的本原問題，其中，f(g)表示把f應(yīng)用于g而得到的狀態(tài)。因為這個問題僅僅由應(yīng)用關(guān)鍵算符f來解決，所以它是本原的。于是，剩下的(未解決的)是由三元狀態(tài)(f(g),F,G)描述的問題。 當(dāng)某個狀態(tài)空間的關(guān)鍵算符能夠被規(guī)定時，我們就能應(yīng)用下列問題歸約(見圖2.17)。,2019/6/19,49,我們沒有表示出本原問題(g,F,f(g)而簡化了這個圖。然后，這兩個后裔問題能夠用直接的狀態(tài)空間搜索技術(shù)或進(jìn)一步的問題歸約來求解。如果采用進(jìn)一步的歸約策略，我們必定能夠辨識問題(S，F(xiàn)，Gf)的某個關(guān)鍵算符，并繼續(xù)歸約下去。,圖 2.17,2019/6/19,50,對于許多問題，我們往往無法辨別某單個關(guān)鍵算符和預(yù)先知道其為某個問題解答的決定性步驟。我們只能推測某個算符的子集合，其中某個算符很有可能是決定性的。該子集合中的每個算符產(chǎn)生一對后裔問題。當(dāng)從各種替換算符中尋求某個解答時，從一個應(yīng)用這種想法的搜索過程可建立起一個與或圖。 要應(yīng)用這個方法，首先我們必須有某種方法用來計算任何狀態(tài)空間搜索問題的候選關(guān)鍵算符集合。下面我們要敘述以差別為基礎(chǔ)的一種特別方法。,2019/6/19,51,差別 尋找候選關(guān)鍵算符的一種方法涉及計算某個問題(S，F(xiàn)，G)的差別。粗略地說，問題(S，F(xiàn)，G)的差別就是用S的元對由集合G規(guī)定的目標(biāo)進(jìn)行測試失敗原因的部分表列(如果S的某個元是在G中，那么此問題就獲得解決，也就不存在差別)。舉例來說，如果目標(biāo)集合G由某個狀態(tài)條件集合所規(guī)定，而且某個sS滿足這些條件中的某些但不是全部條件，那么，差別可由不能被s滿足的條件的部分表列組成。如果這些條件能夠按其重要性分類，那么我們寧愿選用最重要的不滿足條件作為差別。,2019/6/19,52,其次，我們把某些狀態(tài)空間算符或算符集合與每個可能的差別結(jié)合起來。這些算符是候選關(guān)鍵算符。只有當(dāng)應(yīng)用某個算符是與消去某個差別相關(guān)時，此算符才與那個差別結(jié)合在一起。,2019/6/19,53,猴子和香蕉問題的與或圖,2019/6/19,54,解答序列： goto(b),pushbox(c),climbbox,grasp 1.關(guān)鍵算符 在問題求解過程中，具有決定性作用的算符叫做關(guān)鍵算符。 2.差別 尋找候選關(guān)鍵算符的一種方法就是要計算某個問題(S,F,G)的差別.不能被S滿足的條件的部分表列就組成了差別。我們選擇最重要的不滿足條件作為差別。,2019/6/19,55,猴子和香蕉問題把4個算符的作用結(jié)果和適用條件重寫如下： f1:(W,0,Y,z)-goto(U)(U,0,Y,z) f2:(W,0,W,z