1、人 工 智 能 ( 問題求解基本原理及搜索技術(shù) ),問題求解基本原理,問題求解：在給定條件下，尋求一個能解決某類問題且能在有限步驟內(nèi)完成的算法。,問題求解特征： 傳統(tǒng)軟件： 求解的問題是能夠用數(shù)學(xué)精確描述的良結(jié)構(gòu)的問題（如，解方程）； 計算機執(zhí)行的繁雜的統(tǒng)計計算任務(wù)一般不能看成是人工智能活動。,AI軟件： 求解的是不可直接用數(shù)學(xué)模型描述的所謂不良結(jié)構(gòu)問題（如，幾何證明、求不定積分、邏輯演算等），通常需要采用弱方法進行搜索求解； AI程序中符號的內(nèi)涵不僅局限于數(shù)值計算和數(shù)據(jù)處理中的一般數(shù)據(jù)信息，應(yīng)表現(xiàn)人類進行推理所需要的各種知識。,問題求解基本原理,一、問 題 求 解 的 基 本 方 法 二、搜

2、 索 技 術(shù),問題求解基本原理,問題求解方法： 基于狀態(tài)空間的問題求解方法 基于問題空間的問題求解方法 基于博弈搜索的問題求解方法,問題實例,桌上固定了 3 根柱子，按 1，2，3 次序排例。有 n 個大小全不一樣大的盤子d1，dn ，按從小到大，小的在上的次序依次插在第一根柱子上，要把這 n 個盤子全部搬到第三根柱子上，每次只許搬一個，任何時候都不允許把大盤子放在小盤子上面，問該如何搬法。 設(shè) n = 3，該如何搬法？,1 2 3 1 2 3,梵塔問題,基于狀態(tài)空間的問題求解方法,（1，1，1） （1，1，2） （1，1，1） （1，1，3） （1，1，2） （1，3，2） 。,狀態(tài)合法變換

3、規(guī)則（滿足約束條件）：,狀態(tài)定義 -（i大, j中, k小 ）: 設(shè)向量下標分別表示大盤、中盤、小盤；向量值分別表示盤子所在柱子的編號。 狀態(tài)描述 - 大盤在第 i 根柱子上；中號盤在第 j 根柱子上，小號盤在第 k 根柱子上。,基于問題空間的問題求解方法,問題：如何將 i 柱子上的 m 個盤子搬到 k 柱子上 ? 將 i 柱子上的 m 1 個盤子搬到 j 柱子上； 將 i 柱子上的 第 m 個盤子搬到 k 柱子上； 將 j 柱子上的 m 1 個盤子搬到 k 柱子上。,問題描述： 問題（a, b, c): 將 b 柱子上的 a 個盤子搬到 c 柱子上。 問題分解合法規(guī)則： （3，1，3）-（2

4、，1，2） (1，1，3） （2，2，3） 。,基于問題空間的問題求解方法,狀態(tài)空間法有關(guān)概念,狀態(tài)空間法: 從問題的初始狀態(tài)出發(fā)，通過一系列的狀態(tài)變換找到目標狀態(tài)的問題求解方法。,狀態(tài)：描述問題中事物形狀或狀況的符號或數(shù)據(jù)結(jié)構(gòu)。,狀態(tài)空間：所有狀態(tài)的全體構(gòu)成的集合；用四元組（S, S0, O, G) 表示: S: 非空狀態(tài)子集，S0 = 初始狀態(tài)（非空）。 G: 非空目標狀態(tài)子集。 O: 操作算子集合，一個狀態(tài)合法轉(zhuǎn)換為另一個狀態(tài)的描述規(guī)則,問題求解過程：隱含求一個普通有向圖，節(jié)點 - 狀態(tài)，邊 算子,搜索空間：問題求解過程中到達過的所有狀態(tài)（節(jié)點）的集合。,狀態(tài)空間法有關(guān)概念,狀態(tài)空間、搜

