2023/9/221第3章搜索策略問題求解系統劃分為兩大類知識貧乏系統

依靠搜索技術解決問題知識貧乏、缺乏針對性效率低知識豐富系統

依靠推理技術解決問題基于豐富知識的推理技術，直截了當效率高2023/9/222第3章搜索策略兩大類搜索技術:1、一般圖搜索、啟發式搜索2、基于問題歸約的與或圖搜索兩種典型的推理技術:1、基于歸結的演繹推理歸結反演2、基于規則的演繹推理正向演繹推理逆向演繹推理2023/9/2233.1引言

對于給定的問題，智能系統的行為一般是找到能夠達到所希望目標的動作序列，并使其所付出的代價最小、性能最好。基于給定的問題，問題求解的第一步是目標的表示。搜索就是找到智能系統的動作序列的過程。2023/9/224搜索算法的輸入是給定的問題，輸出時表示為動作序列的方案。一旦有了方案，就可以執行該方案所給出的動作了。（執行階段）因此，求解問題包括：目標表示搜索執行2023/9/225（1）初始狀態集合：定義了初始的環境。（2）操作符集合：把一個問題從一個狀態變換為另一個狀態的動作集合。（3）目標檢測函數：用來確定一個狀態是不是目標。（4）路徑費用函數：對每條路徑賦予一定費用的函數。其中，初始狀態集合和操作符集合定義了問題的搜索空間。一般給定問題就是確定該問題的一些基本信息，一個問題由4部分組成:2023/9/226和通常的搜索空間不同，人工智能中大多數問題的狀態空間在問題求解之前不是全部知道的。

在人工智能中，搜索問題一般包括兩個重要的問題：搜索什么搜索什么通常指的就是目標。在哪里搜索在哪里搜索就是“搜索空間”。搜索空間通常是指一系列狀態的匯集，因此稱為狀態空間。2023/9/227所以，人工智能中的搜索可以分成兩個階段：狀態空間的生成階段在該狀態空間中對所求問題狀態的搜索搜索可以根據是否使用啟發式信息分為盲目搜索啟發式搜索2023/9/228盲目搜索只是可以區分出哪個是目標狀態。一般是按預定的搜索策略進行搜索。沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復雜問題的求解。

啟發式搜索是在搜索過程中加入了與問題有關的啟發式信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解并找到最優解。

2023/9/229根據問題的表示方式分為狀態空間搜索與或圖搜索狀態空間搜索是用狀態空間法來求解問題所進行的搜索與/或圖搜索是指用問題規約方法來求解問題時所進行的搜索。2023/9/2210考慮一個問題的狀態空間為一棵樹的形式。寬度優先搜索深度優先搜索如果根節點首先擴展，然后是擴展根節點生成的所有節點，然后是這些節點的后繼，如此反復下去。在樹的最深一層的節點中擴展一個節點。只有當搜索遇到一個死亡節點（非目標節點并且是無法擴展的節點）的時候，才返回上一層選擇其他的節點搜索。2023/9/2211無論是寬度優先搜索還是深度優先搜索，遍歷節點的順序一般都是固定的，即一旦搜索空間給定，節點遍歷的順序就固定了。這種類型的遍歷稱為“確定性”的，也就是盲目搜索。對于啟發式搜索，在計算每個節點的參數之前無法確定先選擇哪個節點擴展，這種搜索一般也稱為非確定的。2023/9/2212完備性：如果存在一個解答，該策略是否保證能夠找到？時間復雜性：需要多長時間可以找到解答？空間復雜性：執行搜索需要多少存儲空間？最優性：如果存在不同的幾個解答，該策略是否可以發現最高質量的解答？搜索策略評價標準:2023/9/2213有許多智力問題(如梵塔問題、旅行商問題、八皇后問題、農夫過河問題等)和實際問題（如路徑規劃、機器人行動規劃等）都可以歸結為狀態空間搜索。用狀態空間搜索來求解問題的系統均定義一個狀態空間，并通過適當的搜索算法在狀態空間中搜索解答路徑。3.2基于狀態空間的搜索技術2023/9/2214狀態空間搜索

——1.狀態空間及其搜索的表示(1)狀態空間的表示★狀態空間記為SP，可表示為二元組：SP=(S,O)S——問題求解（即搜索）過程中所有可能到達的合法狀態構成的集合；O——操作算子的集合，操作算子的執行會導致問題狀態的變遷；狀態——用于記載問題求解（即搜索）過程中某一時刻問題現狀的快照；抽象為矢量形式Q=[q0,q1,…,qn]T每個元素qi稱為狀態分量

給定每個狀態分量qi的值就得到一個具體的狀態

Qk=[q0k,q1k,…,qnk]T2023/9/2215狀態表示狀態的變遷操作算子問題的狀態空間是一個表示該問題的全部可能狀態及其變遷的有向圖。節點狀態有向弧狀態的變遷

弧上的標簽導致狀態變遷的操作算子

用狀態空間搜索來求解問題的系統均定義一個狀態空間，并通過適當的搜索算法在狀態空間中搜索解答路徑。2023/9/2216例1：走迷宮是人們熟悉的一種游戲。狀態空間搜索2023/9/2217格子、入口和出口——節點——狀態通道——有向弧——操作算子迷宮可以由一個有向圖表示2023/9/2218

例2:在一個3×3的方格棋盤上放置著1,2,3,4,5,6,7,8八個數碼，每個數碼占一格，且有一個空格。這些數碼可在棋盤上移動，其移動規則是：與空格相鄰的數碼方可移入空格。 現在的問題是：對于指定的初始棋局和目標棋局，給出數碼的移動序列。該問題稱為八數碼問題。

