人工智能(問題求解基本原理及搜索技術

)人工智能問題求解基本原理問題求解：在給定條件下，尋求一個能解決某類問題且能在有限步驟內完成的算法。

問題求解特征：傳統軟件：

①求解的問題是能夠用數學精確描述的良結構的問題（如，解方程）；②計算機執行的繁雜的統計計算任務一般不能看成是人工智能活動。AI軟件：①求解的是不可直接用數學模型描述的所謂不良結構問題（如，幾何證明、求不定積分、邏輯演算等），通常需要采用弱方法進行搜索求解；②

AI程序中符號的內涵不僅局限于數值計算和數據處理中的一般數據信息，應表現人類進行推理所需要的各種知識。問題求解基本原理問題求解：在給定條件下，尋求一個能解決某類問問題求解基本原理一、問題求解的基本方法二、搜索技術問題求解基本原理一、問題求解的基本方法問題求解基本原理問題求解方法：基于狀態空間的問題求解方法基于問題空間的問題求解方法基于博弈搜索的問題求解方法問題求解基本原理問題求解方法：問題實例

桌上固定了3根柱子，按1，2，3次序排例。有n個大小全不一樣大的盤子d1，…，dn

，按從小到大，小的在上的次序依次插在第一根柱子上，要把這n個盤子全部搬到第三根柱子上，每次只許搬一個，任何時候都不允許把大盤子放在小盤子上面，問該如何搬法。設n=3，該如何搬法？1 23123梵塔問題問題實例桌上固定了3根柱子，按1，2，3次序基于狀態空間的問題求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。狀態合法變換規則（滿足約束條件）：狀態定義-（i大C,j中B,k小A）:設向量下標分別表示小盤A、中盤B、大盤C；向量值分別表示盤子所在柱子的編號。狀態描述-大盤C在第i根柱子上；中號盤B在第j根柱子上，小號盤A在第k根柱子上?；跔顟B空間的問題求解方法（1，1，1）→（1，1，2）狀基于問題空間的問題求解方法問題：如何將

i柱子上的m個盤子搬到k柱子上?將i柱子上的m–1個盤子搬到j柱子上；將i柱子上的第m個盤子搬到k柱子上；將j柱子上的m–1個盤子搬到k柱子上。

問題描述：問題（a,b,c):將b柱子上的a個盤子搬到c柱子上。問題分解合法規則： （3，1，3）--〉（2，1，2）(1，1，3）（2，2，3） 。。。。。。基于問題空間的問題求解方法問題：如何將i柱子上的m個基于問題空間的問題求解方法基于問題空間的問題求解方法狀態空間法有關概念

狀態空間法:從問題的初始狀態出發，通過一系列的狀態變換找到目標狀態的問題求解方法。

狀態：描述問題中事物形狀或狀況的符號或數據結構。

狀態空間：所有狀態的全體構成的集合；用四元組（S,S0,O,G)表示:S:非空狀態子集，S0=初始狀態（非空）。G:非空目標狀態子集。O:操作算子集合，一個狀態合法轉換為另一個狀態的描述規則

問題求解過程：隱含求一個普通有向圖，節點-狀態，邊–算子

搜索空間：問題求解過程中到達過的所有狀態（節點）的集合。狀態空間法有關概念狀態空間法:狀態：描述問題中事物形狀或狀態空間法有關概念狀態空間、搜索空間及解徑的關系：

問題的解（解徑）：初始狀態到目標狀態通路上的每一條規則（或狀態）構成序列，稱為解徑。解不唯一。S0

R1S2R2Sk…..RkG問題有解：從代表初始狀態s節點出發，存在一條通向目標節點的路徑。狀態空間法有關概念狀態空間、搜索空間及解徑的關系：問題的解問題空間法有關概念問題空間法：首先產生待證問題的所有子問題，而后通過解決所有子問題達到問題求解目的的方法。

問題：描述問題及其子問題的符號或數據結構。