5、索空間及解徑的關(guān)系：,問題有解：從代表初始狀態(tài) s 節(jié)點出發(fā)， 存在一條通向目標節(jié)點的路徑。,問題空間法有關(guān)概念,問題空間法： 首先產(chǎn)生待證問題的所有子問題，而后通過解決所有子問題達到問題求解目的的方法。,問題：描述問題及其子問題的符號或數(shù)據(jù)結(jié)構(gòu)。,問題空間：初始問題以及其所有子問題的全體構(gòu)成的集合，用四元組（S, S0, F, G) 表示: S: 問題和子問題； S0 : 初始問題。 G: 具有平凡解的本原問題集合。 F: 操作算子集合，用于將問題分解成其若干個子問題的描述規(guī)則,問題空間法的有關(guān)概念（2）,問題空間分解過程：隱含求一個與或圖 節(jié)點 問題， 邊 - 分解問題的算子。,“與” 節(jié)

6、點：如果節(jié)點 A 有邊通向一組節(jié)點 B1，B2，.Bn ，問題 A 的解決有待于 A 的子問題組 B1,B2.Bn 的全部解決，則稱 A 為“與” 節(jié)點。如圖 a 所示。,“或” 節(jié)點：若節(jié)點有邊通向一組節(jié)點,2，n，問題的解決有待于子問題或2或或n中某一個子問題的解決，則稱 A 為“或” 節(jié)點。如圖 b 所示。,問題空間法有關(guān)概念（2）,問題的解（解圖）：從代表初始問題的節(jié)點出發(fā)，搜索到一個完整的與或 子圖，圖中所有葉節(jié)點均滿足問題求解的結(jié)束條件。,例：（C,B,Z) -（M,M) 重寫規(guī)則: R1: C ( D, L ) R2: C ( B, M ) R3: B ( M, M) R4: Z

7、 ( B, B,M ),小結(jié) 問題求解方法比較,問題求解基本原理,一、問 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) （一）,搜索技術(shù)預(yù)備 狀態(tài)空間搜索 有關(guān)概念 盲目搜索策略 啟發(fā)式搜索策略,問題求解基本原理,搜索策略預(yù)備,盲目搜索： 不考慮給定問題所具有的特定知識，系統(tǒng)按照事先確定好的某種固定順序調(diào)用規(guī)則，或是隨機地調(diào)用規(guī)則。,常用的盲目搜索算法: 深度優(yōu)先搜索策略； 寬度優(yōu)先搜索策略,搜索策略預(yù)備,啟發(fā)式信息： 與問題求解有關(guān)的信息和知識。 由于信息的片面性和不準確性，應(yīng)用啟發(fā)式信息不能百分之百地保證找到問題的解，但能提高問題求解的可能性。,啟發(fā)式信息在問題求解過程中的作用： 有

8、助于加速求解過程； 有助于找到“較優(yōu)”解。,啟發(fā)式搜索策略: 考慮給定問題領(lǐng)域具有的特定知識（啟發(fā)式信息），系統(tǒng)動態(tài)地規(guī)定規(guī)則調(diào)用順序，優(yōu)先使用“較”合適的規(guī)則。,搜索策略預(yù)備,常用的基于狀態(tài)圖的啟發(fā)式搜索策略 : 爬山搜索策略 (Hill Climbing) 大英博物館搜索策略 (British Museum) 啟發(fā)式圖搜索策略 ( A ) 最佳啟發(fā)式圖搜索策略 ( A* ),常用的基于與或圖及博弈的啟發(fā)式搜索策略： 最佳啟發(fā)式與或圖搜索策略 ( AO* ) 極大極小搜索策略 (Minimax) 剪枝搜索策略 (Alpha-Beta Pruning),基于狀態(tài)空間的搜索技術(shù)： 有關(guān)搜索概念

9、盲目搜索策略 啟發(fā)式搜索策略,問題求解基本原理,狀態(tài)空間搜索有關(guān)概念,狀態(tài)圖特點：多條路徑通向同一節(jié)點。例：,狀態(tài)空間搜索有關(guān)概念,狀態(tài)空間搜索有關(guān)概念,節(jié)點深度： 根節(jié)點的深度為0，其它節(jié)點的深度規(guī)定為其父節(jié) 點的深度加 1，即dn+1 = dn + 1 。,標記節(jié)點 n：用指針將后繼節(jié)點連接到父節(jié)點 n 的操作 。,節(jié)點：對應(yīng)狀態(tài)圖中有關(guān)狀態(tài)的描述。,擴展節(jié)點n：稱生成節(jié)點 n 的所有后繼節(jié)點并計算生成這些后繼節(jié)點所造成的花費的過程（ 即，計算各后繼節(jié)點的優(yōu)劣且將其連接到節(jié)點 n 等操作造成的開銷 ）叫做擴展節(jié)點 n 。,后繼節(jié)點：稱將規(guī)則作用于節(jié)點 n 生成的新節(jié)點為節(jié)點 n 的后繼節(jié)點

