人工智能課件第2章1

第二章

問題求解與搜索方法

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

Q=[q0,q1,…,qn]

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

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

(2)規(guī)定一組操作(算子),能夠使狀態(tài)從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)。(3)決定一種搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿某個路徑達到目標狀態(tài)。問題狀態(tài)空間法的基本算法：(2)規(guī)定一組操作(算子),9水壺問題給定兩個水壺，一個可裝4加侖水，一個能裝3加侖水。水壺上沒有任何度量標記。有一水泵可用來往壺中裝水。問題是怎樣在能裝4加侖的水壺里恰好只裝2加侖水。水壺問題10（1）定義狀態(tài)空間:可將問題進行抽象，用數(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)空間:11（1）定義狀態(tài)空間初始狀態(tài)為(0,0)目標狀態(tài)為(2,?)？表示水量不限，因為問題中未規(guī)定在3加侖水壺里裝多少水。（1）定義狀態(tài)空間12（2）確定一組操作1（X，Y|X<4）→（4，Y）4加侖水壺不滿時，將其裝滿；2（X，Y|Y<3）→（X，3）3加侖水壺不滿時，將其裝滿；3（X，Y|X>0）→（X-D，Y）從4加侖水壺中倒出一些水；4（X，Y|Y>0）→（X，Y-D）從3加侖水壺中倒出一些水；5（X，Y|X>0）→（0，Y）把4加侖水壺中的水全部倒出；6（X，Y|Y>0）→（X，0）把3加侖水壺中的水全部倒出；（2）確定一組操作1（X，Y|X<4）→（4，Y）13（2）確定一組操作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加侖水壺裝滿為止；9（X，Y|X+Y≤4∧Y>0）→（X+Y，0）把3加侖水壺中的水全部倒進4加侖水壺里；10（X，Y|X+Y≤3∧X>0）→（0，X+Y）把4加侖水壺中的水全部倒進3加侖水壺里；（2）確定一組操作7（X，Y|X+Y≥4∧Y>0）→4，14（3）選擇一種搜索策略

該策略為一個簡單的循環(huán)控制結構：選擇其左部匹配當前狀態(tài)的某條規(guī)則，并按照該規(guī)則右部的行為對此狀態(tài)作適當改變，然后檢查改變后的狀態(tài)是否為某一目標狀態(tài)，若不是，則繼續(xù)該循環(huán)。（3）選擇一種搜索策略15人工智能課件第2章1164加侖水壺中3加侖水壺中所應用的含水加侖數(shù)含水加侖數(shù)規(guī)則0

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

①本身到本身不必傳遞，用×表示；②洗滌槽不必往液源送，用×表示；例2.2分配問題(2)定義操作。①本身到本身不必傳22例2.2分配問題(2)定義操作。1A→B(A≥75∧B<75)→(A-25，B+25，C,D)4km2A→C(A≥25∧C<75)→(A-25，B，C+25)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分配問題(2)定義操作。23例2.2分配問題(3)定義策略。

因為現(xiàn)在沒有給出任何知識可用來指導搜索,所以可采用耗盡式搜索，即每次卻將7個操作試用一遍。對于該具體問題,搜索時要注意：①若操作重復時，只算一次距離;②邊搜索邊求出距離最短的管長。例2.2分配問題(3)定義策略。24分配問題搜索路徑:分配問題搜索路徑:252.1.2問題特征分析對問題的幾個關鍵指標或特征加以分析。一般要考慮：

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

當結果表明解題步驟不合適的時侯，能忽略或撤回嗎？

問題的全域可預測嗎？2.1.2問題特征分析對問題的幾個關鍵指標或特征262.1.2問題特征分析

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

用于求解問題的知識庫是相容的嗎？求解問題一定需要大量的知識嗎？或者說，有大量知識時候，搜索時應加以限制嗎？只把問題交給電腦，電腦就能返回答案嗎？或者說，為得到問題的解，需要人機交互嗎？2.1.2問題特征分析在未與所有其它可能解作比較272.1.2問題特征分析1．問題是否可分解？如果問題能分解成若干子問題，則將子問題解出后，原問題的解也就求出來了。人們稱這種解決問題的方法為問題的歸約。2.1.2問題特征分析1．問題是否可分解？282.1.2問題特征分析

例2.3符號積分不定積分的計算規(guī)則有：∫udv→uv-∫udv

分部積分產(chǎn)生式規(guī)則∫f(x)+g(x)dx→∫f(x)dx+∫g(x)dx

和式分解規(guī)則∫kf(x)dx→k∫f(x)dx

因子規(guī)則

2.1.2問題特征分析例2.3符號積分29人工智能課件第2章1302.1.2問題特征分析例2.4積木問題──機器人規(guī)劃的抽象模型積木問題關心的是積木塊的相對位置：某一積木在桌上或某一積木在另一積木上。機器人只能一次拿一塊積木，每次搬動時積木上面必須是空的。

2.1.2問題特征分析例2.4積木問題──機器人規(guī)劃312.1.2問題特征分析

