問題求解的基本方法

№1人工智能技術(shù)的一個主要目的就是解決非平凡問題

非平凡問題：難以用常規(guī)（數(shù)值計算，數(shù)據(jù)庫應(yīng)用等）技術(shù)直接解決的問題知識貧乏系統(tǒng)——搜索技術(shù)知識豐富系統(tǒng)——識別技術(shù)№2本章內(nèi)容經(jīng)典搜索技術(shù)：一般圖搜索基于問題歸約的與或圖搜索

經(jīng)典的邏輯推理技術(shù)

基于歸結(jié)的謂詞演算基于規(guī)則的演繹推理

№3一般圖搜索啟發(fā)式搜索狀態(tài)空間抽象和生成-測試法啟發(fā)式搜索的適用性討論狀態(tài)空間搜索№4狀態(tài)空間及其搜索技術(shù)狀態(tài)空間描述待求解問題的狀態(tài)的集合搜索算法在狀態(tài)空間中搜索解答或解答路徑解決組合爆炸問題№5狀態(tài)空間定義狀態(tài)空間以SP指示，其可表示為一個二元組： SP=（S,O）S--在問題求解（即搜索）過程中所有可達(dá)的合法狀態(tài)構(gòu)成的集合；O--操作算子的集合，操作算子的執(zhí)行導(dǎo)致狀態(tài)的變遷。狀態(tài)空間可描述為一個有向圖，其節(jié)點指示狀態(tài)，節(jié)點間的有向弧表示狀態(tài)的變遷，用標(biāo)簽表示操作算子№6№7傳教士與野人例1：傳教士與野人問題（M-C問題） 問題：N個傳教士，N個野人，一條船，可同時乘坐k個人，要求在任何時刻(包括河的兩岸和船上），傳教士人數(shù)不能少于野人的人數(shù)。 問：如何過河。 以N=3，k=2為例求解?！?N=3，K=2變量m——傳教士在左岸或船上實際人數(shù)變量c——野人在左岸或船上的實際人數(shù)變量b指示船是否在左岸（值1指示船在左岸，否則為0）從而上述約束條件轉(zhuǎn)變?yōu)樵诖蟤+c<=2在岸上m>=c

№9№10問題狀態(tài)以三元組（m,c,b）表示則問題求解任務(wù)可描述為：

(3，3，1）→（0，0，0）

狀態(tài)空間可能的狀態(tài)總數(shù)為4×4×2=32這個問題總共只有16個可達(dá)的合法狀態(tài)

№11№12渡河問題中的操作算子可以定義2類：L(m,c)、R(m,c)

L(m,c)——指示從左岸到右岸的劃船操作

R(m,c)——從右岸回到左岸的劃船操作

m和c取值的可能組合只有5個：10，20，11，01，02故而總共有10個操作算子

№13規(guī)則集合：№14渡河問題的狀態(tài)空間有向圖：紅色小圓圈指示船在河的左岸藍(lán)色小圓圈指示船在河的右岸無數(shù)條操作路徑，但只有4條是最短

№15№16狀態(tài)空間的搜索以SE指示，其可表示為1個五元組：

SE=(S,O,E,I,G)

E--搜索引擎；

I--問題的初始狀態(tài)，I∈S;

G--問題的目標(biāo)狀態(tài)集，GS。解答路徑：狀態(tài)序列或相應(yīng)的操作算子調(diào)用序列

№17或關(guān)系：一個狀態(tài)有幾個操作算子供選擇這樣的有向圖，就稱為“或圖”狀態(tài)空間用“或圖”表示，稱為一般圖搜索圖——在搜索解答路徑的過程中只畫出搜索時直接涉及到的節(jié)點和弧線№18八數(shù)碼游戲№19№209!=362880

設(shè)計搜索策略（搜索算法）的關(guān)鍵考慮是解決組合爆炸問題

狀態(tài)圖、搜索圖和解答路徑的關(guān)系№21一般圖搜索策略1、搜索術(shù)語節(jié)點深度:根節(jié)點0，后面的節(jié)點遞歸定義路徑：由相鄰節(jié)點間的弧線構(gòu)成的折線節(jié)點擴展：應(yīng)用操作算子從節(jié)點ni變遷到nj

路徑代價——相臨節(jié)點ni和nj間路徑的代價記為

C（ni,nj

）包括兩部分：路徑本身代價和路徑搜索代價

路徑本身代價：操作算子的執(zhí)行代價

路徑搜索代價包括兩部分：路徑建立代價和路徑選擇代價№22設(shè)：目標(biāo)狀態(tài)相應(yīng)的節(jié)點：ng從ni到ng的路徑代價：C（ni,ng）=C（ni,nj）+C（nj,ng）假定：任意相臨節(jié)點間的路徑代價相同，代價為1№232、一般圖搜索算法定義：s——指示初始狀態(tài)節(jié)點G——指示搜索圖OPEN——作為存放待擴展節(jié)點的表CLOSE——作為存放已被擴展節(jié)點的表MOVE-FIRST（OPEN）——指示取OPEN表首的節(jié)點作為當(dāng)前要被擴展的節(jié)點n，同時將節(jié)點n移至CLOSE表SNS——子節(jié)點集合№24搜索算法的一般過程： 1）G:=s；

2）OPEN:=(s),CLOSE:=()；3）若OPEN是空表，則算法以失敗結(jié)束；4）n:=MOVE-FIRST(OPEN)；

5）若n是目標(biāo)狀態(tài)節(jié)點，則搜索成功結(jié)束，并給出解答路徑；

6）擴展節(jié)點n，將非節(jié)點n祖先的子節(jié)點置于子節(jié)點集合SNS中，并插入搜索圖G中；

№257）標(biāo)記和修改指針：

把SNS中的子節(jié)點分為三類：（1）全新節(jié)點，（2）已出現(xiàn)于OPEN表的節(jié)點，（3）已出現(xiàn)于CLOSE表的節(jié)點；

加第1類子節(jié)點于OPEN表，并建立從子節(jié)點到父節(jié)點n的指針；

比較第2類子節(jié)點經(jīng)由新、老父節(jié)點到達(dá)初始狀態(tài)節(jié)點s的路徑代價，若經(jīng)由新父節(jié)點的代價較小，則移動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點n

對于第3類子節(jié)點作與第2類同樣的處理，并把這些子節(jié)點從CLOSE表中移出，重新加入OPEN表；

8）按某種原則重新排序OPEN表中的節(jié)點；

9）返回語句3）；№26№273、盲目搜索優(yōu)化OPEN表中節(jié)點的排序方式

常用的方式是深度優(yōu)先和寬度優(yōu)先

№28深度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G:=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)記mj到n的指針;10,GOLOOP;№29№30深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關(guān)的方法№31寬度優(yōu)先搜索1,G:=G0(G0=s),OPEN:=(s),CLOSED:=();2,LOOP:IFOPEN=()THENEXIT(FAIL);3,n:=FIRST(OPEN);4,IFGOAL(n)THENEXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G:=ADD(mi,G);7,IF目標(biāo)在{