知識表示狀態(tài)空間問題歸約表示法ppt課件

1、人工智能原理第二講第二講知識表示知識表示 之之形狀空間形狀空間/ /問題歸約表示問題歸約表示主講：王祖喜主講：王祖喜 zuxiw163 zuxiw163 華中科技大學圖像所華中科技大學圖像所2022-6-201知識的表示方法謂詞邏輯法謂詞邏輯法 形狀空間法形狀空間法問題歸約法問題歸約法語義網(wǎng)絡法語義網(wǎng)絡法 框架表示法框架表示法 面向對象表示面向對象表示 劇本劇本scriptscript表示表示 過程過程procedureprocedure表示表示 小結小結2022-6-202形狀空間法問題求解問題求解problem solving是個大課題，它涉是個大課題，它涉及歸約、推斷、決策、規(guī)劃、常識推

2、理、定理證及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關過程的中心概念。在分析了人工智能研明和相關過程的中心概念。在分析了人工智能研討中運用的問題求解方法之后，就會發(fā)現(xiàn)許多問討中運用的問題求解方法之后，就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說，題求解方法是采用試探搜索方法的。也就是說，這些方法是經過在某個能夠的解空間內尋覓一個這些方法是經過在某個能夠的解空間內尋覓一個解來求解問題的。這種基于解答空間的問題表示解來求解問題的。這種基于解答空間的問題表示和求解方法就是形狀空間法，它是以形狀和算符和求解方法就是形狀空間法，它是以形狀和算符operator為根底來表示和求解問題的。為

3、根底來表示和求解問題的。2022-6-203問題求解技術兩個主要的方面問題求解技術兩個主要的方面問題的表示：假設描畫方法不對，對問題求問題的表示：假設描畫方法不對，對問題求解會帶來很大的困難解會帶來很大的困難求解的方法：采用試探搜索方法。求解的方法：采用試探搜索方法。 2022-6-204形狀空間法三要點形狀空間法三要點形狀形狀state：表示問題解法中每一步問題：表示問題解法中每一步問題情況的數(shù)據(jù)構造；情況的數(shù)據(jù)構造；算符算符operator：把問題從一種形狀變換為：把問題從一種形狀變換為另一種形狀的手段；另一種形狀的手段；形狀空間方法：基于解答空間的問題表示和形狀空間方法：基于解答空間的問

4、題表示和求解方法，它是以形狀和算符為根底來表示求解方法，它是以形狀和算符為根底來表示和求解問題的。和求解問題的。2022-6-2051.問題形狀描畫要完成某個問題的形狀描畫，必需確定三件事：要完成某個問題的形狀描畫，必需確定三件事： 1.該形狀描畫方式，特別是初始形狀描畫；該形狀描畫方式，特別是初始形狀描畫； 2.操作符集合及其對形狀描畫的作用；操作符集合及其對形狀描畫的作用； 3.目的形狀描畫的特性。目的形狀描畫的特性。2022-6-206定義定義 : :形狀形狀statestate：為描畫某類不同事物間的：為描畫某類不同事物間的差別而引入的一組最少變量差別而引入的一組最少變量q0q0，q1

5、 q1，qn qn的有序集合，其矢量方式如下：的有序集合，其矢量方式如下： 式中每個元素式中每個元素qi qii=0,1i=0,1，n n為集合為集合的分量，稱為形狀變量。的分量，稱為形狀變量。2022-6-207給定每個變量的一組值就得到一個詳細的形狀，給定每個變量的一組值就得到一個詳細的形狀，如如 Qk=q0k，q1k，. ，qnkT 它只是問題一切能夠形狀的羅列，還必需描畫它只是問題一切能夠形狀的羅列，還必需描畫這些形狀之間的能夠變化。這些形狀之間的能夠變化。所謂操作，或稱為算子是引起形狀中的某分量發(fā)所謂操作，或稱為算子是引起形狀中的某分量發(fā)生改動，從而使問題由一個詳細形狀生改動，從而使

6、問題由一個詳細形狀A變化為另變化為另一詳細形狀一詳細形狀B的作用。的作用。2022-6-208 算符：使問題從一種形狀變化為另一種形狀的手段稱為操算符：使問題從一種形狀變化為另一種形狀的手段稱為操作符或算符。操作符可為走步、過程、規(guī)那么、數(shù)學算子、作符或算符。操作符可為走步、過程、規(guī)那么、數(shù)學算子、運算符號或邏輯符號等。運算符號或邏輯符號等。 問題的形狀空間問題的形狀空間state space：是一個表示該問題全部：是一個表示該問題全部能夠形狀及其關系的圖，它包含三種闡明的集合，即一切能夠形狀及其關系的圖，它包含三種闡明的集合，即一切能夠的問題初始形狀集合能夠的問題初始形狀集合S初始形狀初始形

