人工智能導論第二章搜索與問

1、人工智能導論第二章搜索與問第1頁，共163頁，2022年，5月20日，20點17分，星期日第二章 搜索、問題求解與博弈問題求解能力是人類智能的基本組成部分，研究并實現(xiàn)問題求解是人工智能的重要研究內容之一。知識（問題）的表示是問題求解的基礎，兩種普遍采用的問題表示方法：狀態(tài)空間表示與或圖表示搜索（優(yōu)化）：在問題表示基礎上，在合理的時間范圍內，從問題所有可能的解中找到一個最優(yōu)解或可行解，是問題求解中的核心技術。啟發(fā)式搜索-人工智能的本質特征之一。計算機博弈涉及問題表示、搜索技術等AI核心問題，現(xiàn)有的計算機博弈本質上是將博弈問題轉變?yōu)橐粋€與或圖搜索問題進行處理。第2頁，共163頁，2022年，5月2

2、0日，20點17分，星期日主要內容2.1 搜索概述2.2 問題求解2.2.1 狀態(tài)空間2.2.2 與或圖2.3 搜索技術圖搜索2.4 機器博弈第3頁，共163頁，2022年，5月20日，20點17分，星期日一些例子搭積木智力游戲：有一個農夫帶一條狼、一只羊和一筐菜要從河的左岸乘船到右岸，但受下列條件限制：船太小，農夫每次只能帶一樣東西過河沒有農夫看管，則狼要吃羊，羊要吃菜請設計一個過河方案，使得農夫、狼、羊、菜都不能受損地過河。類似問題：野人和傳教士問題下棋（撲克、西洋跳棋、國際象棋、象棋等）（屬于博弈）第4頁，共163頁，2022年，5月20日，20點17分，星期日2.1 搜索概述人工智能的

3、多個研究領域從求解現(xiàn)實問題的過程來看，都可抽象為一個“問題求解”過程問題求解過程實際上就是一個搜索過程最優(yōu)性和計算法復雜性是搜素中的一對矛盾，搜索必須考慮的三個問題：采用盲目搜索還是啟發(fā)式搜索盲目搜索：不考慮問題本身的特性，通過遍歷問題解的集合來尋找可行解或最優(yōu)解。啟發(fā)式搜索：利用與問題有關的啟發(fā)式信息來確定搜索方向，以加快搜索過程。進行局部搜索還是全集搜索搜索可行解還是最優(yōu)解第5頁，共163頁，2022年，5月20日，20點17分，星期日2.1 搜索概述評價一個搜索算法的因素：完備性：如果問題有解，一定能找到一個解最優(yōu)性：如果問題存在最優(yōu)解，則一定能找到這個最優(yōu)解復雜性：時間和空間復雜性，在

4、保證最優(yōu)性和完備性的前提下，算法的復雜性越小越好。目前的搜索算法還不能同時滿足以上三個要求。為了進行搜索，首先必須用某種形式把問題表示出來：狀態(tài)空間表示法和與或圖表示法就是用來表示問題及其搜索過程的兩種常用方法。第6頁，共163頁，2022年，5月20日，20點17分，星期日2.2 問題求解狀態(tài)空間表示法和與或圖表示法不僅是問題表示的方法，也分別代表了兩種問題求解的思路狀態(tài)空間將問題求解所涉及的每個可能的步驟表示成一個狀態(tài)，全部狀態(tài)以及狀態(tài)之間的所有轉換構成一個以圖的形式表示的狀態(tài)空間。問題的求解過程是在狀態(tài)空間中搜索一條最優(yōu)的或可行的從初始狀態(tài)到目標狀態(tài)的路徑的過程。與或圖表示法的基礎是問題

5、歸約，通過一系列分解或變換，將復雜問題逐步轉化為比較簡單的問題，直至可以直接求解的本原問題。與或圖的求解過程是在與或圖中搜索一個將原始問題變換為簡單問題在變換為本原問題的、最優(yōu)的或可行的歸約步驟的過程。第7頁，共163頁，2022年，5月20日，20點17分，星期日2.2.1 狀態(tài)空間表示法狀態(tài)空間表示法是用“狀態(tài)”和“算子”來表示問題的一種方法狀態(tài)：用來描述問題求解過程中不同時刻的狀況算子：表示對狀態(tài)的操作，算子的每次使用就使問題由一種狀態(tài)變換為另一種狀態(tài)當達到目標狀態(tài)時，由初始狀態(tài)到目標狀態(tài)所用算子的序列就是問題的一個解第8頁，共163頁，2022年，5月20日，20點17分，星期日2.2

6、.1 狀態(tài)空間表示法狀態(tài)狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結構，一般用一組變量的有序組合表示：SK(SK0,SK1,)當給每一分量以確定的值時，就得到一個具體的狀態(tài)算子引起狀態(tài)中某些分量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算子。產生式系統(tǒng)中，每一條產生式規(guī)則就是一個算子狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構成的集合稱為問題的狀態(tài)空間，一般用三元組表示: (S,F,C,I,G)S: 所有狀態(tài)構成的集合F: 用于狀態(tài)轉換的算子的集合C: 狀態(tài)轉換代價的聚合I: 初始狀態(tài)的集合G: 目標狀態(tài)的集合第9頁，共163頁，2022年，5月20日，20點17分，星期日例:二階H