問題空間：初始問題以及其所有子問題的全體構成的集合，用四元組（S,S0,F,G)

表示:

S:問題和子問題；S0

:初始問題。G:具有平凡解的本原問題集合。F:操作算子集合，用于將問題分解成其若干個子問題的描述規則問題空間法有關概念問題空間法：問題：描述問題及其子問題的符問題空間法的有關概念（2）問題空間分解過程：隱含求一個與或圖

節點

–問題，邊

-

分解問題的算子。

“與”節點：如果節點A有邊通向一組節點{B1，B2，…..Bn}，問題A的解決有待于A的子問題組{B1,B2…..Bn}的全部解決，則稱A為“與”節點。如圖a所示。

“或”節點：若節點Ａ有邊通向一組節點{{Ｂ１},{Ｂ2}，…{Ｂn}}，問題Ａ的解決有待于子問題Ｂ１或Ｂ2或…或Ｂn中某一個子問題的解決，則稱A為“或”節點。如圖b所示?！?..a:AB1B2Bn…...b:AB1B2Bn問題空間法的有關概念（2）問題空間分解過程：隱含求一個與或圖問題空間法有關概念（2）問題的解（解圖）：從代表初始問題的節點出發，搜索到一個完整的‘與或’子圖，圖中所有葉節點均滿足問題求解的結束條件。例：（C,B,Z)-〉（M,…M)重寫規則:R1:C(D,L)

R2:C(B,M)

R3:B(M,M)

R4:Z(B,B,M)

解圖問題空間法有關概念（2）問題的解（解圖）：從代表初始問題的節小結–問題求解方法比較狀態空間法問題空間法問題求解狀態變換問題分解搜索過程隱含構建普通有向圖隱含構建與或圖節點狀態問題邊狀態變換規則（算子）問題分解規則（算子）

求解解徑解圖小結–問題求解方法比較狀態空間法問題空問題求解基本原理一、問題求解的基本方法二、搜索技術（一）問題求解基本原理一、問題求解的基本方法搜索技術預備狀態空間搜索有關概念盲目搜索策略啟發式搜索策略問題求解基本原理搜索技術預備問題求解基本原理搜索策略預備盲目搜索：不考慮給定問題所具有的特定知識，系統按照事先確定好的某種固定順序調用規則，或是隨機地調用規則。

常用的盲目搜索算法:

深度優先搜索策略；寬度優先搜索策略搜索策略預備盲目搜索：常用的盲目搜索算法:搜索策略預備啟發式信息：與問題求解有關的信息和知識。由于信息的片面性和不準確性，應用啟發式信息不能百分之百地保證找到問題的解，但能提高問題求解的可能性。

啟發式信息在問題求解過程中的作用：有助于加速求解過程；有助于找到“較優”解。

啟發式搜索策略:考慮給定問題領域具有的特定知識（啟發式信息），系統動態地規定規則調用順序，優先使用“較”合適的規則。搜索策略預備啟發式信息：啟發式信息在問題求解過程中的作用：搜索策略預備常用的基于狀態圖的啟發式搜索策略:爬山搜索策略(HillClimbing)大英博物館搜索策略(BritishMuseum)啟發式圖搜索策略(A)最佳啟發式圖搜索策略(A*

)常用的基于與或圖及博弈的啟發式搜索策略：最佳啟發式與或圖搜索策略(AO*)極大極小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)搜索策略預備常用的基于狀態圖的啟發式搜索策略:常用的基基于狀態空間的搜索技術：

有關搜索概念

盲目搜索策略