2.1.2問題特征分析322.1.2問題特征分析例2.4積木問題積木的相對位置可用謂詞表示為：初始狀態(tài)：ontabel(B)∧clear(B)∧ontabel(A)∧on(C,A)∧clear(C)目標狀態(tài)：ontabel(C)∧on(B,C)∧on(A,B)2.1.2問題特征分析例2.4積木問題332.1.2問題特征分析例2.4積木問題其中目標狀態(tài)可分解為：子問題1:ontabel(c)

子問題2:on(B,C)

子問題3:on(A,B)2.1.2問題特征分析例2.4積木問題342.1.2問題特征分析例2.4積木問題機器人所需完成的操作：

OP1：clear(x)→ontabel(x)

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

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

這個問題的求解方法有兩種：一種方法是采用全面搜索的方法；一種是用分解子問題的方法。從目標來看，總問題可分解成三個子問題，但這三個子問題不能按任意次序求解。2.1.2問題特征分析這個問題的求解方法有兩種：36

372.1.2問題特征分析但若從初態(tài)出發(fā),將on(A,B)作為子問題1首先求解，這樣會使搜索離目標越來越遠。2.1.2問題特征分析但若從初態(tài)出發(fā),將on(A,382.1.2問題特征分析

對于子問題的之間的關系,實際上有兩種:一種為子問題之間是獨立的,其搜索路徑為:2.1.2問題特征分析對于子問題的之間的關系,392.1.2問題特征分析

另一種是子問題之間有依賴關系,其搜索路徑為:2.1.2問題特征分析另一種是子問題之間有依賴關402.1.2問題特征分析2．問題求解步驟是否可撤回？在問題求解的每一步驟完成后，分析一下它的“蹤跡”，可分為：（1）求解步驟可忽略，如定理證明，證明定理的每一件事情都為真或者為假，且總是保存知識庫里，它是怎樣推出來的對下一步并不重要，因而控制結構不需要帶回溯。2.1.2問題特征分析2．問題求解步驟是否可撤回？412.1.2問題特征分析（2）可復原如走迷宮，實在走不通，可退回一步重來。這種搜索需用回溯技術,例如:需用一定的控制結構；需采用堆棧技術。2.1.2問題特征分析（2）可復原422.1.2問題特征分析（3）不可復原如下棋、決策等問題，要提前分析每走一步后會導致的結果。不可回頭重來,這需要使用規(guī)劃技術。在后面的第十章還要討論這個問題。2.1.2問題特征分析（3）不可復原432.1.2問題特征分析3．問題全域可預測否？

有些問題它的全域可預測，如水壺問題、定理證明,這些問題結局肯定，可只用開環(huán)控制結構。有些問題的全域不可預測，如變化環(huán)境下機器人的控制，特別是危險環(huán)境下工作的機器人隨時可能出意外，必須利用反饋信息，應使用閉環(huán)控制結構。2.1.2問題特征分析3．問題全域可預測否？442.1.2問題特征分析4．問題要求的是最優(yōu)解還是較滿意解？一般說來，最佳路徑問題的計算較任意路徑問題的計算要困難。如果使用的啟發(fā)式方法不理想，那么對這個解的搜索就不可能很順利。有些問題要求找出真正的最佳路徑，可能任何啟發(fā)式法都不能適用。因此，得進行耗盡式搜索，2.1.2問題特征分析4．問題要求的是最優(yōu)解還是較滿意解452.2盲目的搜索方法盲目搜索方法又叫非啟發(fā)式搜索，是一種無信息搜索，一般只適用于求解比較簡單的問題。下面我們要討論的幾個搜索方法，它們均屬于盲目搜索方法。2.2盲目的搜索方法462.2盲目的搜索方法2.2.1寬度優(yōu)先搜索如果搜索是以同層鄰近節(jié)點依次擴展節(jié)點的,那么這種搜索就叫寬度優(yōu)先搜索,這種搜索是逐層進行的,在對下一層的任一節(jié)點進行搜索之前,必須搜索完本層的所有節(jié)點。2.2盲目的搜索方法2.2.1寬度優(yōu)先搜索472.2盲目的搜索方法寬度優(yōu)先搜索算法如下:1.令N為一個由初始狀態(tài)構成的表；2.若N為空退出，標志失敗；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n不是目標，將n的后繼點加入到N表的尾部，轉2。2.2盲目的搜索方法寬度優(yōu)先搜索算法如下:482.2盲目的搜索方法寬度優(yōu)先搜索的優(yōu)點是：若問題有解，則可找出最優(yōu)解;寬度優(yōu)先搜索的缺點是：效率低，組合爆炸問題難以解決。2.2盲目的搜索方法492.2盲目的搜索方法2.2.2深度優(yōu)先搜索在深度優(yōu)先搜索中，我們首先擴展最新產(chǎn)生的（即最深的）節(jié)點。深度相等的節(jié)點可以任意排列。2.2盲目的搜索方法502.2盲目的搜索方法深度優(yōu)先搜索算法如下:1.令N為一個由初始狀態(tài)構成的表；2.若N為空退出，標態(tài)失??；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n不是目標，將n的后繼加入到N表的首部轉2。2.2盲目的搜索方法深度優(yōu)先搜索算法如下:512.2盲目的搜索方法深度優(yōu)先搜索的優(yōu)點：節(jié)省大量時間和空間；深度優(yōu)先搜索的缺點：不一定能找到解。因為在無限搜索樹的情況下，最壞的情況可能是不停機。2.2盲目的搜索方法522.2盲目的搜索方法2.2.3分枝有界搜索（Branch-and-Bound）分枝有界搜索也是一種深度優(yōu)先搜索，但每個分支都規(guī)定了一個統(tǒng)一的搜索深度，搜索到這個深度后，如果沒有找到目標便自動退回到上一層，繼續(xù)搜索。2.2盲目的搜索方法2.2.3分枝有界搜索（Branc532.2盲目的搜索方法1.令N為一由初始狀態(tài)構成的表；2.若N為空退出，標志失??；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n深度=預先定好的一個界dmax，則轉2；6.若n不是目標，將n的后繼加入到N表的首部轉2；2.2盲目的搜索方法1.令N為一由初始狀態(tài)構成的表；542.3啟發(fā)式搜索方法如果能夠找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，那么，搜索效率將會大大提高。啟發(fā)式搜索就是基于這種想法,它是深度優(yōu)先的改進。搜索時不是任取一個分枝，而是根據(jù)一些啟發(fā)式信息，選擇最佳一個分枝或幾個分枝往下搜索。2.3啟發(fā)式搜索方法552.3.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)（1）人們善于利用一些線索來幫助自己選擇搜索方向，這些線索統(tǒng)稱為啟發(fā)式(Heuristics)信息，Heuristics一詞來源于希臘語Heuriskein，即“發(fā)現(xiàn)”的意思。（2）現(xiàn)實問題往往只需一個解，而不要求最優(yōu)解或全部解。（3）啟發(fā)式信息可以避免某些領域里的組合爆炸問題。2.3.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)562.3.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：（1）表示為估計函數(shù)，確定一個啟發(fā)式函數(shù)f(n),n

