第三章_搜索策略-1ppt課件

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

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

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

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

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

6、空間搜索來求解問題的系統(tǒng)均定義一個形狀空間，并經(jīng)過適當(dāng)?shù)乃阉魉惴ㄔ谛螤羁臻g中搜索解答途徑。3.2 基于形狀空間的搜索技術(shù)2022/7/1714形狀空間搜索1.形狀空間及其搜索的表示(1)形狀空間的表示形狀空間記為SP，可表示為二元組：SP=(S,O)S問題求解即搜索過程中一切能夠到達(dá)的合法形狀構(gòu)成的集合；O操作算子的集合，操作算子的執(zhí)行會導(dǎo)致問題形狀的變化 ；形狀用于記載問題求解即搜索過程中某一時辰問題現(xiàn)狀的快照；籠統(tǒng)為矢量方式 Q=q0,q1,qnT每個元素qi稱為形狀分量 給定每個形狀分量qi的值就得到一個詳細(xì)的形狀 Qk=q0k,q1k,qnkT2022/7/1715形狀表示形狀的變化操

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

8、定的初始棋局和目的棋局，給出數(shù)碼的挪動序列。該問題稱為八數(shù)碼問題。 56741382初始棋局56748321目的棋局挪動數(shù)碼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:錢幣翻轉(zhuǎn)問題。設(shè)有3個錢幣，其初始形狀為(正、反、正),欲得的目的形狀為(正、正、正)或(反、反、反)。問題是允許每次只能且必需翻轉(zhuǎn)一個錢幣，連翻三次。問能否到達(dá)目的形狀。 分析：經(jīng)過引入一個三維變量將問題表示出來。設(shè)三維變量為：Q=q1,q2,q3，式中qi (i=1,2,3)=1表示錢幣為正面，qi (i=1,2,3)=0表示錢幣為反面。那么三個錢幣能夠出現(xiàn)的形狀有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，要求步數(shù)為3。2022/7/1722錢幣問題的形狀空間圖2022/7/1723形狀空間搜索1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問題 問題的描畫：N個傳教士帶著N個野人劃船過河；3個平安約束條件：1)船上人數(shù)不得超越載重限量，設(shè)為K個人； 2)任何時辰包括兩岸、船上野人數(shù)目不得超越傳教士； 3)允許在河的某一岸或者在船上只需野人而沒有傳教士；2022/7/1724形狀空間搜索1

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

12、夠形狀總數(shù)：442=32根據(jù)條件得出合法形狀：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不能夠到達(dá)的合法形狀：(0,0,1),(0,3,0),(3,0,1),(3,3,0)能夠到達(dá)的合法形狀共16個2022/7/1726形狀空間搜索1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問題定義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.形狀空間及其搜索的表示總結(jié)形狀空間表示方法： 用形狀空間方法表示問題時，首先必需定義形狀的描畫方式，經(jīng)過運(yùn)用這種描畫方式可把問題的一切形狀都表示出來。另外，還要定義一組操作，經(jīng)過運(yùn)用這些操作可把問題由一種形狀轉(zhuǎn)變?yōu)榱硪环N形狀。 問題的求解過程是一個不斷把操作作用于形狀的過程。假設(shè)在運(yùn)用某個操作后得到的新形狀是目的形狀，就得到了問題的一個解。這個解是從初始形狀到目的形狀所用操作構(gòu)成的序列。 2

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

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

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

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

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

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

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

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

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

23、、搜索循環(huán)MOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n作為擴(kuò)展的節(jié)點，同時將其移到close表 擴(kuò)展出n的子節(jié)點,插入搜索圖G和OPEN表 適當(dāng)?shù)臉?biāo)志和修正指針排序OPEN表經(jīng)過循環(huán)地執(zhí)行該算法，搜索圖G會因不斷有新節(jié)點參與而逐漸長大，直到搜索到目的節(jié)點。 2022/7/1748以下面的八數(shù)碼為例，看普通圖的搜索算法初始規(guī)劃目的規(guī)劃挪動數(shù)碼形狀空間搜索2.普通圖搜索戰(zhàn)略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.普通圖搜索戰(zhàn)略2普通圖搜索算法搜索過程中的指針修正節(jié)點n擴(kuò)展后的子節(jié)點分為3類：(i)全新節(jié)點(ii)已出如今OPEN表中的節(jié)點(iii)已出現(xiàn)的CLOSE表中的節(jié)點指針標(biāo)志和修正的方法：(i)類節(jié)點：參與OPEN表，建立從子節(jié)點到父節(jié)點n的指針(ii)類節(jié)點、 (iii)類節(jié)點比較經(jīng)由老父節(jié)點、新父節(jié)點n到達(dá)初始形狀節(jié)點的途徑代價 經(jīng)由節(jié)點n的代價比較小

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

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

