1、3.1 圖搜索策略3.2 盲目搜索3.3 啟發(fā)式搜索3.4 消解原理3.5 規(guī)則演繹系統(tǒng)1第三章 搜索推理技術3.6 產(chǎn)生式系統(tǒng)3.7非單調(diào)推理3.8小結問題：知識表示有那些方法？知識表示的目的是什么？構建智能系統(tǒng)的關鍵是什么？3.1圖搜索策策略思考：狀狀態(tài)空間間法的基基本特點點？基本本推理方方法？其其求解結結果是什什么？簡簡單回顧顧實例：猴子與與香蕉。2用一個四四元表列列（W，x，Y，z）表示這個個問題狀狀態(tài)W猴子的水水平位置置x當猴子在在箱子頂頂上時取取x =1；否則取取x =0Y箱子的水水平位置置z當猴子摘摘到香蕉蕉時取z=1；否則取取z=0算符：Goto（U），（W，0，Y，z）got

2、o（U）（U，0，Y，z）Pushbox（V），（W，0，W，z）pushbox（V）（V，0，V，z）Climbbox，（W，0，W，z）climbbox（W，1，W，z）Grasp，（c，1，c，0）grasp（c，1，c，1）33.1圖搜索策策略4(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）U=b，climbbox猴子和香香蕉問題題的狀態(tài)態(tài)空間圖圖提問：人人工搜索索求解的的解答？目標狀態(tài)態(tài)goto（U）goto（U）goto（U）U=b, pushbox（V）pushbox（V）goto（U）Vc，clim

3、bboxV=c，climbbox3.1圖搜索策策略5猴子和香香蕉問題題自動演演示： 猴子香蕉箱子 猴子香蕉箱子 Ha!Ha!3.1圖搜索策策略思考：計計算機的的搜索策策略？圖搜索控控制策略略:一種在圖圖中尋找找路徑的的方法。圖中每個個節(jié)點對對應一個個狀態(tài);每條連線線對應一一個操作作符。圖搜索過過程（GraphSearch）63.1圖搜索策策略7開始把S放入OPEN表OPEN表為空表表？把第一個個節(jié)點(n)從OPEN表移至CLOSED表n為目標節(jié)節(jié)點嗎？把n的后繼節(jié)節(jié)點放入入OPEN表的末端端，提供供返回節(jié)節(jié)點n的指針修改指針針方向重排OPEN表失敗成功圖3.1圖搜索過過程框圖圖是是否否3.1圖

4、搜索策策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)寬度優(yōu)先先圖搜索的的一般過過程如下下：1）建立一一個只含含有起始始節(jié)點S的搜索圖圖G，把S放到一個個叫做OPEN的未擴展節(jié)節(jié)點表中。2）建立一一個叫做做CLOSED的已擴展節(jié)節(jié)點表，其初初始為空空表.3）LOOP：若OPEN表是空表表，則失失敗退出出。4）選擇OPEN表上的第第一個節(jié)節(jié)點，把把它從OPEN表移出并并放進CLOSED表中。稱稱此節(jié)點點為節(jié)點點n5）若n為一目標標節(jié)點，則有解解并成功功退出，此解是是追蹤圖圖G中沿著指指針從n到S這條路徑徑而得到的的(指針將在在第7步中設置置)。83.1圖

5、搜索策策略6）擴展節(jié)節(jié)點n，同時生生成不是是n的祖先的的那些后后繼節(jié)點點的集合合M。把M的這些成成員作為為n的后繼節(jié)節(jié)點添入入圖G中。7）對那些些未曾在在G中出現(xiàn)過過的M成員設置置一個通通向n的指針。把M的這些成成員加進進OPEN表。對已已經(jīng)在OPEN或CLOSED表上的每每一個M成員，確確定是否否需更改改通到n的指針方方向。對對已在CLOSED表上的每每個M成員，確確定是否否需要更更改圖G中通向它它的每個個后裔節(jié)節(jié)點的指指針方向向。8）按某一一任意方方式或按按某個探探試值，重排OPEN表。9）GOLOOP。93.1圖搜索策策略圖搜索策策略圖搜索的的實質(zhì)是是從問題空空間中找找出一張張包含目目標