7、狀S0S、操作符集、操作符集合合F以及目的形狀集合以及目的形狀集合GGS?？砂研螤羁臻g記為三?？砂研螤羁臻g記為三元形狀元形狀S，F(xiàn)，G。 形狀空間可用有向圖來表示形狀空間可用有向圖來表示2022-6-209形狀空間的一個解形狀空間的一個解 使一個有限的操作算子序列，使一個有限的操作算子序列，它使初始形狀轉化為目的形狀：它使初始形狀轉化為目的形狀：S0-f1-S1-f2-.fk-G 2022-6-2010形狀空間表示詳釋讓我們先用數(shù)碼難題讓我們先用數(shù)碼難題puzzle problem來闡明形來闡明形狀空間表示的概念。由狀空間表示的概念。由15個編有個編有1至至15并放在并放在44方格棋盤上的可走

8、動的棋子組成。棋盤上總有一方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的，以便能夠讓空格周圍的棋子走進空格，格是空的，以便能夠讓空格周圍的棋子走進空格，這也可以了解為挪動空格。圖中繪出了兩種棋局，這也可以了解為挪動空格。圖中繪出了兩種棋局，即初始棋局和目的棋局，它們對應于該下棋問題即初始棋局和目的棋局，它們對應于該下棋問題的初始形狀和目的形狀。的初始形狀和目的形狀。如何把初始棋局變換為目的棋局呢？問題的解答如何把初始棋局變換為目的棋局呢？問題的解答就是某個適宜的棋子走步序列，如就是某個適宜的棋子走步序列，如左移棋子左移棋子12，下移棋子下移棋子15，右移棋子，右移棋子4，等等。等等。202

9、2-6-2011 a初始棋局初始棋局 b目的棋局目的棋局 十五數(shù)碼難題十五數(shù)碼難題1410213685712311549111514131211109876543212022-6-2012總形狀為總形狀為16!20922789888000由于棋盤的對稱性，實踐形狀數(shù)減半由于棋盤的對稱性，實踐形狀數(shù)減半上、下、左、右挪動四種操作上、下、左、右挪動四種操作2022-6-2013十五數(shù)碼難題最直接的求解方法是嘗試各種不同的走步，十五數(shù)碼難題最直接的求解方法是嘗試各種不同的走步，直到偶爾得到該目的棋局為止。這種嘗試本質上涉及某種直到偶爾得到該目的棋局為止。這種嘗試本質上涉及某種試探搜索。從初始棋局開場

10、，試探對于普通問題實踐上試探搜索。從初始棋局開場，試探對于普通問題實踐上是由計算機進展計算和執(zhí)行的由每一合法走步得到的各是由計算機進展計算和執(zhí)行的由每一合法走步得到的各種新棋局，然后計算再走一步而得到的下一組棋局。這樣種新棋局，然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至到達目的棋局為止。把初始形狀可到達的繼續(xù)下去，直至到達目的棋局為止。把初始形狀可到達的各形狀所組成的空間想象為一幅由各種形狀對應的節(jié)點組各形狀所組成的空間想象為一幅由各種形狀對應的節(jié)點組成的圖。這種圖稱為形狀圖。圖中每個節(jié)點標有它所代表成的圖。這種圖稱為形狀圖。圖中每個節(jié)點標有它所代表的棋局。首先把適用的算符用于初始

11、形狀，以產生新的形的棋局。首先把適用的算符用于初始形狀，以產生新的形狀；然后，再把另一些適用算符用于這些新的形狀；這樣狀；然后，再把另一些適用算符用于這些新的形狀；這樣繼續(xù)下去，直至產生目的形狀為止。繼續(xù)下去，直至產生目的形狀為止。部分形狀圖為：部分形狀圖為：2022-6-2014141021368571231154911141021368571231154911141021368571243115911141021368571231154911141021365712831154911141021368571243115911141021368571243115911141021385761

12、2311549112022-6-2015我們普通用形狀空間法這一術語來表示下述方法：我們普通用形狀空間法這一術語來表示下述方法：從某個初始形狀開場，每次加一個操作符，遞增從某個初始形狀開場，每次加一個操作符，遞增地建立起操作符的實驗序列，直到目的形狀為止。地建立起操作符的實驗序列，直到目的形狀為止。尋覓形狀空間的全部過程包括從舊的形狀描畫產尋覓形狀空間的全部過程包括從舊的形狀描畫產生新的形狀描畫，以及以后檢驗這些新的形狀描生新的形狀描畫，以及以后檢驗這些新的形狀描畫，看其能否描畫了該目的。這種檢驗往往只是畫，看其能否描畫了該目的。這種檢驗往往只是查看某個形狀能否與給定的查看某個形狀能否與給定的

13、 目的形狀描畫相匹配。目的形狀描畫相匹配。2022-6-2016要完成某個問題的形狀描畫，必需確定三件事：要完成某個問題的形狀描畫，必需確定三件事： 1.該形狀描畫方式，特別是初始形狀描畫；該形狀描畫方式，特別是初始形狀描畫； 2.操作符集合及其對形狀描畫的作用；操作符集合及其對形狀描畫的作用； 3.目的形狀描畫的特性。目的形狀描畫的特性。2022-6-20172.形狀圖示法 圖論中的幾個術語圖論中的幾個術語節(jié)點節(jié)點node：圖形上的集合點，用來：圖形上的集合點，用來表示形狀、事件和時表示形狀、事件和時 間關系的集合，間關系的集合，也可用來指示通路的集合；也可用來指示通路的集合；弧線弧線arc