27、向方向開展。過程：指從初始節(jié)點S0開場，向下逐層搜索，在n層節(jié)點未搜索完之前，不進(jìn)入n+1層搜索。同層節(jié)點的搜索次序可以恣意。即先按生成規(guī)那么生成第一層節(jié)點，在該層全部節(jié)點中沿寬(廣)度進(jìn)展橫向掃描，檢查目的節(jié)點Sg能否在這些子節(jié)點中。假設(shè)沒有,那么再將一切笫一層節(jié)點逐一擴(kuò)展，得到第二層節(jié)點。并逐一檢查第二層節(jié)點中能否包含有Sg，如此依次按照先生成、先檢查、先擴(kuò)展的原那么進(jìn)展下去，直到發(fā)現(xiàn)Sg為止 2022/7/1773寬度優(yōu)先實例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寬度優(yōu)先搜索 假設(shè)搜索是以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索是逐層進(jìn)展的，在對下一層的恣意節(jié)點進(jìn)展搜索之前，必需搜索完本層的一切節(jié)點。“先產(chǎn)生的節(jié)點先擴(kuò)展2022/7/1775 (1)把初

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

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

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

32、用生成規(guī)那么生成再下一級的子節(jié)點，再檢查能否出現(xiàn)Sg；假設(shè)仍未出現(xiàn)，那么再擴(kuò)展最晚生成的子節(jié)點。如此下去，沿著最晚生成的子節(jié)點分枝，逐級“縱向深化搜索。 2022/7/1781深度優(yōu)先實例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深度優(yōu)先搜索在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點，深度 相等的節(jié)點可以恣意陳列?！白钔懋a(chǎn)生的節(jié)點最先擴(kuò)展起始節(jié)點深度為0 任何其他節(jié)點的深度等于其父輩節(jié)點深度加上1 :dn=dn-1+12022/7/1783深度優(yōu)先搜索很明顯這樣做，不一定找到最正確解，而且由于深度的限制，能夠找不到解，然而，假設(shè)不加深度限制，能夠

34、沿著一條道路無限制地擴(kuò)展下去，這當(dāng)然是不允許的。為保證找到解，應(yīng)選擇適當(dāng)?shù)纳疃冉缦蓿蛘卟扇〔粩嗉哟笊疃冉缦薜姆椒?，反?fù)搜索，直到找到解。這種改良的方法叫做迭代加深搜索。2022/7/1784(1)把初始節(jié)點S0放入OPEN表； (2)假設(shè)OPEN表為空，那么問題無解，失敗并退出。 (3)把OPEN表中的第一個節(jié)點取出放入CLOSE表中，并按順序冠以編號n； (4)調(diào)查節(jié)點n能否為目的節(jié)點。假設(shè)是，那么求得了問題的解，勝利并退出。 (5)假設(shè)節(jié)點n不可擴(kuò)展，那么轉(zhuǎn)第(2)步； (6)擴(kuò)展節(jié)點n，將其子節(jié)點放到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步?；跅崿F(xiàn)的深度優(yōu)先搜

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

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

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

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

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

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

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

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

43、擴(kuò)展出來的子節(jié)點排序，使這些新節(jié)點中最有希望者能優(yōu)先取出調(diào)查和擴(kuò)展；爬山法了解，對深度優(yōu)先法的改良；2022/7/17105啟發(fā)式搜索1.A算法掌握【根本思想】設(shè)計表達(dá)啟發(fā)式知識的評價函數(shù)f(n)；指點普通圖搜索中OPEN表待擴(kuò)展節(jié)點的排序：【評價函數(shù)f(n)=g(n)+h(n) 】 n-搜索圖G中的節(jié)點；f(n)- G中從初始形狀節(jié)點s，經(jīng)由節(jié)點n到達(dá)目的節(jié)點ng，估計的最小途徑代價；g(n)- G中從s到n，目前實踐的途徑代價；h(n)-從n到ng，估計的最小途徑代價；2022/7/17106啟發(fā)式搜索1.A算法掌握Snng目的形狀節(jié)點ng初始形狀節(jié)點S節(jié)點n搜索圖Gh(n): n-ng的