6、節(jié)點點的子圖圖。圖搜索的的結果：1，一個完完整的搜搜索圖G。2一個解路路徑，用指針針表示的的解路徑徑。ProcedureGraphSearch1 G=G0(G0=s),open=(s)/s:初始狀態(tài)態(tài)2 closed=()3Loop:ifopen=() thenexit(fall)4nfirst(open)remove(n,open),add(n,closed)5ifgoal(n) thenexit(success)6mj expand(n), /mj不含n的先輩節(jié)節(jié)點7 openadd(open，mj) / mj不在open，closed中2020-02-1110標記mj每個到n節(jié)點指針針確

7、定是否否需要修修改已在在open，closed中的每個個節(jié)點到到n的指針確定是否否需要修修改已在在closed中的每個個節(jié)點的的后繼節(jié)節(jié)點原來來的指針針。8按照某種種方式排排列open表中的節(jié)節(jié)點，goloop2020-02-11112020-02-11122020-02-1113思考：（1）結果路路徑的形形成中，為什么么其節(jié)點點順序是是明確的的？（2）OPEN表中的節(jié)節(jié)點具有有什么特特點？（3）CLOSED表中的節(jié)節(jié)點具有有什么特特點？（4）對OPEN表節(jié)點的的排序有有何意義義？提出：盲盲目搜索索與啟發(fā)發(fā)式搜索索。143.1圖搜索策策略3.2盲目搜索索盲目搜索索又叫做做無信息搜搜索，一般只只

8、適用于于求解比比較簡單單的問題題。特點：不不需重排排OPEN表；種類：寬寬度優(yōu)先先、深度度優(yōu)先、等代價價搜索等等。153.2.1 寬度優(yōu)先搜索（Breadth-first） 定義： 以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。 特點：一種高代價搜索，但若有解存在，則必能找到它。16SLOMFPQNFFF寬度優(yōu)先先搜索示示意圖1）把起始始節(jié)點放放到OPEN表中(如果該起起始節(jié)點點為一目目標節(jié)點點，則求求得一個個解答)。2）如果OPEN是個空表表，則沒沒有解，失敗退退出；否否則繼續(xù)續(xù)。3）把第一一個節(jié)點點(節(jié)點n)從OPEN表移出，并把它它放入CLOSED的擴展節(jié)節(jié)點表中中。4）擴展節(jié)節(jié)點n。如果

9、沒沒有后繼繼節(jié)點，則轉(zhuǎn)向向上述第第(2)步。5）把n的所有后后繼節(jié)點點放到OPEN表的末端端，并提提供從這這些后繼繼節(jié)點回回到n的指針。6）如果n的任一個個后繼節(jié)節(jié)點是個個目標節(jié)節(jié)點，則則找到一一個解答答，成功功退出；否則轉(zhuǎn)轉(zhuǎn)向第(2)步。17寬度優(yōu)先先搜索算算法：3.2盲目搜索索18開始把S放入OPEN表OPEN表為空表表？把第一個個節(jié)點(n)從OPEN表移至CLOSED表是否有后后繼節(jié)點點為目標節(jié)節(jié)點？擴展n，把n的后繼節(jié)節(jié)點放入入OPEN表的末端，提供供返回節(jié)節(jié)點n的指針失敗成功圖3.2寬度優(yōu)先先算法框框圖是否是否3.2盲目搜索索思考：與與原始算算法比較較異同，寬度優(yōu)優(yōu)先的體體現(xiàn)？202

10、0-02-1119寬度優(yōu)先先算法Procedruebreadth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始狀態(tài)態(tài)2 Loop: if open=()thenexit(fall)3 nfirst(open)4 if goal(n)thenexit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先輩節(jié)節(jié)點7 openadd(open，mj) / mj不在open，closed中2020-02-1120 標記每個個到n節(jié)點指針針，按照照節(jié)點深深度遞增增順序排排列open中