14、：節(jié)點間的銜接線；：節(jié)點間的銜接線；有向圖有向圖directed graph：一對節(jié)點用：一對節(jié)點用弧線銜接起來，從一個節(jié)點指向另一弧線銜接起來，從一個節(jié)點指向另一個節(jié)點。個節(jié)點。 2022-6-2018后繼節(jié)點后繼節(jié)點descendant node與父輩節(jié)點與父輩節(jié)點parent node：假設某條弧線從節(jié)點：假設某條弧線從節(jié)點ni指向節(jié)指向節(jié)點點nj，那么節(jié)點，那么節(jié)點nj就叫做節(jié)點就叫做節(jié)點ni的后繼節(jié)點或后裔，的后繼節(jié)點或后裔，而節(jié)點而節(jié)點ni叫做節(jié)點叫做節(jié)點nj的父輩節(jié)點或祖先。的父輩節(jié)點或祖先。途徑：某個節(jié)點序列途徑：某個節(jié)點序列ni1,ni2,nik當當j=2，3，k時，假設對于

15、每一個時，假設對于每一個ni,j-1都有一個后繼都有一個后繼節(jié)點節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點至節(jié)點nik的長度為的長度為k的途徑。的途徑。代價：用代價：用cni,nj來表示從節(jié)點來表示從節(jié)點ni指向節(jié)點指向節(jié)點nj的的那段弧線的代價。那段弧線的代價。2022-6-2019假設從節(jié)點假設從節(jié)點ni至節(jié)點至節(jié)點nj存在有一條途徑，那么就稱節(jié)點存在有一條途徑，那么就稱節(jié)點nj 是從節(jié)點是從節(jié)點ni可到達的節(jié)點?？傻竭_的節(jié)點。兩節(jié)點間途徑的代價等于銜接該途徑上各節(jié)點的一切弧線兩節(jié)點間途徑的代價等于銜接該途徑上各節(jié)點的一切弧線代價之和。最

16、小者稱為最小代價的途徑。代價之和。最小者稱為最小代價的途徑。2022-6-2020顯式表示：各節(jié)點及其具有代價的弧線由一張闡顯式表示：各節(jié)點及其具有代價的弧線由一張闡明確給出。此表能夠列出該圖中的每一節(jié)點、它明確給出。此表能夠列出該圖中的每一節(jié)點、它的后繼節(jié)點以及銜接弧線的代價。的后繼節(jié)點以及銜接弧線的代價。隱式表示：節(jié)點的無限集合隱式表示：節(jié)點的無限集合si作為起始節(jié)點是的。作為起始節(jié)點是的。后繼節(jié)點算符后繼節(jié)點算符也是的，它能作用于任一節(jié)點以產也是的，它能作用于任一節(jié)點以產生該節(jié)點的全部后繼節(jié)點和各銜接弧線的代價。生該節(jié)點的全部后繼節(jié)點和各銜接弧線的代價。2022-6-2021圖的顯式和隱

17、式表示 一個圖可由顯式闡明也可由隱式闡明。顯然，顯式闡明對一個圖可由顯式闡明也可由隱式闡明。顯然，顯式闡明對于大型的圖是不真實踐的，而對于具有無限節(jié)點集合的圖于大型的圖是不真實踐的，而對于具有無限節(jié)點集合的圖那么是不能夠的。那么是不能夠的。 此外，引入后繼節(jié)點算符的概念是方便的。后繼節(jié)點算符此外，引入后繼節(jié)點算符的概念是方便的。后繼節(jié)點算符也是的，它能作用于任一節(jié)點以產生該節(jié)點的全部后繼也是的，它能作用于任一節(jié)點以產生該節(jié)點的全部后繼節(jié)點和各銜接弧線的代價用我們的形狀空間術語來說，節(jié)點和各銜接弧線的代價用我們的形狀空間術語來說，后繼算符是由適用于形狀描畫的算符集合所確定的。把后繼算符是由適用于

18、形狀描畫的算符集合所確定的。把后繼算符運用于后繼算符運用于si的成員和它們的后繼節(jié)點以及這些后的成員和它們的后繼節(jié)點以及這些后繼節(jié)點的后繼節(jié)點，如此無限制地進展下去，最后使得由繼節(jié)點的后繼節(jié)點，如此無限制地進展下去，最后使得由和和si所規(guī)定的隱式圖變?yōu)轱@示圖。把后繼算符運用于節(jié)所規(guī)定的隱式圖變?yōu)轱@示圖。把后繼算符運用于節(jié)點的過程，就是擴展一個節(jié)點的過程。點的過程，就是擴展一個節(jié)點的過程。2022-6-2022因此，搜索某個形狀空間以求得算符序列的一個因此，搜索某個形狀空間以求得算符序列的一個解答的過程，就對應于使隱式圖足夠大一部分變解答的過程，就對應于使隱式圖足夠大一部分變?yōu)轱@式以便包含目的的