56741382初始棋局56748321目標棋局移動數碼2023/9/2219231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123847652023/9/22202023/9/2221

例3:錢幣翻轉問題。設有3個錢幣，其初始狀態為(正、反、正),欲得的目標狀態為(正、正、正)或(反、反、反)。問題是允許每次只能且必須翻轉一個錢幣，連翻三次。問能否達到目標狀態。分析：通過引入一個三維變量將問題表示出來。設三維變量為：Q=[q1,q2,q3]，式中qi(i=1,2,3)=1表示錢幣為正面，qi(i=1,2,3)=0表示錢幣為反面。則三個錢幣可能出現的狀態有8種組合：Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1),Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)。即初始狀態為Q5，目標狀態為Q0或Q7，要求步數為3。2023/9/2222錢幣問題的狀態空間圖2023/9/2223狀態空間搜索

——1.狀態空間及其搜索的表示(2)狀態空間表示的經典例子“傳教士和野人問題”★問題的描述：N個傳教士帶領N個野人劃船過河；3個安全約束條件：1)船上人數不得超過載重限量，設為K個人；2)任何時刻（包括兩岸、船上）野人數目不得超過傳教士；3)允許在河的某一岸或者在船上只有野人而沒有傳教士；2023/9/2224狀態空間搜索

——1.狀態空間及其搜索的表示(2)狀態空間表示的經典例子“傳教士和野人問題”特例：N=3，K=2狀態分量m——傳教士在左岸的實際人數狀態分量c——野人在左岸的實際人數狀態分量b——指示船是否在左岸(1、0)3個安全約束條件m≧c(左岸安全)且N-m≧N-c(右岸安全);(想一想，為什么不考慮船安全？)m=0且0≤c≤N(左岸沒有傳道士，右岸一定安全);N-m=0且0≤N-c≤N(右岸沒有傳道士，左岸一定安全);2023/9/2225設初始狀態下傳教士、野人和船都在左岸，目標狀態下這三者均在右岸，問題狀態以（m,c,b）表示。問題的求解任務可描述為：(3,3,1)→(0,0,0)該簡單問題可能到達的合法狀態：可能狀態總數：4×4×2=32根據條件得出合法狀態：20m≧c且N-m≧N-c(左岸安全且右岸安全)m=1,c=1；m=2,c=2

m=0且0≤c≤N(左岸沒有傳道士)m=0,c=0,1,2,3

N-m=0且0≤N-c≤N(右岸沒有傳道士)m=3,c=0,1,2,3不可能到達的合法狀態：(0,0,1),(0,3,0),(3,0,1),(3,3,0)可能到達的合法狀態共16個2023/9/2226狀態空間搜索

——1.狀態空間及其搜索的表示(2)狀態空間表示的經典例子“傳教士和野人問題”定義2類操作算子：L(x,y)——指示從左岸到右岸的劃船操作R(x,y)——指示從右岸到左岸的劃船操作x+y≤K=2(船的載重限制)；x和y取值的可能組合只有5個10，20，11，01，02

(允許在船上只有野人而沒有傳教士)共有10個操作算子2023/9/2227渡河問題的狀態空間有向圖2023/9/2228狀態空間搜索

——1.狀態空間及其搜索的表示總結狀態空間表示方法：★用狀態空間方法表示問題時，首先必須定義狀態的描述形式，通過使用這種描述形式可把問題的一切狀態都表示出來。另外，還要定義一組操作，通過使用這些操作可把問題由一種狀態轉變為另一種狀態。

問題的求解過程是一個不斷把操作作用于狀態的過程。如果在使用某個操作后得到的新狀態是目標狀態，就得到了問題的一個解。這個解是從初始狀態到目標狀態所用操作構成的序列。

2023/9/2229狀態空間搜索

——1.狀態空間及其搜索的表示總結狀態空間表示方法：★要使問題由一種狀態轉變到另一種狀態時，就必須使用一次操作。這樣，在從初始狀態轉變到目標狀態時，就可能存在多個操作序列(即得到多個解)。那么，其中使用操作最少或較少的解才為最優解(因為只有在使用操作時所付出的代價為最小的解才是最優解)。

對其中的某一個狀態，可能存在多個操作．使該狀態變到幾個不同的后繼狀態．那么到底用哪個操作進行搜索呢?這就有賴于搜索策略了．不同的搜索策略有不同的順序，這就是本章后面要討論的問題。

2023/9/2230課堂練習有一農夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設船太小，農夫每次只能帶一樣東西過河；考慮到安全，無農夫看管時，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請為該問題的解決設計狀態空間，并畫出狀態空間圖。

2023/9/2231解析以變量m、f、s、v分別指示農夫、狐貍、小羊、菜,且每個變量只可取值1(表示在左岸)或0(表示在右岸)。問題狀態可以四元組(m、f、s、v)描述,設初始狀態下均在左岸,目標狀態下都到達右岸。從而,問題求解任務可描述為

(1,1,1,1)->(0,0,0,0)思考：為什么不把船的狀態放到狀態空間中去？由于問題簡單,狀態空間中可能的狀態總數為2×2×2×2=16,由于要遵從安全限制,合法的狀態只有(除初、目狀態外):

1110，1101，1011，1010，0101，0001，0010，0100；