啟發式搜索策略問題求解基本原理基于狀態空間的搜索技術：問題求解基本原理狀態空間搜索有關概念狀態圖特點：多條路徑通向同一節點。例：E狀態空間搜索有關概念狀態圖特點：多條路徑通向同一節點。例：狀態空間搜索有關概念狀態空間搜索有關概念狀態空間搜索有關概念節點深度：根節點的深度為0，其它節點的深度規定為其父節點的深度加1，即dn+1=dn+1。標記節點n：利用指針把后繼節點連接到父節點n的操作。節點：對應狀態圖中有關狀態的描述。擴展節點n：算符（規則）作用于節點n生成的新節點稱為節點n的后繼節點。生成節點n的所有后繼節點并計算生成這些后繼節點所使用的花費的過程叫做擴展節點n。狀態空間搜索有關概念節點深度：根節點的深度為0，其它節點路徑：對于一個節點序列（n0,n1,…,nl,…,nk），如若每一節點ni-1都有一個后繼節點ni（i=1,2,…,k），則稱該節點序列為一條從節點n0到節點nk、長度為k的路徑；路徑還可表示為與節點序列對應的規則序列。狀態空間搜索有關概念路徑花費：設C（ni，nj）為節點ni到nj這段路徑（或弧線）的花費。一條路徑的花費等于連接這條路徑各節點間所有弧線花費值的總和。路徑ni

→nj→t的花費值C（ni，t）可遞歸計算如下:

C（ni，t）=C(ni，nj)+C（nj，t)。路徑：對于一個節點序列（n0,n1,…,nl,…,基于狀態空間的盲目搜索算法:寬度優先搜索策略深度優先搜索策略問題求解基本原理基于狀態空間的盲目搜索算法:問題求解基本原理盲目搜索算法的符號及數據結構

s：

初始節點；n：當前節點。

open：

已被生成但未被擴展的節點序列表；closed：已被生成且已被擴展的節點序列表；{mi}={mj}∪{mk}∪{ml}：擴展n后所得的n的后繼節點其中，{mk}：在OPEN表中出現過的待擴展節點，{ml}：在CLOSED表中出現過的已擴展節點。{mj}：第一次生成的節點，mj∈OPEN且mj∈CLOSED表，盲目搜索算法的符號及數據結構s：初始節點寬度優先搜索算法