11、的節(jié)點點8goloop理論上可可以利用用寬度優(yōu)優(yōu)先搜索索能夠找找到解，如果問問題有解解的話。討論：寬寬度優(yōu)先先算法和和深度優(yōu)優(yōu)先算法法可能出出現(xiàn)組合合爆炸。都沒有有利用任任何啟發(fā)發(fā)式信息息，所以以稱為無無信息搜搜索策略略。2020-02-1121：寬度優(yōu)先先例題：由一張桌桌子T、三個積積木A、B、C組成一個個積木世世界，初初始狀態(tài)態(tài)是A在B上，B在桌子上上，C在桌子上上；目標標狀態(tài)是是：A、B、C依次從上上到下排排列在桌桌子上。如圖2020-02-1122解：1）狀態(tài)描描述（P1，P2，P3）表示按按A、B、C順序依次次分別在在P1,P2,P3上其中Pi是積木或或者桌子子。初始始狀態(tài)時時（B、

12、T、T）,目標狀態(tài)態(tài) 可以以表示（B、C、T）2）定義操操作:move(x,y)表示將積積木x移到Y上；約束條件件:aX頂部必須須是空的的b如果Y是積木，Y的頂部必必須是空空的c同一種狀狀態(tài)出現(xiàn)現(xiàn)不得多多于一次次。2020-02-11231）解題過過程2）open表和closed表3）節(jié)點樣樣子畫出出整個圖圖G和解路徑徑4）程序何何時結束束5）改用深深度優(yōu)先先如何？例子八數(shù)碼難難題（8-puzzleproblem）241238456712384567（目標狀態(tài)）（初始狀狀態(tài)）規(guī)定：將牌移入入空格的的順序為為：從空空格左邊邊開始順順時針旋旋轉(zhuǎn)。不不許斜向向移動，也不返返回先輩輩節(jié)點。從圖可可見，

13、要要擴展26個節(jié)點，共生成成46個節(jié)點之之后才求求得解（目標節(jié)節(jié)點）。3.2盲目搜索索253.2盲目搜索索3.2.2深度優(yōu)先先搜索(Dephth-first)26定義：首先擴展展最新產(chǎn)產(chǎn)生的(即最深的的)節(jié)點。特點：防止搜索索過程沿沿著無益益的路徑徑擴展下下去，往往往給出出一個節(jié)節(jié)點擴展展的最大大深度深度界限限。與寬度優(yōu)優(yōu)先搜索索算法最最根本的的不同在在于：將將擴展的的后繼節(jié)節(jié)點放在在OPEN表的前端端。3.2盲目搜索索深度優(yōu)先先搜索示示意圖27SLOMFPQNFFF3.2盲目搜索索28開始把S放入OPEN表OPEN表為空表表？把第一個個節(jié)點(n)從OPEN表移至CLOSED表是否有后后繼節(jié)點

14、點為目標節(jié)節(jié)點？擴展n，把n的后繼節(jié)節(jié)點放入入OPEN表的前端，提供供返回節(jié)節(jié)點n的指針失敗成功圖3.6深度優(yōu)先先算法框框圖是否是否3.2盲目搜索索節(jié)點n的深度等等于最大大深度？否2020-02-1129深度優(yōu)先先算法Procedruedepth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始狀態(tài)態(tài)2 Loop:ifopen=()then exit(fall)3 nfirst(open)4 if goal(n)thenexit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n

15、的先輩節(jié)節(jié)點7 openadd(open，mj) / mj不在open，closed中標記mj每個到n節(jié)點指針針，按照照節(jié)點深深度遞減減順序排排列open中的節(jié)點點8goloop示范：有有界深度度(4)優(yōu)先的八八數(shù)碼問問題深度度優(yōu)先搜搜索樹？303.2盲目搜索索1238456712384567（目標狀態(tài)）（初始狀狀態(tài)）313.2盲目搜索索2020-02-1132討論1：如果問問題有解解，用深深度優(yōu)先先搜索算算法，是是否能夠夠找到解解？不一定.解空間是是否有限限？討論2：本算法法的改進進之處是是open中節(jié)點按按照深度度優(yōu)先排排列，但但是沒有有對深度度加以控控制，可可能造成成搜索代代價太大大3.