不合法狀態有:0111,1000,1100,0011,0110,1001設計二類操作算子:Lx、Rx,x為m、f、s、v時分別指示農夫獨自,帶狐貍,帶小羊,帶菜過河；狀態空間圖如下所示.由于Lx和Rx是互逆操作,故而解答路徑可有無數條,但最近的只有二條;都是7個操作步.2023/9/2232解析:四元組(m、f、s、v)代表（農夫、狐貍、小羊、菜）2023/9/2233狀態空間搜索

——1.狀態空間及其搜索的表示(3)狀態空間的搜索狀態空間的搜索記為SE，可表示為五元組：SE=(S,O,E,I,G)；E——搜索引擎；I——問題的初始狀態，I∈S；G——問題的目標狀態集合，G

S。搜索引擎E——可以設計為實現任何搜索算法的控制系統。基本思想——通過搜索引擎E尋找一個操作算子的調用序列，使問題從初始狀態I變遷到目標狀態G之一。解答路徑——初-目變遷過程中的狀態序列或相應的操作算子調用序列。2023/9/2234狀態空間搜索

——1.狀態空間及其搜索的表示或圖（一般圖）一個狀態可以有多個可供選擇的操作算子；操作算子間的選擇是一種“或”的關系;這樣的有向圖稱為或圖。2023/9/2235狀態空間搜索

——1.狀態空間及其搜索的表示(3)狀態空間的搜索或圖（一般圖）一個狀態可以有多個可供選擇的操作算子；操作算子間的選擇是一種“或”的關系，這樣的有向圖稱為或圖。狀態空間一般都表示為或圖（一般圖）搜索圖——在搜索解答路徑的過程中畫出搜索時涉及到的節點和弧線，構成所謂的搜索圖。狀態空間搜索一般圖搜索2023/9/2236狀態空間搜索

——1.狀態空間及其搜索的表示(3)狀態空間的搜索狀態空間、搜索圖和解答路徑之間的關系S0Sg2023/9/2237狀態空間搜索

——1.狀態空間及其搜索的表示(4)一般圖搜索例子——八數碼游戲

求解的問題：給定初始布局(即初始狀態)和目標布局(即目標狀態)，如何移動數碼才能從初始布局到達目標布局？解答就是一個合法的棋牌走步序列。初始布局目標布局移動數碼2023/9/2238狀態空間搜索

——1.狀態空間及其搜索的表示(4)一般圖搜索例子——八數碼游戲

用一般圖搜索方法解決該問題的步驟：1、為問題狀態的表示建立數據結構2、制定操作算子集合3、設計搜索引擎第一步：為問題狀態的表示建立數據結構3×3的一個矩陣S矩陣元素Sij∈{0,1,2,3,4,5,6,7,8},其中1≤i,j≤3數字0表示空格數字1-8表示相應的棋牌八數碼問題就可表示為：2023/9/2239狀態空間搜索

——1.狀態空間及其搜索的表示初始布局目標布局移動數碼(4)一般圖搜索例子——八數碼游戲

2023/9/2240狀態空間搜索

——1.狀態空間及其搜索的表示(4)一般圖搜索例子——八數碼游戲

第二步：制定操作算子集直觀方法——為每個棋牌制定一套可能的走步：左、上、右、下四種移動。需要32個操作算子簡易方法——僅為空格制定這4種走步。僅需4個操作算子第三步：設計搜索引擎

問題狀態空間的大小與問題涉及的元素個數是程指數級爆炸式增長（即，組合爆炸問題）如，棋盤布局（問題狀態）總共有9!=362880個研究焦點是解決組合爆炸問題，通過壓縮搜索空間，提高搜索效率。2023/9/2241狀態空間搜索

——1.狀態空間及其搜索的表示狀態空間、搜索圖和解答路徑之間的關系S0Sg2023/9/2242狀態空間搜索

——2.一般圖搜索策略

（1）搜索術語★1、節點深度根節點指示初始狀態，令其深度為0；搜索圖中的其他節點的深度dn就可以遞歸地定義為其父節點深度dn-1加1：dn=dn-1+1。

根節點深度=0第n-1層節點dn-1第n層節點dn=

dn-1+1搜索圖2023/9/2243狀態空間搜索

——2.一般圖搜索策略

（1）搜索術語★2、節點擴展應用操作算子將上一狀態（節點ni）變遷到下一狀態（節點nj）節點ni稱為被擴展節點（父節點）節點nj稱為ni的子節點節點ni節點nj2023/9/2244（1）搜索術語★3、路徑節點ni到nj的路徑是由相鄰節點間的弧線構成的折線要求路徑是無環的4、路徑代價——相鄰節點ni和ni+1間的路徑代價記為C(ni,ni+1)通常令任意相鄰節點間的路徑代價相同，并以路徑長度1指示。即C(ni,ni+1)=1。狀態空間搜索

——2.一般圖搜索策略節點ni節點ni+1節點nj2023/9/2245狀態空間搜索

——2.一般圖搜索策略

（1）搜索術語★4、路徑代價目標狀態節點ng節點ni節點nkC(nk,ng)

C(ni,nk)

C(ni,ng)

2023/9/2246狀態空間搜索

——2.一般圖搜索策略（2）一般圖搜索算法★符號說明：s-初始狀態節點G-搜索圖OPEN-存放待擴展節點的表CLOSE-存放已被擴展的節點的表MOVE-FIRST(OPEN)-取OPEN表首的節點作為當前要被擴展的節點n，同時將節點n移至CLOSE表一般圖搜索算法劃分為二個階段：1、初始化

2、搜索循環

2023/9/2247狀態空間搜索