open:=[S];closed:=[];whileopen≠[]do{ n:=first(open); remove(first(open));

add(n,closed)；

ifn=goalthenexit(success); expand(n)->{mi}; delete((mi)(mi∈

{mk}∨

(mi∈{ml}

)

);

add(open,mj)};exit(fail);寬度優先搜索算法open:=[S];cl寬度優先搜索算法

1、S,A,D2、A,D,B,D3、D,B,A,E………Open表為隊操作：先進先出！寬度優先搜索算法1、S,A,D2、A,D,B,DG節點擴展順序寬度優先搜索算法

G節點擴展順序寬度優先搜索算法

open:=[S];closed:=[];d=深度限制值whileopen≠[]do{ n:=first(open); remove(first(open)); add(n,closed)；

ifn=goalthenexit(success); ifdepth(n)>dthencontinue; expand(n)->{mi}; delete((mi)(mi∈{mk}∨(mi∈{ml}

));

add(mj,open)};exit(fail);深度優先搜索算法 open:=[S];closed:=深度優先搜索算法

1、S2、A,D3、B,

D,D………Open表為棧操作：后進先出！4、C,

E,D深度優先搜索算法1、S2、A,D3、B,D,D………節點擴展順序深度優先搜索算法

節點擴展順序深度優先搜索算法盲目搜索算法應用實例-8數碼問題描述狀態：

矩陣(Sij)，其中

1≤i,j≤3，Sij∈{0,1,…,8};盲目搜索算法應用實例-8數碼問題描述狀態：盲目搜索算法應用實例-

合法走步規則：設(i0、j0)為空格所在行列數值，

Si0j0=0R1:ifj-1≥1thenSi0j0:=

Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=

S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=

Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=

S(i0+1)j0,S(i0+1)j0:=0空格下移。8數碼問題盲目搜索算法應用實例-合法走步規則：設(i0、j0)為寬度優先策略求解8數碼問題：目標R1R2R3R2R1R2R3R2R2R3R2R4R1R3寬度優先策略求解8數碼問題：目標R1R2R3R2R1R2R3深度優先策略求解8數碼問題：說明：

設規則固定使用順序：R1-左移、R2-上移、R3-右移、R4-下移；設節點深度限制值：6；合法的走步規則重復節點–造成循環深度優先策略求解8數碼問題：說明：合法的走步規則重復節點問題求解基本原理基于狀態空間的啟發式搜索算法:

A算法；A*算法問題求解基本原理基于狀態空間的啟發式搜索算法:啟發式圖搜索算法假設：

f(n)=g(n)+h(n)

–任意節點n的評價函數：指迄今為止已找到的從初始節點s，到達節點n，再從節點n到達目標節點t的路徑全程的最小費用，是對f*(n)的一個估計。

h(n)

：迄今為止從節點n到目標節點t最佳分段路徑將要花費的未知估計費用，是對h*(n)的一個估計，可視為啟發式分量函數，有h(n)≥0。

g(n)

：迄今為止搜索到的從初始節點s到當前節點n最佳路徑分段的已知費用，是對g*(n)的一個估計。

f*(n)=g*(n)+h*(n)：從初始節點s出發，經過最佳路徑上任意節點n，到達目標節點t的最小費用。

h*(n)：n→t最佳路徑的分段費用。

g*(n)：s→n最佳路徑的分段費用。

s：初始節點；n：當前節點；t：目標節點。啟發式圖搜索算法假設：f(n)=g(n)+h啟發式圖搜索算法-A算法

定義：按照f(n)=g(n)+h(n)估價函數值由小到大地排列待擴展節點順序的圖搜索算法，稱為A算法。

A算法流程。A算法應用實例:

普通有向圖A算法搜索實例；

8數碼問題A算法搜索實例。啟發式圖搜索算法-A算法定義：按照f(n)啟發式圖搜索算法-A算法算法中符號：s：初始節點；G：搜索圖的節點集合；OPEN表：已生成但尚未被擴展的節點序列表；CLOSED表：已生成且已被擴展的節點序列表；n：待擴展的當前節點；{mi}={mj}∪{mk}∪{ml}：擴展n后生成的后繼節點其中，mj：第一次生成的節點，mj∈OPEN且mj∈CLOSED表，mk：在OPEN表中出現過的待擴展節點，ml：在CLOSED表中出現過的已擴展節點。啟發式圖搜索算法-A算法算法中符號：A算法n為目標t?取當前節點nn:=first(OPEN),從OPEN中刪除n,CLOSED:=CLOSED∪{n}初始化G:=G0∪S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=Φ

^未發現目標tReturn(Fail)AyesNoyesNoBExit(Success)輸出解徑A算法n為目標t?取當前節點n初始化OPEN=Φ擴展節點n：生成n的后繼節點；計算后繼節點的花費。{mi}:=Expand(n),計算:f(n,mi):=g(n,mi)+h(mi)比較花費，修改連接標記

對于{mj}∈{mi}:OPEN:=OPEN∪{mj},mj->n;

對于{mk}∈{mi}:

iff(n,mk)<f(mk)thenf(mk):=f(n,mk),mk->n;

對于{ml}∈{mi}:iff(n,ml)<f(ml)thenf(ml):=f(n,ml),ml->n,OPEN:=OPEN∪{ml}將OPEN表中節點按f值從小到大重新排序AB擴展節點n：生成n的后繼節點；計算后繼節點的花費。比較花費，啟發式最佳圖搜索算法-A*算法A*算法定義：

若將A算法中評價函數f(n)的啟發式分量函數h（n）的值限制在h*（n）的下界范圍內，亦即對所有節點n，都滿足h（n）≤h*（n），則稱此時的A算法為A*算法。

A*算法作用：問題有解時，A*算法一定能夠找到從初始節點s到目標節點t的最佳解徑。啟發式最佳圖搜索算法-A*算法A*算法定義：A*算法信息性定理：有兩個A*算法A1和A2,若A2比A1有較多的啟發式信息（即對所有非目標節點均有：

h1（n）≤h2（n）≤h*（n）），則在具有一條從s到t的隱含狀態圖上，搜索結束時，由A2擴展的每一個節點，也必定由A1所擴展，即A1擴展的節點數至少和A2一樣多。啟發式最佳圖搜索算法-A*算法A*算法應用驗證:

8數碼問題A*算法搜索實例。信息性定理：啟發式最佳圖搜索算法-A*算法A*算法8數碼問題搜索策略比較：

寬度優先A算法A*算法8數碼問題搜索策略比較：寬度優先A算法小結啟發式搜索策略g:

考慮當前路徑已經花費的費用，及時拋棄已經經過的花費太大且距目標仍遠的路徑;h:

估計當前路徑上節點到目標節點還需要的費用，引導搜索向最有希望的路徑前進。

A算法：定義估計函數：f=g+h；

A*算法：定義估計函數：f=g+h； 滿足h（n）≤h*（n）。小結啟發式搜索策略g:h:A算法：定義估計函數：f程序實現寬度優先法和深度優先法求解High-waymap問題，給出求解過程（Open，Closed內容），標出解徑。作業:作業:給定兩個油桶,一個可裝4公斤油,一個可裝3公斤油,油桶上無任何度量標記。問：怎樣才能使4公斤油桶里恰好只裝2公斤油？ 設狀態定義：(x,y)，其中， x：4公斤油桶中實際裝油公斤數； y：3公斤油桶中實際裝油公斤數。 問題表示：(0,0)-〉(2,y) 要求定義合法的裝油規則，利用盲目搜索策略畫出狀態圖。作業:給定兩個油桶,一個可裝4公斤油,一個可裝3公斤油,油人工智能(問題求解基本原理及搜索技術

)人工智能問題求解基本原理問題求解：在給定條件下，尋求一個能解決某類問題且能在有限步驟內完成的算法。

問題求解特征：傳統軟件：

①求解的問題是能夠用數學精確描述的良結構的問題（如，解方程）；②計算機執行的繁雜的統計計算任務一般不能看成是人工智能活動。AI軟件：①求解的是不可直接用數學模型描述的所謂不良結構問題（如，幾何證明、求不定積分、邏輯演算等），通常需要采用弱方法進行搜索求解；②

AI程序中符號的內涵不僅局限于數值計算和數據處理中的一般數據信息，應表現人類進行推理所需要的各種知識。問題求解基本原理問題求解：在給定條件下，尋求一個能解決某類問問題求解基本原理一、問題求解的基本方法二、搜索技術問題求解基本原理一、問題求解的基本方法問題求解基本原理問題求解方法：基于狀態空間的問題求解方法基于問題空間的問題求解方法基于博弈搜索的問題求解方法問題求解基本原理問題求解方法：問題實例

桌上固定了3根柱子，按1，2，3次序排例。有n個大小全不一樣大的盤子d1，…，dn

，按從小到大，小的在上的次序依次插在第一根柱子上，要把這n個盤子全部搬到第三根柱子上，每次只許搬一個，任何時候都不允許把大盤子放在小盤子上面，問該如何搬法。設n=3，該如何搬法？1 23123梵塔問題問題實例桌上固定了3根柱子，按1，2，3次序基于狀態空間的問題求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。狀態合法變換規則（滿足約束條件）：狀態定義-（i大C,j中B,k小A）:設向量下標分別表示小盤A、中盤B、大盤C；向量值分別表示盤子所在柱子的編號。狀態描述-大盤C在第i根柱子上；中號盤B在第j根柱子上，小號盤A在第k根柱子上。基于狀態空間的問題求解方法（1，1，1）→（1，1，2）狀基于問題空間的問題求解方法問題：如何將

i柱子上的m個盤子搬到k柱子上?將i柱子上的m–1個盤子搬到j柱子上；將i柱子上的第m個盤子搬到k柱子上；將j柱子上的m–1個盤子搬到k柱子上。

問題描述：問題（a,b,c):將b柱子上的a個盤子搬到c柱子上。問題分解合法規則： （3，1，3）--〉（2，1，2）(1，1，3）（2，2，3） 。。。。。?；趩栴}空間的問題求解方法問題：如何將i柱子上的m個基于問題空間的問題求解方法基于問題空間的問題求解方法狀態空間法有關概念

狀態空間法:從問題的初始狀態出發，通過一系列的狀態變換找到目標狀態的問題求解方法。

狀態：描述問題中事物形狀或狀況的符號或數據結構。

狀態空間：所有狀態的全體構成的集合；用四元組（S,S0,O,G)表示:S:非空狀態子集，S0=初始狀態（非空）。G:非空目標狀態子集。O:操作算子集合，一個狀態合法轉換為另一個狀態的描述規則

