1、2022/7/171第3章 搜索戰略問題求解系統劃分為兩大類知識貧乏系統 依托搜索技術處理問題 知識貧乏、缺乏針對性效率低 知識豐富系統 依托推理技術處理問題基于豐富知識的推理技術，直截了當 效率高 2022/7/172第3章 搜索戰略兩大類搜索技術:1、普通圖搜索、啟發式搜索2、基于問題歸約的與或圖搜索 兩種典型的推理技術:1、基于歸結的演繹推理歸結反演2、基于規那么的演繹推理正向演繹推理逆向演繹推理 2022/7/1733.1 引言 對于給定的問題，智能系統的行為普通是找到可以到達所希望目的的動作序列，并使其所付出的代價最小、性能最好。基于給定的問題，問題求解的第一步是目的的表示。搜索就是

2、找到智能系統的動作序列的過程。 2022/7/174搜索算法的輸入是給定的問題，輸出時表示為動作序列的方案。一旦有了方案，就可以執行該方案所給出的動作了。執行階段因此，求解問題包括：目的表示搜索執行2022/7/1751初始形狀集合：定義了初始的環境。2操作符集合：把一個問題從一個形狀變換為另一個形狀的動作集合。3目的檢測函數：用來確定一個形狀是不是目的。4途徑費用函數：對每條途徑賦予一定費用的函數。其中，初始形狀集合和操作符集合定義了問題的搜索空間。普通給定問題就是確定該問題的一些根本信息，一個問題由4部分組成:2022/7/176和通常的搜索空間不同，人工智能中大多數問題的形狀空間在問題求

3、解之前不是全部知道的。 在人工智能中，搜索問題普通包括兩個重要的問題：搜索什么搜索什么通常指的就是目的。在哪里搜索在哪里搜索就是“搜索空間。搜索空間通常是指一系列形狀的聚集，因此稱為形狀空間。2022/7/177所以，人工智能中的搜索可以分成兩個階段：形狀空間的生成階段在該形狀空間中對所求問題形狀的搜索搜索可以根據能否運用啟發式信息分為盲目搜索啟發式搜索 2022/7/178盲目搜索 只是可以區分出哪個是目的形狀。 普通是按預定的搜索戰略進展搜索。 沒有思索到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復雜問題的求解。 啟發式搜索是在搜索過程中參與了與問題有關的啟發式信息，用于指

4、點搜索朝著最有希望的方向前進，加速問題的求解并找到最優解。 2022/7/179根據問題的表示方式分為形狀空間搜索與或圖搜索形狀空間搜索是用形狀空間法來求解問題所進展的搜索與/或圖搜索是指用問題規約方法來求解問題時所進展的搜索。2022/7/1710思索一個問題的形狀空間為一棵樹的方式。寬度優先搜索深度優先搜索假設根節點首先擴展，然后是擴展根節點生成的一切節點，然后是這些節點的后繼，如此反復下去。在樹的最深一層的節點中擴展一個節點。只需當搜索遇到一個死亡節點非目的節點并且是無法擴展的節點的時候，才前往上一層選擇其他的節點搜索。2022/7/1711無論是寬度優先搜索還是深度優先搜索，遍歷節點的

5、順序普通都是固定的，即一旦搜索空間給定，節點遍歷的順序就固定了。這種類型的遍歷稱為“確定性的，也就是盲目搜索。對于啟發式搜索，在計算每個節點的參數之前無法確定先選擇哪個節點擴展，這種搜索普通也稱為非確定的。 2022/7/1712完備性：假設存在一個解答，該戰略能否保證可以找到？時間復雜性：需求多長時間可以找到解答？空間復雜性：執行搜索需求多少存儲空間？最優性：假設存在不同的幾個解答，該戰略能否可以發現最高質量的解答？搜索戰略評價規范:2022/7/1713有許多智力問題(如梵塔問題、游覽商問題、八皇后問題、農夫過河問題等)和實踐問題如途徑規劃、機器人行動規劃等都可以歸結為形狀空間搜索。用形狀

6、空間搜索來求解問題的系統均定義一個形狀空間，并經過適當的搜索算法在形狀空間中搜索解答途徑。3.2 基于形狀空間的搜索技術2022/7/1714形狀空間搜索1.形狀空間及其搜索的表示(1)形狀空間的表示形狀空間記為SP，可表示為二元組：SP=(S,O)S問題求解即搜索過程中一切能夠到達的合法形狀構成的集合；O操作算子的集合，操作算子的執行會導致問題形狀的變化 ；形狀用于記載問題求解即搜索過程中某一時辰問題現狀的快照；籠統為矢量方式 Q=q0,q1,qnT每個元素qi稱為形狀分量 給定每個形狀分量qi的值就得到一個詳細的形狀 Qk=q0k,q1k,qnkT2022/7/1715形狀表示形狀的變化操