19、過程。這樣的搜索圖是形為顯式以便包含目的的過程。這樣的搜索圖是形狀空間問題求解的主要根底。狀空間問題求解的主要根底。問題的表示對求解任務量有很大的影響。人們顯問題的表示對求解任務量有很大的影響。人們顯然希望有較小的形狀空間表示。許多似乎很難的然希望有較小的形狀空間表示。許多似乎很難的問題，當表示適當時就能夠具有小而簡單的形狀問題，當表示適當時就能夠具有小而簡單的形狀空間?？臻g。2022-6-20233.形狀空間表示舉例 各種問題都可用形狀空間加以表示，并用形狀空各種問題都可用形狀空間加以表示，并用形狀空間搜索法來求解。間搜索法來求解。假設可以用一種不同的表示方法來求解用一問題，假設可以用一種不

20、同的表示方法來求解用一問題，也不用感到詫異。也不用感到詫異。產生式系統(tǒng)產生式系統(tǒng)Production System是描畫搜索過程的方法。是描畫搜索過程的方法。2022-6-2024一個產生式系統(tǒng)由下面三部分組成：一個產生式系統(tǒng)由下面三部分組成：一個總數(shù)據(jù)庫一個總數(shù)據(jù)庫global databaseglobal database：它含有與詳細義務：它含有與詳細義務有關的信息；隨著運用情況的不同，這些數(shù)據(jù)庫有關的信息；隨著運用情況的不同，這些數(shù)據(jù)庫能夠小得像數(shù)字矩陣那樣簡單，或許大得如檢索能夠小得像數(shù)字矩陣那樣簡單，或許大得如檢索文件構造那么復雜。文件構造那么復雜。一套規(guī)那么：它對數(shù)據(jù)庫進展操作運

21、算。每條規(guī)那一套規(guī)那么：它對數(shù)據(jù)庫進展操作運算。每條規(guī)那么由左右兩部分組成，左部鑒別規(guī)那么的適用性么由左右兩部分組成，左部鑒別規(guī)那么的適用性或先決條件，右部描畫規(guī)那么運用時所完成的動或先決條件，右部描畫規(guī)那么運用時所完成的動作。運用規(guī)那么來改動數(shù)據(jù)庫，就象運用算符來作。運用規(guī)那么來改動數(shù)據(jù)庫，就象運用算符來改動形狀一樣改動形狀一樣一個控制戰(zhàn)略：它確定應該采用哪一條適用規(guī)那么，一個控制戰(zhàn)略：它確定應該采用哪一條適用規(guī)那么，而且當數(shù)據(jù)庫的終止條件滿足時，就停頓計算。而且當數(shù)據(jù)庫的終止條件滿足時，就停頓計算?？刂茟?zhàn)略由控制系統(tǒng)選擇和確定。控制戰(zhàn)略由控制系統(tǒng)選擇和確定。2022-6-2025形狀空間表

22、示舉例 猴子和香蕉問題monkey and banana problem 在一個房間內有一只猴子可把這只猴子看做一個機器人、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度缺乏以碰到它。那么這只猴子怎樣才干摘到香蕉呢?圖中表示出猴子、香蕉和箱子在房間內的相對位置。猴子和香蕉問題猴子和香蕉問題2022-6-2026用一個四元表列用一個四元表列W,x,Y,z來表示這個問題的形狀，來表示這個問題的形狀，其中其中W猴子的程度位置猴子的程度位置X當猴子在箱子頂上時取當猴子在箱子頂上時取X=1；否那么取；否那么取X=0Y箱子的程度位置箱子的程度位置Z當猴子摘到香蕉時取當猴子摘到香蕉時取Z=1；否那么取

23、；否那么取Z=02022-6-2027這個問題中的操作算符如下：這個問題中的操作算符如下：1 gotoU猴子走到程度位置猴子走到程度位置U，或者用產生式規(guī)那，或者用產生式規(guī)那么表示為么表示為 W，0，Y，z U，0，Y，z 即運用操作即運用操作gotoU，能把形狀，能把形狀W，0，Y，z變換變換為形狀為形狀U，0，Y，z。2 pushboxV猴子把箱子推到程度位置猴子把箱子推到程度位置V，即有，即有 W，0，W，z V，0，V，z 該當留意的是，要運用算符該當留意的是，要運用算符pushboxV，就要求產，就要求產生式規(guī)那么的左邊，猴子與箱子必需在同一位置上，并且，生式規(guī)那么的左邊，猴子與箱子

24、必需在同一位置上，并且，猴子不是在箱子頂上。這種強加于操作的適用性條件，叫猴子不是在箱子頂上。這種強加于操作的適用性條件，叫做產生式規(guī)那么的先決條件。做產生式規(guī)那么的先決條件。2022-6-20283 climbbox猴子爬上箱頂，即有猴子爬上箱頂，即有 W，0，W，z W，1，W，z 在運用算符在運用算符climbbox時也必需留意到，猴子和箱子該當在時也必需留意到，猴子和箱子該當在同一位置上，而且猴子不在箱頂上同一位置上，而且猴子不在箱頂上 。4 grasp猴子摘到香蕉，即有猴子摘到香蕉，即有 c,1,c,0 c,1,c,1 其中，其中，c是香蕉正下方的地板位置，在運用算符是香蕉正下方的地