10、。,路徑：對于一個節(jié)點序列（n0, n1, , nl, , nk），如若每一節(jié)點 ni-1都有一個后繼節(jié)點 ni（i = 1, 2, , k），則稱該節(jié)點序列為一條從節(jié)點 n0 到節(jié)點 nk、長度為 k 的路徑；路徑還可表示為與節(jié)點序列對應(yīng)的規(guī)則序列 。,狀態(tài)空間搜索有關(guān)概念,路徑花費：設(shè) C（ni，nj）為節(jié)點 ni 到 nj 這段路徑（或弧線）的花費。一條路徑的花費等于連接這條路徑各節(jié)點間所有弧線花費值的總和。路徑 ni nj t 的花費值C（ni，t）可遞歸計算如下: C（ni，t）= C (ni，nj) + C（nj，t )。,基于狀態(tài)空間的盲目搜索算法: 寬度優(yōu)先搜索策略 深度優(yōu)先搜

11、索策略,問題求解基本原理,盲目搜索算法的符號及數(shù)據(jù)結(jié)構(gòu),s： 初始節(jié)點；n：當前節(jié)點。,open： 已被生成但未被擴展的節(jié)點序列表；,closed：已被生成且已被擴展的節(jié)點序列表；,mi = mj mk ml：擴展 n 后所得的 n 的后繼節(jié)點 其中，, mk ：在OPEN表中出現(xiàn)過的待擴展節(jié)點，, ml ：在CLOSED表中出現(xiàn)過的已擴展節(jié)點。,寬度優(yōu)先搜索算法,open := S; closed := ; while open do n := first ( open ); remove ( first ( open ) ); add ( n, closed )； if n = goal