7、作算子問題的形狀空間是一個表示該問題的全部能夠形狀及其變化的有向圖。 節點形狀有向弧形狀的變化 弧上的標簽導致形狀變化的操作算子 用形狀空間搜索來求解問題的系統均定義一個形狀空間，并經過適當的搜索算法在形狀空間中搜索解答途徑。2022/7/1716例1：走迷宮是人們熟習的一種游戲。形狀空間搜索2022/7/1717格子、入口和出口節點形狀通道有向弧操作算子迷宮可以由一個有向圖表示2022/7/1718 例2:在一個33的方格棋盤上放置著1,2,3,4,5,6,7,8八個數碼，每個數碼占一格，且有一個空格。這些數碼可在棋盤上挪動，其挪動規那么是：與空格相鄰的數碼方可移入空格。如今的問題是：對于指

8、定的初始棋局和目的棋局，給出數碼的挪動序列。該問題稱為八數碼問題。 56741382初始棋局56748321目的棋局挪動數碼2022/7/17192 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5

9、 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52022/7/17202022/7/1721 例3:錢幣翻轉問題。設有3個錢幣，其初始形狀為(正、反、正),欲得的目的形狀為(正、正、正)或(反、反、反)。問題是允許每次只能且必需翻轉一個錢幣，連翻三次。問能否到達目的形狀。 分析：經過引入一個三維變量將問題表示出來。設三維變量為：Q=q1,q2,q3，式中qi (i=1,2,3)=1表示錢幣為正面，qi (i=1,2,3)=0表示錢幣為反面。那么三個錢幣能夠出現的形狀有8種組合：Q0=(0,0,0),Q1=(

10、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。2022/7/1722錢幣問題的形狀空間圖2022/7/1723形狀空間搜索1.形狀空間及其搜索的表示(2)形狀空間表示的經典例子“傳教士和野人問題 問題的描畫：N個傳教士帶著N個野人劃船過河；3個平安約束條件：1)船上人數不得超越載重限量，設為K個人； 2)任何時辰包括兩岸、船上野人數目不得超越傳教士； 3)允許在河的某一岸或者在船上只需野人而沒有傳教士；2022/7/1724形狀空間搜索1

11、.形狀空間及其搜索的表示(2)形狀空間表示的經典例子“傳教士和野人問題 特例：N=3，K=2 形狀分量m傳教士在左岸的實踐人數形狀分量c野人在左岸的實踐人數形狀分量b指示船能否在左岸(1、0)3個平安約束條件m c (左岸平安)且 N-m N-c(右岸平安);(想一想，為什么不思索船平安？)m=0且0c N (左岸沒有傳道士，右岸一定平安);N-m=0且0N-cN (右岸沒有傳道士，左岸一定平安);2022/7/1725設初始形狀下傳教士、野人和船都在左岸，目的形狀下這三者均在右岸，問題形狀以m,c,b表示。問題的求解義務可描畫為：(3,3,1) (0,0,0)該簡單問題能夠到達的合法形狀：能

12、夠形狀總數：442=32根據條件得出合法形狀：20m c 且 N-m N-c (左岸平安且右岸平安)m=1,c=1；m=2,c=2 m=0且0c N(左岸沒有傳道士)m=0,c=0,1,2,3 N-m=0且0N-cN(右岸沒有傳道士)m=3,c=0,1,2,3不能夠到達的合法形狀：(0,0,1),(0,3,0),(3,0,1),(3,3,0)能夠到達的合法形狀共16個2022/7/1726形狀空間搜索1.形狀空間及其搜索的表示(2)形狀空間表示的經典例子“傳教士和野人問題定義2類操作算子：L(x,y)指示從左岸到右岸的劃船操作 R(x,y)指示從右岸到左岸的劃船操作x + y K=2(船的載重

13、限制)；x和y取值的能夠組合只需5個10，20，11，01，02 ( 允許在船上只需野人而沒有傳教士 )共有10個操作算子2022/7/1727渡河問題的形狀空間有向圖2022/7/1728形狀空間搜索1.形狀空間及其搜索的表示總結形狀空間表示方法： 用形狀空間方法表示問題時，首先必需定義形狀的描畫方式，經過運用這種描畫方式可把問題的一切形狀都表示出來。另外，還要定義一組操作，經過運用這些操作可把問題由一種形狀轉變為另一種形狀。 問題的求解過程是一個不斷把操作作用于形狀的過程。假設在運用某個操作后得到的新形狀是目的形狀，就得到了問題的一個解。這個解是從初始形狀到目的形狀所用操作構成的序列。 2