問題求解過程：隱含求一個普通有向圖，節點-狀態，邊–算子

搜索空間：問題求解過程中到達過的所有狀態（節點）的集合。狀態空間法有關概念狀態空間法:狀態：描述問題中事物形狀或狀態空間法有關概念狀態空間、搜索空間及解徑的關系：

問題的解（解徑）：初始狀態到目標狀態通路上的每一條規則（或狀態）構成序列，稱為解徑。解不唯一。S0

R1S2R2Sk…..RkG問題有解：從代表初始狀態s節點出發，存在一條通向目標節點的路徑。狀態空間法有關概念狀態空間、搜索空間及解徑的關系：問題的解問題空間法有關概念問題空間法：首先產生待證問題的所有子問題，而后通過解決所有子問題達到問題求解目的的方法。

問題：描述問題及其子問題的符號或數據結構。

問題空間：初始問題以及其所有子問題的全體構成的集合，用四元組（S,S0,F,G)

表示:

S:問題和子問題；S0

:初始問題。G:具有平凡解的本原問題集合。F:操作算子集合，用于將問題分解成其若干個子問題的描述規則問題空間法有關概念問題空間法：問題：描述問題及其子問題的符問題空間法的有關概念（2）問題空間分解過程：隱含求一個與或圖

節點