——2.一般圖搜索策略（2）一般圖搜索算法★算法劃分為二個階段：1、初始化建立只包含初始狀態節點s的搜索圖G:={s}OPEN:={s}CLOSE:={}2、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n作為擴展的節點，同時將其移到close表擴展出n的子節點,插入搜索圖G和OPEN表適當的標記和修改指針排序OPEN表通過循環地執行該算法，搜索圖G會因不斷有新節點加入而逐步長大，直到搜索到目標節點。2023/9/2248以下面的八數碼為例，看一般圖的搜索算法初始布局目標布局移動數碼狀態空間搜索

——2.一般圖搜索策略2023/9/22492023/9/22502023/9/22512023/9/22522023/9/22532023/9/22542023/9/22552023/9/22562023/9/22572023/9/22582023/9/22592023/9/22602023/9/22612023/9/22622023/9/22632023/9/22642023/9/22652023/9/22662023/9/22672023/9/2268狀態空間搜索

——2.一般圖搜索策略（2）一般圖搜索算法——搜索過程中的指針修改★節點n擴展后的子節點分為3類：(i)全新節點(ii)已出現在OPEN表中的節點(iii)已出現的CLOSE表中的節點指針標記和修改的方法：(i)類節點：加入OPEN表，建立從子節點到父節點n的指針(ii)類節點、(iii)類節點比較經由老父節點、新父節點n到達初始狀態節點的路徑代價

經由節點n的代價比較小，則移動子節點指向老父節點的指針，改為指向新父節點n

(iii)類節點還得從CLOSE表中移出，重新加入OPEN表。2023/9/2269狀態空間搜索

——2.一般圖搜索策略Sn4ninjn1n2n3n31n32節點ni是當前擴展的節點；擴展出4個后續節點；n1、n2是新節點，只需建立指向父節點的指針，并加入OPEN表；2023/9/2270狀態空間搜索

——2.一般圖搜索策略Sn4ninjn1n2n3n31n32n4已經存在于OPEN表，并且已有父節點njn4經nj的路徑代價大取消n4指向nj的指針改為建立n4指向新父節點ni的指針n3已經存在于CLOSE表，并且已有父節點nj需要做和n4同樣的比較和指針修改工作。并且要重新加入open表。2023/9/22713.3

盲目搜索

提高搜索效率的關鍵——優化OPEN表中節點的排序方式。簡單的排序策略——按預先確定的順序或隨機地排序新加入到OPEN表中的節點。

常用的簡單方式：

寬度優先——擴展當前節點后生成的子節點總是置于OPEN表的后端，即OPEN表作為隊列使用，先進先出，使搜索優先向橫廣方向發展。

深度優先——擴展當前節點后生成的子節點總是置于OPEN表的前端，即OPEN表作為棧使用，后進先出，使搜索優先向縱深方向發展。2023/9/2272寬度優先寬度優先——擴展當前節點后生成的子節點總是置于OPEN表的后端，即OPEN表作為隊列，先進先出，使搜索優先向橫向方向發展。過程：指從初始節點S0開始，向下逐層搜索，在n層節點未搜索完之前，不進入n+1層搜索。同層節點的搜索次序可以任意。即先按生成規則生成第一層節點，在該層全部節點中沿寬(廣)度進行橫向掃描，檢查目標節點Sg是否在這些子節點中。若沒有,則再將所有笫一層節點逐一擴展，得到第二層節點。并逐一檢查第二層節點中是否包含有Sg，如此依次按照先生成、先檢查、先擴展的原則進行下去，直到發現Sg為止

2023/9/2273寬度優先實例23184765283147652318476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654910111213141516172023/9/2274寬度優先搜索

如果搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索。這種搜索是逐層進行的，在對下一層的任意節點進行搜索之前，必須搜索完本層的所有節點。“先產生的節點先擴展”2023/9/2275(1)把初始節點S0，放入OPEN表。

(2)如果OPEN表為空。則問題無解，失敗并退出。

(3)把OPEN表中的第一個節點取出放入CLOSE表中，并按順序冠以編號n；

(4)考察節點n是否為目標節點。若是，則求得了問題的解，成功并退出。

(5)若節點n不可擴展，則轉第(2)步；

(6)擴展節點n，將其子節點放到OPEN表的尾部，并為每一個子節點都配置指向父節點的指針，然后轉第(2)步。采用隊列結構，寬度優先算法可以表示如下：2023/9/2276

例通過挪動積木塊，希望從初始狀態達到一個目的狀態，即三塊積木堆疊在一起。積木A在頂部，積木B在頂中間，積木C在底部。請畫出按照寬度優先搜索策略所產生的搜索樹。這個問題的唯一操作算子為MOVE(X,Y)，即積木X搬到Y（積木或桌面）上面。如“挪動積木A到桌面上表示為MOVE(A,Table)。該操作算子可運用的先決條件是：（1）被挪動積木的頂部必須為空。（2）如Y是積木（不是桌面），則積木Y的頂部也必須為空。（3）同一狀態下，運用操作算子的次數不得多于一次。2023/9/2277積木問題的寬度優先搜索樹

2023/9/2278寬度優先搜索的性質當問題有解時，一定能找到解(完備性)當問題為單位代價時，且問題有解時，一定能找到最優解（最優性）方法與問題無關，具有通用性效率較低屬于圖搜索方法2023/9/2279寬度優先搜索是一種盲目搜索，時間和空間復雜度都比較高，當目標節點距離初始節點較遠時會產生許多無用的節點，搜索效率低。寬度優先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執行時間更嚴重的問題。