14、022/7/1729形狀空間搜索1.形狀空間及其搜索的表示總結形狀空間表示方法： 要使問題由一種形狀轉變到另一種形狀時，就必需運用一次操作。這樣，在從初始形狀轉變到目的形狀時，就能夠存在多個操作序列(即得到多個解)。那么，其中運用操作最少或較少的解才為最優解(由于只需在運用操作時所付出的代價為最小的解才是最優解)。 對其中的某一個形狀，能夠存在多個操作使該形狀變到幾個不同的后繼形狀那么究竟用哪個操作進展搜索呢?這就有賴于搜索戰略了不同的搜索戰略有不同的順序，這就是本章后面要討論的問題。 2022/7/1730課堂練習有一農夫帶一只狐貍、一只小羊和一籃菜過河從左岸到右岸。假設船太小，農夫每次只能

15、帶一樣東西過河；思索到平安，無農夫看管時，狐貍和小羊不能在一同，小羊和那籃菜也不能在一同。請為該問題的處理設計形狀空間，并畫出形狀空間圖。2022/7/1731解析以變量m、f、s、v分別指示農夫、狐貍、小羊、菜,且每個變量只可取值1(表示在左岸)或0(表示在右岸)。問題形狀可以四元組(m、f、s、v)描畫,設初始形狀下均在左岸,目的形狀下都到達右岸。從而,問題求解義務可描畫為 (1, 1, 1, 1) -(0, 0, 0, 0)思索：為什么不把船的形狀放到形狀空間中去？由于問題簡單,形狀空間中能夠的形狀總數為2222 = 16,由于要服從平安限制,合法的形狀只需(除初、目形狀外): 1110

16、，1101，1011，1010，0101，0001，0010，0100；不合法形狀有: 0111,1000,1100,0011,0110,1001設計二類操作算子:Lx、Rx,x為m、f、s、v時分別指示農夫單獨,帶狐貍,帶小羊,帶菜過河；形狀空間圖如下所示.由于Lx和Rx是互逆操作,故而解答途徑可有無數條,但最近的只需二條;都是7個操作步. 2022/7/1732解析:四元組(m、f、s、v)代表農夫、狐貍、小羊、菜2022/7/1733形狀空間搜索1.形狀空間及其搜索的表示(3)形狀空間的搜索形狀空間的搜索記為SE，可表示為五元組：SE=(S,O,E,I,G)；E搜索引擎；I問題的初始形狀

17、，I S；G問題的目的形狀集合，G S。搜索引擎E可以設計為實現任何搜索算法的控制系統。根本思想經過搜索引擎E尋覓一個操作算子的調用序列，使問題從初始形狀I變化到目的形狀G之一。解答途徑初-目變化過程中的形狀序列或相應的操作算子調用序列。2022/7/1734形狀空間搜索1.形狀空間及其搜索的表示或圖普通圖一個形狀可以有多個可供選擇的操作算子；操作算子間的選擇是一種“或的關系;這樣的有向圖稱為或圖。2022/7/1735形狀空間搜索1.形狀空間及其搜索的表示(3)形狀空間的搜索或圖普通圖一個形狀可以有多個可供選擇的操作算子；操作算子間的選擇是一種“或的關系，這樣的有向圖稱為或圖。形狀空間普通都

18、表示為或圖普通圖搜索圖在搜索解答途徑的過程中畫出搜索時涉及到的節點和弧線，構成所謂的搜索圖。形狀空間搜索普通圖搜索2022/7/1736形狀空間搜索1.形狀空間及其搜索的表示(3)形狀空間的搜索形狀空間、搜索圖和解答途徑之間的關系S0Sg2022/7/1737形狀空間搜索1.形狀空間及其搜索的表示(4)普通圖搜索例子八數碼游戲 求解的問題：給定初始規劃(即初始形狀)和目的規劃(即目的形狀)，如何挪動數碼才干從初始規劃到達目的規劃？解答就是一個合法的棋牌走步序列。初始規劃目的規劃挪動數碼2022/7/1738形狀空間搜索1.形狀空間及其搜索的表示(4)普通圖搜索例子八數碼游戲 用普通圖搜索方法處

19、理該問題的步驟：1、為問題形狀的表示建立數據構造2、制定操作算子集合3、設計搜索引擎 第一步：為問題形狀的表示建立數據構造33的一個矩陣S矩陣元素Sij0,1,2,3,4,5,6,7,8,其中1i,j3 數字0表示空格 數字1-8表示相應的棋牌八數碼問題就可表示為：2022/7/1739形狀空間搜索1.形狀空間及其搜索的表示初始規劃目的規劃挪動數碼(4)普通圖搜索例子八數碼游戲 2022/7/1740形狀空間搜索1.形狀空間及其搜索的表示(4)普通圖搜索例子八數碼游戲 第二步：制定操作算子集直觀方法為每個棋牌制定一套能夠的走步：左、上、右、下四種挪動。需求32個操作算子簡易方法僅為空格制定這4