25、板位置，在運用算符grasp時，要求猴子和箱子都在位置時，要求猴子和箱子都在位置c上，并且猴子已在箱子頂上，并且猴子已在箱子頂上。上。2022-6-2029該當闡明的是，在這種情況下，算符操作的該當闡明的是，在這種情況下，算符操作的適用性及作用均由產生式規(guī)那么表示。例如，對適用性及作用均由產生式規(guī)那么表示。例如，對于規(guī)那么于規(guī)那么2，只需當算符，只需當算符pushboxV的先的先決條件，即猴子與箱子在同一位置上而且猴子不決條件，即猴子與箱子在同一位置上而且猴子不在箱頂上這些條件得到滿足時，算符在箱頂上這些條件得到滿足時，算符pushboxV才是適用的。這一操作算符的作用是猴子把箱子才是適用的。

26、這一操作算符的作用是猴子把箱子推到位置推到位置V。在這一表示中，目的形狀的集合可。在這一表示中，目的形狀的集合可由任何最后元素為由任何最后元素為1的表列來描畫。的表列來描畫。2022-6-2030令初始形狀為令初始形狀為a,0,b,0。這時，。這時，gotoU是獨是獨一適用的操作，并導致下一形狀一適用的操作，并導致下一形狀U,0,b,0。如。如今有今有3個適用的操作，即個適用的操作，即gotoU，pushboxV和和climbbox假設假設U=b。 把一切適用的操作繼續(xù)運用于每個形狀，我們就把一切適用的操作繼續(xù)運用于每個形狀，我們就可以得到形狀空間圖。從圖不難看出，把該初始可以得到形狀空間圖。

27、從圖不難看出，把該初始形狀變換為目的形狀的操作序列為形狀變換為目的形狀的操作序列為 g o t o b , p u s h b o xc,climbbox,grasp2022-6-2031猴子和香蕉問題的形狀空間圖猴子和香蕉問題的形狀空間圖2022-6-2032問題歸約法 問題歸約問題歸約problem reduction是另一種問題描是另一種問題描畫與求解方法。畫與求解方法。先把問題分解為子問題和子先把問題分解為子問題和子-子問題，然后處置較子問題，然后處置較小的問題。小的問題。對該問題的某個詳細子集的解答就意味著對原始對該問題的某個詳細子集的解答就意味著對原始問題的一個解答。問題的一個解答

28、。2022-6-20331. 問題歸約描畫問題歸約表示的組成部分：問題歸約表示的組成部分：一個初始問題描畫；一個初始問題描畫；一套把問題變換為子問題的操作符；一套把問題變換為子問題的操作符；一套本原問題描畫。一套本原問題描畫。其中的每一個問題是不證明的，自然成立的，如其中的每一個問題是不證明的，自然成立的，如公理、的實事等本原問題集公理、的實事等本原問題集問題歸約的本質：從目的要處置的問題動身問題歸約的本質：從目的要處置的問題動身逆向推理，建立子問題以及子問題的子問題，直逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集至最后把初始問題歸約為一個平凡的本原問題

29、集合。合。2022-6-2034梵塔難題 有有3個柱子個柱子1，2和和3和和3個不同尺寸的圓盤個不同尺寸的圓盤A，B和和C。在每個圓盤的中心有一個孔，所以圓盤可以堆疊在。在每個圓盤的中心有一個孔，所以圓盤可以堆疊在柱子上。最初，柱子上。最初，3個圓盤都堆在柱子個圓盤都堆在柱子1上：最大的圓盤上：最大的圓盤C在在底部，最小的圓盤底部，最小的圓盤A在頂部。要求把一切圓盤都移到柱子在頂部。要求把一切圓盤都移到柱子3上，每次只許挪動一個，而且只能先搬動柱子頂部的圓盤，上，每次只許挪動一個，而且只能先搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。這個還不許把尺寸較大的圓盤堆放在尺寸較

30、小的圓盤上。這個問題的初始配置和目的配置如以下圖。問題的初始配置和目的配置如以下圖。圖 梵塔問題2022-6-2035解題過程：解題過程：將原始問題歸約為一個較簡單問題集合，要把一將原始問題歸約為一個較簡單問題集合，要把一切圓盤都移至柱子切圓盤都移至柱子3 3，我們必需首先把圓盤，我們必需首先把圓盤C C移至移至柱子柱子3 3；而且在挪動圓盤；而且在挪動圓盤C C至柱子至柱子3 3之前，要求柱子之前，要求柱子3 3必需是空的。只需在移開圓盤必需是空的。只需在移開圓盤A A和和B B之后，才干挪之后，才干挪動圓盤動圓盤C C；而且圓盤；而且圓盤A A和和B B最好不要移至柱子最好不要移至柱子3