寬度優先搜索優點：目標節點如果存在，用寬度優先搜索算法總可以找到該目標節點，而且是最小（即最短路徑）的節點。寬度優先搜索的優點和缺點2023/9/2280深度優先深度優先——擴展當前節點后生成的子節點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優先向縱深方向發展。過程：從初始節點S0開始，按生成規則生成下一級各子節點，檢查是否出現目標節點Sg；若未出現，則按“最晚生成的子節點優先擴展”的原則，再用生成規則生成再下一級的子節點，再檢查是否出現Sg；若仍未出現，則再擴展最晚生成的子節點。如此下去，沿著最晚生成的子節點分枝，逐級“縱向”深入搜索。

2023/9/2281深度優先實例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123468911131416181912384765目標571012151720212023/9/2282深度優先搜索在深度優先搜索中，首先擴展最新產生的(最深的)節點，深度相等的節點可以任意排列。“最晚產生的節點最先擴展”起始節點深度為0任何其他節點的深度等于其父輩節點深度加上1

:dn=dn-1+12023/9/2283深度優先搜索很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴展下去，這當然是不允許的。為保證找到解，應選擇適當的深度界限，或者采取不斷加大深度界限的辦法，反復搜索，直到找到解。這種改進的方法叫做迭代加深搜索。2023/9/2284(1)把初始節點S0放入OPEN表；

(2)如果OPEN表為空，則問題無解，失敗并退出。

(3)把OPEN表中的第一個節點取出放入CLOSE表中，并按順序冠以編號n；

(4)考察節點n是否為目標節點。若是，則求得了問題的解，成功并退出。

(5)若節點n不可擴展，則轉第(2)步；

(6)擴展節點n，將其子節點放到OPEN表的首部，并為其配置指向父節點的指針，然后轉第(2)步。基于棧實現的深度優先搜索算法：2023/9/2285

例卒子穿陣問題:要求一卒子從頂部通過圖所示的列陣到達底部。要求卒子行進中不可進入到代表敵兵駐守的區域內（標注1），并不準后退。假定限制值為5。請畫出按照深度優先搜索策略所產生的搜索樹2023/9/2286卒子穿陣的深度優先搜索樹2023/9/2287深度優先搜索的性質一般不能保證找到最優解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關的方法2023/9/2288深度優先搜索的優點是比寬度優先搜索算法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當前正在搜索的路徑和該路徑上還沒有完全展開的節點標志所組成。深度優先搜索的存儲器要求是深度約束的線性函數。深度優先搜索的優點2023/9/2289深度優先搜索的缺點

既不是完備的，也不是最優的。主要問題是可能搜索到了錯誤的路徑上。很多問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一來對于這些問題，深度優先搜索要么陷入無限的循環而不能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優的答案。2023/9/2290比較

適用場合

深度優先——當一個問題有多個解答或多條解答路徑，且只須找到其中一個時；往往應對搜索深度加以限制。

寬度優先——確保搜索到最短的解答路徑。共同優缺點：

可直接應用一般圖搜索算法實現，不需要設計特別的節點排序方法，從而簡單易行，適合于許多復雜度不高的問題求解任務。

節點排序的盲目性，由于不采用領域專門知識去指導排序，往往會在白白搜索了大量無關的狀態節點后才碰到解答，所以也稱為盲目搜索。

2023/9/2291有界深度搜索和迭代加深搜索

有界深度優先搜索過程總體上按深度優先算法方法進行，但對搜索深度需要給出一個深度限制dm，當深度達到了dm的時候，如果還沒有找到解答，就停止對該分支的搜索，換到另外一個分支進行搜索。2023/9/2292(1)把初始節點S0放入OPEN表中，置S0的深度d(S0)=0。

(2)如果OPEN表為空，則問題無解，失敗并退出。

(3)把OPEN表中的第一個節點取出放入CLOSE表中。并按順序冠以編號n。(4)考察節點n是否為目標節點。若是，則求得了問題的解，成功并退出。

(5)如果節點n的深度d(n)=dm，則轉第(2)步。

(6)如果節點n不可擴展，則轉第(2)步。

(7)擴展節點n。將其子節點放入OPEN表的首部，并為其配置指向父節點的指針。然后轉第(2)步。有界深度搜索算法2023/9/2293策略說明:（1）深度限制dm很重要。當問題有解，且解的路徑長度小于或等于dm時，則搜索過程一定能夠找到解，但是和深度優先搜索一樣這并不能保證最先找到的是最優解。但是當dm取得太小，解的路徑長度大于dm時，則搜索過程中就找不到解，即這時搜索過程甚至是不完備的。2023/9/2294（2）深度限制dm不能太大。當dm太大時，搜索過程會產生過多的無用節點，既浪費了計算機資源，又降低了搜索效率。（3）有界深度搜索的主要問題是深度限制值dm的選取。2023/9/2295改進方法：（迭代加深搜索）先任意給定一個較小的數作為dm，然后按有界深度算法搜索，若在此深度限制內找到了解，則算法結束；如在此限制內沒有找到問題的解，則增大深度限制dm，繼續搜索。2023/9/2296迭代加深搜索，試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等。如果初始深度為0，則該算法只生成根節點，并檢測它。如果根節點不是目標，則深度加1，通過典型的深度優先算法，生成深度為1的樹。當深度限制為m時，樹的深度為m。2023/9/2297迭代加深搜索看起來會很浪費，因為很多節點都可能擴展多次。然而對于很多問題，這種多次的擴展負擔實際上很小，直覺上可以想象，如果一棵樹的分支系數很大，幾乎所有的節點都在最底層上，則對于上面各層節點擴展多次對整個系統來說影響不是很大。

