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

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

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

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

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

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

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

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

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

11、.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問(wèn)題 特例：N=3，K=2 形狀分量m傳教士在左岸的實(shí)踐人數(shù)形狀分量c野人在左岸的實(shí)踐人數(shù)形狀分量b指示船能否在左岸(1、0)3個(gè)平安約束條件m c (左岸平安)且 N-m N-c(右岸平安);(想一想，為什么不思索船平安？)m=0且0c N (左岸沒(méi)有傳道士，右岸一定平安);N-m=0且0N-cN (右岸沒(méi)有傳道士，左岸一定平安);2022/7/1725設(shè)初始形狀下傳教士、野人和船都在左岸，目的形狀下這三者均在右岸，問(wèn)題形狀以m,c,b表示。問(wèn)題的求解義務(wù)可描畫(huà)為：(3,3,1) (0,0,0)該簡(jiǎn)單問(wèn)題能夠到達(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éi)有傳道士)m=0,c=0,1,2,3 N-m=0且0N-cN(右岸沒(méi)有傳道士)m=3,c=0,1,2,3不能夠到達(dá)的合法形狀：(0,0,1),(0,3,0),(3,0,1),(3,3,0)能夠到達(dá)的合法形狀共16個(gè)2022/7/1726形狀空間搜索1.形狀空間及其搜索的表示(2)形狀空間表示的經(jīng)典例子“傳教士和野人問(wèn)題定義2類操作算子：L(x,y)指示從左岸到右岸的劃船操作 R(x,y)指示從右岸到左岸的劃船操作x + y K=2(船的載重

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、該算法只生成根節(jié)點(diǎn)，并檢測(cè)它。假設(shè)根節(jié)點(diǎn)不是目的，那么深度加1，經(jīng)過(guò)典型的深度優(yōu)先算法，生成深度為1的樹(shù)。當(dāng)深度限制為m時(shí)，樹(shù)的深度為m。 2022/7/1797迭代加深搜索看起來(lái)會(huì)很浪費(fèi)，由于很多節(jié)點(diǎn)都能夠擴(kuò)展多次。然而對(duì)于很多問(wèn)題，這種多次的擴(kuò)展負(fù)擔(dān)實(shí)踐上很小，直覺(jué)上可以想象，假設(shè)一棵樹(shù)的分支系數(shù)很大，幾乎一切的節(jié)點(diǎn)都在最底層上，那么對(duì)于上面各層節(jié)點(diǎn)擴(kuò)展多次對(duì)整個(gè)系統(tǒng)來(lái)說(shuō)影響不是很大。 2022/7/1798 Procedure Iterative-deepeningBegin(1)設(shè)置當(dāng)前深度限制=1; (2)把初始節(jié)點(diǎn)壓入棧,并設(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)先搜索和迭代加深搜索都可以用于生成和測(cè)試算法。寬度優(yōu)先搜索需求指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。 2022/7/17100迭代加深搜索對(duì)一棵深度受控的樹(shù)采用深度優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點(diǎn)。和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完備的。但對(duì)空間要求和深度優(yōu)先搜索一樣是適中的。 2022/7/1

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

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

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

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

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

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

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

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

50、的其他節(jié)點(diǎn)的深度dn就可以遞歸地定義為其父節(jié)點(diǎn)深度dn-1加1：dn= dn-1+1。 根節(jié)點(diǎn)深度=0第n-1層節(jié)點(diǎn)dn-1第n層節(jié)點(diǎn)dn= dn-1+1搜索圖G2022/7/17116啟發(fā)式搜索1.A算法掌握啟發(fā)式算法A實(shí)例八數(shù)碼游戲1)設(shè)計(jì)評(píng)價(jià)函數(shù)f(n)f(n)計(jì)算實(shí)例初始規(guī)劃s目的規(guī)劃ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)深度 f(s)h(n): n-ng的最小途徑代價(jià) g(n):s-n的最小途徑代價(jià) f(n):s-n-ng的最小途徑代價(jià) 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的水壺各一個(gè)，水壺上沒(méi)有刻度，可以向水壺中加水。如何在4L的壺中準(zhǔn)確地得到2L水？ x,y4L壺里的水有xL，3L壺里的水有yL，n表示搜索空間中的任一節(jié)點(diǎn)。那么給出下面的啟發(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.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素1搜索算法的可采用性(Admissibility)4)改良啟發(fā)式函數(shù)八數(shù)碼游戲f(n)=d(n)+w(n),其中w(n)-表示錯(cuò)位的棋牌個(gè)數(shù)，不夠貼切，錯(cuò)誤的擴(kuò)展了節(jié)點(diǎn)d；p(n)-節(jié)點(diǎn)n與目的形狀節(jié)點(diǎn)比較，錯(cuò)位棋牌在不受阻攔的情況下，挪動(dòng)到目的形狀相應(yīng)位置所需走步挪動(dòng)次數(shù)的總和；p(n)比w(n)更接近于h*(n)-p(n)不僅思索了棋牌的錯(cuò)位要素，還思索了錯(cuò)位的間隔挪動(dòng)間隔2022/7/17136啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素4)改良啟發(fā)式函數(shù)八數(shù)碼游戲f(s)計(jì)算實(shí)例初始規(guī)劃s目的規(guī)劃ngw(s):錯(cuò)位的棋牌個(gè)數(shù)d(s):當(dāng)前節(jié)點(diǎn)

55、深度 f(s)0 4 4 p(s):錯(cuò)位棋牌挪動(dòng)間隔d(s):當(dāng)前節(jié)點(diǎn)深度 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防止了錯(cuò)誤選擇2022/7/17145啟發(fā)式搜索2.實(shí)現(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)-錯(cuò)位的棋牌個(gè)數(shù)p(n)-錯(cuò)位棋牌在不受阻攔的情況下，挪動(dòng)到目的形狀相應(yīng)位置所需走步挪動(dòng)次數(shù)的總和；上述兩者均是可采用的。(想想為什么)2022/7/17146啟發(fā)式搜索2.實(shí)現(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是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；3由于最短解答途徑只需有限個(gè)節(jié)點(diǎn)n，所以有限步后算法必然因到達(dá)目的形狀ng。這就是最優(yōu)解。證明終了。2022/7/17147啟發(fā)式搜索2.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素1搜索算法的可采用性(Admissibility)5)滿足可采用性條件的算法A*算法證明：2設(shè)形狀n是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后，n必然會(huì)成為OPEN表的第一個(gè)節(jié)點(diǎn)；f(n)=g(n)+h(n)根據(jù)假設(shè)，n在最短解答途徑上 經(jīng)過(guò)有限步驟后，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.實(shí)現(xiàn)啟發(fā)式搜索的關(guān)鍵要素1搜索算法的可采用性(Admissibility)5)滿足可采用性條件的算法A*算法證明：2設(shè)形狀n是最短解答途徑上的一個(gè)形狀，那么經(jīng)過(guò)有限步后