為被搜索的節(jié)點,它把問題狀態(tài)的描述映射成問題解決的程度，通常這種程度用數(shù)值來表示，就是啟發(fā)式函數(shù)的值。這個值的大小用來決定最佳搜索路徑。2.3.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：572.3.1啟發(fā)式信息的表示（2）表示成規(guī)則，如一條啟發(fā)式規(guī)則為：如果存在一個有趣的二元函數(shù)f(x,y)，那么看看兩變元相同時會發(fā)生什么？若f表示乘法：導致發(fā)現(xiàn)平方；若f表示集合并運算：導致發(fā)現(xiàn)恒等函數(shù)；若f表示思考：導致發(fā)現(xiàn)反省；若f表示謀殺：導致發(fā)現(xiàn)自殺。2.3.1啟發(fā)式信息的表示（2）表示成規(guī)則，如一條啟發(fā)式規(guī)582.3.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法啟發(fā)式函數(shù)是一種映射函數(shù)，它把對問題狀態(tài)的描述映射成一種希望的程度。在搜索算法的設計中，考慮問題的狀態(tài)的哪些方面、怎樣對所考慮的方面作出估計、怎樣對某些因素加權等，都取決于啟發(fā)式函數(shù)的設計，取決于該函數(shù)對節(jié)點是否在解路徑上作出盡可能準確的估計。2.3.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法592.3.1啟發(fā)式信息的表示啟發(fā)式函數(shù)設計得好，對有效引導搜索過程有著重要的作用。在有的情況下，非常簡單的啟發(fā)式函數(shù)搜索路徑能夠作出非常令人滿意的估計,當然也有一些場合需要使用非常復雜的啟發(fā)式函數(shù)。下面就簡單討論一下如何構造啟發(fā)式函數(shù)。（1）啟發(fā)式函數(shù)能夠根據(jù)問題的當前狀態(tài)，確定用于繼續(xù)求解問題的信息。2.3.1啟發(fā)式信息的表示啟發(fā)式函數(shù)設計得好，對有效引導搜602.3.1啟發(fā)式信息的表示

例2.6利用啟發(fā)式信息去求解水壺問題，人們決不盲目搜索，而是利用水壺容量信息4，3，0，考慮如何求得2。用這幾個數(shù)字可以考慮4減2或3減1得到2。但前一個方法肯定不行，因為它用到2來求得2，用后一個方法要考慮如何求得1，這很容易在當前信息中找出，因為4減3等于1。因而導致求解路徑為：（0，0）→（4，0）→（1，3）→（1，0）→（4，1）→（2，3）=目標2.3.1啟發(fā)式信息的表示例2.6利用啟發(fā)式信息去求解612.3.1啟發(fā)式信息的表示

(2)啟發(fā)式函數(shù)能夠估計已找到的狀態(tài)與達到目標的有利程度。這樣的啟發(fā)式函數(shù)能夠有效地幫助決定那些后繼節(jié)點應被產(chǎn)生。2.3.1啟發(fā)式信息的表示622.3.1啟發(fā)式信息的表示2831

6475

例2.7八數(shù)碼問題。1

238