7、anoi Tower （梵塔）問題設有三根柱子，在1號柱于上穿有A、B兩個盤片，盤A小于盤B，盤A位于盤B的上面。要求把這兩個盤片全部移到另一根柱子上，而且規(guī)定每次只能移動一片，任何時刻都不能使盤B位于盤A的上面。設SK=(SK0,SK1)表示問題的狀態(tài)，SK0 表示盤片A所在的柱號，SK1 表示盤片B所在的柱號全部可能的狀態(tài):S0=(1,1), S1=(1,2), S2=(1,3),S3=(2,1), S4=(2,2), S5=(2,3),S6=(3,1), S7=(3,2), S8=(3,3).問題的初始狀態(tài)集合S=S0,目標集合為G=S4,S8算子分別用A(i,j), B(i,j)表示A

8、(i,j):盤片A從柱i移到柱j；B(i,j):盤片B從柱i移到柱j全部可能的算子：A(1,2), A(1,3), A(2,1), A(2,3), A(3,1), A(3,2), B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2) 第10頁，共163頁，2022年，5月20日，20點17分，星期日例:二階Hanoi Tower （梵塔）問題9種狀態(tài)，12種算子構成的狀態(tài)空間轉移圖：第11頁，共163頁，2022年，5月20日，20點17分，星期日2.2.1 狀態(tài)空間表示法總結：用狀態(tài)空間方法表示問題時，首先必須定義狀態(tài)的描述形式，通過使用這種描述形式可

9、把問題的一切狀態(tài)都表示出來。其次，還安定義一組算符，通過使用算符可把問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。如果在使用某個算符后得到的新狀態(tài)是目標狀態(tài)，就得到問題的一個解：從初始狀態(tài)到目標狀態(tài)所用算符構成的序列。算符的一次使用，就使問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。可能有多個算特序列都可使問題從初始狀態(tài)變到目標狀態(tài)，這就得到了多個解。把使用算符最少的解稱為最優(yōu)解。對任何一個狀態(tài)，可使用的算符可能不止一個，因而由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。當對這些后繼狀態(tài)使用算子生成更進一步狀態(tài)時，首先應對哪一狀態(tài)進行操作呢？這取決于搜索策略，不同搜索策略的操作順

10、序是不相同的。第12頁，共163頁，2022年，5月20日，20點17分，星期日狀態(tài)空間表示法基于狀態(tài)空間表示的問題求解算法Step1： 確定問題狀態(tài)的計算機描述形式，將所有可能的狀態(tài)表示出來，并確定其中的初始狀態(tài)和目標狀態(tài)。Step2：確定促使狀態(tài)發(fā)生轉換的操作，并在計算機中將其表示為相應的算符。Step3：以狀態(tài)為頂點，狀態(tài)之間所允許的操作為有向邊，獲得圖形式的狀態(tài)空間。Step4：應用圖搜索方法，在狀態(tài)空間中搜索從初始狀態(tài)到目標狀態(tài)的最優(yōu)路徑或可行路徑。第13頁，共163頁，2022年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題第14頁，共163頁，20

11、22年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題第15頁，共163頁，2022年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題第16頁，共163頁，2022年，5月20日，20點17分，星期日2.2.2 與或圖表示法也稱為問題歸約方法：把初始問題通過一系列交換最終變?yōu)橐粋€子問題集合，而這些于問題的解可以直接得到，從而解答了初始問題。分解：把一個復雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解為若干個更為簡單的子問題。重復此過程，直到不需要再分解或者不能再分解為止。然后對每個子問題分別進行求解，最后把各子問題的解復合

12、起來就得到了原問題的解。問題的分解可以用圖表示出來，稱為與樹。例如，把問題P分解為三個子問題P1、P2和P3，可以表示為下圖：第17頁，共163頁，2022年，5月20日，20點17分，星期日2.2.2 與或圖表示法等價變換：利用同構或同態(tài)的等價變換，把它變換成若干個較容易求解的新問題。若新問題中有一個可求解，則就得到了原問題的解。問題的等價變換過程也可用一個圖表示出來，稱為“或”樹。與或樹的結合稱為與或圖（樹）。第18頁，共163頁，2022年，5月20日，20點17分，星期日2.2.2 與或圖表示法本原問題：不能再分解或變換，而且直接可解的子問題稱為本原問題。端節(jié)點與終止節(jié)點：在與或樹中，

13、沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應的節(jié)點稱為終止節(jié)點。顯然，終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點?？山夤?jié)點：在與或樹今，滿足下列條件之一的節(jié)點：1)它是一個終止節(jié)點。2)它是一個“或”節(jié)點，且其子節(jié)點至少有一個是可解節(jié)點。3)它是一個“與”節(jié)點，且其子節(jié)點全部是可解節(jié)點。不可解節(jié)點：上面三個條件全不滿足的節(jié)點。解樹：由可解節(jié)點所構成的，并且由這些可解節(jié)點可推出初始節(jié)點(它對應于原始問題)為可解節(jié)點的子樹稱為解樹。在解樹中定包含初始節(jié)點。第19頁，共163頁，2022年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題設有A、B、C三個盤片以及三根柱