–問題，邊

-

分解問題的算子。

“與”節點：如果節點A有邊通向一組節點{B1，B2，…..Bn}，問題A的解決有待于A的子問題組{B1,B2…..Bn}的全部解決，則稱A為“與”節點。如圖a所示。

“或”節點：若節點Ａ有邊通向一組節點{{Ｂ１},{Ｂ2}，…{Ｂn}}，問題Ａ的解決有待于子問題Ｂ１或Ｂ2或…或Ｂn中某一個子問題的解決，則稱A為“或”節點。如圖b所示?！?..a:AB1B2Bn…...b:AB1B2Bn問題空間法的有關概念（2）問題空間分解過程：隱含求一個與或圖問題空間法有關概念（2）問題的解（解圖）：從代表初始問題的節點出發，搜索到一個完整的‘與或’子圖，圖中所有葉節點均滿足問題求解的結束條件。例：（C,B,Z)-〉（M,…M)重寫規則:R1:C(D,L)

R2:C(B,M)

R3:B(M,M)

R4:Z(B,B,M)

解圖問題空間法有關概念（2）問題的解（解圖）：從代表初始問題的節小結–問題求解方法比較狀態空間法問題空間法問題求解狀態變換問題分解搜索過程隱含構建普通有向圖隱含構建與或圖節點狀態問題邊狀態變換規則（算子）問題分解規則（算子）

