第2章用搜索求解問題的基本原理

第2章用搜索求解問題的基本原理1問題求解(Problem-solving)是AI領(lǐng)域中的一大課題,它涉及規(guī)約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明等相關(guān)過程的核心概念,是人工智能中研究得較早而且比較成熟的一個(gè)領(lǐng)域。問題求解(Problem-solving)是AI領(lǐng)域中的一大22.1問題與問題空間AI早期的目的是想通過計(jì)算技術(shù)來求解這樣一些問題：它們不存在現(xiàn)成的求解算法或求解方法非常復(fù)雜，而人使用其自身的智能都能較好地求解。為模擬這些問題的求解過程而發(fā)展的一種技術(shù)叫搜索。2.1問題與問題空間AI早期的目的是想通過計(jì)算技術(shù)來求解3把問題求解定義為狀態(tài)空間的搜索在分析和研究了人運(yùn)用智能求解的方法之后，人們發(fā)現(xiàn)許多問題的求解方法都是通過試探在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題，這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法。許多涉及智力的問題求解可看成狀態(tài)空間的搜索。把問題求解定義為狀態(tài)空間的搜索在分析和研究了人運(yùn)用智能求解4狀態(tài)和狀態(tài)空間狀態(tài)（state）是為描述某些不同事物間的差別而引入的一組最少變量q0，q1，q2…,qn的有序集合,并表示為:

Q=（q0,q1,…,qn）其中，每個(gè)元素qⅰ稱為狀態(tài)變量。給定每個(gè)分量的一組值，就得到一個(gè)具體的狀態(tài)。狀態(tài)和狀態(tài)空間狀態(tài)（state）是為描述某些不同事物間的差5狀態(tài)和狀態(tài)空間使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算子（operator）。操作符可能是走步（下棋）、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號或邏輯運(yùn)算符等。問題的狀態(tài)空間（statespace）是一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系的集合。狀態(tài)和狀態(tài)空間使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作6狀態(tài)和狀態(tài)空間它包含三種類型的集合，即該問題所有可能的初始狀態(tài)集合S，操作符集合F目標(biāo)狀態(tài)集合G。因此，可把狀態(tài)空間記為三元組（S，F(xiàn)，G）。狀態(tài)和狀態(tài)空間它包含三種類型的集合，即該問題所有可能的7問題狀態(tài)空間法的基本思想是：

（1）將問題中的已知條件看成狀態(tài)空間中初始狀態(tài)；將問題中要求的目標(biāo)看成狀態(tài)空間中目標(biāo)狀態(tài)；將問題中其它可能的情況看成狀態(tài)空間的任一狀態(tài)。（2）設(shè)法在狀態(tài)空間尋找一條路徑，由初始狀態(tài)出發(fā)，能夠沿著這條路徑達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)空間法的基本思想是：（1）將問題中的已知條件看成8問題狀態(tài)空間法的基本算法：（1）根據(jù)問題，定義出相應(yīng)的狀態(tài)空間，確定出狀態(tài)的一般表示，它含有相關(guān)對象的各種可能的排列。這里僅僅是定義這個(gè)空間的狀態(tài)，而不必枚舉該狀態(tài)空間的所有狀態(tài)，但由此可以得出問題的初始狀態(tài)、目標(biāo)狀態(tài)，并能夠表示出所有其它狀態(tài)。問題狀態(tài)空間法的基本算法：（1）根據(jù)問題，定義出相應(yīng)的狀態(tài)9問題狀態(tài)空間法的基本算法：

(2)規(guī)定一組操作(算子),能夠使?fàn)顟B(tài)從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)。(3)決定一種搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿某個(gè)路徑達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)空間法的基本算法：(2)規(guī)定一組操作(算子),10水壺問題給定兩個(gè)水壺，一個(gè)可裝4加侖水，一個(gè)能裝3加侖水。水壺上沒有任何度量標(biāo)記。有一水泵可用來往壺中裝水。問：怎樣在能裝4加侖的水壺里恰好只裝2加侖水？水壺問題11（1）定義狀態(tài)空間可將問題進(jìn)行抽象，用數(shù)偶(x,y)表示狀態(tài)空間的任一狀態(tài)。

x—表示4gallon水壺中所裝的水量，x=0，1，2，3或4；