2023/9/2298

ProcedureIterative-deepeningBegin (1)設置當前深度限制=1;(2)把初始節點壓入棧,并設置棧頂指針;(3)While棧不空并且深度在給定的深度限制之內doBegin

彈出棧頂元素；

If棧頂元素=goal,返回并結束;Else以任意的順序把棧頂元素的子女壓入棧中; EndEndwhild(4)深度限制加1,并返回2;End.迭代加深搜索算法2023/9/2299總結寬度優先搜索、深度優先搜索和迭代加深搜索都可以用于生成和測試算法。寬度優先搜索需要指數數量的空間，深度優先搜索的空間復雜度和最大搜索深度呈線性關系。2023/9/22100迭代加深搜索對一棵深度受控的樹采用深度優先的搜索。它結合了寬度優先和深度優先搜索的優點。和寬度優先搜索一樣，它是最優的，也是完備的。但對空間要求和深度優先搜索一樣是適中的。2023/9/22101搜索最優策略的比較表注：b是分支系數，d是解答的深度，m是搜索樹的最大深度，l是深度限制。2023/9/221023.4啟發式搜索★一般圖搜索算法常用的簡單方式：深度優先寬度優先【缺點：節點排序的盲目性】在白白搜索了大量無關的狀態節點后才碰到解答，效率低提高一般圖搜索效率的關鍵★優化OPEN表中節點的排序方式盲目搜索2023/9/22103125634最理想情況：每次排序后OPEN表表首元素n總在解答路徑上2023/9/22104啟發式搜索啟發式知識指導OPEN表排序的一般圖搜索：全局排序——對OPEN表中的所有節點排序，使最有希望的節點排在表首。A算法，A*算法（重點掌握！）局部排序——僅對新擴展出來的子節點排序，使這些新節點中最有希望者能優先取出考察和擴展；爬山法（了解，對深度優先法的改進）；2023/9/22105啟發式搜索

——1.A算法（掌握）【基本思想】設計體現啟發式知識的評價函數f(n)；指導一般圖搜索中OPEN表待擴展節點的排序：【評價函數f(n)=g(n)+h(n)】★n-搜索圖G中的節點；f(n)-G中從初始狀態節點s，經由節點n到達目標節點ng，估計的最小路徑代價；g(n)-G中從s到n，目前實際的路徑代價；h(n)-從n到ng，估計的最小路徑代價；2023/9/22106啟發式搜索

——1.A算法（掌握）Snng目標狀態節點ng初始狀態節點S節點n搜索圖Gh(n):

n-ng的估計最小路徑代價

g(n):s-n的實際路徑代價

f(n):s-n-ng的估計最小路徑代價

2023/9/22107啟發式搜索

——1.A算法（掌握）【評價函數f(n)=g(n)+h(n)】n-搜索圖G中的節點；f(n)-G中從s經n到ng，估計的最小路徑代價；g(n)-G中從s到n，目前實際的路徑代價；h(n)-從n到ng，估計的最小路徑代價；

h(n)值-依賴于啟發式知識加以計算；h(n)稱為啟發式函數★

。如何用評價函數來實現A算法?（掌握！）2023/9/22108啟發式搜索

——1.A算法（掌握）A算法的設計與一般圖搜索相同，劃分為二個階段★：1、初始化建立只包含初始狀態節點s的搜索圖G:={s}OPEN:={s}CLOSE:={}2、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n

⑥擴展出n的子節點,插入搜索圖G和OPEN表⑦適當的標記和修改指針（子節點父節點）⑧排序OPEN表（評價函數f(n)的值排序）通過循環地執行該算法，搜索圖會因不斷有新節點加入而逐步長大，直到搜索到目標節點。2023/9/22109啟發式搜索

——1.A算法（掌握）算法A的設計與一般圖搜索類似，劃分為二個階段★：1、初始化2、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n

⑥擴展出n的子節點,插入搜索圖G和OPEN表對每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni)⑦適當的標記和修改指針（子節點父節點）⑧排序OPEN表（評價函數f(n)的值排序）2023/9/22110啟發式搜索

——1.A算法（掌握）⑥擴展出n的子節點,插入搜索圖G和OPEN表對每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni)⑦適當的標記和修改指針（子節點父節點）(i)全新節點：f(ni)=f(n,ni)(ii)已出現在OPEN表中的節點(iii)已出現的CLOSE表中的節點IF

f(ni)>f(n,ni)

THEN

修改指針指向新父結點n

f(ni)=f(n,ni)⑧排序OPEN表（f(n)值從小到大排序）2023/9/221112.若OPEN表是空表，則失敗退出；算法A3.選擇OPEN表上的第一個節點，把它從OPEN表移出并放進CLOSE表中，稱此節點為節點n；