20、種走步。僅需4個操作算子第三步：設計搜索引擎 問題形狀空間的大小與問題涉及的元素個數是程指數級爆炸式增長即，組合爆炸問題如，棋盤規劃問題形狀總共有9!=362880個 研討焦點是處理組合爆炸問題，經過緊縮搜索空間，提高搜索效率。 2022/7/1741形狀空間搜索1.形狀空間及其搜索的表示形狀空間、搜索圖和解答途徑之間的關系S0Sg2022/7/1742形狀空間搜索2.普通圖搜索戰略 1搜索術語1、節點深度根節點指示初始形狀，令其深度為0；搜索圖中的其他節點的深度dn就可以遞歸地定義為其父節點深度dn-1加1：dn= dn-1+1。 根節點深度=0第n-1層節點dn-1第n層節點dn= dn-

21、1+1搜索圖2022/7/1743形狀空間搜索2.普通圖搜索戰略 1搜索術語2、節點擴展運用操作算子將上一形狀節點ni變化到下一形狀節點nj節點ni稱為被擴展節點父節點節點nj稱為ni的子節點節點ni節點nj2022/7/17441搜索術語3、途徑 節點ni到nj的途徑是由相鄰節點間的弧線構成的折線要求途徑是無環的4、途徑代價相鄰節點ni和ni+1間的途徑代價記為C(ni, ni+1) 通常令恣意相鄰節點間的途徑代價一樣，并以途徑長度1指示。即C(ni, ni+1)=1 。形狀空間搜索2.普通圖搜索戰略節點ni節點ni+1節點nj2022/7/1745形狀空間搜索2.普通圖搜索戰略 1搜索術語

22、4、途徑代價目的形狀節點ng節點ni節點nkC(nk,ng) C(ni,nk) C(ni,ng) 2022/7/1746形狀空間搜索2.普通圖搜索戰略2普通圖搜索算法符號闡明：s-初始形狀節點G-搜索圖OPEN-存放待擴展節點的表CLOSE-存放已被擴展的節點的表MOVE-FIRST(OPEN)-取OPEN表首的節點作為當前要被擴展的節點n，同時將節點n移至CLOSE表普通圖搜索算法劃分為二個階段：1、初始化 2、搜索循環 2022/7/1747形狀空間搜索2.普通圖搜索戰略2普通圖搜索算法算法劃分為二個階段：1、初始化 建立只包含初始形狀節點s的搜索圖G:=sOPEN:=sCLOSE:= 2

23、、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n作為擴展的節點，同時將其移到close表 擴展出n的子節點,插入搜索圖G和OPEN表 適當的標志和修正指針排序OPEN表經過循環地執行該算法，搜索圖G會因不斷有新節點參與而逐漸長大，直到搜索到目的節點。 2022/7/1748以下面的八數碼為例，看普通圖的搜索算法初始規劃目的規劃挪動數碼形狀空間搜索2.普通圖搜索戰略2022/7/17492022/7/17502022/7/17512022/7/17522022/7/17532022/7/17542022/7/17552022/7/17562022/7/17572022/7/1

24、7582022/7/17592022/7/17602022/7/17612022/7/17622022/7/17632022/7/17642022/7/17652022/7/17662022/7/17672022/7/1768形狀空間搜索2.普通圖搜索戰略2普通圖搜索算法搜索過程中的指針修正節點n擴展后的子節點分為3類：(i)全新節點(ii)已出如今OPEN表中的節點(iii)已出現的CLOSE表中的節點指針標志和修正的方法：(i)類節點：參與OPEN表，建立從子節點到父節點n的指針(ii)類節點、 (iii)類節點比較經由老父節點、新父節點n到達初始形狀節點的途徑代價 經由節點n的代價比較小

25、，那么挪動子節點指向老父節點的指針，改為指向新父節點n (iii)類節點還得從CLOSE表中移出，重新參與OPEN表。2022/7/1769形狀空間搜索2.普通圖搜索戰略Sn4ninjn1n2n3n31n32節點ni是當前擴展的節點；擴展出4個后續節點；n1、n2是新節點，只需建立指向父節點的指針，并參與OPEN表；2022/7/1770形狀空間搜索2.普通圖搜索戰略Sn4ninjn1n2n3n31n32n4曾經存在于OPEN表，并且已有父節點njn4經nj的途徑代價大取消n4指向nj的指針改為建立n4指向新父節點ni的指針n3曾經存在于CLOSE表，并且已有父節點nj需求做和n4同樣的比較和