16、2.3等代價搜搜索33 定義是寬度優(yōu)先先搜索的一種推推廣，不不是沿著著等長度度路徑斷斷層進行行擴展，而是沿沿著等代代價路徑徑斷層進進行擴展展。搜索樹中中每條連連接弧線線上的有有關代價價,表示時間間、距離離等花費費。 算法在等價搜搜索算法法中，把把從節(jié)點點i到其后續(xù)續(xù)節(jié)點j的連接弧弧線記為為c(I,j),把從起始始節(jié)點S到任一節(jié)節(jié)點I的路徑代代價記為為g(i)。在搜索索樹上，假設g(i)也是從起起始節(jié)點點S到節(jié)點的的最少代代價路徑徑上的代代價。3.2盲目搜索索思考：如如何動態(tài)態(tài)計算g(i)?34開始把S放入OPEN表OPEN表為空表表？把具有最小小g(i)值的節(jié)點點i從OPEN表移至CLOSED

17、表是否有后后繼節(jié)點點為目標節(jié)節(jié)點？失敗成功圖3.8等代價搜搜索算法法框圖是否是否令g(s)=0S是否目標標節(jié)點？是成功否3.2盲目搜索索擴展i，計算其其后繼節(jié)節(jié)點j的g(j)，并把后后繼節(jié)點點放入OPEN表課后例題題講解1.設有如圖圖所示的的一棵與與/或樹，請請用與/或樹的寬度優(yōu)先先搜索及與/或樹的深度優(yōu)先先搜索求出解樹樹。35解：（1）與/或樹的寬寬度優(yōu)先先搜索先擴展節(jié)節(jié)點A，得到節(jié)節(jié)點B和C；再擴展節(jié)節(jié)點B,得節(jié)點t1、t2，因為t1、t2為可解節(jié)節(jié)點，故故節(jié)點B可解，從從而可節(jié)節(jié)點A可解。所以求得得解樹為為：36（2）與/或樹的深深度優(yōu)先先搜索先擴展節(jié)節(jié)點A,得到節(jié)點點B和C；再擴展節(jié)節(jié)

18、點C,得節(jié)點D和t5；t5為可解節(jié)節(jié)點，再再擴展節(jié)節(jié)D，得節(jié)點點t3、t4；t3、t4為可解節(jié)節(jié)點，故故節(jié)點D可解，因因為節(jié)點點D和t5可解故節(jié)節(jié)點C可解，從從而可節(jié)節(jié)點A可解。所以求得得解樹為為：372.下圖是5個城市的的交通圖圖，城市市之間的的連線旁旁邊的數(shù)數(shù)字是城城市之間間路程的的費用。要求從從A城出發(fā)，經(jīng)過其其它各城城市一次次且僅一一次，最最后回到到A城，請找找出一條條最優(yōu)線線路。等代價搜搜索383.3啟發(fā)式搜搜索啟發(fā)式信信息：用來加速速搜索過過程的問問題領域域信息，一般與與有關問問題具體體領域背背景有關關，不一一定具有有通用性性。啟發(fā)式搜搜索：利用啟發(fā)發(fā)式信息息的搜索索方法特點：重排

19、OPEN表，選擇擇最有希希望的節(jié)節(jié)點加以以擴展種類：有有序搜索索、A*算法等39基本步驟驟：初始化，判斷OPEN表是否為為空，選選擇節(jié)點點n，判斷n是否目標標節(jié)點，擴展節(jié)節(jié)點n，重排OPEN表、調(diào)整整指針，循環(huán)。各自特點點：重排OPEN表的依據(jù)據(jù)不同。盲目搜索索可能帶帶來組合合爆炸。思考： （1）圖搜索索方法的的基本步步驟？（2）寬度優(yōu)優(yōu)先、深深度優(yōu)先先、等代代價方法法的特點點？（3）盲目搜搜索的缺缺點？有序搜索索（Ordered Search）總是選擇擇“最有希望望”的節(jié)點作作為下一一被擴展展節(jié)點估價函數(shù)數(shù)（Evaluation Function）為獲得某某些節(jié)點點“希望”的啟發(fā)信信息，提提