1.建立一個只包含起始節點S的搜索圖G,把S放到一個叫OPEN的未擴展節點表中；建立一個叫做CLOSE的已擴展節點表，其初始為空表；5.擴展節點n，同時生成不是n的祖先的那些子節點的集合M,把M的這些成員作為n的后繼節點添入圖G中；對于M中每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni);4.若n為一目標節點，則有解成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的；2023/9/221126.對那些未曾在G中出現過的M成員（全新結點）設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN表上的每一個M成員，比較子節點ni經由新、老父節點的評價函數值f(n,ni)、f(ni);若f(n,ni)<f(ni)點,則令f(ni)=f(n,ni),并移動子節點指向老父節點的指針，改為指向新父節點。對已在CLOSE表上的每個M成員，作與第2類同樣的處理，并把這些子結點從CLOSE表移出，重新加入OPEN表。7.按f(n)排序OPEN表中的節點，f(n)值最小者排在首位，重排OPEN表；8.轉2。此過程生成一個明確的圖G(搜索圖）和一個G的子集T(搜索樹）。2023/9/22113啟發式搜索

——1.A算法（掌握）A算法實例——八數碼游戲1)設計評價函數f(n)f(n)=d(n)+w(n),其中d(n)-節點n在搜索圖中的節點深度，對g(n)的度量；w(n)-代表啟發式函數h(n),其值是節點n與目標狀態節點ng相比較，不考慮空格，錯位的棋牌個數；初始布局目標布局移動數碼2023/9/22114啟發式搜索

——1.A算法（掌握）啟發式算法A實例——八數碼游戲1)設計評價函數f(n)f(n)計算實例初始布局s目標布局ngw(s):錯位的棋牌個數d(s):當前節點深度

f(s)h(n):n-ng的最小路徑代價g(n):s-n的最小路徑代價

f(n):s-n-ng的最小路徑代價

注：W(S)不考慮空格2023/9/22115狀態空間搜索

——2.一般圖搜索策略

（1）搜索術語1、節點深度根節點指示初始狀態，令其深度為0；搜索圖中的其他節點的深度dn就可以遞歸地定義為其父節點深度dn-1加1：dn=dn-1+1。

根節點深度=0第n-1層節點dn-1第n層節點dn=

dn-1+1搜索圖G2023/9/22116啟發式搜索

——1.A算法（掌握）啟發式算法A實例——八數碼游戲1)設計評價函數f(n)f(n)計算實例初始布局s目標布局ngw(s):錯位的棋牌個數d(s):當前節點深度

f(s)h(n):n-ng的最小路徑代價g(n):s-n的最小路徑代價

f(n):s-n-ng的最小路徑代價

0

4

4

注：W(S)不考慮空格2023/9/22117初始化OPEN:={s4}

CLOSE:={}

目標布局ng2023/9/22118循環1CLOSE:={s4}

OPEN:={a

b

c}

OPEN:={a6

b4

c6}

OPEN:={b4

a6

c6}

目標布局ng2023/9/22119循環2CLOSE:={s4

b4}

OPEN:={a6 c6

d

e

i}

OPEN:={a6 c6

d5

e5

i6}

OPEN:={d5

e5 a6 c6

i6}

目標布局ng2023/9/22120循環3CLOSE:={s4 b4

d5}

OPEN:={e5 a6 c6 i6

j

k}

OPEN:={e5 a6 c6 i6

j7

k6}

OPEN:={e5 a6 c6 i6

k6

j7}

目標布局ng2023/9/22121循環4CLOSE:={s4,b4,d5,e5}

OPEN:={a6 c6 i6 k6 j7

l

m}

OPEN:={a6 c6 i6 k6 j7

l5

m7}

OPEN:={l5 a6 c6 i6 k6 j7

m7}

目標布局ng2023/9/22122CLOSE:={s4,b4,d5,e5,l5}

循環5OPEN:={a6 c6 i6 k6 j7 m7

n}

OPEN:={a6 c6 i6 k6 j7 m7

n5}

OPEN:={n5 a6 c6 i6 k6 j7 m7}

目標布局ng2023/9/22123循環6CLOSE:={s4,b4,d5, e5,l5,n5}

OPEN:={a6 c6 i6 k6 j7 m7

o

g}

OPEN:={a6 c6 i6 k6 j7 m7

o7

g5}

OPEN:={g5 a6 c6 i6 k6 j7 m7

o7}

目標布局ng2023/9/22124循環7成功結束目標布局ng2023/9/22125最理想搜索圖G2023/9/22126判斷失誤2023/9/22127

例2

給定4L和3L的水壺各一個，水壺上沒有刻度，可以向水壺中加水。如何在4L的壺中準確地得到2L水？

（x,y）——4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節點。則給出下面的啟發式函數：2023/9/22128h(n)=2

如果0<x<4并且0<y<3

=4 如果0<x<4或者0<y<3

=8 如果x=0并且y=3

或者x=4并且y=0 =10 如果x=0并且y=0

或者x=4并且y=3假定g(n)表示搜索樹中搜索的深度，則根據圖搜索策略得下圖的搜索空間。

2023/9/22129水壺問題的狀態空間擴展圖在第0步，由節點O可以得到g+h=10。在第1步，得到兩個節點M和N，其估價函數值都為1+8=9，因此可以任選一個節點擴展。2023/9/22130水壺問題的狀態空間擴展圖假定選擇了節點M，在第2步擴展M得到兩個后繼了點P和R，對于P有2+4=6，對于R有2+10=12。現在，在節點P、R、N中，節點P具有最小的估價函數值，所以選擇節點P擴展。在第3步，可以得到節點S，其中3+4=7。現在，在節點S、R、N中，節點S的估價函數值最小，所以下一步就會選擇S節點擴展。該過程一直進行下去，直到到達目標節點。

2023/9/22131啟發式搜索

