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

Goto（U），（W，0，Y，z）goto（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圖搜索策略用一個四元表列（W，x，Y，z）表示這個問題狀態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猴子和香蕉問題的狀態空間圖提問：人工搜索求解的解答？目標狀態goto（U）goto（U）goto（U）U=b,pushbox（V）pushbox（V）goto（U）V≠c，climbboxV=c，climbbox3.1圖搜索策略4(b，1，b，0)（U，0，b，0）（V，0，V，0）（c5猴子和香蕉問題自動演示：

猴子香蕉箱子

猴子香蕉箱子

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

圖搜索過程框圖是是否否3.1圖搜索策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)寬度優先7開始把S放入OPEN表OPEN表為空表？把第一個節點(n)圖搜索的一般過程如下：1）建立一個只含有起始節點S的搜索圖G，把S放到一個叫做OPEN的未擴展節點表中。2）建立一個叫做CLOSED的已擴展節點表，其初始為空表.3）LOOP：若OPEN表是空表，則失敗退出。4）選擇OPEN表上的第一個節點，把它從OPEN表移出并放進CLOSED表中。稱此節點為節點n5）若n為一目標節點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設置)。83.1圖搜索策略圖搜索的一般過程如下：1）建立一個只含有起始節點S的搜索圖G6）擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。把M的這些成員作為n的后繼節點添入圖G中。7）對那些未曾在G中出現過的M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是否需更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節點的指針方向。8）按某一任意方式或按某個探試值，重排OPEN表。9）GOLOOP。93.1圖搜索策略6）擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節點的子圖。圖搜索的結果：1，一個完整的搜索圖G。2一個解路徑，用指針表示的解路徑。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始狀態2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2022/12/1010圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節點的子標記mj每個到n節點指針確定是否需要修改已在open，closed中的每個節點到n的指針確定是否需要修改已在closed中的每個節點的后繼節點原來的指針。8按照某種方式排列open表中的節點，goloop2022/12/1011標記mj每個到n節點指針2022/12/8112022/12/10122022/12/8122022/12/10132022/12/813思考：（1）結果路徑的形成中，為什么其節點順序是明確的？（2）OPEN表中的節點具有什么特點？（3）CLOSED表中的節點具有什么特點？（4）對OPEN表節點的排序有何意義？提出：盲目搜索與啟發式搜索。143.1圖搜索策略思考：143.1圖搜索策略3.2盲目搜索盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。特點：不需重排OPEN表；種類：寬度優先、深度優先、等代價搜索等。153.2.1寬度優先搜索（Breadth-first）

定義：