y—表示3gallon水壺中所裝的水量，y=0，1，2或3；（1）定義狀態(tài)空間12初始狀態(tài)為(0,0)目標(biāo)狀態(tài)為(2,?)？表示水量不限，因?yàn)閱栴}中未規(guī)定在3加侖水壺里裝多少水。初始狀態(tài)為(0,0)13（2）確定一組操作1（X，Y|X<4）→（4，Y）4加侖水壺不滿時(shí)，將其裝滿；2（X，Y|Y<3）→（X，3）3加侖水壺不滿時(shí)，將其裝滿；5（X，Y|X>0）→（0，Y）把4加侖水壺中的水全部倒出；（2）確定一組操作146（X，Y|Y>0）→（X，0）把3加侖水壺中的水全部倒出；7（X，Y|X+Y≥4∧Y>0）→（4，Y-（4-X））把3加侖水壺中的水往4加侖水壺里倒，直至4加侖水壺裝滿為止8（X，Y|X+Y≥3∧X>0）→（X-（3-Y），3）把4加侖水壺中的水往3加侖水壺里倒，直至3加侖水壺裝滿為止；6（X，Y|Y>0）→（X，0）159（X，Y|X+Y≤4∧Y>0）→（X+Y，0）把3加侖水壺中的水全部倒進(jìn)4加侖水壺里；10（X，Y|X+Y≤3∧X>0）→（0，X+Y）把4加侖水壺中的水全部倒進(jìn)3加侖水壺里；9（X，Y|X+Y≤4∧Y>0）→（X+Y，0）16（3）選擇一種搜索策略

該策略為一個(gè)簡單的循環(huán)控制結(jié)構(gòu)：選擇其左部匹配當(dāng)前狀態(tài)的某條規(guī)則，并按照該規(guī)則右部的行為對此狀態(tài)作適當(dāng)改變，然后檢查改變后的狀態(tài)是否為某一目標(biāo)狀態(tài)，若不是，則繼續(xù)該循環(huán)。（3）選擇一種搜索策略17人工智能課件2問題求解與搜索技術(shù)184加侖水壺中3加侖水壺中所應(yīng)用的含水加侖數(shù)含水加侖數(shù)規(guī)則0

00323093324270252094加侖水壺中3加侖水壺中所應(yīng)19例2.2分配問題有兩個(gè)液源A和B。A的流量為100L/m,B的流量為50L/m?，F(xiàn)要求它們以75L/m的流量分別供應(yīng)兩個(gè)同樣的洗滌槽C，D。液體從液源經(jīng)過最大輸出能力為75L/m的管道進(jìn)行分配，A、B、C、D的位置、距離如圖2-2所示。并且要求只允許管子在液源或洗滌槽位置有接頭。例2.2分配問題有兩個(gè)液源A和B。A的流量為100L/m20例2.2分配問題問：如何連接管子使得管材最少？圖2-2液源分配問題示意圖例2.2分配問題問：如何連接管子使得管材最少？圖2-221例2.2分配問題(1)定義狀態(tài)空間中的狀態(tài)表示狀態(tài)以表的形式表示為：(A=?B=?C=?D=?)初態(tài)：(A=100B=50C=0D=0)目標(biāo)狀態(tài)：(A=0B=0C=75D=75)例2.2分配問題(1)定義狀態(tài)空間中的狀態(tài)表示22例2.2分配問題(2)定義操作現(xiàn)在取從一處到另一處流量的增量，為各點(diǎn)流量與各處所需流量的最大公約數(shù)(greatestcommondivisor)。100、50、75的GCD為25，所以取增量為25。例2.2分配問題(2)定義操作23例2.2分配問題