14、子，三個盤片按從小到大的順序穿在1號柱上，要求把它們全部移到3號柱上，而且每次只能移動一個盤片，任何時刻都不能把大的盤片壓在小的盤片上面，如圖所示。第20頁，共163頁，2022年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題分析：1)為了把三個盤片全部移到3號柱上，必須先把盤片C移到3號柱上。2)為了移盤片C，必須先把盤片A及B移到2號柱上。3)當把盤片C移到3號盤上后，就可把A、B從2號柱移到3號柱上，以完成問題的求解。把原問題分解為三個子問題：1)把盤片A及B移到2號柱的雙盤片問題。2)把盤片C移到3號柱的單盤片問題。3)把盤片A及B移到3號柱的雙盤片問題

15、。其中，子問題1)與子問題3)又分別可分解為三個子問題第21頁，共163頁，2022年，5月20日，20點17分，星期日例:三階Hanoi Tower （梵塔）問題定義問題狀態(tài)表示：設三元組(i,j,k)表示狀態(tài)，其中i表示盤片C所在的柱號,j表示盤片B所在的柱號；k表示盤片A所在的柱號。初始問題可表示為：(1、11) (3，3，3)與或樹表示如圖所示。(把圖中7個終止節(jié)點(本原問題)按從左至右排列，得到了初始問題的解)第22頁，共163頁，2022年，5月20日，20點17分，星期日2.2.2 與或圖表示法基于與或圖表示的問題求解算法Step1： 確定單個問題描述形式，可采用狀態(tài)空間表示法。

16、Step2：從原始問題開始，逐步進行分解和變換，直到本原問題，然后將全部分解和變換過程表示為與或圖。Step3：從端頂點開始，逐步向上回溯，標注各頂點為可解或不可解頂點，直到標注原始頂點為可解頂點或不可解頂點為止Step4：當原始頂點被確定為可解頂點時，輸出相應解圖為問題的解。第23頁，共163頁，2022年，5月20日，20點17分，星期日2.3 搜索技術 搜索技術是人工智能的基本技術之一, 在人工智能各應用領域中被廣泛地使用。早期的人工智能程序與搜索技術聯(lián)系就更為緊密，幾乎所有的早期的人工智能程序都是以搜索為基礎的。例如，A.Newell(艾倫紐厄爾)和HASimon(西蒙)等人編寫的LT

17、(Logic Theorist)程序, J.Slagle寫的符號積分程序SAINT, ANewell和HASimon寫的GPS(General Problem Solver)程序, HGelernter(格倫特爾)寫的Geometry theorem-proving machine程序, R.Fikes(菲克斯)和N.Nilsson(尼爾遜)寫的STRIPS(Stanford Research Institute Problem Solver)程序以及A.Samuel(塞繆爾)寫的Chechers程序等, 都使用了各種搜索技術?，F(xiàn)在, 搜索技術滲透在各種人工智能系統(tǒng)中, 可以說沒有哪一種人工智

18、能的應用不用搜索方法,在專家系統(tǒng)、自然語言理解、自動程序設計、模式識別、機器人學、信息檢索和博弈都廣泛使用搜技術。第24頁，共163頁，2022年，5月20日，20點17分，星期日2.3 搜索技術 搜索問題是AI核心理論問題之一一般一個問題可以用好幾種搜索技術解決, 選擇一種好的搜索技術對解決問題的效率很有關系, 甚至關系到求解問題有沒有解。搜索方法好的標準, 一般認為有兩個：(1)搜索空間小;(2)解最佳。 第25頁，共163頁，2022年，5月20日，20點17分，星期日2.3 搜索技術 搜索從問題性質上來看, 可分為一般搜索和博奕搜索, 從處理方法上來看, 可分為盲目搜索和啟發(fā)式搜索。還

19、可以分得更細。當所給定的問題用狀態(tài)空間表示時, 則求解過程可歸結為對狀態(tài)空間的搜索。 當問題有解時, 使用不同的搜索策略, 找到解的搜索空間范圍是有區(qū)別的。一般來說, 對大空間問題, 搜索策略是要解決組合爆炸的問題第26頁，共163頁，2022年，5月20日，20點17分，星期日第27頁，共163頁，2022年，5月20日，20點17分，星期日2.3 搜索策略 通常搜索策略的主要任務是確定如何選取規(guī)則的方式。有兩種基本方式:一種是不考慮給定問題所具有的特定知識, 系統(tǒng)根據(jù)事先確定好的某種固定排序, 依次調用規(guī)則或隨機調用規(guī)則,這實際上是盲目搜索的方法, 一般統(tǒng)稱為無信息引導的搜索策略。另一種是