——2.實現啟發式搜索的關鍵因素（理解）實現啟發式搜索應考慮的關鍵因素★：（1）搜索算法的可采納性(Admissibility);（2）啟發式函數h(n)的強弱及其影響；2023/9/22132啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)-1968★1)定義在存在從初始狀態節點到目標狀態節點解答路徑的情況下，若一個搜索法總能找到最短（代價最小）的解答路徑，則稱該狀態空間中的搜索算法具有可采納性，也叫最優性。如，寬度優先的搜索算法是可采納的，只是搜索效率不高。2)A算法的可采納性——定義f*(n)=g*(n)+h*(n)n-搜索圖G中最短解答路徑的節點；f*(n)-s經節點n到ng的實際最短解答路徑的路徑代價；g*(n)-該路徑前段（從s到n）的路徑代價；h*(n)-該路徑后段（從n到ng）的路徑代價；2023/9/22133啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)★3)評價函數f與f*的比較f(n)、g(n)、h(n)分別是f*(n)、g*(n)、h*(n)的近似值（估計值）理想情況下：若g(n)=g*(n)、h(n)=h*(n)，則搜索過程中，每次都正確選擇，不擴展任何無關的節點。實際情況：設計接近f*的f是很困難的在算法執行過程中，g(n)容易從已經生成的搜索樹中計算出來Sn搜索圖Gng2023/9/22134啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)★3)評價函數f與f*的比較理想情況下：若g(n)=g*(n)、h(n)=h*(n)，不擴展無關的節點實際情況：設計接近f*的f是很困難的在算法執行過程中，g(n)容易從已經生成的搜索樹中計算出來，比如就以節點深度d(n)當做g(n),且有g(n)>=g*(n)h(n)盡可能靠近h*(n)——A算法的關鍵。2023/9/22135啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)4)改進啟發式函數——八數碼游戲f(n)=d(n)+w(n),其中w(n)-表示錯位的棋牌個數，不夠貼切，錯誤的擴展了節點d；p(n)-節點n與目標狀態節點比較，錯位棋牌在不受阻攔的情況下，移動到目標狀態相應位置所需走步（移動次數）的總和；p(n)比w(n)更接近于h*(n)-p(n)不僅考慮了棋牌的錯位因素，還考慮了錯位的距離（移動距離）2023/9/22136啟發式搜索

——2.實現啟發式搜索的關鍵因素4)改進啟發式函數——八數碼游戲f(s)計算實例初始布局s目標布局ngw(s):錯位的棋牌個數d(s):當前節點深度

f(s)0

4

4

p(s):錯位棋牌移動距離d(s):當前節點深度

f(s)0

5

5

1

1

1

2

2023/9/22137初始化OPEN:={s5}

CLOSE:={}

目標布局ng2023/9/22138循環1CLOSE:={s5}

OPEN:={a

b

c}

OPEN:={a7

b5

c7}

OPEN:={b5 a7 c7}

目標布局ng2023/9/22139循環2CLOSE:={s5

b5}

OPEN:={a7 c7

d

e

i}

OPEN:={a7 c7

d7

e5

i7}

OPEN:={e5 a7 c7

d7

i7}

目標布局ng2023/9/22140循環3CLOSE:={s5 b5

e5}

OPEN:={a7 c7 d7 i7 l m}

OPEN:={a7 c7 d7 i7 l5 m7}

OPEN:={l5 a7 c7 d7 i7 m7}

目標布局ng2023/9/22141CLOSE:={s5,b5,e5,l5}

循環4OPEN:={a7 c7 d7 i7

m7 n}

OPEN:={a7 c7 d7 i7

m7 n5}

OPEN:={n5 a7 c7 d7 i7

m7}

目標布局ng2023/9/22142CLOSE:={s5,b5, e5,l5,

n5}

循環5OPEN:={a7 c7 d7 i7

m7

o g}

OPEN:={a7 c7 d7 i7

m7

o7 g5}

OPEN:={g5 a7 c7 d7 i7

m7

o7}

目標布局ng2023/9/22143循環6成功結束最理想搜索圖G目標布局ng2023/9/22144避免了錯誤選擇2023/9/22145啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)5)A*算法定義★：1、在A算法中，規定h(n)≤h*(n);2、經如此限制以后的A算法就是A*算法。A*算法是可采納的，即總能搜索到最短解答路徑【回顧：八數碼游戲的h(n)】w(n)-錯位的棋牌個數p(n)-錯位棋牌在不受阻攔的情況下，移動到目標狀態相應位置所需走步（移動次數）的總和；上述兩者均是可采納的。(想想為什么)2023/9/22146啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)5)A*算法定義：1、在A算法中，規定h(n)≤h*(n);2、經如此限制以后的A算法就是A*算法。A*算法是可采納的，即總能搜索到最短解答路徑證明：【《人工智能上冊》陸汝鈐P248】1）如果存在一條從初始狀態到目標狀態的解答路徑，則一定存在一條最短解答通路；2）設狀態n’是最短解答路徑上的一個狀態，那么經過有限步后，n’必然會成為OPEN表的第一個節點；3）因為最短解答路徑只有有限個節點n’，所以有限步后算法必然因到達目標狀態ng。這就是最優解。證明完畢。2023/9/22147啟發式搜索

——2.實現啟發式搜索的關鍵因素（1）搜索算法的可采納性(Admissibility)5)滿足可采納性條件的算法——A*算法證明：2）設狀態n’是最短解答路徑上的一個狀態，那么經過有限步后，n’必然會成為OPEN表的第一個節點；f(n’)=g(n’)+h(n’)∵根據假設，n’在最短解答路徑上∴經過有限步驟后，g(n’)=g*(n’)∴f(n’)=g*(n’)+h(n’)∵h(n)≤h*(n)∴f(n’)=g*(n’)+h(n’)≤g*(n’)+h*(n’)=f*(n’)∵f*(n’)=f*(ng)∴f(n’)≤f*(ng)2023/9/22148啟發式搜索

——2