①本身到本身不必傳遞，用×表示；②洗滌槽不必往液源送，用⊕表示；例2.2分配問題①本身到本身不必傳遞，用×表示；24例2.2分配問題1A→B(A≥25∧B<75)→(A-25，B+25，C,D)4km2A→C(A≥25∧C<75)→(A-25，B，C+25，D)5km3A→D(A≥25∧D<75)→(A-25，B，C，D+25)5km4B→C(B≥25∧C<75)→(A，B-25，C+25，D)3km例2.2分配問題1A→B(A≥25∧B<75)→(25例2.2分配問題5B→D(B≥25∧D<75)→(A，B-25，C，D+25)3km6C→D(C≥25∧D<75)→(A，B，C-25，D+25)6km7D→C(C<75∧D≥25)→(A，B，C+25，D-25)6km例2.2分配問題5B→D(B≥25∧D<75)→(26例2.2分配問題

(3)定義策略因?yàn)楝F(xiàn)在沒有給出任何知識(shí)可用來指導(dǎo)搜索,所以可采用耗盡式搜索，即每次卻將7個(gè)操作試用一遍。對于該具體問題,搜索時(shí)要注意：①若操作重復(fù)時(shí)，只算一次距離;②邊搜索邊求出距離最短的管長。例2.2分配問題(3)定義策略27分配問題搜索路徑:分配問題搜索路徑:28

2.4問題特征分析對問題的幾個(gè)關(guān)鍵指標(biāo)或特征加以分析。一般要考慮：

問題可分解成為一組獨(dú)立的、更小、更容易解決的子問題嗎？

當(dāng)結(jié)果表明解題步驟不合適的時(shí)侯，能忽略或撤回嗎？

問題的全域可預(yù)測嗎？2.4問題特征分析對問題的幾個(gè)關(guān)鍵指標(biāo)或特征加以分析。29

2.4問題特征分析

在未與所有其它可能解作比較之前，能說當(dāng)前的解是最好的嗎？

用于求解問題的知識(shí)庫是相容的嗎？求解問題一定需要大量的知識(shí)嗎？或者說，有大量知識(shí)時(shí)候，搜索時(shí)應(yīng)加以限制嗎？只把問題交給電腦，電腦就能返回答案嗎？或者說，為得到問題的解，需要人機(jī)交互嗎？2.4問題特征分析在未與所有其它可能解作比較之前30

2.4.1

問題是否可分解？ 如果問題能分解成若干子問題，則將子問題解出后，原問題的解也就求出來了。人們稱這種解決問題的方法為問題的歸約。2.4.1問題是否可分解？31

例2.3符號積分不定積分的計(jì)算規(guī)則有：∫udv→uv-∫vdu分部積分產(chǎn)生式規(guī)則∫（f(x)+g(x)）dx→∫f(x)dx+∫g(x)dx和式分解規(guī)則∫kf(x)dx→k∫f(x)dx因子規(guī)則

例2.3符號積分32例2.4積木問題──機(jī)器人規(guī)劃的抽象模型積木問題關(guān)心的是積木塊的相對位置：某一積木在桌上或某一積木在另一積木上。機(jī)器人一次只能拿一塊積木，每次搬動(dòng)時(shí)積木上面必須是空的。

例2.4積木問題──機(jī)器人規(guī)劃的抽象模型33

34

例2.4積木問題積木的相對位置可用謂詞表示為：初始狀態(tài)：ontabel(B)∧clear(B)∧ontabel(A)∧on(C,A)∧clear(C)目標(biāo)狀態(tài)：ontabel(C)∧on(B,C)∧on(A,B)例2.4積木問題35

其中目標(biāo)狀態(tài)可分解為：子問題1:ontabel(c)子問題2:on(B,C)子問題3:on(A,B)

36

例2.4積木問題機(jī)器人所需完成的操作：

OP1：clear(x)→ontabel(x)

無論x在何處，若x上無物體，則可將x放于桌上

OP2：clear(x)∧clear(y)→On(x,y)若x，y上無物體，則可將x放在y上例2.4積木問題37

這個(gè)問題的求解方法有兩種：一種方法是采用全面搜索的方法；一種是用分解子問題的方法。從目標(biāo)來看，總問題可分解成三個(gè)子問題，但這三個(gè)子問題不能按任意次序求解。這個(gè)問題的求解方法有兩種：38

39

但若從初態(tài)出發(fā),將on(A,B)作為子問題1首先求解，這樣會(huì)使搜索離目標(biāo)越來越遠(yuǎn)。但若從初態(tài)出發(fā),將on(A,B)作為子問題1首40

對于子問題的之間的關(guān)系,實(shí)際上有兩種:一種為子問題之間是獨(dú)立的,其搜索路徑為:對于子問題的之間的關(guān)系,實(shí)際上有兩種:一種為子問題之41

另一種是子問題之間有依賴關(guān)系,其搜索路徑為:另一種是子問題之間有依賴關(guān)系,其搜索路徑為:422.4.2問題求解步驟是否可撤回？在問題求解的每一步驟完成后，分析一下它的“蹤跡”，可分為3類：（1）求解步驟可忽略如定理證明，證明定理的每一件事情都為真或者為假，且總是保存知識(shí)庫里，它是怎樣推出來的對下一步并不重要，因而控制結(jié)構(gòu)不需要帶回溯。2.4.2問題求解步驟是否可撤回？在問題求解的每一43（2）可復(fù)原

如走迷宮，實(shí)在走不通，可退回一步重來。這種搜索需用回溯技術(shù),例如:需用一定的控制結(jié)構(gòu)；需采用堆棧技術(shù)。（2）可復(fù)原44（3）不可復(fù)原如下棋、決策等問題，要提前分析每走一步后會(huì)導(dǎo)致的結(jié)果。不可回頭重來,這需要使用規(guī)劃技術(shù)。（3）不可復(fù)原452.4.3問題全域可預(yù)測否？

有些問題它的全域可預(yù)測，如水壺問題、定理證明,這些問題結(jié)局肯定，可只用開環(huán)控制結(jié)構(gòu)。有些問題的全域不可預(yù)測，如變化環(huán)境下機(jī)器人的控制，特別是危險(xiǎn)環(huán)境下工作的機(jī)器人隨時(shí)可能出意外，必須利用反饋信息，應(yīng)使用閉環(huán)控制結(jié)構(gòu)。2.4.3問題全域可預(yù)測否？462.4.4問題要求的是最優(yōu)解還是

較滿意解？一般說來，最佳路徑問題的計(jì)算較任意路徑問題的計(jì)算要困難。如果使用的啟發(fā)式方法不理想，那么對這個(gè)解的搜索就不可能很順利。有些問題要求找出真正的最佳路徑，可能任何啟發(fā)式法都不能適用。因此，得進(jìn)行耗盡式搜索，2.4.4問題要求的是最優(yōu)解還是

較滿意解？47第2章用搜索求解問題的基本原理

第2章用搜索求解問題的基本原理48問題求解(Problem-solving)是AI領(lǐng)域中的一大課題,它涉及規(guī)約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明等相關(guān)過程的核心概念,是人工智能中研究得較早而且比較成熟的一個(gè)領(lǐng)域。問題求解(Problem-solving)是AI領(lǐng)域中的一大492.1問題與問題空間AI早期的目的是想通過計(jì)算技術(shù)來求解這樣一些問題：它們不存在現(xiàn)成的求解算法或求解方法非常復(fù)雜，而人使用其自身的智能都能較好地求解。為模擬這些問題的求解過程而發(fā)展的一種技術(shù)叫搜索。2.1問題與問題空間AI早期的目的是想通過計(jì)算技術(shù)來求解50把問題求解定義為狀態(tài)空間的搜索在分析和研究了人運(yùn)用智能求解的方法之后，人們發(fā)現(xiàn)許多問題的求解方法都是通過試探在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題，這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法。許多涉及智力的問題求解可看成狀態(tài)空間的搜索。把問題求解定義為狀態(tài)空間的搜索在分析和研究了人運(yùn)用智能求解51狀態(tài)和狀態(tài)空間狀態(tài)（state）是為描述某些不同事物間的差別而引入的一組最少變量q0，q1，q2…,qn的有序集合,并表示為:

Q=（q0,q1,…,qn）其中，每個(gè)元素qⅰ稱為狀態(tài)變量。給定每個(gè)分量的一組值，就得到一個(gè)具體的狀態(tài)。狀態(tài)和狀態(tài)空間狀態(tài)（state）是為描述某些不同事物間的差52狀態(tài)和狀態(tài)空間使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算子（operator）。操作符可能是走步（下棋）、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號或邏輯運(yùn)算符等。問題的狀態(tài)空間（statespace）是一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系的集合。狀態(tài)和狀態(tài)空間使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作53狀態(tài)和狀態(tài)空間它包含三種類型的集合，即該問題所有可能的初始狀態(tài)集合S，操作符集合F目標(biāo)狀態(tài)集合G。因此，可把狀態(tài)空間記為三元組（S，F(xiàn)，G）。狀態(tài)和狀態(tài)空間它包含三種類型的集合，即該問題所有可能的54問題狀態(tài)空間法的基本思想是：

（1）將問題中的已知條件看成狀態(tài)空間中初始狀態(tài)；將問題中要求的目標(biāo)看成狀態(tài)空間中目標(biāo)狀態(tài)；將問題中其它可能的情況看成狀態(tài)空間的任一狀態(tài)。（2）設(shè)法在狀態(tài)空間尋找一條路徑，由初始狀態(tài)出發(fā)，能夠沿著這條路徑達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)空間法的基本思想是：（1）將問題中的已知條件看成55問題狀態(tài)空間法的基本算法：（1）根據(jù)問題，定義出相應(yīng)的狀態(tài)空間，確定出狀態(tài)的一般表示，它含有相關(guān)對象的各種可能的排列。這里僅僅是定義這個(gè)空間的狀態(tài)，而不必枚舉該狀態(tài)空間的所有狀態(tài)，但由此可以得出問題的初始狀態(tài)、目標(biāo)狀態(tài)，并能夠表示出所有其它狀態(tài)。問題狀態(tài)空間法的基本算法：（1）根據(jù)問題，定義出相應(yīng)的狀態(tài)56問題狀態(tài)空間法的基本算法：