20、考慮問題領域可應用的知識, 動態(tài)地確定規(guī)則的排序, 優(yōu)先調用較合適的規(guī)則使用, 這就是通常稱為啟發(fā)式搜索策略或有信息引導的搜索策略。第28頁，共163頁，2022年，5月20日，20點17分，星期日AI領域的搜索方法(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(Hill Climbing)寬度優(yōu)先法(Breadth-first)深度優(yōu)先法(Depth-first)限定范圍搜索法(Beam Search)最佳優(yōu)先法(Best-first)(2)求最佳解路的搜索策略大英博物館法(British Museum)分枝界限法(Branch and Bound)動態(tài)規(guī)劃法(Dynam

21、ic Programming)最佳圖搜索法(A*)第29頁，共163頁，2022年，5月20日，20點17分，星期日AI領域的搜索方法(3)求與或關系解圖的搜索法一般與或圖搜索法(AO*) 極小極大法(Minimax)剪枝法(Alpha-beta Pruning) 啟發(fā)式剪枝法(Heuristic Pruning)第30頁，共163頁，2022年，5月20日，20點17分，星期日搜索策略分類第31頁，共163頁，2022年，5月20日，20點17分，星期日盲目搜索方法盲目搜索是不利用問題的有關信息, 而根據(jù)事先確定好的某種固定的搜索方法進行搜索。典型的盲目搜索方法是深度優(yōu)先搜索和寬度優(yōu)先搜索(

22、亦稱廣度優(yōu)先搜索), 這是兩處基本搜索方法第32頁，共163頁，2022年，5月20日，20點17分，星期日回溯策略例：皇后問題 在一個44的國際象棋棋盤上,一次一個地擺布四枚皇后棋子, 擺好后要滿足每行、每列和對象線上只允許出現(xiàn)一枚棋子, 即棋子間不許相互俘獲 第33頁，共163頁，2022年，5月20日，20點17分，星期日( )第34頁，共163頁，2022年，5月20日，20點17分，星期日( )Q(1,1)第35頁，共163頁，2022年，5月20日，20點17分，星期日( )QQ(1,1)(1,1) (2,3)第36頁，共163頁，2022年，5月20日，20點17分，星期日( )

23、Q(1,1)(1,1) (2,3)第37頁，共163頁，2022年，5月20日，20點17分，星期日( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)第38頁，共163頁，2022年，5月20日，20點17分，星期日( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)第39頁，共163頁，2022年，5月20日，20點17分，星期日( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第40頁，共163頁，2022年，5月20日，20點17分，星期日( )Q(1,1)(1,1) (2,3)

24、(1,1) (2,4)(1,1) (2,4) (3.2)第41頁，共163頁，2022年，5月20日，20點17分，星期日( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)第42頁，共163頁，2022年，5月20日，20點17分，星期日( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)第43頁，共163頁，2022年，5月20日，20點17分，星期日( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)第44頁，共16

25、3頁，2022年，5月20日，20點17分，星期日( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)第45頁，共163頁，2022年，5月20日，20點17分，星期日( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)Q(1,2) (2,4) (3,1) (4,3)第46頁，共163頁，2022年，5月20日，20點17分，星期日遞歸的思想從前有座山 從前有座山 從前

26、有座山第47頁，共163頁，2022年，5月20日，20點17分，星期日Fibonacci數(shù)列1202年，意大利家斐波那契在提出了一個關于兔子繁殖的問題： 如果一對兔子每月能生一對小兔（一雄一雌），而每對小兔在它出生後的第三個月里，又能開始生一對小兔，假定在不發(fā)生死亡的情況下，由一對出生的小兔開始，50個月后會有多少對兔子？ 第48頁，共163頁，2022年，5月20日，20點17分，星期日當n1時，F(xiàn)n+2 = Fn+1 + Fn，而 F0=F1=1。 第49頁，共163頁，2022年，5月20日，20點17分，星期日遞歸的思想（續(xù)）當前狀態(tài)目標狀態(tài)g第50頁，共163頁，2022年，5月2

27、0日，20點17分，星期日回溯搜索算法BACKTRACK（DATA）DATA：當前狀態(tài)。返回值：從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。第51頁，共163頁，2022年，5月20日，20點17分，星期日回溯搜索算法遞歸過程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);4, LOOP: IF NULL(RULES) RETURN FAIL;5, R:=FIRST(RULES);6,RULES:=TAIL(RULES);7,R

28、DATA:=GEN(R, DATA);8,PATH:=BACKTRACK(RDATA);9,IF PATH=FAIL GO LOOP;10,RETURN CONS(R, PATH);第52頁，共163頁，2022年，5月20日，20點17分，星期日存在問題及解決辦法問題：深度問題死循環(huán)問題解決辦法：對搜索深度加以限制記錄從初始狀態(tài)到當前狀態(tài)的路徑第53頁，共163頁，2022年，5月20日，20點17分，星期日回溯搜索算法1BACKTRACK1（DATALIST）DATALIST：從初始到當前的狀態(tài)表（逆向）返回值：從當前狀態(tài)到目標狀態(tài)的路徑（以規(guī)則表的形式表示）或FAIL。第54頁，共163

29、頁，2022年，5月20日，20點17分，星期日回溯搜索算法11, DATA:=FIRST(DATALIST)2, IF MENBER(DATA, TAIL(DATALIST) RETURN FAIL;3, IF TERM(DATA) RETURN NIL;4, IF DEADEND(DATA) RETURN FAIL;5, IF LENGTH(DATALIST)BOUND RETURN FAIL;6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);第55頁，共163頁，2022年，5月2

30、0日，20點17分，星期日回溯搜索算法1（續(xù)）9,RULES:=TAIL(RULES);10,RDATA:=GEN(R, DATA);11,RDATALIST:=CONS(RDATA, DATALIST);12,PATH:=BACKTRCK1(RDATALIST)13,IF PATH=FAIL GO LOOP;14,RETURN CONS(R, PATH);第56頁，共163頁，2022年，5月20日，20點17分，星期日一些深入的問題失敗原因分析、多步回溯QQ第57頁，共163頁，2022年，5月20日，20點17分，星期日一些深入問題（續(xù)）回溯搜索中知識的利用基本思想：盡可能選取劃去對角線

31、上位置數(shù)最少的。QQQQ4 3 3 4第58頁，共163頁，2022年，5月20日，20點17分，星期日 圖搜索策略問題的引出回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。圖搜索：保留所有已經搜索過的路徑。第59頁，共163頁，2022年，5月20日，20點17分，星期日一些基本概念節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+10123第60頁，共163頁，2022年，5月20日，20點17分，星期日一些基本概念（續(xù)1）路徑設一節(jié)點序列為(n0, n1,nk)，對于i=1,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。路徑的耗散值一條路徑的耗散值等于連接這條路

32、徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。第61頁，共163頁，2022年，5月20日，20點17分，星期日一些基本概念（續(xù)1）擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。第62頁，共163頁，2022年，5月20日，20點17分，星期日圖搜索的一般過程(1) 建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN的未擴展節(jié)點表中（簡稱OPEN表）。(2) 建立一個叫做CLOSED的已擴展節(jié)點表（簡稱CLOSED表），其初始為空表。(3) LOOP：若OPEN表是空表，則失敗退出。(4) 選擇OPEN

33、表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n，它是CLOSED表中節(jié)點的編號。(5) 若n為一目標節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設置)。第63頁，共163頁，2022年，5月20日，20點17分，星期日(6) 擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。 (7) 對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是

