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

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

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

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

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

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

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

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

8、動(dòng)的棋子組成。棋盤(pán)上總有一方格棋盤(pán)上的可走動(dòng)的棋子組成。棋盤(pán)上總有一格是空的，以便能夠讓空格周?chē)钠遄幼哌M(jìn)空格，格是空的，以便能夠讓空格周?chē)钠遄幼哌M(jìn)空格，這也可以了解為挪動(dòng)空格。圖中繪出了兩種棋局，這也可以了解為挪動(dòng)空格。圖中繪出了兩種棋局，即初始棋局和目的棋局，它們對(duì)應(yīng)于該下棋問(wèn)題即初始棋局和目的棋局，它們對(duì)應(yīng)于該下棋問(wèn)題的初始形狀和目的形狀。的初始形狀和目的形狀。如何把初始棋局變換為目的棋局呢？問(wèn)題的解答如何把初始棋局變換為目的棋局呢？問(wèn)題的解答就是某個(gè)適宜的棋子走步序列，如就是某個(gè)適宜的棋子走步序列，如左移棋子左移棋子12，下移棋子下移棋子15，右移棋子，右移棋子4，等等。等等。202

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

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

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

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

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

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

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

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

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

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

19、過(guò)程。這樣的搜索圖是形為顯式以便包含目的的過(guò)程。這樣的搜索圖是形狀空間問(wèn)題求解的主要根底。狀空間問(wèn)題求解的主要根底。問(wèn)題的表示對(duì)求解任務(wù)量有很大的影響。人們顯問(wèn)題的表示對(duì)求解任務(wù)量有很大的影響。人們顯然希望有較小的形狀空間表示。許多似乎很難的然希望有較小的形狀空間表示。許多似乎很難的問(wèn)題，當(dāng)表示適當(dāng)時(shí)就能夠具有小而簡(jiǎn)單的形狀問(wèn)題，當(dāng)表示適當(dāng)時(shí)就能夠具有小而簡(jiǎn)單的形狀空間。空間。2022-6-20233.形狀空間表示舉例 各種問(wèn)題都可用形狀空間加以表示，并用形狀空各種問(wèn)題都可用形狀空間加以表示，并用形狀空間搜索法來(lái)求解。間搜索法來(lái)求解。假設(shè)可以用一種不同的表示方法來(lái)求解用一問(wèn)題，假設(shè)可以用一種不

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

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

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

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

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

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

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

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

28、。2022-6-20331. 問(wèn)題歸約描畫(huà)問(wèn)題歸約表示的組成部分：?jiǎn)栴}歸約表示的組成部分：一個(gè)初始問(wèn)題描畫(huà)；一個(gè)初始問(wèn)題描畫(huà)；一套把問(wèn)題變換為子問(wèn)題的操作符；一套把問(wèn)題變換為子問(wèn)題的操作符；一套本原問(wèn)題描畫(huà)。一套本原問(wèn)題描畫(huà)。其中的每一個(gè)問(wèn)題是不證明的，自然成立的，如其中的每一個(gè)問(wèn)題是不證明的，自然成立的，如公理、的實(shí)事等本原問(wèn)題集公理、的實(shí)事等本原問(wèn)題集問(wèn)題歸約的本質(zhì)：從目的要處置的問(wèn)題動(dòng)身問(wèn)題歸約的本質(zhì)：從目的要處置的問(wèn)題動(dòng)身逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題

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

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

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

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

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

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

35、子問(wèn)題集合子問(wèn)題集合圖圖 2.14 2.14 與或圖與或圖2022-6-2041一些關(guān)于與或圖的術(shù)語(yǔ)：一些關(guān)于與或圖的術(shù)語(yǔ)：父節(jié)點(diǎn)、子后繼節(jié)點(diǎn)、弧線、起始節(jié)點(diǎn)。父節(jié)點(diǎn)、子后繼節(jié)點(diǎn)、弧線、起始節(jié)點(diǎn)。終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)?；蚬?jié)點(diǎn)：只需處置某個(gè)問(wèn)題就可處置其父輩問(wèn)題或節(jié)點(diǎn)：只需處置某個(gè)問(wèn)題就可處置其父輩問(wèn)題的節(jié)點(diǎn)集合，如的節(jié)點(diǎn)集合，如M，N，H。與節(jié)點(diǎn)：只需處置一切子問(wèn)題，才干處置其父輩與節(jié)點(diǎn)：只需處置一切子問(wèn)題，才干處置其父輩問(wèn)題的節(jié)點(diǎn)集合，如問(wèn)題的節(jié)點(diǎn)集合，如B,C和和D,E,F各個(gè)結(jié)各個(gè)結(jié)點(diǎn)之間用一端小圓弧銜接標(biāo)志。點(diǎn)之間用一端小圓弧銜接標(biāo)志。 與

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

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

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

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

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

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

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

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

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

45、測(cè)某個(gè)算符的子集合，其中某個(gè)算符我們只能推測(cè)某個(gè)算符的子集合，其中某個(gè)算符很有能夠是決議性的。該子集合中的每個(gè)算符產(chǎn)很有能夠是決議性的。該子集合中的每個(gè)算符產(chǎn)生一對(duì)后裔問(wèn)題。當(dāng)從各種交換算符中尋求某個(gè)生一對(duì)后裔問(wèn)題。當(dāng)從各種交換算符中尋求某個(gè)解答時(shí)，從一個(gè)運(yùn)用這種想法的搜索過(guò)程可建立解答時(shí)，從一個(gè)運(yùn)用這種想法的搜索過(guò)程可建立起一個(gè)與或圖。起一個(gè)與或圖。要運(yùn)用這個(gè)方法，首先我們必需有某種方法用來(lái)要運(yùn)用這個(gè)方法，首先我們必需有某種方法用來(lái)計(jì)算任何形狀空間搜索問(wèn)題的候選關(guān)鍵算符集合。計(jì)算任何形狀空間搜索問(wèn)題的候選關(guān)鍵算符集合。下面我們要表達(dá)以差別為根底的一種特別方法。下面我們要表達(dá)以差別為根底的一種

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

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