(2)規(guī)定一組操作(算子),能夠使?fàn)顟B(tài)從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)。(3)決定一種搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿某個(gè)路徑達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)空間法的基本算法：(2)規(guī)定一組操作(算子),57水壺問題給定兩個(gè)水壺，一個(gè)可裝4加侖水，一個(gè)能裝3加侖水。水壺上沒有任何度量標(biāo)記。有一水泵可用來往壺中裝水。問：怎樣在能裝4加侖的水壺里恰好只裝2加侖水？水壺問題58（1）定義狀態(tài)空間可將問題進(jìn)行抽象，用數(shù)偶(x,y)表示狀態(tài)空間的任一狀態(tài)。

x—表示4gallon水壺中所裝的水量，x=0，1，2，3或4；

y—表示3gallon水壺中所裝的水量，y=0，1，2或3；（1）定義狀態(tài)空間59初始狀態(tài)為(0,0)目標(biāo)狀態(tài)為(2,?)？表示水量不限，因?yàn)閱栴}中未規(guī)定在3加侖水壺里裝多少水。初始狀態(tài)為(0,0)60（2）確定一組操作1（X，Y|X<4）→（4，Y）4加侖水壺不滿時(shí)，將其裝滿；2（X，Y|Y<3）→（X，3）3加侖水壺不滿時(shí)，將其裝滿；5（X，Y|X>0）→（0，Y）把4加侖水壺中的水全部倒出；（2）確定一組操作616（X，Y|Y>0）→（X，0）把3加侖水壺中的水全部倒出；7（X，Y|X+Y≥4∧Y>0）→（4，Y-（4-X））把3加侖水壺中的水往4加侖水壺里倒，直至4加侖水壺裝滿為止8（X，Y|X+Y≥3∧X>0）→（X-（3-Y），3）把4加侖水壺中的水往3加侖水壺里倒，直至3加侖水壺裝滿為止；6（X，Y|Y>0）→（X，0）629（X，Y|X+Y≤4∧Y>0）→（X+Y，0）把3加侖水壺中的水全部倒進(jìn)4加侖水壺里；10（X，Y|X+Y≤3∧X>0）→（0，X+Y）把4加侖水壺中的水全部倒進(jìn)3加侖水壺里；9（X，Y|X+Y≤4∧Y>0）→（X+Y，0）63（3）選擇一種搜索策略