34、否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。(8) 按某一任意方式或按某個探試值，重排OPEN表。 (9) GO LOOP。 第64頁，共163頁，2022年，5月20日，20點17分，星期日OPEN表節(jié)點父節(jié)點CLOSED表標號節(jié)點父節(jié)點OPEN表節(jié)點父節(jié)點編號CLOSED表編號節(jié)點父節(jié)點編號第65頁，共163頁，2022年，5月20日，20點17分，星期日例子例子：從某王姓家族的四代中找王A的后代且其壽命為X的人。王A：壽命47，有兒子王B1、王B3、王B2王B1：壽命77，有兒子王C1、王C2王B3：壽命52，有兒

35、子王D1王B2：壽命65，有兒子王E1、王E2王F1：壽命32王G1：壽命96王C2：壽命87，有兒子王F1王D1：壽命77，沒有兒子王E1：壽命57，有兒子王G1王E2：壽命92，有兒子王H1 王C1：壽命27，沒有兒子王H1：壽命51若X=57，如何尋找？第66頁，共163頁，2022年，5月20日，20點17分，星期日問題的搜索樹第67頁，共163頁，2022年，5月20日，20點17分，星期日深度優(yōu)先搜索的搜索過程無信息圖搜索過程深度優(yōu)先第68頁，共163頁，2022年，5月20日，20點17分，星期日重排九宮深度優(yōu)先只是搜索樹的一部分，尚未到達目標節(jié)點，仍需繼續(xù)往下搜索。第69頁，共

36、163頁，2022年，5月20日，20點17分，星期日有界深度優(yōu)先搜索的搜索過程如果問題有解，且其路徑長度dm，則搜索過程就得不到解。-深度界限的選擇很重要。第70頁，共163頁，2022年，5月20日，20點17分，星期日有界深度優(yōu)先搜索設深度界度dm=4，有界深度優(yōu)先搜索求解圖如下，解的路徑為S020252628(Sg)第71頁，共163頁，2022年，5月20日，20點17分，星期日深度優(yōu)先搜索的性質一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個通用的與問題無關的方法第72頁，共163頁，202

37、2年，5月20日，20點17分，星期日無信息圖搜索過程寬度優(yōu)先寬度優(yōu)先搜索過程：(1) 把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。(2) 如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把OPEN表中第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED擴展節(jié)點表中。(4) 考察節(jié)點n是否為目標節(jié)點，若是則求得問題的解，退出，(5)若節(jié)點n不可擴展，則轉第(2)步。(6)擴展節(jié)點n。將其所有后繼節(jié)點放到OPEN表的末端，并為每個后續(xù)節(jié)點都配置指向n的指針。然后轉向第(2)步。第73頁，共163頁，2022年，5月20日，20點17分，星期日寬度

38、優(yōu)先第74頁，共163頁，2022年，5月20日，20點17分，星期日重排九宮寬度優(yōu)先解的路徑：S0381626第75頁，共163頁，2022年，5月20日，20點17分，星期日寬度優(yōu)先搜索的性質只要問題有解，一定能找到解，而且得到的是路徑最短的解。盲目性較大，當目標節(jié)點距離初始節(jié)點較遠時將會產生許多無用節(jié)點，因此搜索效率低。方法與問題無關，具有通用性屬于圖搜索方法第76頁，共163頁，2022年，5月20日，20點17分，星期日非啟發(fā)式搜索按照事先規(guī)定的路線進行搜索廣度優(yōu)先搜索是按“層”進行搜索的，先進入OPEN 表的節(jié)點先被考察深度優(yōu)先搜索是沿著縱深方向進行搜索的，后進入OPEN表的節(jié)點先