求解解徑解圖小結–問題求解方法比較狀態空間法問題空問題求解基本原理一、問題求解的基本方法二、搜索技術（一）問題求解基本原理一、問題求解的基本方法搜索技術預備狀態空間搜索有關概念盲目搜索策略啟發式搜索策略問題求解基本原理搜索技術預備問題求解基本原理搜索策略預備盲目搜索：不考慮給定問題所具有的特定知識，系統按照事先確定好的某種固定順序調用規則，或是隨機地調用規則。

常用的盲目搜索算法:

深度優先搜索策略；寬度優先搜索策略搜索策略預備盲目搜索：常用的盲目搜索算法:搜索策略預備啟發式信息：與問題求解有關的信息和知識。由于信息的片面性和不準確性，應用啟發式信息不能百分之百地保證找到問題的解，但能提高問題求解的可能性。

啟發式信息在問題求解過程中的作用：有助于加速求解過程；有助于找到“較優”解。

啟發式搜索策略:考慮給定問題領域具有的特定知識（啟發式信息），系統動態地規定規則調用順序，優先使用“較”合適的規則。搜索策略預備啟發式信息：啟發式信息在問題求解過程中的作用：搜索策略預備常用的基于狀態圖的啟發式搜索策略:爬山搜索策略(HillClimbing)大英博物館搜索策略(BritishMuseum)啟發式圖搜索策略(A)最佳啟發式圖搜索策略(A*

)常用的基于與或圖及博弈的啟發式搜索策略：最佳啟發式與或圖搜索策略(AO*)極大極小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)搜索策略預備常用的基于狀態圖的啟發式搜索策略:常用的基基于狀態空間的搜索技術：

有關搜索概念

盲目搜索策略

啟發式搜索策略問題求解基本原理基于狀態空間的搜索技術：問題求解基本原理狀態空間搜索有關概念狀態圖特點：多條路徑通向同一節點。例：E狀態空間搜索有關概念狀態圖特點：多條路徑通向同一節點。例：狀態空間搜索有關概念狀態空間搜索有關概念狀態空間搜索有關概念節點深度：根節點的深度為0，其它節點的深度規定為其父節點的深度加1，即dn+1=dn+1。標記節點n：利用指針把后繼節點連接到父節點n的操作。節點：對應狀態圖中有關狀態的描述。擴展節點n：算符（規則）作用于節點n生成的新節點稱為節點n的后繼節點。生成節點n的所有后繼節點并計算生成這些后繼節點所使用的花費的過程叫做擴展節點n。狀態空間搜索有關概念節點深度：根節點的深度為0，其它節點路徑：對于一個節點序列（n0,n1,…,nl,…,nk），如若每一節點ni-1都有一個后繼節點ni（i=1,2,…,k），則稱該節點序列為一條從節點n0到節點nk、長度為k的路徑；路徑還可表示為與節點序列對應的規則序列。狀態空間搜索有關概念路徑花費：設C（ni，nj）為節點ni到nj這段路徑（或弧線）的花費。一條路徑的花費等于連接這條路徑各節點間所有弧線花費值的總和。路徑ni

→nj→t的花費值C（ni，t）可遞歸計算如下:

C（ni，t）=C(ni，nj)+C（nj，t)。路徑：對于一個節點序列（n0,n1,…,nl,…,基于狀態空間的盲目搜索算法:寬度優先搜索策略深度優先搜索策略問題求解基本原理基于狀態空間的盲目搜索算法:問題求解基本原理盲目搜索算法的符號及數據結構

s：

初始節點；n：當前節點。

open：

已被生成但未被擴展的節點序列表；closed：已被生成且已被擴展的節點序列表；{mi}={mj}∪{mk}∪{ml}：擴展n后所得的n的后繼節點其中，{mk}：在OPEN表中出現過的待擴展節點，{ml}：在CLOSED表中出現過的已擴展節點。{mj}：第一次生成的節點，mj∈OPEN且mj∈CLOSED表，盲目搜索算法的符號及數據結構s：初始節點寬度優先搜索算法