26、指針修正任務。并且要重新參與open表。2022/7/17713.3 盲目搜索 提高搜索效率的關鍵優化OPEN表中節點的排序方式。簡單的排序戰略按預先確定的順序或隨機地排序新參與到OPEN表中的節點。 常用的簡一方式： 寬度優先擴展當前節點后生成的子節點總是置于OPEN表的后端，即OPEN表作為隊列運用，先進先出，使搜索優先向橫廣方向開展。 深度優先擴展當前節點后生成的子節點總是置于OPEN表的前端，即OPEN表作為棧運用，后進先出，使搜索優先向縱深方向開展。2022/7/1772寬度優先寬度優先擴展當前節點后生成的子節點總是置于OPEN表的后端，即OPEN表作為隊列，先進先出，使搜索優先向橫

27、向方向開展。過程：指從初始節點S0開場，向下逐層搜索，在n層節點未搜索完之前，不進入n+1層搜索。同層節點的搜索次序可以恣意。即先按生成規那么生成第一層節點，在該層全部節點中沿寬(廣)度進展橫向掃描，檢查目的節點Sg能否在這些子節點中。假設沒有,那么再將一切笫一層節點逐一擴展，得到第二層節點。并逐一檢查第二層節點中能否包含有Sg，如此依次按照先生成、先檢查、先擴展的原那么進展下去，直到發現Sg為止 2022/7/1773寬度優先實例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8

28、 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目的82 3 41 8 7 6 54910111213141516172022/7/1774寬度優先搜索 假設搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索。這種搜索是逐層進展的，在對下一層的恣意節點進展搜索之前，必需搜索完本層的一切節點。“先產生的節點先擴展2022/7/1775 (1)把初

29、始節點S0，放入OPEN表。 (2)假設OPEN表為空。那么問題無解，失敗并退出。 (3)把OPEN表中的第一個節點取出放入CLOSE表中，并按順序冠以編號n； (4)調查節點n能否為目的節點。假設是，那么求得了問題的解，勝利并退出。 (5)假設節點n不可擴展，那么轉第(2)步； (6)擴展節點n，將其子節點放到OPEN表的尾部，并為每一個子節點都配置指向父節點的指針，然后轉第(2)步。采用隊列構造，寬度優先算法可以表示如下：2022/7/1776 例 經過挪動積木塊，希望從初始形狀到達一個目的形狀，即三塊積木堆疊在一同。積木A在頂部，積木B在頂中間，積木C在底部。請畫出按照寬度優先搜索戰略所

30、產生的搜索樹。 這個問題的獨一操作算子為MOVE(X,Y)，即積木X搬到Y積木或桌面上面。如“挪動積木A到桌面上表示為MOVE(A,Table)。該操作算子可運用的先決條件是：1被挪動積木的頂部必需為空。2如Y是積木不是桌面，那么積木Y的頂部也必需為空。3同一形狀下，運用操作算子的次數不得多于一次。2022/7/1777積木問題的寬度優先搜索樹 2022/7/1778寬度優先搜索的性質當問題有解時，一定能找到解(完備性)當問題為單位代價時，且問題有解時，一定能找到最優解最優性方法與問題無關，具有通用性效率較低屬于圖搜索方法2022/7/1779寬度優先搜索是一種盲目搜索，時間和空間復雜度都比較

31、高，當目的節點間隔初始節點較遠時會產生許多無用的節點，搜索效率低。寬度優先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執行時間更嚴重的問題。 寬度優先搜索優點：目的節點假設存在，用寬度優先搜索算法總可以找到該目的節點，而且是最小即最短途徑的節點。寬度優先搜索的優點和缺陷2022/7/1780深度優先深度優先擴展當前節點后生成的子節點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優先向縱深方向開展。過程：從初始節點S0開場，按生成規那么生成下一級各子節點，檢查能否出現目的節點Sg；假設未出現，那么按“最晚生成的子節點優先擴展的原那么，再

32、用生成規那么生成再下一級的子節點，再檢查能否出現Sg；假設仍未出現，那么再擴展最晚生成的子節點。如此下去，沿著最晚生成的子節點分枝，逐級“縱向深化搜索。 2022/7/1781深度優先實例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8

33、3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 612346891113141618191 2 3 8 47 6 5目的571012151720212022/7/1782深度優先搜索在深度優先搜索中，首先擴展最新產生的(最深的)節點，深度 相等的節點可以恣意陳列。“最晚產生的節點最先擴展起始節點深度為0 任何其他節點的深度等于其父輩節點深度加上1 :dn=dn-1+12022/7/1783深度優先搜索很明顯這樣做，不一定找到最正確解，而且由于深度的限制，能夠找不到解，然而，假設不加深度限制，能夠