44、估計最小途徑代價 g(n):s-n的實踐途徑代價 f(n):s-n-ng的估計最小途徑代價 2022/7/17107啟發(fā)式搜索1.A算法掌握【評價函數(shù)f(n)=g(n)+h(n) 】n-搜索圖G中的節(jié)點；f(n)- G中從s經(jīng)n到ng，估計的最小途徑代價；g(n)- G中從s到n，目前實踐的途徑代價；h(n)-從n到ng，估計的最小途徑代價； h(n)值-依賴于啟發(fā)式知識加以計算；h(n)稱為啟發(fā)式函數(shù) 。如何用評價函數(shù)來實現(xiàn)A算法? 掌握！ 2022/7/17108啟發(fā)式搜索1.A算法掌握A算法的設(shè)計與普通圖搜索一樣，劃分為二個階段 ：1、初始化 建立只包含初始形狀節(jié)點s的搜索圖G:=sOP

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

46、子節(jié)點父節(jié)點排序OPEN表評價函數(shù)f(n)的值排序2022/7/17110啟發(fā)式搜索1.A算法掌握擴(kuò)展出n的子節(jié)點,插入搜索圖G和OPEN表 對每個子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)適當(dāng)?shù)臉?biāo)志和修正指針子節(jié)點父節(jié)點(i)全新節(jié)點：f(ni)=f(n,ni)(ii)已出如今OPEN表中的節(jié)點(iii)已出現(xiàn)的CLOSE表中的節(jié)點IF f(ni)f(n,ni) THEN 修正指針指向新父結(jié)點n f(ni)=f(n,ni)排序OPEN表f(n)值從小到大排序2022/7/171112.假設(shè)OPEN表是空表，那么失敗退出；算法A3.選擇OPEN表上的第一個節(jié)點，把它從OPEN表

47、移出并放進(jìn)CLOSE表中，稱此節(jié)點為節(jié)點n； 1.建立一個只包含起始節(jié)點S的搜索圖G,把S放到一個叫OPEN的未擴(kuò)展節(jié)點表中；建立一個叫做CLOSE的已擴(kuò)展節(jié)點表，其初始為空表；5.擴(kuò)展節(jié)點n，同時生成不是n的祖先的那些子節(jié)點的集合M,把M的這些成員作為n的后繼節(jié)點添入圖G中；對于M中每個子節(jié)點ni,計算f(n,ni) = g(n,ni) + h(ni);4.假設(shè)n為一目的節(jié)點，那么有解勝利退出，此解是追蹤圖G中沿著指針從n到S這條途徑而得到的；2022/7/171126.對那些未曾在G中出現(xiàn)過的M成員全新結(jié)點設(shè)置一個通向n的指針。把M的這些成員加進(jìn)OPEN表。對曾經(jīng)在OPEN表上的每一個M成

48、員，比較子節(jié)點ni經(jīng)由新、老父節(jié)點的評價函數(shù)值f(n,ni)、f(ni);假設(shè)f(n,ni) f(ni)點,那么令f(ni) = f(n,ni),并挪動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點。對已在CLOSE表上的每個M成員，作與第2類同樣的處置，并把這些子結(jié)點從CLOSE表移出，重新參與OPEN表。7.按f(n)排序OPEN表中的節(jié)點，f(n)值最小者排在首位，重排OPEN表；8.轉(zhuǎn)2。此過程生成一個明確的圖G(搜索圖和一個G的子集T(搜索樹。2022/7/17113啟發(fā)式搜索1.A算法掌握A算法實例八數(shù)碼游戲1)設(shè)計評價函數(shù)f(n)f(n)=d(n)+w(n),其中d(n)-節(jié)點n在搜

49、索圖中的節(jié)點深度，對g(n)的度量；w(n)-代表啟發(fā)式函數(shù)h(n),其值是節(jié)點n與目的形狀節(jié)點ng相比較，不思索空格，錯位的棋牌個數(shù)；初始規(guī)劃目的規(guī)劃挪動數(shù)碼2022/7/17114啟發(fā)式搜索1.A算法掌握啟發(fā)式算法A實例八數(shù)碼游戲1)設(shè)計評價函數(shù)f(n)f(n)計算實例初始規(guī)劃s目的規(guī)劃ngw(s):錯位的棋牌個數(shù)d(s):當(dāng)前節(jié)點深度 f(s)h(n): n-ng的最小途徑代價 g(n):s-n的最小途徑代價 f(n):s-n-ng的最小途徑代價 注：W(S)不思索空格2022/7/17115形狀空間搜索2.普通圖搜索戰(zhàn)略 1搜索術(shù)語1、節(jié)點深度根節(jié)點指示初始形狀，令其深度為0；搜索圖中