open:=[S];closed:=[];whileopen≠[]do{ n:=first(open); remove(first(open));

add(n,closed)；

ifn=goalthenexit(success); expand(n)->{mi}; delete((mi)(mi∈

{mk}∨

(mi∈{ml}

)

);

add(open,mj)};exit(fail);寬度優先搜索算法open:=[S];cl寬度優先搜索算法

1、S,A,D2、A,D,B,D3、D,B,A,E………Open表為隊操作：先進先出！寬度優先搜索算法1、S,A,D2、A,D,B,DG節點擴展順序寬度優先搜索算法

G節點擴展順序寬度優先搜索算法

open:=[S];closed:=[];d=深度限制值whileopen≠[]do{ n:=first(open); remove(first(open)); add(n,closed)；

ifn=goalthenexit(success); ifdepth(n)>dthencontinue; expand(n)->{mi}; delete((mi)(mi∈{mk}∨(mi∈{ml}

));

add(mj,open)};exit(fail);深度優先搜索算法 open:=[S];closed:=深度優先搜索算法

1、S2、A,D3、B,

D,D………Open表為棧操作：后進先出！4、C,

E,D深度優先搜索算法1、S2、A,D3、B,D,D………節點擴展順序深度優先搜索算法

節點擴展順序深度優先搜索算法盲目搜索算法應用實例-8數碼問題描述狀態：

矩陣(Sij)，其中

1≤i,j≤3，Sij∈{0,1,…,8};盲目搜索算法應用實例-8數碼問題描述狀態：盲目搜索算法應用實例-

合法走步規則：設(i0、j0)為空格所在行列數值，

Si0j0=0R1:ifj-1≥1thenSi0j0:=

Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=

S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=

Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=

S(i0+1)j0,S(i0+1)j0:=0空格下移。8數碼問題盲目搜索算法應用實例-合法走步規則：設(i0、j0)為寬度優先策略求解8數碼問題：目標R1R2R3R2R1R2R3R2R2R3R2R4R1R3寬度優先策略求解8數碼問題：目標R1R2R3R2R1R2R3深度優先策略求解8數碼問題：說明：

設規則固定使用順序：R1-左移、R2-上移、R3-右移、R4-下移；設節點深度限制值：6；合法的走步規則重復節點–造成循環深度優先策略求解8數碼問題：說明：合法的走步規則重復節點問題求解基本原理基于狀態空間的啟發式搜索算法:

A算法；A*算法問題求解基本原理基于狀態空間的啟發式搜索算法:啟發式圖搜索算法假設：

f(n)=g(n)+h(n)

–任意節點n的評價函數：指迄今為止已找到的從初始節點s，到達節點n，再從節點n到達目標節點t的路徑全程的最小費用，是對f*(n)的一個估計。

h(n)

：迄今為止從節點n到目標節點t最佳分段路徑將要花費的未知估計費用，是對h*(n)的一個估計，可視為啟發式分量函數，有h(n)≥0。

g(n)

：迄今為止搜索到的從初始節點s到當前節點n最佳路徑分段的已知費用，是對g*(n)的一個估計。

f*(n)=g*(n)+h*(n)：從初始節點s出發，經過最佳路徑上任意節點n，到達目標節點t的最小費用。

h*(n)：n→t最佳路徑的分段費用。

g*(n)：s→n最佳路徑的分段費用。

s：初始節點；n：當前節點；t：目標節點。啟發式圖搜索算法假設：f(n)=g(n)+h啟發式圖搜索算法-A算法

定義：按照f(n)=g(n)+h(n)估價函數值由小到大地排列待擴展節點順序的圖搜索算法，稱為A算法。

A算法流程。A算法應用實例:

普通有向圖A算法搜索實例；

8數碼問題A算法搜索實例。啟發式圖搜索算法-A算法定義：按照f(n)啟發式圖搜索算法-A算法算法中符號：s：初始節點；G：搜索圖的節