34、沿著一條道路無限制地擴展下去，這當然是不允許的。為保證找到解，應選擇適當的深度界限，或者采取不斷加大深度界限的方法，反復搜索，直到找到解。這種改良的方法叫做迭代加深搜索。2022/7/1784(1)把初始節點S0放入OPEN表； (2)假設OPEN表為空，那么問題無解，失敗并退出。 (3)把OPEN表中的第一個節點取出放入CLOSE表中，并按順序冠以編號n； (4)調查節點n能否為目的節點。假設是，那么求得了問題的解，勝利并退出。 (5)假設節點n不可擴展，那么轉第(2)步； (6)擴展節點n，將其子節點放到OPEN表的首部，并為其配置指向父節點的指針，然后轉第(2)步。基于棧實現的深度優先搜

35、索算法： 2022/7/1785 例 卒子穿陣問題: 要求一卒子從頂部經過圖所示的列陣到達底部。要求卒子行進中不可進入到代表敵兵駐守的區域內標注1，并不準后退。假定限制值為5。請畫出按照深度優先搜索戰略所產生的搜索樹 2022/7/1786卒子穿陣的深度優先搜索樹 2022/7/1787深度優先搜索的性質普通不能保證找到最優解當深度限制不合理時，能夠找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關的方法2022/7/1788深度優先搜索的優點是比寬度優先搜索算法需求較少的空間，該算法只需求保管搜索樹的一部分，它由當前正在搜索的途徑和該途徑上還沒有完全展開

36、的節點標志所組成。深度優先搜索的存儲器要求是深度約束的線性函數。 深度優先搜索的優點2022/7/1789深度優先搜索的缺陷 既不是完備的，也不是最優的。 主要問題是能夠搜索到了錯誤的途徑上。很多問題能夠具有很深甚至是無限的搜索樹，假設不幸選擇了一個錯誤的途徑，那么深度優先搜索會不斷搜索下去，而不會回到正確的途徑上。這樣一來對于這些問題，深度優先搜索要么墮入無限的循環而不能給出一個答案，要么最后找到一個答案，但途徑很長而且不是最優的答案。2022/7/1790比較 適用場所 深度優先當一個問題有多個解答或多條解答途徑，且只須找到其中一個時；往往應對搜索深度加以限制。 寬度優先確保搜索到最短的解

37、答途徑。共同優缺陷： 可直接運用普通圖搜索算法實現，不需求設計特別的節點排序方法，從而簡單易行，適宜于許多復雜度不高的問題求解義務。 節點排序的盲目性，由于不采用領域專門知識去指點排序，往往會在白白搜索了大量無關的形狀節點后才碰到解答，所以也稱為盲目搜索。 2022/7/1791有界深度搜索和迭代加深搜索 有界深度優先搜索過程總體上按深度優先算法方法進展，但對搜索深度需求給出一個深度限制dm，當深度到達了dm的時候，假設還沒有找到解答，就停頓對該分支的搜索，換到另外一個分支進展搜索。2022/7/1792(1)把初始節點S0放入OPEN表中，置S0的深度d(S0)=0。 (2)假設OPEN表為

38、空，那么問題無解，失敗并退出。 (3)把OPEN表中的第一個節點取出放入CLOSE表中。并按順序冠以編號n。(4)調查節點n能否為目的節點。假設是，那么求得了問題的解，勝利并退出。 (5)假設節點n的深度d(n)= dm，那么轉第(2)步。 (6)假設節點n不可擴展，那么轉第(2)步。 (7)擴展節點n。將其子節點放入OPEN表的首部，并為其配置指向父節點的指針。然后轉第(2)步。 有界深度搜索算法2022/7/1793戰略闡明: 1深度限制dm很重要。當問題有解，且解的途徑長度小于或等于dm時，那么搜索過程一定可以找到解，但是和深度優先搜索一樣這并不能保證最先找到的是最優解。但是當dm獲得太

39、小，解的途徑長度大于dm時，那么搜索過程中就找不到解，即這時搜索過程甚至是不完備的。2022/7/17942深度限制dm不能太大。當dm太大時，搜索過程會產生過多的無用節點，既浪費了計算機資源，又降低了搜索效率。3有界深度搜索的主要問題是深度限制值dm的選取。 2022/7/1795改良方法： 迭代加深搜索 先恣意給定一個較小的數作為dm，然后按有界深度算法搜索，假設在此深度限制內找到了解，那么算法終了；如在此限制內沒有找到問題的解，那么增大深度限制dm，繼續搜索。2022/7/1796迭代加深搜索，試圖嘗試一切能夠的深度限制：首先深度為0，然后深度為1，然后為2，等等。假設初始深度為0，那么

40、該算法只生成根節點，并檢測它。假設根節點不是目的，那么深度加1，經過典型的深度優先算法，生成深度為1的樹。當深度限制為m時，樹的深度為m。 2022/7/1797迭代加深搜索看起來會很浪費，由于很多節點都能夠擴展多次。然而對于很多問題，這種多次的擴展負擔實踐上很小，直覺上可以想象，假設一棵樹的分支系數很大，幾乎一切的節點都在最底層上，那么對于上面各層節點擴展多次對整個系統來說影響不是很大。 2022/7/1798 Procedure Iterative-deepeningBegin(1)設置當前深度限制=1; (2)把初始節點壓入棧,并設置棧頂指針; (3)While棧不空并且深度在給定的深度