該策略為一個(gè)簡單的循環(huán)控制結(jié)構(gòu)：選擇其左部匹配當(dāng)前狀態(tài)的某條規(guī)則，并按照該規(guī)則右部的行為對此狀態(tài)作適當(dāng)改變，然后檢查改變后的狀態(tài)是否為某一目標(biāo)狀態(tài)，若不是，則繼續(xù)該循環(huán)。（3）選擇一種搜索策略64人工智能課件2問題求解與搜索技術(shù)654加侖水壺中3加侖水壺中所應(yīng)用的含水加侖數(shù)含水加侖數(shù)規(guī)則0

00323093324270252094加侖水壺中3加侖水壺中所應(yīng)66例2.2分配問題有兩個(gè)液源A和B。A的流量為100L/m,B的流量為50L/m?，F(xiàn)要求它們以75L/m的流量分別供應(yīng)兩個(gè)同樣的洗滌槽C，D。液體從液源經(jīng)過最大輸出能力為75L/m的管道進(jìn)行分配，A、B、C、D的位置、距離如圖2-2所示。并且要求只允許管子在液源或洗滌槽位置有接頭。例2.2分配問題有兩個(gè)液源A和B。A的流量為100L/m67例2.2分配問題問：如何連接管子使得管材最少？圖2-2液源分配問題示意圖例2.2分配問題問：如何連接管子使得管材最少？圖2-268例2.2分配問題(1)定義狀態(tài)空間中的狀態(tài)表示狀態(tài)以表的形式表示為：(A=?B=?C=?D=?)初態(tài)：(A=100B=50C=0D=0)目標(biāo)狀態(tài)：(A=0B=0C=75D=75)例2.2分配問題(1)定義狀態(tài)空間中的狀態(tài)表示69例2.2分配問題(2)定義操作現(xiàn)在取從一處到另一處流量的增量，為各點(diǎn)流量與各處所需流量的最大公約數(shù)(greatestcommondivisor)。100、50、75的GCD為25，所以取增量為25。例2.2分配問題(2)定義操作70例2.2分配問題