31、3就不就不能把圓盤能把圓盤C C移至柱子移至柱子3 3。因此，首先應該把圓盤。因此，首先應該把圓盤A A和和B B移到柱子移到柱子2 2上。然后才可以進展關鍵的一步，把上。然后才可以進展關鍵的一步，把圓盤圓盤C C從柱子從柱子1 1移至柱子移至柱子3 3，并繼續(xù)處置難題的其他，并繼續(xù)處置難題的其他部分。部分。將原始難題歸約簡化為以下子難題：挪動圓將原始難題歸約簡化為以下子難題：挪動圓盤盤A A和和B B至柱子至柱子2 2的雙圓盤難題，如圖的雙圓盤難題，如圖a a所示。所示。2022-6-2036把原始難題歸約簡化為以下三個子難題：把原始難題歸約簡化為以下三個子難題： 挪動圓盤挪動圓盤A和和B至

32、柱子至柱子2的雙圓盤難題；如圖的雙圓盤難題；如圖a所示所示挪動圓盤挪動圓盤C至柱子至柱子3的單圓盤難題的單圓盤難題 ；如圖；如圖b所所示示挪動圓盤挪動圓盤A和和B至柱子至柱子3雙圓盤難題；如圖雙圓盤難題；如圖c所所示示2022-6-2037圖圖 2.7 2.7 梵塔問題解答梵塔問題解答a a圖圖 2.8 2.8 梵塔問題解答梵塔問題解答b b圖圖 2.9 2.9 梵塔問題解答梵塔問題解答c c2022-6-2038梵塔問題歸約圖：子問題梵塔問題歸約圖：子問題2可作為本原問題思索，由于它可作為本原問題思索，由于它的解只包含一步挪動。運用一系列類似的推理，子問題的解只包含一步挪動。運用一系列類似的

33、推理，子問題1和子問題和子問題3也可被歸約為本原問題，如圖也可被歸約為本原問題，如圖2.10所示。這種圖所示。這種圖式構造，叫做與或圖式構造，叫做與或圖AND/OR graph。它能有效地闡明如何由問題歸約法求得問題的解答。它能有效地闡明如何由問題歸約法求得問題的解答。 圖圖 2.10 2.10 梵塔問題歸約圖梵塔問題歸約圖2022-6-2039把一個問題描畫變換為一個歸約或后繼問題描畫把一個問題描畫變換為一個歸約或后繼問題描畫的集合，這是由問題歸約算符進展的。變換所得的集合，這是由問題歸約算符進展的。變換所得一切后繼問題的解就意味著父輩問題的一個解。一切后繼問題的解就意味著父輩問題的一個解。

34、一切問題歸約的目的是最終產生具有明顯解答的一切問題歸約的目的是最終產生具有明顯解答的本原問題。這些問題能夠是可以由形狀空間搜索本原問題。這些問題能夠是可以由形狀空間搜索中走動一步來處置的問題，或者能夠是別的具有中走動一步來處置的問題，或者能夠是別的具有解答的更復雜的問題。解答的更復雜的問題。2022-6-20402. 與或圖表示 普通地，我們用一個類似圖的構造來表示把問題普通地，我們用一個類似圖的構造來表示把問題歸約為后繼問題的交換集合，這種構造圖叫做問歸約為后繼問題的交換集合，這種構造圖叫做問題歸約圖，或叫與或圖。如以以下圖所示題歸約圖，或叫與或圖。如以以下圖所示:圖圖 2.13 2.13

35、子問題集合子問題集合圖圖 2.14 2.14 與或圖與或圖2022-6-2041一些關于與或圖的術語：一些關于與或圖的術語：父節(jié)點、子后繼節(jié)點、弧線、起始節(jié)點。父節(jié)點、子后繼節(jié)點、弧線、起始節(jié)點。終葉節(jié)點：對應于原問題的本原節(jié)點。終葉節(jié)點：對應于原問題的本原節(jié)點。或節(jié)點：只需處置某個問題就可處置其父輩問題或節(jié)點：只需處置某個問題就可處置其父輩問題的節(jié)點集合，如的節(jié)點集合，如M，N，H。與節(jié)點：只需處置一切子問題，才干處置其父輩與節(jié)點：只需處置一切子問題，才干處置其父輩問題的節(jié)點集合，如問題的節(jié)點集合，如B,C和和D,E,F各個結各個結點之間用一端小圓弧銜接標志。點之間用一端小圓弧銜接標志。 與

36、或圖：由與節(jié)點及或節(jié)點組成的構造圖。與或圖：由與節(jié)點及或節(jié)點組成的構造圖。2022-6-2042可解節(jié)點的普通定義可解節(jié)點的普通定義1 1 終葉節(jié)點是可解節(jié)點由于它們與本原問題終葉節(jié)點是可解節(jié)點由于它們與本原問題相關連。相關連。2 2 假設某個非終葉節(jié)點含有或后繼節(jié)點，那么假設某個非終葉節(jié)點含有或后繼節(jié)點，那么只需當其后繼節(jié)點至少有一個是可解的時，此非只需當其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。終葉節(jié)點才是可解的。3 3 假設某個非終葉節(jié)點含有與后繼節(jié)點，那么假設某個非終葉節(jié)點含有與后繼節(jié)點，那么只需當其后繼節(jié)點全部為可解時，此非終葉節(jié)點只需當其后繼節(jié)點全部為可解時，此非終葉

