人工智能與或圖搜索課件.ppt

《人工智能與或圖搜索課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第四章與或圖搜索4.1問題歸約法當問題復雜時，可把初始問題分解成若干簡單的子問題，若子問題仍復雜，可再進一步分解，直到這些子問題的解可直接得到。這種問題的描述和求解方法，稱為問題歸約法?？芍苯咏獯鸬膯栴}稱為本原問題。歸約法的問題表示可由下列三部分組成：1）??????一個初始問題的描述2）??????一組把問題變成子問題的算符3）??????一組本原問題的描述4.2與或圖對問題歸約的描述可以很方便地用一個與或圖的結構來表示它。與節(jié)點：一個歸約算符能夠把單個問題變?yōu)閹讉€子問題組成的集合，這時所有子問題都有解，該父輩節(jié)點才有解。這種關系稱為“與

2、”關系，對應的節(jié)點成為與節(jié)點?；蚬?jié)點：幾個算符適用于同一個問題，從而產(chǎn)生不同的后繼問題集合。這時只要有一個后繼集合有解，則意味該父輩問題有解，此時關系是“或”關系，對應節(jié)點為或節(jié)點。在圖中N，M，H是或節(jié)點，B，C，D，E，F(xiàn)分別是與節(jié)點。ANMHBCDEF圖與節(jié)點和或節(jié)點與或節(jié)點是針對與或樹而言，對于一般的與或圖有歧義目標目標初始節(jié)點sabcK—連接符：假設節(jié)點N被某個算符歸約為一個包含K個子問題的替換集合，K?1，我們用一個叫做K—連接符的超弧線把它們和節(jié)點N連接起來。每個K—連接符從一個父節(jié)點指向一個含有K個后繼節(jié)點的集合，并說N有一

3、個外向連接符K。這種圖稱為超圖，但我們?nèi)园堰@種結構叫與或圖。問題歸約描述對應的結構就是一個與或圖，原始問題描述對應于起始節(jié)點（或根節(jié)點），本原問題所對應的節(jié)點叫做葉節(jié)點。在某些特殊情況下，不出現(xiàn)任何與節(jié)點，此時的圖成了普通圖，問題歸約描述也就成為狀態(tài)空間描述。4.3與或圖搜索在與或圖上執(zhí)行搜索的過程，其目的在于表明起始節(jié)點是有解的，也就是說，搜索不是去尋找目標節(jié)點，而是尋找一個解圖。定義：一個與或圖G中，從節(jié)點n到節(jié)點集N的解圖記為G?，G?是G的子圖。1．若n是N的一個元素，則G?由一節(jié)點組成；2．若n有一個指向節(jié)點{n1…,nk}的外向

4、連接符K，使得從每一個ni到N有一個解圖(i=1,…,k)，則G?由節(jié)點n，連接符K，及{n1,…,nk}中的每一個節(jié)點到N的解圖所組成；3．否則n到N不存在解圖。目標目標初始節(jié)點解圖：在搜索解圖的過程中，還需要進行耗散值的計算。設連接符的耗散值規(guī)定為：k-連接符的耗散值=k，若解圖的耗散值記為k(n,N)，則可遞歸計算如下：1．若n是N的一個元素，則k(n,N)=0；2．若n有一個外向連接符指向后繼節(jié)點(n1…,ni)，并設該連接符的耗散值為Cn，則k(n,N)=Cn+k(n1,N)+…+k(ni,N)具有最小耗散值的解圖稱為最佳解圖，其

5、值也用h*(n)標記。耗散值的計算:k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點集Cn為連接符的耗散值…...i個nn1n2ni搜索過程還要標記能解節(jié)點(SOLVED)，為此給出如下定義：能解節(jié)點終節(jié)點是能解節(jié)點若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。不能解節(jié)點沒有后裔的非終節(jié)點是不能解節(jié)點。若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。若非終節(jié)點有“與”子節(jié)點時，當至少有

6、一個子節(jié)點不能解時，該非終節(jié)點才不能解。不過與或圖搜索與狀態(tài)空間圖搜索有所不同，說明如下：搜索目的是證明起始節(jié)點是否可解，而可解節(jié)點是遞歸定義的，取決于后繼節(jié)點是否可解，即搜索是否找到葉節(jié)點。因此，搜索有可解標示過程和不可解標示過程。初始節(jié)點被標示為可解，則搜索成功結束，初始節(jié)點被標示為不可解，則搜索失敗。普通圖的情況f(n)=g(n)+h(n)對n的評價實際是對從s到n這條路徑的評價ns與或圖:對局部圖的評價目標目標初始節(jié)點abc兩個過程圖生成過程，即擴展節(jié)點從最優(yōu)的局部途中選擇一個節(jié)點擴展計算耗散值的過程對當前的局部圖新計算耗散值下面我

7、們討論一般與或圖的啟發(fā)式搜索算法——AO*算法。與A*算法不同，其評價函數(shù)f(n)=h(n)，只考慮h(n)這個分量，h(n)作為h*(n)的一個估計。過程AO*:1建立一個搜索圖G，G:=s，計算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；開始時圖G只包括s，耗散值估計為h(s)，若s是終節(jié)點,則標記上能解。2Untils已標記上SOLVED,do:3begin4G?:=FIND(G)；根據(jù)連接符標記（指針）找出一個待擴展的局部解圖G?，指針后面步驟有說明。5n:=G?中的任一非終節(jié)點;選一個非終結點作為當前節(jié)點

8、。6EXPAND(n),生成子節(jié)點集(ni)，G:=ADD((nj),G),計算q(nj)=h(nj)，其中nj?G，IFGOAL(nj)THENM(nj,SOLVED);把n的