4765a11a12a13a21a22a23a31a32a33

問題空間為：S0

Sg

2.3.1啟發(fā)式信息的表示283例2.7632.3.1啟發(fā)式信息的表示各狀態(tài)間的轉換規(guī)則為：Pr1:空格上移↑If□i，jandi≠1thenai-1,j←→□i，j

Pr2:空格下移↓If□i，jandi≠3thenai+1,j←→□i，j

2.3.1啟發(fā)式信息的表示各狀態(tài)間的轉換規(guī)則為：642.3.1啟發(fā)式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j2.3.1啟發(fā)式信息的表示65f1(S5)=4啟發(fā)式函數(shù)f1=數(shù)字錯放位置的個數(shù)，f1=0，則達到目標。2831647528316475283147652831476523184765283164752831476528316475f1(S0)=4f1(S1)=3f1(S2)=5f1(S3)=5f1(S4)=3f1(S6)=3f1(S7)=4f1(S5)=4啟發(fā)式函數(shù)f1=數(shù)字錯放位置的個數(shù)，f1=662.3.1啟發(fā)式信息的表示當f1值相同時如何決定走步?現(xiàn)在定義：F2=所有數(shù)字當前位置次最短路徑走到正確位置的步數(shù)之和。在這個定義之下，各狀態(tài)的啟發(fā)式函數(shù)值為：數(shù)碼12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=42.3.1啟發(fā)式信息的表示當f1值相同時如何決定走步672.3.1啟發(fā)式信息的表示數(shù)碼12345678