39、被考察按已經付出的代價決定下一步要搜索的節(jié)點（為樹中的每條邊賦予代價，廣度及深度優(yōu)先搜索實質是每條邊的代價都為1）代價樹的廣度優(yōu)先代價樹的深度優(yōu)先第77頁，共163頁，2022年，5月20日，20點17分，星期日代價樹的寬度憂先搜索邊上標有代價(或費用)的樹稱為代價樹。在代價樹中，若用g(x)表示從初姑節(jié)點S0到節(jié)點x的代價，用c(xl,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2) 代價樹寬度優(yōu)先搜索的基本思想是：OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的，每次擴展時總是從OPEN表中選取代價最小的節(jié)點進行擴展。其搜索過程如下：第78頁，

40、共163頁，2022年，5月20日，20點17分，星期日五城市間的交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交道費用(代價)如左圖小數(shù)字所示。求從A到E的最小費用交通路線。交通代價樹如右圖，解為ACDE代價樹的寬度優(yōu)先搜索舉例第79頁，共163頁，2022年，5月20日，20點17分，星期日代價樹的深度憂先搜索代價樹的寬度優(yōu)先搜索中，每次擴展時總是從OPEN表中選取代價最小的節(jié)點進行擴展。而代價樹的深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選一個代價最小的節(jié)點送入CLOSE表中進行考察。其搜索過程如下：解也為ACDE第80頁，共163頁，2022年，5月20日，20點17分，星期日啟發(fā)式圖

41、搜索利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。啟發(fā)性信息用于指導搜索過程，且與具體問題求解有關的控制性信息稱為啟發(fā)性信息啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最 優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解第81頁，共163頁，2022年，5月20日，20點17分，星期日希望：引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。第82頁，共163頁，2022年，5月20日，20點17分，星期日基本思想定義一個評價函數(shù)f，對當前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。第83頁，共163頁，2022年，5月

42、20日，20點17分，星期日1，啟發(fā)式搜索算法A（A算法）評價函數(shù)的格式：f(n) = g(n) + h(n)f(n)：評價函數(shù)g(n): 實際已經付出的代價函數(shù)h(n)：啟發(fā)函數(shù)第84頁，共163頁，2022年，5月20日，20點17分，星期日符號的意義g*(n)：從s(初始狀態(tài)S0)到n(當前狀態(tài)Sn)的最短路徑的耗散值h*(n)：從n到g(目標狀態(tài)Sg)的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值第85頁，共163頁，2022年，5月20日，20點17分，星期日一個A算法

43、的例子定義評價函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點到當前節(jié)點的耗散值,即頂點Sn在狀態(tài)空間中的深度(從根頂點到Sn所經歷的層次數(shù))。h(n)為當前節(jié)點“不在位”的將牌數(shù)2 8 31 6 47 51 2 38 47 6 5第86頁，共163頁，2022年，5月20日，20點17分，星期日h計算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 8第87頁，共163頁，2022年，5月20日，20點17分，星期日2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1

44、 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標123456g=0,h=4f=0+4=4g=1,h=5f=1+5=6g=0g=1g=2g=3第88頁，共163頁，2022年，5月20日，20點17分，星期日最佳圖搜索算法A*（A*算法）在A算法中，如果滿足條件：h(n)h*(n)則A算法稱為A*算法

45、。其中h*(n)是從頂點Sn到Sg的最小代價。由于h*(n)最小代價通常不知道，因此用h(n)（不在位的將牌數(shù)）進行代價估計，因此可得h(n)=f12 8 31 6 47 51 2 3457 6 8將牌1：1將牌2：1將牌6：1將牌8：2第90頁，共163頁，2022年，5月20日，20點17分，星期日A*算法的性質定理1：對有限圖，如果從初始節(jié)點s到目標節(jié)點t有路徑存在，則算法A一定成功結束。第91頁，共163頁，2022年，5月20日，20點17分，星期日AO*算法是A*算法在與或圖上的擴展算法。AO*算法中由于與節(jié)點的存在，解對應的不是一條路徑，而是一個子圖，因此對頂點的評估實際上是對局

46、部解圖的評價。與節(jié)點代價計算：最大代價和代價或節(jié)點的代價計算：最小代價AO*算法第92頁，共163頁，2022年，5月20日，20點17分，星期日AO*算法舉例7=3+1(左樹)+2+18=3+1+3+18=min(8+1,7+1)第93頁，共163頁，2022年，5月20日，20點17分，星期日與或樹的寬度優(yōu)先與深度優(yōu)先搜索寬度優(yōu)先：12345深度優(yōu)先：13B524第94頁，共163頁，2022年，5月20日，20點17分，星期日問題圖搜索是針對什么知識表示方法的問題求解方法？什么是圖搜索? 其中，重排OPEN表意味著什么，重排的原則是什么?寬度優(yōu)先搜索方法中OPEN表需要按什么方式進行操作

47、A先進后出 B先進先出有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑嗎？試比較各種盲目搜索搜索方法的效率，找出影響算法效率的原因試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實例數(shù)據(jù)加以說明第95頁，共163頁，2022年，5月20日，20點17分，星期日啟發(fā)式搜索的必要性 現(xiàn)實的困難迫使人們轉而求援于啟發(fā)式算法。這種算法的本質是部分地放棄算法“一般化, 通用化”的概念, 把所要解的問題的具體領域的知識加進算法中去, 以提高算法的效率。如, 廣度優(yōu)先法幾乎可以用于解一切搜索問題：九宮圖(八數(shù)碼難題), hanoi塔(焚塔問題), 旅行推銷員, 華容道, 以