37、節(jié)點才是可解的。才是可解的。2022-6-2043不可解節(jié)點的普通定義不可解節(jié)點的普通定義: :1 1 沒有后裔的非終葉節(jié)點為不可解節(jié)點。沒有后裔的非終葉節(jié)點為不可解節(jié)點。2 2 假設某個非終葉節(jié)點含有或后繼節(jié)點，那么假設某個非終葉節(jié)點含有或后繼節(jié)點，那么只需當其全部后裔為不可解時，此非終葉節(jié)點才只需當其全部后裔為不可解時，此非終葉節(jié)點才是不可解的。是不可解的。3 3 假設某個非終葉節(jié)點含有與后繼節(jié)點，那么假設某個非終葉節(jié)點含有與后繼節(jié)點，那么只需當其后裔至少有一個為不可解時，此非終葉只需當其后裔至少有一個為不可解時，此非終葉節(jié)點才是不可解的。節(jié)點才是不可解的。2022-6-2044圖2.15

38、 中，終葉節(jié)點用字母t表示，有解節(jié)點用小原點表示，而解圖用粗線分支表示。 圖圖 2.15 2.15 與或圖例子與或圖例子2022-6-2045與或圖構成規(guī)那么1 與或圖中的每個節(jié)點代表一個要處置的單一問題或問題集合。與或圖中的每個節(jié)點代表一個要處置的單一問題或問題集合。圖中所含起始節(jié)點對應于原始問題。圖中所含起始節(jié)點對應于原始問題。2 對應于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔。對應于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔。3 對于把算符運用于問題對于把算符運用于問題A的每種能夠情況，都把問題變換為一的每種能夠情況，都把問題變換為一個子問題集合；有向弧線自個子問題集合；有向弧線自A 指向

39、后繼節(jié)點表示所求得的子問題集指向后繼節(jié)點表示所求得的子問題集合。合。4 普通對于代表兩個或兩個以上子問題集合的每個節(jié)點，有向弧普通對于代表兩個或兩個以上子問題集合的每個節(jié)點，有向弧線從此節(jié)點指向此子問題集合中的各個節(jié)點。由于只需當集合中一線從此節(jié)點指向此子問題集合中的各個節(jié)點。由于只需當集合中一切的項都有解時，這個子問題的集合才干獲得解答，所以這些子問切的項都有解時，這個子問題的集合才干獲得解答，所以這些子問題節(jié)點叫做與節(jié)點。題節(jié)點叫做與節(jié)點。5 在特殊情況下，當只需一個算符可運用于問題在特殊情況下，當只需一個算符可運用于問題A，而且這個算，而且這個算符產生具有一個以上子問題的某個集合時，由上

40、述規(guī)那么符產生具有一個以上子問題的某個集合時，由上述規(guī)那么3和規(guī)那么和規(guī)那么4所產生的圖可以得到簡化。所產生的圖可以得到簡化。因此，代表子問題集合的中間或節(jié)點可以被略去，如右圖所示。因此，代表子問題集合的中間或節(jié)點可以被略去，如右圖所示。圖圖 2.16 2.16 與或樹與或樹2022-6-20463. 問題歸約機理 關鍵算符關鍵算符 對于許多形狀空間的搜索問題，要推測一個形狀對于許多形狀空間的搜索問題，要推測一個形狀空間算符的特性并不是太困難的。也就是說，雖空間算符的特性并不是太困難的。也就是說，雖然尋求某個解答中整個算符序列的問題是困難的，然尋求某個解答中整個算符序列的問題是困難的，但是規(guī)定

41、這些算符中的一個卻往往是容易的。當?shù)且?guī)定這些算符中的一個卻往往是容易的。當運用該算符中的一個被以為是問題求解的決議性運用該算符中的一個被以為是問題求解的決議性步驟時，尋覓這樣一個算符的能夠性就添加了。步驟時，尋覓這樣一個算符的能夠性就添加了。例如，對我們前面討論過的梵塔問題，例如，對我們前面討論過的梵塔問題， 挪動圓盤挪動圓盤C C至柱子至柱子33這個算符可被選為問題求解的決議性步這個算符可被選為問題求解的決議性步驟見圖驟見圖2.92.9，我們把這種具有決議性作用的算，我們把這種具有決議性作用的算符叫做關鍵算符。符叫做關鍵算符。 2022-6-2047 當某個關鍵算符被決議時，它可被用來區(qū)分