F2(S2）=1+1+0+0+0+1+1+2=6F2(S3）=1+1+0+0+1+1+0+2=6F2(S4）=1+1+0+0+0+0+0+1=3F2(S5）=1+1+0+0+0+1+0+2=5F2(S6）=2+1+0+0+0+0+0+2=52.3.1啟發(fā)式信息的表示數(shù)碼12682.3.1啟發(fā)式信息的表示

(3)啟發(fā)式函數(shù)應能夠估計出可能加速達到目標的程度，這可以幫助確定當擴展一個節(jié)點時，那些節(jié)點應從搜索樹中刪除。啟發(fā)式函數(shù)對搜索樹(圖)的每一節(jié)點的真正優(yōu)點估計得愈精確,解題過程就愈少走彎路。2.3.1啟發(fā)式信息的表示(3)啟發(fā)式函數(shù)應能夠估計出692.3.1啟發(fā)式信息的表示

例2.8八皇后問題(8-Queensproblem）。在8*8棋盤要求放下8個皇后，要求沒有一個皇后能夠攻擊其它皇后，即要使得在任何一行、一列或對角線上都不存在兩個或兩個以上的皇后。2.3.1啟發(fā)式信息的表示例2.8八皇后問題(8-Q702.3.1啟發(fā)式信息的表示求解這個問題的過程為：（a）定義狀態(tài)空間。設狀態(tài)空間的一點為：8*8矩陣。（b）定義操作規(guī)則。為簡單起見，可按如下規(guī)則放置皇后：2.3.1啟發(fā)式信息的表示求解這個問題的過程為：712.3.1啟發(fā)式信息的表示第一個皇后放第一行。第二個皇后放在第二行且不與第一個皇后在同一列或對角線的空格上?！趇個皇后放在第i行且不與前面i–1個皇后在同一列或對角線的空格上?！?.3.1啟發(fā)式信息的表示第一個皇后放第一行。722.3.1啟發(fā)式信息的表示可使用如下啟發(fā)式函數(shù)：設x為當前要放置Queen的空格f（x）=剩下未放行中能夠用來放Queen的空格數(shù)不難看出，f（x）愈大愈好，應選擇f（x）最大的空格來放置皇后。例如，在放置了三個Q后，第4個Q可放在第4行的A，B，C三個位置。2.3.1啟發(fā)式信息的表示可使用如下啟發(fā)式函數(shù)：732.3.1啟發(fā)式信息的表示a為第4行A處放了皇后剩下可放Q的位置；

b為第4行B處放了皇后剩下可放Q的位置；c為第4行C處放了皇后剩下可放Q的位置。按照以上定義，可求得：f（A）=8，f（B）=9，f（C）=10。所以搜索可以從C對應的空格放置一個皇后開始，其余的空格對應的搜索樹可以刪除。2.3.1啟發(fā)式信息的表示a為第4行A處放了皇后剩下可放Q742.3.1啟發(fā)式信息的表示

Q

Q

Q

A

BC

abc

bc

ab

bc

c

ac

abc

b

acb

ac

acabbc

2.3.1啟發(fā)式信息的表示

Q

Q

752.3.1啟發(fā)式信息的表示（c）定義搜索策略。第i個皇后放到第i行中的那個與前面i-l個皇后不在同一列或對角線上且f（x）值最大的空格中。由此可見,啟發(fā)式信息是某些領域里的知識信息，它能使計算機系統(tǒng)在這些知識信息提示以后可能采取的某些可能的動作或避免某些不可能的動作，它能夠說明動作適合的條件或不適合的條件。2.3.1啟發(fā)式信息的表示（c）定義搜索策略。第i個皇后放762.3.1啟發(fā)式信息的表示啟發(fā)式搜索方法按其適用的范圍也可以分為兩種:一種是適用于特定的領域，如果這個領域很窄，這種啟發(fā)式搜索方法就變成了類似于計算方法中的算法；一種是適用于較廣泛領域的通用啟發(fā)式搜索算法，這類算法是后面要討論的弱法。2.3.1啟發(fā)式信息的表示啟發(fā)式搜索方法按其適用的范圍也可772.3.1啟發(fā)式信息的表示3．搜索方向的選擇搜索過程：在問題空間中找出從開始狀態(tài)到目標狀態(tài)的一條最好的或較好的路徑。這種搜索可按兩個方向進行：

正向搜索：從初始狀態(tài)朝著目標狀態(tài)方向搜索；逆向搜索：從目標狀態(tài)朝著初始狀態(tài)方向搜索。將以上兩種搜索方法結合起來，就產(chǎn)生了雙向搜索

2.3.1啟發(fā)式信息的表示3．搜索方向的選擇782.3.1啟發(fā)式信息的表示正向搜索和逆向搜索S0S0SgSg2.3.1啟發(fā)式信息的表示正向搜索792.3.1啟發(fā)式信息的表示搜索方向的選擇：(1)

朝分枝因子低的方向更有效。分子因子指從一點出發(fā)可以直接到達的平均結點數(shù)。朝著分枝因子低的方向搜索意味著朝著“收斂”的方向搜索，例如定理證明,一般是從公理或定理出發(fā)，推出新的定理。公理是有限的，而定理是大量的。2.3.1啟發(fā)式信息的表示搜索方向的選擇：802.3.1啟發(fā)式信息的表示(2)

由狀態(tài)少的一方出發(fā)，朝著大量的可識別的狀態(tài)的方向搜索，會容易一些。例如符號積分問題,正向搜索意味著從被積函數(shù)出發(fā)，按照積分規(guī)則，尋找原函數(shù)。而逆向搜索，則要從大量的原函數(shù)的任意組合出發(fā)，通過積分規(guī)則，找出被積函數(shù)，這顯然要困難得多，我們在人工演算積分問題時決不會這么去做。2.3.1啟發(fā)式信息的表示(2)

由狀態(tài)少的一方出發(fā)812.3.1啟發(fā)式信息的表示(3)依據(jù)用戶可接受的方向。特別是需要向用戶解釋推理過程時，順應用戶的心理，選擇搜索方向會使系統(tǒng)顯得更自然一些。在建造專家系統(tǒng)時，向用戶解釋為什么系統(tǒng)會得出某個結論,這一步驟是必不可少的，所以尤其要考慮這個問題。2.3.1啟發(fā)式信息的表示(3)依據(jù)用戶可接受的方向。82第二章

問題求解與搜索方法

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

Q=[q0,q1,…,qn]

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

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

(2)規(guī)定一組操作(算子),能夠使狀態(tài)從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)。(3)決定一種搜索策略，使得能夠從初始狀態(tài)出發(fā)，沿某個路徑達到目標狀態(tài)。問題狀態(tài)空間法的基本算法：(2)規(guī)定一組操作(算子),91水壺問題給定兩個水壺，一個可裝4加侖水，一個能裝3加侖水。水壺上沒有任何度量標記。有一水泵可用來往壺中裝水。問題是怎樣在能裝4加侖的水壺里恰好只裝2加侖水。水壺問題92（1）定義狀態(tài)空間:可將問題進行抽象，用數(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)空間:93（1）定義狀態(tài)空間初始狀態(tài)為(0,0)目標狀態(tài)為(2,?)？表示水量不限，因為問題中未規(guī)定在3加侖水壺里裝多少水。（1）定義狀態(tài)空間94（2）確定一組操作1（X，Y|X<4）→（4，Y）4加侖水壺不滿時，將其裝滿；2（X，Y|Y<3）→（X，3）3加侖水壺不滿時，將其裝滿；3（X，Y|X>0）→（X-D，Y）從4加侖水壺中倒出一些水；4（X，Y|Y>0）→（X，Y-D）從3加侖水壺中倒出一些水；5（X，Y|X>0）→（0，Y）把4加侖水壺中的水全部倒出；6（X，Y|Y>0）→（X，0）把3加侖水壺中的水全部倒出；（2）確定一組操作1（X，Y|X<4）→（4，Y）95（2）確定一組操作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加侖水壺裝滿為止；9（X，Y|X+Y≤4∧Y>0）→（X+Y，0）把3加侖水壺中的水全部倒進4加侖水壺里；10（X，Y|X+Y≤3∧X>0）→（0，X+Y）把4加侖水壺中的水全部倒進3加侖水壺里；（2）確定一組操作7（X，Y|X+Y≥4∧Y>0）→4，96（3）選擇一種搜索策略

該策略為一個簡單的循環(huán)控制結構：選擇其左部匹配當前狀態(tài)的某條規(guī)則，并按照該規(guī)則右部的行為對此狀態(tài)作適當改變，然后檢查改變后的狀態(tài)是否為某一目標狀態(tài)，若不是，則繼續(xù)該循環(huán)。（3）選擇一種搜索策略97人工智能課件第2章1984加侖水壺中3加侖水壺中所應用的含水加侖數(shù)含水加侖數(shù)規(guī)則0

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

①本身到本身不必傳遞，用×表示；②洗滌槽不必往液源送，用×表示；例2.2分配問題(2)定義操作。①本身到本身不必傳104例2.2分配問題(2)定義操作。1A→B(A≥75∧B<75)→(A-25，B+25，C,D)4km2A→C(A≥25∧C<75)→(A-25，B，C+25)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分配問題(2)定義操作。105例2.2分配問題(3)定義策略。

因為現(xiàn)在沒有給出任何知識可用來指導搜索,所以可采用耗盡式搜索，即每次卻將7個操作試用一遍。對于該具體問題,搜索時要注意：①若操作重復時，只算一次距離;②邊搜索邊求出距離最短的管長。例2.2分配問題(3)定義策略。106分配問題搜索路徑:分配問題搜索路徑:1072.1.2問題特征分析對問題的幾個關鍵指標或特征加以分析。一般要考慮：

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

當結果表明解題步驟不合適的時侯，能忽略或撤回嗎？

問題的全域可預測嗎？2.1.2問題特征分析對問題的幾個關鍵指標或特征1082.1.2問題特征分析

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

用于求解問題的知識庫是相容的嗎？求解問題一定需要大量的知識嗎？或者說，有大量知識時候，搜索時應加以限制嗎？只把問題交給電腦，電腦就能返回答案嗎？或者說，為得到問題的解，需要人機交互嗎？2.1.2問題特征分析在未與所有其它可能解作比較1092.1.2問題特征分析1．問題是否可分解？如果問題能分解成若干子問題，則將子問題解出后，原問題的解也就求出來了。人們稱這種解決問題的方法為問題的歸約。2.1.2問題特征分析1．問題是否可分解？1102.1.2問題特征分析

例2.3符號積分不定積分的計算規(guī)則有：∫udv→uv-∫udv

分部積分產(chǎn)生式規(guī)則∫f(x)+g(x)dx→∫f(x)dx+∫g(x)dx

和式分解規(guī)則∫kf(x)dx→k∫f(x)dx

因子規(guī)則

2.1.2問題特征分析例2.3符號積分111人工智能課件第2章11122.1.2問題特征分析例2.4積木問題──機器人規(guī)劃的抽象模型積木問題關心的是積木塊的相對位置：某一積木在桌上或某一積木在另一積木上。機器人只能一次拿一塊積木，每次搬動時積木上面必須是空的。

2.1.2問題特征分析例2.4積木問題──機器人規(guī)劃1132.1.2問題特征分析

2.1.2問題特征分析1142.1.2問題特征分析例2.4積木問題積木的相對位置可用謂詞表示為：初始狀態(tài)：ontabel(B)∧clear(B)∧ontabel(A)∧on(C,A)∧clear(C)目標狀態(tài)：ontabel(C)∧on(B,C)∧on(A,B)2.1.2問題特征分析例2.4積木問題1152.1.2問題特征分析例2.4積木問題其中目標狀態(tài)可分解為：子問題1:ontabel(c)

子問題2:on(B,C)

子問題3:on(A,B)2.1.2問題特征分析例2.4積木問題1162.1.2問題特征分析例2.4積木問題機器人所需完成的操作：

OP1：clear(x)→ontabel(x)

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

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

這個問題的求解方法有兩種：一種方法是采用全面搜索的方法；一種是用分解子問題的方法。從目標來看，總問題可分解成三個子問題，但這三個子問題不能按任意次序求解。2.1.2問題特征分析這個問題的求解方法有兩種：118

1192.1.2問題特征分析但若從初態(tài)出發(fā),將on(A,B)作為子問題1首先求解，這樣會使搜索離目標越來越遠。2.1.2問題特征分析但若從初態(tài)出發(fā),將on(A,1202.1.2問題特征分析

對于子問題的之間的關系,實際上有兩種:一種為子問題之間是獨立的,其搜索路徑為:2.1.2問題特征分析對于子問題的之間的關系,1212.1.2問題特征分析

另一種是子問題之間有依賴關系,其搜索路徑為:2.1.2問題特征分析另一種是子問題之間有依賴關1222.1.2問題特征分析2．問題求解步驟是否可撤回？在問題求解的每一步驟完成后，分析一下它的“蹤跡”，可分為：（1）求解步驟可忽略，如定理證明，證明定理的每一件事情都為真或者為假，且總是保存知識庫里，它是怎樣推出來的對下一步并不重要，因而控制結構不需要帶回溯。2.1.2問題特征分析2．問題求解步驟是否可撤回？1232.1.2問題特征分析（2）可復原如走迷宮，實在走不通，可退回一步重來。這種搜索需用回溯技術,例如:需用一定的控制結構；需采用堆棧技術。2.1.2問題特征分析（2）可復原1242.1.2問題特征分析（3）不可復原如下棋、決策等問題，要提前分析每走一步后會導致的結果。不可回頭重來,這需要使用規(guī)劃技術。在后面的第十章還要討論這個問題。2.1.2問題特征分析（3）不可復原1252.1.2問題特征分析3．問題全域可預測否？

有些問題它的全域可預測，如水壺問題、定理證明,這些問題結局肯定，可只用開環(huán)控制結構。有些問題的全域不可預測，如變化環(huán)境下機器人的控制，特別是危險環(huán)境下工作的機器人隨時可能出意外，必須利用反饋信息，應使用閉環(huán)控制結構。2.1.2問題特征分析3．問題全域可預測否？1262.1.2問題特征分析4．問題要求的是最優(yōu)解還是較滿意解？一般說來，最佳路徑問題的計算較任意路徑問題的計算要困難。如果使用的啟發(fā)式方法不理想，那么對這個解的搜索就不可能很順利。有些問題要求找出真正的最佳路徑，可能任何啟發(fā)式法都不能適用。因此，得進行耗盡式搜索，2.1.2問題特征分析4．問題要求的是最優(yōu)解還是較滿意解1272.2盲目的搜索方法盲目搜索方法又叫非啟發(fā)式搜索，是一種無信息搜索，一般只適用于求解比較簡單的問題。下面我們要討論的幾個搜索方法，它們均屬于盲目搜索方法。2.2盲目的搜索方法1282.2盲目的搜索方法2.2.1寬度優(yōu)先搜索如果搜索是以同層鄰近節(jié)點依次擴展節(jié)點的,那么這種搜索就叫寬度優(yōu)先搜索,這種搜索是逐層進行的,在對下一層的任一節(jié)點進行搜索之前,必須搜索完本層的所有節(jié)點。2.2盲目的搜索方法2.2.1寬度優(yōu)先搜索1292.2盲目的搜索方法寬度優(yōu)先搜索算法如下:1.令N為一個由初始狀態(tài)構成的表；2.若N為空退出，標志失敗；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n不是目標，將n的后繼點加入到N表的尾部，轉2。2.2盲目的搜索方法寬度優(yōu)先搜索算法如下:1302.2盲目的搜索方法寬度優(yōu)先搜索的優(yōu)點是：若問題有解，則可找出最優(yōu)解;寬度優(yōu)先搜索的缺點是：效率低，組合爆炸問題難以解決。2.2盲目的搜索方法1312.2盲目的搜索方法2.2.2深度優(yōu)先搜索在深度優(yōu)先搜索中，我們首先擴展最新產(chǎn)生的（即最深的）節(jié)點。深度相等的節(jié)點可以任意排列。2.2盲目的搜索方法1322.2盲目的搜索方法深度優(yōu)先搜索算法如下:1.令N為一個由初始狀態(tài)構成的表；2.若N為空退出，標態(tài)失??；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n不是目標，將n的后繼加入到N表的首部轉2。2.2盲目的搜索方法深度優(yōu)先搜索算法如下:1332.2盲目的搜索方法深度優(yōu)先搜索的優(yōu)點：節(jié)省大量時間和空間；深度優(yōu)先搜索的缺點：不一定能找到解。因為在無限搜索樹的情況下，最壞的情況可能是不停機。2.2盲目的搜索方法1342.2盲目的搜索方法2.2.3分枝有界搜索（Branch-and-Bound）分枝有界搜索也是一種深度優(yōu)先搜索，但每個分支都規(guī)定了一個統(tǒng)一的搜索深度，搜索到這個深度后，如果沒有找到目標便自動退回到上一層，繼續(xù)搜索。2.2盲目的搜索方法2.2.3分枝有界搜索（Branc1352.2盲目的搜索方法1.令N為一由初始狀態(tài)構成的表；2.若N為空退出，標志失敗；3.令n為N中第一個點，將n從N中刪除；4.若n是目標，則退出，標態(tài)成功；5.若n深度=預先定好的一個界dmax，則轉2；6.若n不是目標，將n的后繼加入到N表的首部轉2；2.2盲目的搜索方法1.令N為一由初始狀態(tài)構成的表；1362.3啟發(fā)式搜索方法如果能夠找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，那么，搜索效率將會大大提高。啟發(fā)式搜索就是基于這種想法,它是深度優(yōu)先的改進。搜索時不是任取一個分枝，而是根據(jù)一些啟發(fā)式信息，選擇最佳一個分枝或幾個分枝往下搜索。2.3啟發(fā)式搜索方法1372.3.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)（1）人們善于利用一些線索來幫助自己選擇搜索方向，這些線索統(tǒng)稱為啟發(fā)式(Heuristics)信息，Heuristics一詞來源于希臘語Heuriskein，即“發(fā)現(xiàn)”的意思。（2）現(xiàn)實問題往往只需一個解，而不要求最優(yōu)解或全部解。（3）啟發(fā)式信息可以避免某些領域里的組合爆炸問題。2.3.1啟發(fā)式信息的表示1．啟發(fā)式搜索的依據(jù)1382.3.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：（1）表示為估計函數(shù)，確定一個啟發(fā)式函數(shù)f(n),n

為被搜索的節(jié)點,它把問題狀態(tài)的描述映射成問題解決的程度，通常這種程度用數(shù)值來表示，就是啟發(fā)式函數(shù)的值。這個值的大小用來決定最佳搜索路徑。2.3.1啟發(fā)式信息的表示啟發(fā)信息按其形式可分為下列2種：1392.3.1啟發(fā)式信息的表示（2）表示成規(guī)則，如一條啟發(fā)式規(guī)則為：如果存在一個有趣的二元函數(shù)f(x,y)，那么看看兩變元相同時會發(fā)生什么？若f表示乘法：導致發(fā)現(xiàn)平方；若f表示集合并運算：導致發(fā)現(xiàn)恒等函數(shù)；若f表示思考：導致發(fā)現(xiàn)反??；若f表示謀殺：導致發(fā)現(xiàn)自殺。2.3.1啟發(fā)式信息的表示（2）表示成規(guī)則，如一條啟發(fā)式規(guī)1402.3.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法啟發(fā)式函數(shù)是一種映射函數(shù)，它把對問題狀態(tài)的描述映射成一種希望的程度。在搜索算法的設計中，考慮問題的狀態(tài)的哪些方面、怎樣對所考慮的方面作出估計、怎樣對某些因素加權等，都取決于啟發(fā)式函數(shù)的設計，取決于該函數(shù)對節(jié)點是否在解路徑上作出盡可能準確的估計。2.3.1啟發(fā)式信息的表示2．啟發(fā)式函數(shù)的表示方法1412.3.1啟發(fā)式信息的表示啟發(fā)式函數(shù)設計得好，對有效引導搜索過程有著重要的作用。在有的情況下，非常簡單的啟發(fā)式函數(shù)搜索路徑能夠作出非常令人滿意的估計,當然也有一些場合需要使用非常復雜的啟發(fā)式函數(shù)。下面就簡單討論一下如何構造啟發(fā)式函數(shù)。（1）啟發(fā)式函數(shù)能夠根據(jù)問題的當前狀態(tài)，確定用于繼續(xù)求解問題的信息。2.3.1啟發(fā)式信息的表示啟發(fā)式函數(shù)設計得好，對有效引導搜1422.3.1啟發(fā)式信息的表示

例2.6利用啟發(fā)式信息去求解水壺問題，人們決不盲目搜索，而是利用水壺容量信息4，3，0，考慮如何求得2。用這幾個數(shù)字可以考慮4減2或3減1得到2。但前一個方法肯定不行，因為它用到2來求得2，用后一個方法要考慮如何求得1，這很容易在當前信息中找出，因為4減3等于1。因而導致求解路徑為：（0，0）→（4，0）→（1，3）→（1，0）→（4，1）→（2，3）=目標2.3.1啟發(fā)式信息的表示例2.6利用啟發(fā)式信息去求解1432.3.1啟發(fā)式信息的表示

(2)啟發(fā)式函數(shù)能夠估計已找到的狀態(tài)與達到目標的有利程度。這樣的啟發(fā)式函數(shù)能夠有效地幫助決定那些后繼節(jié)點應被產(chǎn)生。2.3.1啟發(fā)式信息的表示1442.3.1啟發(fā)式信息的表示2831

6475

例2.7八數(shù)碼問題。1

238

4765a11a12a13a21a22a23a31a32a33

問題空間為：S0

Sg

2.3.1啟發(fā)式信息的表示283例2.71452.3.1啟發(fā)式信息的表示各狀態(tài)間的轉換規(guī)則為：Pr1:空格上移↑If□i，jandi≠1thenai-1,j←→□i，j

Pr2:空格下移↓If□i，jandi≠3thenai+1,j←→□i，j

2.3.1啟發(fā)式信息的表示各狀態(tài)間的轉換規(guī)則為：1462.3.1啟發(fā)式信息的表示Pr3:空格左移←If□i，jandj≠1thenai,j-1←→□i，j

Pr4:空格右移→If□i，jandj≠3thenai,j+1←→□i，j2.3.1啟發(fā)式信息的表示147f1(S5)=4啟發(fā)式函數(shù)f1=數(shù)字錯放位置的個數(shù)，f1=0，則達到目標。2831647528316475283147652831476523184765283164752831476528316475f1(S0)=4f1(S1)=3f1(S2)=5f1(S3)=5f1(S4)=3f1(S6)=3f1(S7)=4f1(S5)=4啟發(fā)式函數(shù)f1=數(shù)字錯放位置的個數(shù)，f1=1482.3.1啟發(fā)式信息的表示當f1值相同時如何決定走步?現(xiàn)在定義：F2=所有數(shù)字當前位置次最短路徑走到正確位置的步數(shù)之和。在這個定義之下，各狀態(tài)的啟發(fā)式函數(shù)值為：數(shù)碼12345678F2(S0）=1+1+0+0+0+1+0+2=5F2(S1）=1+1+0+0+0+0+0+2=42.3.1啟發(fā)式信息的表示當f1值相同時如何決定走步1492.3.1啟發(fā)式信息的表示數(shù)碼12345678

F2(