20、供一個個評定侯侯選擴展展節(jié)點的的方法，以便確確定哪個個節(jié)點最最有可能能在通向向目標的的最佳路路徑上。f(n)表示節(jié)點點n的估價函函數(shù)值應用節(jié)點點“希望”程度（估估價函數(shù)數(shù)值）重重排OPEN表；有序序搜索也也稱為最佳優(yōu)先先搜索；估價函數(shù)數(shù)舉例：（1）棋局的的得分；（2）距離目目標狀態(tài)態(tài)的距離離量度；（3）TSP問題中的的路徑；思考：f函數(shù)的計計算，重重排序的的方法？403.3.1啟發(fā)式搜搜索策略略和估價價函數(shù)3.3啟發(fā)式搜搜索413.3.2有序搜索索（Ordered Search；BestfirstSearch）實質(zhì)：選擇OPEN表上具有有最小f值的節(jié)點點作為下下一個要要擴展的的節(jié)點。3.3啟發(fā)

21、式搜搜索Nilsson（尼爾遜遜）方法法：一個節(jié)點點的“希望”越大，則則其f值越小。被選擇擇的節(jié)點點是估價價函數(shù)最最小的節(jié)節(jié)點。思考：如如果把寬寬度優(yōu)先先、深度度優(yōu)先、等代價價搜索方方法作為為有序搜搜索的特特例，那那么它們們的f函數(shù)如何何計算？舉例示范范。42開始把S放入OPEN表，計算算估價函函數(shù)f(s)OPEN表為空表表？選取OPEN表中f值最小的的節(jié)點i放入CLOSED表i為目標節(jié)節(jié)點嗎？擴展i，得后繼繼節(jié)點j，計算f(j)，提供返返回節(jié)點點i的指針，利用f(j)對OPEN表重新排排序，調(diào)調(diào)整親子子關系及及指針失敗成功圖3.9有序搜索索算法框框圖是否是否3.3啟發(fā)式搜搜索算法八數(shù)碼難難題

22、43（2）如下的的八數(shù)碼碼難題（8-puzzleproblem）12384567（目標狀態(tài)）12384567（初始狀態(tài)）（3）八數(shù)碼難難題的有有序搜索索樹見下下圖：3.3啟發(fā)式搜搜索（1）估價函函數(shù)設置置：f(n) =d(n) +W(n)d(n):節(jié)點n的深度；W(n):錯放的棋棋子數(shù)443.3啟發(fā)式搜搜索f函數(shù)的重重要性有序搜索索的有效效性直接接取決于于f,是提高搜搜索效率率的關鍵鍵；如果f不準確，可能失失去最佳佳解，也也可能失失去全部部解；f一般選擇擇策略搜索時間間與空間間的折衷衷；保證有解解或有最最佳解；f選擇的三三種典型型情況：（1）最優(yōu)解解答：狀狀態(tài)空間間中有多多條解答答路徑，求解最

23、最優(yōu)解答答，如A*算法；（2）搜索代代價與解解答質(zhì)量量的綜合合：問題題類似于于（1），但搜搜索過程程可能超超出時間間與空間間的界限限。在適適當?shù)乃阉阉鲗嶒烌炛姓业降綕M意解解答，并并限制滿滿意解答答與最優(yōu)優(yōu)解答的的差異程程度；如如：TSP問題；（3）最小搜搜索代價價：不考考慮解答答的最優(yōu)優(yōu)化（只只有一個個解答或或多個解解答間無無差異），盡量量使搜索索代價最最小；如如：定理理證明。思考： （1）f不能識別別某些節(jié)節(jié)點的真真實“希希望”值值會怎么么樣？（2）f過多估計計了全部部節(jié)點又又會怎么么樣？453.3啟發(fā)式搜搜索3.3.3A*算法思考：經(jīng)經(jīng)過節(jié)點點n的最佳路路徑，怎怎么表示示？怎么求解解最優(yōu)解解答路徑。估價函數(shù)數(shù)f*：對節(jié)點點n定義f*(n)=g*(n)+h*(n),表示從S開始通過過節(jié)點n的一條最最佳路徑徑的代價價。其中中g*(n)表示從起起始節(jié)點點S到n的最佳路路徑，h*(n)表示從n到某目標標節(jié)點的的最佳路路徑。估價函數(shù)數(shù)f：f(n)=g(n)+h(n)；其中g是g*的估計，h是h*的估計；g的一個選選擇就是是搜索樹樹中從S到n的這段