42、問題歸約過程當某個關鍵算符被決議時，它可被用來區(qū)分問題歸約過程中的路標。假設中的路標。假設F中的某個中的某個f是由三元形狀是由三元形狀S，F(xiàn)，G表表示的問題的關鍵算符。既然我們以為示的問題的關鍵算符。既然我們以為f必定要運用，所以必定要運用，所以S，F(xiàn)，G表示第一個后裔問題是一個對應于尋覓一條表示第一個后裔問題是一個對應于尋覓一條通向某一通向某一f適用的形狀的途徑問題。令適用的形狀的途徑問題。令Gf表示表示f適用的一切適用的一切形狀的集合。由此，我們設立了一個由形狀的集合。由此，我們設立了一個由S，F(xiàn)，Gf描畫描畫的子問題。一旦這個子問題獲得處置，規(guī)定一個形狀的子問題。一旦這個子問題獲得處置，

43、規(guī)定一個形狀gGf,我們就可以設立由我們就可以設立由g,F,fg表示的本原問表示的本原問題，其中，題，其中，fg表示把表示把f運用于運用于g而得到的形狀。由于這而得到的形狀。由于這個問題僅僅由運用關鍵算符個問題僅僅由運用關鍵算符f來處置，所以它是本原的。來處置，所以它是本原的。于是，剩下的未處置的是由三元形狀于是，剩下的未處置的是由三元形狀fg,F,G描畫的問題。描畫的問題。 當某個形狀空間的關鍵算符可以被規(guī)定時，我們就能運用當某個形狀空間的關鍵算符可以被規(guī)定時，我們就能運用以下問題歸約見圖以下問題歸約見圖2.17。2022-6-2048我們沒有表示出本原問題我們沒有表示出本原問題g,F,fg

44、,F,fg g 而簡化了這個而簡化了這個圖。然后，這兩個后裔問題可以用直接的形狀空間搜索技術圖。然后，這兩個后裔問題可以用直接的形狀空間搜索技術或進一步的問題歸約來求解。假設采用進一步的歸約戰(zhàn)略，或進一步的問題歸約來求解。假設采用進一步的歸約戰(zhàn)略，我們必定可以辨識問題我們必定可以辨識問題S S，F(xiàn) F，GfGf的某個關鍵算符，并繼的某個關鍵算符，并繼續(xù)歸約下去。續(xù)歸約下去。圖圖 2.17 2.172022-6-2049對于許多問題，我們往往無法區(qū)分某單個關鍵算對于許多問題，我們往往無法區(qū)分某單個關鍵算符和預先知道其為某個問題解答的決議性步驟。符和預先知道其為某個問題解答的決議性步驟。我們只能推

45、測某個算符的子集合，其中某個算符我們只能推測某個算符的子集合，其中某個算符很有能夠是決議性的。該子集合中的每個算符產很有能夠是決議性的。該子集合中的每個算符產生一對后裔問題。當從各種交換算符中尋求某個生一對后裔問題。當從各種交換算符中尋求某個解答時，從一個運用這種想法的搜索過程可建立解答時，從一個運用這種想法的搜索過程可建立起一個與或圖。起一個與或圖。要運用這個方法，首先我們必需有某種方法用來要運用這個方法，首先我們必需有某種方法用來計算任何形狀空間搜索問題的候選關鍵算符集合。計算任何形狀空間搜索問題的候選關鍵算符集合。下面我們要表達以差別為根底的一種特別方法。下面我們要表達以差別為根底的一種

46、特別方法。 2022-6-2050 差別差別尋覓候選關鍵算符的一種方法涉及計算某個問題尋覓候選關鍵算符的一種方法涉及計算某個問題S S，F(xiàn) F，G G的差別。粗略地說，問題的差別。粗略地說，問題S S，F(xiàn) F，G G的差別就是用的差別就是用S S的元對由集合的元對由集合G G規(guī)定的目的進規(guī)定的目的進展測試失敗緣由的部分表列假設展測試失敗緣由的部分表列假設S S的某個元是的某個元是在在G G中，那么此問題就獲得處置，也就不存在差中，那么此問題就獲得處置，也就不存在差別。舉例來說，假設目的集合別。舉例來說，假設目的集合G G由某個形狀條由某個形狀條件集合所規(guī)定，而且某個件集合所規(guī)定，而且某個sSs

47、S滿足這些條件中的滿足這些條件中的某些但不是全部條件，那么，差別可由不能被某些但不是全部條件，那么，差別可由不能被s s滿滿足的條件的部分表列組成。假設這些條件可以按足的條件的部分表列組成。假設這些條件可以按其重要性分類，那么我們寧愿選用最重要的不滿其重要性分類，那么我們寧愿選用最重要的不滿足條件作為差別。足條件作為差別。2022-6-2051其次，我們把某些形狀空間算符或算符集合與每其次，我們把某些形狀空間算符或算符集合與每個能夠的差別結合起來。這些算符是候選關鍵算個能夠的差別結合起來。這些算符是候選關鍵算符。只需當運用某個算符是與消去某個差別相關符。只需當運用某個算符是與消去某個差別相關時，此算符才與那個差別結合在一同。時，此算符才與那個差別結合在一同。 2022-6-2052猴子