41、限制之內do Begin 彈出棧頂元素； If棧頂元素=goal,前往并終了; Else以恣意的順序把棧頂元素的子女壓入棧中; End End whild (4)深度限制加1,并前往2;End.迭代加深搜索算法2022/7/1799總結寬度優先搜索、深度優先搜索和迭代加深搜索都可以用于生成和測試算法。寬度優先搜索需求指數數量的空間，深度優先搜索的空間復雜度和最大搜索深度呈線性關系。 2022/7/17100迭代加深搜索對一棵深度受控的樹采用深度優先的搜索。它結合了寬度優先和深度優先搜索的優點。和寬度優先搜索一樣，它是最優的，也是完備的。但對空間要求和深度優先搜索一樣是適中的。 2022/7/1

42、7101搜索最優戰略的比較 表注：b是分支系數，d是解答的深度，m是搜索樹的最大深度，l是深度限制。2022/7/171023.4 啟發式搜索普通圖搜索算法常用的簡一方式：深度優先寬度優先【缺陷：節點排序的盲目性】在白白搜索了大量無關的形狀節點后才碰到解答，效率低提高普通圖搜索效率的關鍵優化OPEN表中節點的排序方式盲目搜索2022/7理想情況：每次排序后OPEN表表首元素n總在解答途徑上2022/7/17104啟發式搜索啟發式知識指點OPEN表排序的普通圖搜索：全局排序對OPEN表中的一切節點排序，使最有希望的節點排在表首。A算法， A*算法重點掌握！部分排序僅對新

43、擴展出來的子節點排序，使這些新節點中最有希望者能優先取出調查和擴展；爬山法了解，對深度優先法的改良；2022/7/17105啟發式搜索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，估計的最小途徑代價；2022/7/17106啟發式搜索1.A算法掌握Snng目的形狀節點ng初始形狀節點S節點n搜索圖Gh(n): n-ng的

44、估計最小途徑代價 g(n):s-n的實踐途徑代價 f(n):s-n-ng的估計最小途徑代價 2022/7/17107啟發式搜索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算法? 掌握！ 2022/7/17108啟發式搜索1.A算法掌握A算法的設計與普通圖搜索一樣，劃分為二個階段 ：1、初始化 建立只包含初始形狀節點s的搜索圖G:=sOP

45、EN:=sCLOSE:= 2、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n 擴展出n的子節點,插入搜索圖G和OPEN表 適當的標志和修正指針子節點父節點排序OPEN表評價函數f(n)的值排序經過循環地執行該算法，搜索圖會因不斷有新節點參與而逐漸長大，直到搜索到目的節點。2022/7/17109啟發式搜索1.A算法掌握算法A的設計與普通圖搜索類似，劃分為二個階段 ：1、初始化 2、搜索循環MOVE-FIRST(OPEN)-取出OPEN表首的節點n 擴展出n的子節點,插入搜索圖G和OPEN表 對每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni)適當的標志和修正指針

46、子節點父節點排序OPEN表評價函數f(n)的值排序2022/7/17110啟發式搜索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)值從小到大排序2022/7/171112.假設OPEN表是空表，那么失敗退出；算法A3.選擇OPEN表上的第一個節點，把它從OPEN表

47、移出并放進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這條途徑而得到的；2022/7/171126.對那些未曾在G中出現過的M成員全新結點設置一個通向n的指針。把M的這些成員加進OPEN表。對曾經在OPEN表上的每一個M成

48、員，比較子節點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(搜索樹。2022/7/17113啟發式搜索1.A算法掌握A算法實例八數碼游戲1)設計評價函數f(n)f(n)=d(n)+w(n),其中d(n)-節點n在搜

49、索圖中的節點深度，對g(n)的度量；w(n)-代表啟發式函數h(n),其值是節點n與目的形狀節點ng相比較，不思索空格，錯位的棋牌個數；初始規劃目的規劃挪動數碼2022/7/17114啟發式搜索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)不思索空格2022/7/17115形狀空間搜索2.普通圖搜索戰略 1搜索術語1、節點深度根節點指示初始形狀，令其深度為0；搜索圖中

50、的其他節點的深度dn就可以遞歸地定義為其父節點深度dn-1加1：dn= dn-1+1。 根節點深度=0第n-1層節點dn-1第n層節點dn= dn-1+1搜索圖G2022/7/17116啟發式搜索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)不思索空格2022/7/17117初始化OPEN:=s4 CLOSE:= 目的規劃ng2022/7/17118循環1