50、的其他節(jié)點的深度dn就可以遞歸地定義為其父節(jié)點深度dn-1加1：dn= dn-1+1。 根節(jié)點深度=0第n-1層節(jié)點dn-1第n層節(jié)點dn= dn-1+1搜索圖G2022/7/17116啟發(fā)式搜索1.A算法掌握啟發(fā)式算法A實例八數(shù)碼游戲1)設(shè)計評價函數(shù)f(n)f(n)計算實例初始規(guī)劃s目的規(guī)劃ngw(s):錯位的棋牌個數(shù)d(s):當(dāng)前節(jié)點深度 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:= 目的規(guī)劃ng2022/7/17118循環(huán)1

51、CLOSE:=s4 OPEN:=a b c OPEN:=a6 b4 c6 OPEN:=b4 a6 c6 目的規(guī)劃ng2022/7/17119循環(huán)2CLOSE:=s4 b4 OPEN:=a6 c6 d e i OPEN:=a6 c6 d5 e5 i6 OPEN:=d5 e5 a6 c6 i6 目的規(guī)劃ng2022/7/17120循環(huán)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 目的規(guī)劃ng2022/7/17121循環(huán)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 目的規(guī)劃ng2022/7/17122CLOSE:=s4,b4,d5,e5,l5 循環(huán)5OPEN:=a6 c6 i6 k6 j7 m7 n OPEN:=a6 c6 i6 k6 j7 m7 n5 OPEN:=n5 a6 c6 i6 k6 j7 m7 目的規(guī)劃ng2022/7/17123循環(huán)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 目的規(guī)劃ng2022/7/17124循環(huán)7勝利終了目的規(guī)劃ng2022/7/17125最理想搜索圖G2022/7/17126判別失誤2022/7/17127 例 2 給定4L和3L的水壺各一個，水壺上沒有刻度，可以向水壺中加水。如何在4L的壺中準(zhǔn)確地得到2L水？ x,y4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節(jié)點。那么給出下面的啟發(fā)式函數(shù)： 2022/7/17128 h(n) = 2 假設(shè)0 x 4并且0 y 3 = 4 假設(shè)0 x 4或者0 y =g*(n)h(n)盡能夠接近h*(n) A算法的關(guān)鍵。2022/7

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

55、深度 f(s)0 4 4 p(s):錯位棋牌挪動間隔d(s):當(dāng)前節(jié)點深度 f(s)0 5 5 1 1 1 2 2022/7/17137初始化OPEN:=s5 CLOSE:= 目的規(guī)劃ng2022/7/17138循環(huán)1CLOSE:=s5 OPEN:=a b c OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 目的規(guī)劃ng2022/7/17139循環(huán)2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 目的規(guī)劃ng2022/7/17140循環(huán)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 目的規(guī)劃ng2022/7/17141CLOSE:=s5,b5,e5,l5 循環(huán)4OPEN:=a7 c7 d7 i7 m7 n OPEN:=a7 c7 d7 i7 m7 n5 OPEN:=n5 a7 c7 d7 i7 m7 目的規(guī)劃ng2022/7/17142CLOSE:=s5,b5,e5,l5,n5 循環(huán)5OPEN:=a7 c7 d7 i7 m7 o g OPEN:=a7 c7 d7 i7 m7 o7 g5 OPEN:=g5 a7 c7 d7 i7 m7 o7 目的規(guī)劃n

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

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