12、then exit ( success ); expand ( n ) - mi ; delete ( (mi)( mi mk ( mi ml ) ); add ( open, mj) ; exit ( fail );,寬度優(yōu)先搜索算法,1、S, A, D,2、A, D, B, D,3、D, B, A, E,Open 表為隊 操 作： 先進先出！,節(jié)點擴展順序,寬度優(yōu)先搜索算法,open := S; closed := ; d = 深度限制值 while open do n := first ( open ); remove ( first ( open ) ); add ( n, close

13、d )； if n = goal then exit ( success ); if depth ( n ) d then continue; expand ( n ) - mi ; delete ( (mi)( mi mk ( mi ml ) ); add ( mj, open ) ; exit ( fail );,深度優(yōu)先搜索算法,深度優(yōu)先搜索算法,1、S,2、A, D,3、B, D, D,Open表為棧 操 作：后進先出！,4、C, E, D,節(jié)點擴展順序,深度優(yōu)先搜索算法,盲目搜索算法應(yīng)用實例-,8數(shù)碼問題,描述狀態(tài)： 矩陣(Sij)，其中 1i,j3，Sij0,1,8;,盲目搜索算法

14、應(yīng)用實例 -,合法走步規(guī)則：,設(shè) (i0、j0)為空格所在行列數(shù)值，Si0j0 = 0 R1: if j-11 then Si0j0:=Si0(j0-1), Si0(j0-1):=0 空格左移； R2: if i-11 then Si0j0:=S(i0-1)j0, S(i0-1)j0:=0 空格上移； R3: if j+13 then Si0j0:=Si0(j0+1), Si0(j0+1):=0 空格右移； R4: if i+13 then Si0j0:=S(i0+1)j0, S(i0+1)j0:=0 空格下移。,8數(shù)碼問題,寬度優(yōu)先策略求解8數(shù)碼問題：,深度優(yōu)先策略求解8數(shù)碼問題：,說明：

15、設(shè)規(guī)則固定使用順序： R1- 左移、R2-上移、R3- 右移、R4-下移； 設(shè)節(jié)點深度限制值：6 ；,合法的走步規(guī)則,重復(fù)節(jié)點 造成循環(huán),問題求解基本原理,基于狀態(tài)空間的啟發(fā)式搜索算法: A 算法； A* 算法,啟發(fā)式圖搜索算法,假設(shè)：,f (n) = g (n) + h (n) 任意節(jié)點 n 的評價函數(shù)：指迄今為止已找到的從初始節(jié)點 s ，到達節(jié)點 n，再從節(jié)點 n 到達目標節(jié)點 t 的路徑全程的最小費用，是對 f *(n ) 的一個估計。,h (n) ：迄今為止從節(jié)點 n 到目標節(jié)點 t 最佳分段路徑將要花費的未知估計費用，是對 h* (n) 的一個估計，可視為啟發(fā)式分量函數(shù)，有h (n)

16、 0。,g (n) ：迄今為止搜索到的從初始節(jié)點 s 到當前節(jié)點 n 最佳路徑分段的已知費用，是對g* (n) 的一個估計。,f *(n) = g* (n) + h* (n)：從初始節(jié)點 s 出發(fā)，經(jīng)過最佳路徑上任意節(jié)點 n，到達目標節(jié)點 t 的最小費用。,h* (n)：n t 最佳路徑的分段費用。,g* (n)：sn 最佳路徑的分段費用。,s：初始節(jié)點；n：當前節(jié)點；t：目標節(jié)點。,啟發(fā)式圖搜索算法 - A 算 法,定義：按照 f (n) = g (n) + h (n) 估價函數(shù)值由小到大地排列待擴展節(jié)點順序的圖搜索算法，稱為A 算法。,A 算法流程。,A算法應(yīng)用實例: 普通有向圖 A 算法

17、搜索實例； 8數(shù)碼問題A 算法搜索實例。,算法中符號： s：初始節(jié)點；G：搜索圖的節(jié)點集合； OPEN表： 已生成但尚未被擴展的節(jié)點序列表； CLOSED表： 已生成且已被擴展的節(jié)點序列表； n： 待擴展的當前節(jié)點； mi = mj mk ml：擴展 n 后生成的后繼節(jié)點 其中， mj：第一次生成的節(jié)點，mj OPEN 且 mj CLOSED表， mk：在OPEN表中出現(xiàn)過的待擴展節(jié)點， ml：在CLOSED表中出現(xiàn)過的已擴展節(jié)點。,啟發(fā)式圖搜索算法 - A算法,A算法,啟發(fā)式最佳圖搜索算法 - A*算法,A*算法定義： 若將A算法中評價函數(shù) f (n)的啟發(fā)式分量函數(shù) h（n）的值限制在 h

18、*（n）的下界范圍內(nèi)，亦即對所有節(jié)點 n，都滿足h（n） h*（n），則稱此時的 A 算法為 A* 算法。,A*算法作用： 問題有解時， A*算法一定能夠找到從初始節(jié)點 s 到目標節(jié)點 t 的最佳解徑。,信息度定理： 有兩個A*算法A1和A2, 若A2比A1有較多的啟發(fā)式信息（即對所有非目標節(jié)點均有： h1（n） h2（n） h*（n），則在具有一條從 s 到 t 的隱含狀態(tài)圖上，搜索結(jié)束時，由A2擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。,啟發(fā)式最佳圖搜索算法 - A*算法,A *算法應(yīng)用驗證: 8數(shù)碼問題A * 算法搜索實例。,8數(shù)碼問題搜索策略比較：,寬度優(yōu)先 A算法 A*算法,小結(jié),啟發(fā)式搜索策略,g: 考慮當前路徑已經(jīng)花費的費用，及時拋棄已經(jīng)經(jīng)過的花費太大且距目標仍遠的路徑;,h: 估計當前路徑上節(jié)點到目標節(jié)點還需要的費用，引導(dǎo)搜索向最有希望的路徑前進。,A 算法：定義估計函數(shù)：f = g + h；,A* 算法：定義估計函數(shù)：f = g + h； 滿足h（n） h*（n）。,作業(yè):,利用寬度優(yōu)先法或深度優(yōu)先法，程序?qū)崿F(xiàn) High-way map 問題求解，只考慮節(jié)