51、CLOSE:=s4 OPEN:=a b c OPEN:=a6 b4 c6 OPEN:=b4 a6 c6 目的規劃ng2022/7/17119循環2CLOSE:=s4 b4 OPEN:=a6 c6 d e i OPEN:=a6 c6 d5 e5 i6 OPEN:=d5 e5 a6 c6 i6 目的規劃ng2022/7/17120循環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 目的規劃ng2022/7/17121循環4CLOSE:=s4,b4,d5,e5 OPEN:=a

52、6 c6 i6 k6 j7 l m OPEN:=a6 c6 i6 k6 j7 l5 m7 OPEN:=l5 a6 c6 i6 k6 j7 m7 目的規劃ng2022/7/17122CLOSE:=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 目的規劃ng2022/7/17123循環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 O

53、PEN:=g5 a6 c6 i6 k6 j7 m7 o7 目的規劃ng2022/7/17124循環7勝利終了目的規劃ng2022/7/17125最理想搜索圖G2022/7/17126判別失誤2022/7/17127 例 2 給定4L和3L的水壺各一個，水壺上沒有刻度，可以向水壺中加水。如何在4L的壺中準確地得到2L水？ x,y4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節點。那么給出下面的啟發式函數： 2022/7/17128 h(n) = 2 假設0 x 4并且0 y 3 = 4 假設0 x 4或者0 y =g*(n)h(n)盡能夠接近h*(n) A算法的關鍵。2022/7

54、/17135啟發式搜索2.實現啟發式搜索的關鍵要素1搜索算法的可采用性(Admissibility)4)改良啟發式函數八數碼游戲f(n)=d(n)+w(n),其中w(n)-表示錯位的棋牌個數，不夠貼切，錯誤的擴展了節點d；p(n)-節點n與目的形狀節點比較，錯位棋牌在不受阻攔的情況下，挪動到目的形狀相應位置所需走步挪動次數的總和；p(n)比w(n)更接近于h*(n)-p(n)不僅思索了棋牌的錯位要素，還思索了錯位的間隔挪動間隔2022/7/17136啟發式搜索2.實現啟發式搜索的關鍵要素4)改良啟發式函數八數碼游戲f(s)計算實例初始規劃s目的規劃ngw(s):錯位的棋牌個數d(s):當前節點

55、深度 f(s)0 4 4 p(s):錯位棋牌挪動間隔d(s):當前節點深度 f(s)0 5 5 1 1 1 2 2022/7/17137初始化OPEN:=s5 CLOSE:= 目的規劃ng2022/7/17138循環1CLOSE:=s5 OPEN:=a b c OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 目的規劃ng2022/7/17139循環2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 目的規劃ng2022/7/17140循環3CLOSE:=s5 b5 e5 OPEN:=a7

56、 c7 d7 i7 l m OPEN:=a7 c7 d7 i7 l5 m7 OPEN:=l5 a7 c7 d7 i7 m7 目的規劃ng2022/7/17141CLOSE:=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 目的規劃ng2022/7/17142CLOSE:=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 目的規劃n

57、g2022/7/17143循環6勝利終了最理想搜索圖G目的規劃ng2022/7/17144防止了錯誤選擇2022/7/17145啟發式搜索2.實現啟發式搜索的關鍵要素1搜索算法的可采用性(Admissibility)5) A*算法定義 ：1、在A算法中，規定h(n)h*(n);2、經如此限制以后的A算法就是A*算法。A*算法是可采用的，即總能搜索到最短解答途徑【回想：八數碼游戲的h(n)】w(n)-錯位的棋牌個數p(n)-錯位棋牌在不受阻攔的情況下，挪動到目的形狀相應位置所需走步挪動次數的總和；上述兩者均是可采用的。(想想為什么)2022/7/17146啟發式搜索2.實現啟發式搜索的關鍵要素1

58、搜索算法的可采用性(Admissibility)5) A*算法定義：1、在A算法中，規定h(n)h*(n);2、經如此限制以后的A算法就是A*算法。A*算法是可采用的，即總能搜索到最短解答途徑證明：【陸汝鈐P248】1假設存在一條從初始形狀到目的形狀的解答途徑，那么一定存在一條最短解答通路；2設形狀n是最短解答途徑上的一個形狀，那么經過有限步后，n必然會成為OPEN表的第一個節點；3由于最短解答途徑只需有限個節點n，所以有限步后算法必然因到達目的形狀ng。這就是最優解。證明終了。2022/7/17147啟發式搜索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)2022/7/17148啟發式搜索2.實現啟發式搜索的關鍵要素1搜索算法的可采用性(Admissibility)5)滿足可采用性條件的算法A*算法證明：2設形狀n是最短解答途徑上的一個形狀，那么經過有限步后