48、至魔方等等。但實際使用時, 效率也許低得驚人, 甚至根本解不出來(例如魔方問題)。如果我們?yōu)槊款悊栴}找出一些特殊規(guī)則, 和廣度優(yōu)先法配合起來使用, 那結果就可能完全不一樣了。第96頁，共163頁，2022年，5月20日，20點17分，星期日啟發(fā)式搜索的必要性根據(jù)啟發(fā)信息, 在生成各種搜索樹時可以考慮種種可能的選擇, 如: 1. 下一步展開哪個節(jié)點?2. 是部分展開還是完全展開?3. 使用哪個規(guī)則(或算子)?4. 怎樣決定舍棄還是保留新生成的節(jié)點?5. 怎樣決定舍棄還是保留一棵子樹?6. 怎樣決定停止或繼續(xù)搜索?7. 如何定義啟發(fā)函數(shù)(評價函數(shù))?8. 如何決定搜索方向? 由于這些選擇的不同,

49、就得到了不同的啟發(fā)式算法第97頁，共163頁，2022年，5月20日，20點17分，星期日*解路徑如粗線所標左、上、右、下*S、A、B、L、M等為狀態(tài)空間圖中各個節(jié)點名, 其后的小括號中數(shù)字表示該節(jié)點的評價函數(shù)f(n)的估計值, 例如S(4)、L(5)等。* 圖中標記節(jié)點為被擴的節(jié)點, 標記的節(jié)點為生成的節(jié)點。九宮重排問題第98頁，共163頁，2022年，5月20日，20點17分，星期日搜索效率比較第99頁，共163頁，2022年，5月20日，20點17分，星期日啟發(fā)式搜索策略人工智能問題求解者在兩種基本情況下運用啟發(fā)式策略: 一個問題由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性可能使它沒有一個確

50、定的解。醫(yī)療診斷即是一例。所給出的一系列癥狀可能有多個原因, 醫(yī)生運用啟發(fā)式搜索來選擇最有可能的論斷并依此產生治療計劃。一個問題可能有確定解, 但是求解過程中的計算機代價令人難以接受。在很多問題(如國際象棋)中, 狀態(tài)空間的增長特別快, 可能的狀態(tài)數(shù)隨著搜索的深度呈指數(shù)級增長、分解。在這種情況下, 窮盡式搜索策略諸如深度優(yōu)先或廣度優(yōu)先搜索, 在一個給定的較實際的時空內很可能得不到最終的解和發(fā)明創(chuàng)造的所有規(guī)則一樣, 啟發(fā)式策略也是極易出錯的第100頁，共163頁，2022年，5月20日，20點17分，星期日圖搜索策略圖搜索策略的定義圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點和目標節(jié)點分別

51、代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。圖搜索算法中的幾個重要名詞術語（1）OPEN表與CLOSE表（2）搜索圖與搜索樹第101頁，共163頁，2022年，5月20日，20點17分，星期日你可曾聽說過“深藍”？ 1997年5月11日，IBM開發(fā)的“深藍”擊敗了國際象棋冠軍卡斯帕羅夫。1980年他獲得世界少年組冠軍 1982年他并列奪得蘇聯(lián)冠軍 1985年22歲的卡斯帕羅夫成為歷史上最年輕的國 際象棋冠軍積分是2849，這一分數(shù)是有史以來最高分。 遠遠領先于第二位的克拉

52、姆尼克的2770 卡氏何許人也？第102頁，共163頁，2022年，5月20日，20點17分，星期日第103頁，共163頁，2022年，5月20日，20點17分，星期日電腦棋手：永不停歇的挑戰(zhàn)！1988年“深思”擊敗了丹麥特級大師拉森。1993年“深思”第二代擊敗了丹麥世界優(yōu)秀女棋手小波爾加。第104頁，共163頁，2022年，5月20日，20點17分，星期日電腦棋手：永不停歇的挑戰(zhàn)！2001年“更弗里茨” 擊敗了除了克拉姆尼克之外的所有排名世界前十位的棋手。2002年10月“更弗里茨”與世界棋王克拉姆尼克在巴林交手，雙方以4比4戰(zhàn)平。2003年1至2月“更年少者”與卡斯帕羅夫在紐約較量，3比

53、3戰(zhàn)平。第105頁，共163頁，2022年，5月20日，20點17分，星期日許多人在努力 第106頁，共163頁，2022年，5月20日，20點17分，星期日機器博弈20世紀50年代，有人設想利用機器智能來實現(xiàn)機器與人的對弈。1997年IBM的“深藍”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。加拿大阿爾伯塔大學的奧賽羅程序Logistello和西洋跳棋程序Chinook也相繼成為確定的、二人、零和、完備信息游戲世界冠軍西洋雙陸棋這樣的存在非確定因素的棋類也有了美國卡內基梅隆大學的西洋雙陸琪程序BKG這樣的世界冠軍。對圍棋、中國象棋、橋牌、撲克等許多種其它種類游戲博弈的研究也正在進行中。第1