①本身到本身不必傳遞，用×表示；②洗滌槽不必往液源送，用⊕表示；例2.2分配問題①本身到本身不必傳遞，用×表示；71例2.2分配問題1A→B(A≥25∧B<75)→(A-25，B+25，C,D)4km2A→C(A≥25∧C<75)→(A-25，B，C+25，D)5km3A→D(A≥25∧D<75)→(A-25，B，C，D+25)5km4B→C(B≥25∧C<75)→(A，B-25，C+25，D)3km例2.2分配問題1A→B(A≥25∧B<75)→(72例2.2分配問題5B→D(B≥25∧D<75)→(A，B-25，C，D+25)3km6C→D(C≥25∧D<75)→(A，B，C-25，D+25)6km7D→C(C<75∧D≥25)→(A，B，C+25，D-25)6km例2.2分配問題5B→D(B≥25∧D<75)→(73例2.2分配問題

(3)定義策略因?yàn)楝F(xiàn)在沒有給出任何知識(shí)可用來指導(dǎo)搜索,所以可采用耗盡式搜索，即每次卻將7個(gè)操作試用一遍。對于該具體問題,搜索時(shí)要注意：①若操作重復(fù)時(shí)，只算一次距離;②邊搜索邊求出距離最短的管長。例2.2分配問題(3)定義策略74分配問題搜索路徑:分配問題搜索路徑:75

2.4問題特征分析對問題的幾個(gè)關(guān)鍵指標(biāo)或特征加以分析。一般要考慮：

問題可分解成為一組獨(dú)立的、更小、更容易解決的子問題嗎？

當(dāng)結(jié)果表明解題步驟不合適的時(shí)侯，能忽略或撤回嗎？

問題的全域可預(yù)測嗎？2.4問題特征分析對問題的幾個(gè)關(guān)鍵指標(biāo)或特征加以分析。76

2.4問題特征分析

在未與所有其它可能解作比較之前，能說當(dāng)前的解是最好的嗎？

用于求解問題的知識(shí)庫是相容的嗎？求解問題一定需要大量的知識(shí)嗎？或者說，有大量知識(shí)時(shí)候，搜索時(shí)應(yīng)加以限制嗎？只把問題交給電腦，電腦就能返回答案嗎？或者說，為得到問題的解，需要人機(jī)交互嗎？2.4問題特征分析在未與所有其它可能解作比較之前77

2.4.1

問題是否可分解？ 如果問題能分解成若干子問題，則將子問題解出后，原問題的解也就求出來了。人們稱這種解決問題的方法為問題的歸約。2.4.1問題是否可分解？78

例2.3符號積分不定積分的計(jì)算規(guī)則有：∫udv→uv-∫vdu分部積分產(chǎn)生式規(guī)則∫（f(x)+g(x)）dx→∫f(x)dx+∫g(x)dx和式分解規(guī)則∫kf(x)dx→k∫f(x)dx因子規(guī)則

例2.3符號積分79例2.4積木問題──機(jī)器人規(guī)劃的抽象模型積木問題關(guān)心的是積木塊的相對位置：某一積木在桌上或某一積木在另一積木上。機(jī)器人一次只能拿一塊積木，每次搬動(dòng)時(shí)積木上面必須是空的。

例2.4積木問題──機(jī)器人規(guī)劃的抽象模型80

81

例2.4積木問題積木的相對位置可用謂詞表示為：初始狀態(tài)：ontabel(B)∧clear(B)∧ontabe