以接近起始節點的程度逐層擴展節點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。3.2盲目搜索盲目搜索又叫做無信息搜索，一般只適用于16SLOMFPQNFFF寬度優先搜索示意圖16SLOMFPQNFFF寬度優先搜索示意圖1）把起始節點放到OPEN表中(如果該起始節點為一目標節點，則求得一個解答)。2）如果OPEN是個空表，則沒有解，失敗退出；否則繼續。3）把第一個節點(節點n)從OPEN表移出，并把它放入CLOSED的擴展節點表中。4）擴展節點n。如果沒有后繼節點，則轉向上述第(2)步。5）把n的所有后繼節點放到OPEN表的末端，并提供從這些后繼節點回到n的指針。6）如果n的任一個后繼節點是個目標節點，則找到一個解答，成功退出；否則轉向第(2)步。17寬度優先搜索算法：3.2盲目搜索1）把起始節點放到OPEN表中(如果該起始節點為一目標節點，18開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針失敗成功圖3.2寬度優先算法框圖是否是否3.2盲目搜索思考：與原始算法比較異同，寬度優先的體現？18開始把S放入OPEN表OPEN表為空表？把第一個節點(n2022/12/1019寬度優先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2022/12/819寬度優先算法Procedruebre2022/12/1020

標記每個到n節點指針，按照節點深度遞增順序排列open中的節點

8goloop

理論上可以利用寬度優先搜索能夠找到解，如果問題有解的話。討論：寬度優先算法和深度優先算法可能出現組合爆炸。都沒有利用任何啟發式信息，所以稱為無信息搜索策略。2022/12/820標記每個到n節點指針，按2022/12/1021：寬度優先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態是A在B上，B在桌子上，C在桌子上；目標狀態是：A、B、C依次從上到下排列在桌子上。如圖2022/12/821：寬度優先例題：2022/12/1022解：1）狀態描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態時（B、T、T）,目標狀態可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的

c同一種狀態出現不得多于一次。2022/12/822解：1）狀態描述（P1，P2，P3）表2022/12/10231）解題過程2）open表和closed表3）節點樣子畫出整個圖G和解路徑4）程序何時結束5）改用深度優先如何？2022/12/8231）解題過程2）open表和clos

例子

八數碼難題（8-puzzleproblem）

241238456712384567（目標狀態）（初始狀態）規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。從圖可見，要擴展26個節點，共生成46個節點之后才求得解（目標節點）。3.2盲目搜索例子

八數碼難題（8-puzzleproblem）24253.2盲目搜索253.2盲目搜索3.2.2

深度優先搜索(Dephth-first)26

定義：

首先擴展最新產生的(即最深的)節點。

特點：

防止搜索過程沿著無益的路徑擴展下去，往往給出一個節點擴展的最大深度——深度界限。與寬度優先搜索算法最根本的不同在于：將擴展的后繼節點放在OPEN表的前端。3.2盲目搜索3.2.2深度優先搜索(Dephth-first)26深度優先搜索示意圖27SLOMFPQNFFF3.2盲目搜索深度優先搜索示意圖27SLOMFPQNFFF3.2盲目搜索28開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的前端，提供返回節點n的指針失敗成功圖3.6深度優先算法框圖是否是否3.2盲目搜索節點n的深度等于最大深度？否28開始把S放入OPEN表OPEN表為空表？把第一個節點(n2022/12/1029深度優先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中標記mj每個到n節點指針，按照節點深度遞減順序排列open中的節點

8goloop2022/12/829深度優先算法Procedruedep示范：有界深度(4)優先的八數碼問題深度優先搜索樹？303.2盲目搜索1238456712384567（目標狀態）（初始狀態）303.2盲目搜索1238456712384567（目標狀313.2盲目搜索313.2盲目搜索2022/12/1032討論1：如果問題有解，用深度優先搜索算法，是否能夠找到解？

不一定.解空間是否有限？討論2：本算法的改進之處是open中節點按照深度優先排列，但是沒有對深度加以控制，可能造成搜索代價太大2022/12/832討論1：如果問題有解，用深度優先搜索算3.2.3

等代價搜索33

定義

是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。

算法

在等價搜索算法中，把從節點i到其后續節點j的連接弧線記為c(I,j),把從起始節點S到任一節點I的路徑代價記為g(i)。在搜索樹上，假設g(i)也是從起始節點S到節點的最少代價路徑上的代價。3.2盲目搜索思考：如何動態計算g(i)?3.2.3等代價搜索33定義是寬度優先搜索的一34開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功圖3.8等代價搜索算法框圖是否是否令g(s)=0S是否目標節點？是成功否3.2盲目搜索擴展i，計算其后繼節點j的g(j)，并把后繼節點放入OPEN表34開始把S放入OPEN表OPEN表為空表？把具有最小g(i課后例題講解1.設有如圖所示的一棵與/或樹，請用與/或樹的寬度優先搜索及與/或樹的深度優先搜索求出解樹。35課后例題講解1.設有如圖所示的一棵與/或樹，請用與/或樹的解：（1）與/或樹的寬度優先搜索先擴展節點A，得到節點B和C；再擴展節點B,得節點t1、t2，因為t1、t2為可解節點，故節點B可解，從而可節點A可解。所以求得解樹為：36解：（1）與/或樹的寬度優先搜索36（2）與/或樹的深度優先搜索先擴展節點A,得到節點B和C；再擴展節點C,得節點D和t5；t5為可解節點，再擴展節D，得節點t3、t4；t3、t4為可解節點，故節點D可解，因為節點D和t5可解故節點C可解，從而可節點A可解。所以求得解樹為：37（2）與/或樹的深度優先搜索372.下圖是5個城市的交通圖，城市之間的連線旁邊的數字是城市之間路程的費用。要求從A城出發，經過其它各城市一次且僅一次，最后回到A城，請找出一條最優線路。等代價搜索382.下圖是5個城市的交通圖，城市之間的連線旁邊的數字是城市之3.3啟發式搜索啟發式信息：用來加速搜索過程的問題領域信息，一般與有關問題具體領域背景有關，不一定具有通用性。啟發式搜索：利用啟發式信息的搜索方法特點：重排OPEN表，選擇最有希望的節點加以擴展種類：有序搜索、A*算法等39基本步驟：初始化，判斷OPEN表是否為空，選擇節點n，判斷n是否目標節點，擴展節點n，重排OPEN表、調整指針，循環。各自特點：重排OPEN表的依據不同。盲目搜索可能帶來組合爆炸。思考：（1）圖搜索方法的基本步驟？（2）寬度優先、深度優先、等代價方法的特點？

（3）盲目搜索的缺點？3.3啟發式搜索39基本步驟：初始化，判斷OPEN表是否有序搜索（OrderedSearch）總是選擇“最有希望”的節點作為下一被擴展節點估價函數（EvaluationFunction）為獲得某些節點“希望”的啟發信息，提供一個評定侯選擴展節點的方法，以便確定哪個節點最有可能在通向目標的最佳路徑上。

f(n)——表示節點n的估價函數值

應用節點“希望”程度（估價函數值）重排OPEN表；有序搜索也稱為最佳優先搜索；估價函數舉例：（1）棋局的得分；（2）距離目標狀態的距離量度；（3）TSP問題中的路徑；思考：f函數的計算，重排序的方法？403.3.1啟發式搜索策略和估價函數3.3啟發式搜索有序搜索（OrderedSearch）403.3.1啟發413.3.2

有序搜索（OrderedSearch；Best－firstSearch）實質：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。3.3啟發式搜索Nilsson（尼爾遜）方法：一個節點的“希望”越大，則其f值越小。被選擇的節點是估價函數最小的節點。思考：如果把寬度優先、深度優先、等代價搜索方法作為有序搜索的特例，那么它們的f

函數如何計算？ 舉例示范。413.3.2有序搜索（OrderedSearch；B42開始把S放入OPEN表，計算估價函數

f(s)OPEN表為空表？選取OPEN表中f值最小的節點i放入CLOSED表i為目標節點嗎？擴展i，得后繼節點j，計算f(j)，提供返回節點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發式搜索算法42開始把S放入OPEN表，計算估價函數f(s)OPEN八數碼難題43（2）如下的八數碼難題（8-puzzleproblem）12384567（目標狀態）12384567（初始狀態）（3）八數碼難題的有序搜索樹見下圖：3.3啟發式搜索（1）估價函數設置：

f(n)=d(n)+W(n)

d(n):節點n的深度；W(n):錯放的棋子數

八數碼難題43（2）如下的八數碼難題（8-puzzlepr443.3啟發式搜索443.3啟發式搜索f

函數的重要性有序搜索的有效性直接取決于f,是提高搜索效率的關鍵；如果f

不準確，可能失去最佳解，也可能失去全部解；f

一般選擇策略搜索時間與空間的折衷；保證有解或有最佳解；f

選擇的三種典型情況：（1）最優解答：狀態空間中有多條解答路徑，求解最優解答，如A*算法；（2）搜索代價與解答質量的綜合：問題類似于（1），但搜索過程可能超出時間與空間的界限。在適當的搜索實驗中找到滿意解答，并限制滿意解答與最優解答的差異程度；如：TSP問題；（3）最小搜索代價：不考慮解答的最優化（只有一個解答或多個解答間無差異），盡量使搜索代價最小；如：定理證明。思考：（1）f不能識別某些節點的真實“希望”值會怎么樣？（2）f過多估計了全部節點又會怎么樣？453.3啟發式搜索f函數的重要性453.3啟發式搜索3.3.3A*算法思考：經過節點n的最佳路徑，怎么表示？怎么求解最優解答路徑。估價函數f*：對節點n定義f*(n)=g*(n)+h*(n),表示從S開始通過節點n的一條最佳路徑的代價。其中g*(n)表示從起始節點S到n的最佳路徑，h*(n)表示從n到某目標節點的最佳路徑。估價函數f

：f(n)=g(n)+h(n)；其中g是g*的估計，h是h*的估計；g的一個選擇就是搜索樹中從S到n的這段路徑的代價；顯然有g(n)≥g*(n)；h

的依賴于領域的啟發信息，比如八數碼問題中的W(n),h

稱為啟發式函數；463.3啟發式搜索3.3.3A*算法思考：經過節點n的最佳路徑，怎么表示？A*算法：

定義1

在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據f(x)=g(x)+h(x)進行的，則稱該過程為A算法。定義2

在A算法中，如果對所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。定義3

采用h*(x)的下界h(x)為啟發函數的A算法，稱為A*算法。當h=0時，A*算法就變為等代價搜索算法。47A*算法：

47A*算法總框圖48開始把S放入OPEN表，記f=hOPEN=NIL?失敗BESTNODE是目標節點？成功擴展BESTNODE，產生后續節點SUCCESSOR否否

是

是A*子過程選取OPEN表上未設置過的具有最小f值的節點BESTNODE,放入CLOSED表中A*算法總框圖48開始把S放入OPEN表，記f=hOP49SUC屬于OPEN？SUC屬于CLOSED？SUC=OLD，把它添加到BESTNODE的后續節點表中g(SUC)<g(OLD)?重新確定OLD的父輩節點為BESTNODE，并修訂父輩節點的g、f值，記下g（OLD）計算f的值把SUCCESSOR放入OPEN表，添進BESTNODE的后裔表是否

是否否

是計算g(SUC)=g(BES)+h(BES,SUC)建立從SUCCESSOR返回BESTNODE的指針A*算法子過程49SUC屬于OPEN？SUC屬于CLOSED？SUC=OL思考：（1）寬度優先搜索、深度優先搜索與等代價搜索的關系？（2）有序與A*算法等搜索方法的關系？（3）等代價搜索與A*算法的關系？基于狀態空間搜索算法的智能系統應用領域：問題求解（智能問題）：迷宮下棋軟件：國際象棋，圍棋，中國象棋等策略游戲：RPG，50思考：503.1圖搜索策略3.2盲目搜索3.3啟發式搜索3.4消解原理3.5規則演繹系統51第三章搜索推理技術3.6產生式系統3.7非單調推理3.8小結問題：知識表示有那些方法？知識表示的目的是什么？構建智能系統的關鍵是什么？3.1圖搜索策略1第三章搜索推理技術3.6產生式系統3.1圖搜索策略思考：狀態空間法的基本特點？基本推理方法？其求解結果是什么？簡單回顧實例：猴子與香蕉。523.1圖搜索策略思考：狀態空間法的基本特點？基本推理方用一個四元表列（W，x，Y，z）表示這個問題狀態W猴子的水平位置x當猴子在箱子頂上時取x=1；否則取x=0Y箱子的水平位置z 當猴子摘到香蕉時取z=1；否則取z=0算符：

Goto（U），（W，0，Y，z）goto（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）533.1圖搜索策略用一個四元表列（W，x，Y，z）表示這個問題狀態33.1圖54(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猴子和香蕉問題的狀態空間圖提問：人工搜索求解的解答？目標狀態goto（U）goto（U）goto（U）U=b,pushbox（V）pushbox（V）goto（U）V≠c，climbboxV=c，climbbox3.1圖搜索策略4(b，1，b，0)（U，0，b，0）（V，0，V，0）（c55猴子和香蕉問題自動演示：

猴子香蕉箱子

猴子香蕉箱子

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

圖搜索過程框圖是是否否3.1圖搜索策略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)寬度優先7開始把S放入OPEN表OPEN表為空表？把第一個節點(n)圖搜索的一般過程如下：1）建立一個只含有起始節點S的搜索圖G，把S放到一個叫做OPEN的未擴展節點表中。2）建立一個叫做CLOSED的已擴展節點表，其初始為空表.3）LOOP：若OPEN表是空表，則失敗退出。4）選擇OPEN表上的第一個節點，把它從OPEN表移出并放進CLOSED表中。稱此節點為節點n5）若n為一目標節點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設置)。583.1圖搜索策略圖搜索的一般過程如下：1）建立一個只含有起始節點S的搜索圖G6）擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。把M的這些成員作為n的后繼節點添入圖G中。7）對那些未曾在G中出現過的M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是否需更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節點的指針方向。8）按某一任意方式或按某個探試值，重排OPEN表。9）GOLOOP。593.1圖搜索策略6）擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節點的子圖。圖搜索的結果：1，一個完整的搜索圖G。2一個解路徑，用指針表示的解路徑。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始狀態2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2022/12/1060圖搜索策略圖搜索的實質是從問題空間中找出一張包含目標節點的子標記mj每個到n節點指針確定是否需要修改已在open，closed中的每個節點到n的指針確定是否需要修改已在closed中的每個節點的后繼節點原來的指針。8按照某種方式排列open表中的節點，goloop2022/12/1061標記mj每個到n節點指針2022/12/8112022/12/10622022/12/8122022/12/10632022/12/813思考：（1）結果路徑的形成中，為什么其節點順序是明確的？（2）OPEN表中的節點具有什么特點？（3）CLOSED表中的節點具有什么特點？（4）對OPEN表節點的排序有何意義？提出：盲目搜索與啟發式搜索。643.1圖搜索策略思考：143.1圖搜索策略3.2盲目搜索盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。特點：不需重排OPEN表；種類：寬度優先、深度優先、等代價搜索等。653.2.1寬度優先搜索（Breadth-first）

定義：

以接近起始節點的程度逐層擴展節點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。3.2盲目搜索盲目搜索又叫做無信息搜索，一般只適用于66SLOMFPQNFFF寬度優先搜索示意圖16SLOMFPQNFFF寬度優先搜索示意圖1）把起始節點放到OPEN表中(如果該起始節點為一目標節點，則求得一個解答)。2）如果OPEN是個空表，則沒有解，失敗退出；否則繼續。3）把第一個節點(節點n)從OPEN表移出，并把它放入CLOSED的擴展節點表中。4）擴展節點n。如果沒有后繼節點，則轉向上述第(2)步。5）把n的所有后繼節點放到OPEN表的末端，并提供從這些后繼節點回到n的指針。6）如果n的任一個后繼節點是個目標節點，則找到一個解答，成功退出；否則轉向第(2)步。67寬度優先搜索算法：3.2盲目搜索1）把起始節點放到OPEN表中(如果該起始節點為一目標節點，68開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針失敗成功圖3.2寬度優先算法框圖是否是否3.2盲目搜索思考：與原始算法比較異同，寬度優先的體現？18開始把S放入OPEN表OPEN表為空表？把第一個節點(n2022/12/1069寬度優先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中2022/12/819寬度優先算法Procedruebre2022/12/1070

標記每個到n節點指針，按照節點深度遞增順序排列open中的節點

8goloop

理論上可以利用寬度優先搜索能夠找到解，如果問題有解的話。討論：寬度優先算法和深度優先算法可能出現組合爆炸。都沒有利用任何啟發式信息，所以稱為無信息搜索策略。2022/12/820標記每個到n節點指針，按2022/12/1071：寬度優先例題：由一張桌子T、三個積木A、B、C組成一個積木世界，初始狀態是A在B上，B在桌子上，C在桌子上；目標狀態是：A、B、C依次從上到下排列在桌子上。如圖2022/12/821：寬度優先例題：2022/12/1072解：1）狀態描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其中Pi是積木或者桌子。初始狀態時（B、T、T）,目標狀態可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y上；約束條件:aX頂部必須是空的b如果Y是積木，Y的頂部必須是空的

c同一種狀態出現不得多于一次。2022/12/822解：1）狀態描述（P1，P2，P3）表2022/12/10731）解題過程2）open表和closed表3）節點樣子畫出整個圖G和解路徑4）程序何時結束5）改用深度優先如何？2022/12/8231）解題過程2）open表和clos

例子

八數碼難題（8-puzzleproblem）

741238456712384567（目標狀態）（初始狀態）規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。從圖可見，要擴展26個節點，共生成46個節點之后才求得解（目標節點）。3.2盲目搜索例子

八數碼難題（8-puzzleproblem）24753.2盲目搜索253.2盲目搜索3.2.2

深度優先搜索(Dephth-first)76

定義：

首先擴展最新產生的(即最深的)節點。

特點：

防止搜索過程沿著無益的路徑擴展下去，往往給出一個節點擴展的最大深度——深度界限。與寬度優先搜索算法最根本的不同在于：將擴展的后繼節點放在OPEN表的前端。3.2盲目搜索3.2.2深度優先搜索(Dephth-first)26深度優先搜索示意圖77SLOMFPQNFFF3.2盲目搜索深度優先搜索示意圖27SLOMFPQNFFF3.2盲目搜索78開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的前端，提供返回節點n的指針失敗成功圖3.6深度優先算法框圖是否是否3.2盲目搜索節點n的深度等于最大深度？否28開始把S放入OPEN表OPEN表為空表？把第一個節點(n2022/12/1079深度優先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始狀態2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先輩節點7open←add(open，mj)//mj不在open，closed中標記mj每個到n節點指針，按照節點深度遞減順序排列open中的節點

8goloop2022/12/829深度優先算法Procedruedep示范：有界深度(4)優先的八數碼問題深度優先搜索樹？803.2盲目搜索1238456712384567（目標狀態）（初始狀態）303.2盲目搜索1238456712384567（目標狀813.2盲目搜索313.2盲目搜索2022/12/1082討論1：如果問題有解，用深度優先搜索算法，是否能夠找到解？

不一定.解空間是否有限？討論2：本算法的改進之處是open中節點按照深度優先排列，但是沒有對深度加以控制，可能造成搜索代價太大2022/12/832討論1：如果問題有解，用深度優先搜索算3.2.3

等代價搜索83

定義

是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。

算法

在等價搜索算法中，把從節點i到其后續節點j的連接弧線記為c(I,j),把從起始節點S到任一節點I的路徑代價記為g(i)。在搜索樹上，假設g(i)也是從起始節點S到節點的最少代價路徑上的代價。3.2盲目搜索思考：如何動態計算g(i)?3.2.3等代價搜索33定義是寬度優先搜索的一84開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功圖3.8等代價搜索算法框圖是否是否令g(s)=0S是否目標節點？是成功否3.2盲目搜索擴展i，計算其后繼節點j的g(j)，并把后繼節點放入OPEN表34開始把S放入OPEN表OPEN表為空表？把具有最小g(i課后例題講解1.設有如圖所示的一棵與/或樹，請用與/或樹的寬度優先搜索及與/或樹的深度優先搜索求出解樹。85課后例題講解1.設有如圖所示的一棵與/或樹，請用與/或樹的解：（1）與/或樹的寬度優先搜索先擴展節點A，得到節點B和C；再擴展節點B,得節點t1、t2，因為t1、t2為可解節點，故節點B可解，從而可節點A可解。所以求得解樹為：86解：（1）與/或樹的寬度優先搜索36（2）與/或樹的深度優先搜索先擴展節點A,得到節點B和C；再擴展節點C,得節點D和t5；t5為可解節點，再擴展節D，得節點t3、t4；t3、t4為可解節點，故節點D可解，因為節點D和t5可解故節點C可解，從而可節點A可解。所以求得解樹為：87（2）與/或樹的深度優先搜索372.下圖是5個城市的交通圖，城市之間的連線旁邊的數字是城市之間路程的費用。要求從A城出發，經過其它各城市一次且僅一次，最后回到A城，請找出一條最優線路。等代價搜索882.下圖是5個城市的交通圖，城市之間的連線旁邊的數字是城市之3.3啟發式搜索啟發式信息：用來加速搜索過程的問題領域信息，一般與有關問題具體領域背景有關，不一定具有通用性。啟發式搜索：利用啟發式信息的搜索方法特點：重排OPEN表，選擇最有希望的節點加以擴展種類：有序搜索、A*算法等89基本步驟：初始化，判斷OPEN表是否為空，選擇節點n，判斷n是否目標節點，擴展節點n，重排OPEN表、調整指針，循環。各自特點：重排OPEN表的依據不同。盲目搜索可能帶來組合爆炸。思考：（1）圖搜索方法的基本步驟？（2）寬度優先、深度優先、等代價方法的特點？

（3）盲目搜索的缺點？3.3啟發式搜索39基本步驟：初始化，判斷OPEN表是否有序搜索（OrderedSearch）總是選擇“最有希望”的節點作為下一被擴展節點估價函數（EvaluationFunction）為獲得某些節點“希望”的啟發信息，提供一個評定侯選擴展節點的方法，以便確定哪個節點最有可能在通向目標的最佳路徑上。

f(n)——表示節點n的估價函數值

應用節點“希望”程度（估價函數值）重排OPEN表；有序搜索也稱為最佳優先搜索；估價函數舉例：（1）棋局的得分；（2）距離目標狀態的距離量度；（3）TSP問題中的路徑；思考：f函數的計算，重排序的方法？903.3.1啟發式搜索策略和估價函數3.3啟發式搜索有序搜索（OrderedSearch）403.3.1啟發913.3.2

有序搜索（OrderedSearch；Best－firstSearch）實質：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。3.3啟發式搜索Nilsson（尼爾遜）方法：一個節點的“希望”越大，則其f值越小。被選擇的節點是估價函數最小的節點。思考：如果把寬度優先、深度優先、等代價搜索方法作為有序搜索的特例，那么它們的f

函數如何計算？ 舉例示范。413.3.2有序搜索（OrderedSearch；B92開始把S放入OPEN表，計算估價函數

f(s)OPEN表為空表？選取OPEN表中f值最小的節點i放入CLOSED表i為目標節點嗎？擴展i，得后繼節點j，計算f(j)，提供返回節點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針失敗成功圖3.9有序搜