54、07頁，共163頁，2022年，5月20日，20點17分，星期日機器博弈的基本思想機器博弈的核心思想就是對博弈樹節(jié)點的估值過程和對博弈樹搜索過程的結合 第108頁，共163頁，2022年，5月20日，20點17分，星期日博弈樹在博弈的任何一個中間階段，站在博弈雙方其中一方的立場上，可以構想一個博弈樹。這個博弈樹的根節(jié)點是當前時刻的棋局，它的兒子節(jié)點是假設再行棋一步以后的各種棋局，孫子節(jié)點是從兒子節(jié)點的棋局再行棋一步的各種棋局，以此類推，構造整棵博弈樹，直到可以分出勝負的棋局。 第109頁，共163頁，2022年，5月20日，20點17分，星期日機器博弈系統(tǒng)的構成知識表示規(guī)則集，產生機制，構建博

55、弈樹搜索技術估值技術第110頁，共163頁，2022年，5月20日，20點17分，星期日博弈搜索博弈搜索的基本思想已經提出半個多世紀，目前廣泛研究的是確定的、二人、零和、完備信息的博弈搜索。沒有隨機因素的博弈在兩個人之間進行，在任何一個時刻，一方失去的利益即為另一方得到的利益，不會出現(xiàn)“雙贏”的局面，而且在任何時刻，博弈的雙方都明確的知道每一個棋子是否存在和存在于哪里。二人、零和、完備信息的博弈搜索理論已經很系統(tǒng)。極大極小算法是所有搜索算法的基礎。一類是作為主流的深度優(yōu)先的alpha-beta搜索及其系列增強算法另一類是最佳優(yōu)先的系列算法。第111頁，共163頁，2022年，5月20日，20點

56、17分，星期日解謎：電腦是怎樣下棋的 人機博弈程序的一般設計方法以中國 棋為例第112頁，共163頁，2022年，5月20日，20點17分，星期日（1）第一步該做什么？數(shù)據(jù)結構的選取棋盤表示占用空間-少操作速度-快是否方便-方便在機器中表示棋局，讓程序知道博弈狀態(tài)。第113頁，共163頁，2022年，5月20日，20點17分，星期日九列十行十四種不同的棋子三十二個棋子第114頁，共163頁，2022年，5月20日，20點17分，星期日幾種棋盤表示的方式二維數(shù)組直觀 緊湊的數(shù)據(jù)結構省空間，不直 觀，速度? 比特棋盤用于8*8棋盤（國際象 棋），64位主機第115頁，共163頁，2022年，5月2

57、0日，20點17分，星期日（2）接下來怎么辦？產生合法走步的規(guī)則，使博弈能公正的進行，并且能夠判斷對手是否亂走。依賴于具體棋類特征。是一段將局面所有可能的正確走法羅列出來的程序。稱之為走法產生。第116頁，共163頁，2022年，5月20日，20點17分，星期日幾種走法產生的實現(xiàn)方式一般做法 建立小型數(shù)據(jù)庫 位運算第117頁，共163頁，2022年，5月20日，20點17分，星期日位運算走法產生之例尋找象的可走步第118頁，共163頁，2022年，5月20日，20點17分，星期日位運算走法產生之要求一個基于比特棋盤的完善的數(shù)據(jù)庫該數(shù)據(jù)庫應位于內存中第119頁，共163頁，2022年，5月20日

58、，20點17分，星期日（3）終于到核心了從所有的走法中找出最佳的走法， 也就是搜索第120頁，共163頁，2022年，5月20日，20點17分，星期日博弈概述 諸如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動稱為博弈。博弈有很多種，我們討論最簡單的二人零和、全信息、非偶然博弈，其特征如下：(1) 對壘的MAX、MIN雙方輪流采取行動，博弈的結果只有三種情況：MAX方勝，MIN方??；MIN方勝，MAX方?。缓途?。(2) 在對壘過程中，任何一方都了解當前的格局及過去的歷史。(3) 任何一方在采取行動前都要根據(jù)當前的實際情況，進行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的碰

59、運氣因素。即雙方都是很理智地決定自己的行動。 第121頁，共163頁，2022年，5月20日，20點17分，星期日博弈概述在博弈過程中，任何一方都希望自己取得勝利。因此，當某一方當前有多個行動方案可供選擇時，他總是挑選對自己最為有利而對對方最為不利的那個行動方案。此時，如果我們站在MAX方的立場上，則可供MAX方選擇的若干行動方案之間是或關系，因為主動權操在MAX方手里，他或者選擇這個行動方案，或者選擇另一個行動方案，完全由MAX方自已決定。當MAX方選取任一方案走了一步后，MIN方也有若干個可供選擇的行動方案，此時這些行動方案對MAX方來說它們之間則是與關系，因為這時主動權操在MIN方手里，

60、這些可供選擇的行動方案中的任何一個都可能被MIN方選中，MAX方必須應付每一種情況的發(fā)生。第122頁，共163頁，2022年，5月20日，20點17分，星期日博弈概述這樣，如果站在某一方(如MAX方，即MAX要取勝)，把上述博弈過程用圖表示出來，則得到的是一棵與或樹。描述博弈過程的與或樹稱為博弈樹，它有如下特點：(1) 博弈的初始格局是初始節(jié)點。(2) 在博弈樹中，或節(jié)點和與節(jié)點是逐層交替出現(xiàn)的。自己一方擴展的節(jié)點之間是或關系，對方擴展的節(jié)點之間是與關系。雙方輪流地擴展節(jié)點。(3) 所有自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都認為是不可解節(jié)點。我們假定MAX