1、第第5章章 狀態(tài)空間搜索策略狀態(tài)空間搜索策略Searching5.1 搜索概述搜索概述l在解空間中尋找解的過程與在解空間中尋找解的過程與策略策略l搜索問題的產(chǎn)生搜索問題的產(chǎn)生 （1）結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，無解析解）結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，無解析解 （2）理論上可解的問題，計(jì)算復(fù)雜度可能太高）理論上可解的問題，計(jì)算復(fù)雜度可能太高l基本搜索方式基本搜索方式 （1）盲目搜索盲目搜索 按預(yù)定策略進(jìn)行搜索，不考慮問題本身的特性按預(yù)定策略進(jìn)行搜索，不考慮問題本身的特性 （2）啟發(fā)式啟發(fā)式(Heuristic)搜索搜索 利用與問題有關(guān)的啟發(fā)式信息，加快搜索過程利用與問題有關(guān)的啟發(fā)式信息，加快搜索過程啟

2、發(fā)式搜索啟發(fā)式搜索l啟發(fā)式信息啟發(fā)式信息與與評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù) 反映問題特性，可用于確定搜索方向的信息反映問題特性，可用于確定搜索方向的信息 評(píng)價(jià)函數(shù)的作用是根據(jù)啟發(fā)式信息，計(jì)算對(duì)應(yīng)于評(píng)價(jià)函數(shù)的作用是根據(jù)啟發(fā)式信息，計(jì)算對(duì)應(yīng)于特定搜索方向的評(píng)價(jià)值，作為選擇搜索方向的依特定搜索方向的評(píng)價(jià)值，作為選擇搜索方向的依據(jù)。據(jù)。l局部局部(local)搜索搜索 vs. 全局全局(global)搜索搜索 確定搜索方向時(shí)考慮局部信息還是全局信息？確定搜索方向時(shí)考慮局部信息還是全局信息？l任一解任一解 vs. 最優(yōu)解最優(yōu)解搜索方法搜索方法l圖搜索方法圖搜索方法 寬度優(yōu)先法寬度優(yōu)先法(breadth-first)，

3、深度優(yōu)先法，深度優(yōu)先法(depth-first)，有界深度優(yōu)先法，啟發(fā)式最優(yōu)圖搜索法有界深度優(yōu)先法，啟發(fā)式最優(yōu)圖搜索法(A*，AO*).l博弈搜索方法博弈搜索方法 極小極大法極小極大法(MiniMax)，Alpha-Beta剪枝法剪枝法 (pruning)l現(xiàn)代優(yōu)化搜索方法現(xiàn)代優(yōu)化搜索方法 爬山法爬山法(hill climbing)，模擬退火法，模擬退火法(simulated annealing)，遺傳算法遺傳算法(genetic algorithms).搜索策略的評(píng)價(jià)搜索策略的評(píng)價(jià)l完備性完備性 如果問題有解，能否保證找到？如果問題有解，能否保證找到？l最優(yōu)性最優(yōu)性(optimization

4、) 如果問題存在不同的解，能否找到最優(yōu)解？如果問題存在不同的解，能否找到最優(yōu)解？l時(shí)間復(fù)雜性時(shí)間復(fù)雜性-找到一個(gè)解需要花費(fèi)多少時(shí)間找到一個(gè)解需要花費(fèi)多少時(shí)間l空間復(fù)雜性空間復(fù)雜性-在搜索過程中需要占用多少內(nèi)存在搜索過程中需要占用多少內(nèi)存時(shí)空復(fù)雜性的量度時(shí)空復(fù)雜性的量度l狀態(tài)空間圖的大小l分支因子 bl目標(biāo)節(jié)點(diǎn)的深度 dl路徑的最大長(zhǎng)度 ml搜索深度限制 l5.2 問題及其搜索過程的表示問題及其搜索過程的表示l狀態(tài)空間狀態(tài)空間表示法表示法 通過通過“狀態(tài)狀態(tài)”表示問題，通過表示問題，通過“操作符操作符”求解問求解問題題 狀態(tài)的改變狀態(tài)的改變表示了問題求解過程表示了問題求解過程狀態(tài)空間狀態(tài)空間l以

5、以“狀態(tài)狀態(tài)”和和“操作符操作符”為基礎(chǔ)為基礎(chǔ) 狀態(tài)狀態(tài)： 問題求解過程中任意時(shí)刻的狀況問題求解過程中任意時(shí)刻的狀況 操作符操作符：使問題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作使問題從一個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的操作l問題的全部狀態(tài)問題的全部狀態(tài)(包含初始狀態(tài)和目標(biāo)狀態(tài)包含初始狀態(tài)和目標(biāo)狀態(tài))及及一切可用操作符所構(gòu)成的集合稱為問題的狀態(tài)一切可用操作符所構(gòu)成的集合稱為問題的狀態(tài)空間。空間。,10kkkSSS GSFS,0初始初始狀態(tài)狀態(tài)中間中間狀態(tài)狀態(tài)1 1中間中間狀態(tài)狀態(tài)2 2目標(biāo)目標(biāo)狀態(tài)狀態(tài)狀態(tài)空間例：狀態(tài)空間例：二階梵塔問題二階梵塔問題l設(shè)有三根鋼針，它們的編號(hào)分別是設(shè)有三根鋼針，它們的編號(hào)分別是1

6、1號(hào)、號(hào)、2 2號(hào)和號(hào)和3 3號(hào)。在初始情況下，號(hào)。在初始情況下，l l號(hào)鋼針上穿有號(hào)鋼針上穿有A A、B B兩個(gè)兩個(gè)金片，金片，A A比比B B小，小，A A位于位于B B的上面。要求把這兩個(gè)的上面。要求把這兩個(gè)金片全部移到另一根鋼針上，而且規(guī)定每次只金片全部移到另一根鋼針上，而且規(guī)定每次只能移動(dòng)一個(gè)金片，任何時(shí)刻都不能使大片位于能移動(dòng)一個(gè)金片，任何時(shí)刻都不能使大片位于小片的上面。小片的上面。l用用 Sk=Sk=Sk0Sk0， Sk1Sk1表示問題的表示問題的狀態(tài)狀態(tài)，其中，其中，Sk0Sk0表示金片表示金片A A所在的鋼針號(hào)，所在的鋼針號(hào)，Sk1Sk1表示金片表示金片B B所在的鋼針號(hào)。全

7、部可能的問題狀態(tài)共有以所在的鋼針號(hào)。全部可能的問題狀態(tài)共有以下下9 9種：種： SO=(1SO=(1，l) S1=l) S1=（1 1，2 2） S2=S2=（1 1，3 3） S3=(2S3=(2，1 1） S4=S4=（2 2，2 2） S5=S5=（2 2，3 3） S6=(3S6=(3，1 1） S7=S7=（3 3，2 2） S8=S8=（3 3，3 3）123BABABA123S0=(1,1)S4=(2,2)S8=(3,3) 二階梵塔問題的初始與目標(biāo)狀態(tài)二階梵塔問題的初始與目標(biāo)狀態(tài)l操作符操作符：A(i,j)表示把金片表示把金片A從第從第i號(hào)鋼針移到號(hào)鋼針移到j(luò)號(hào)鋼針號(hào)鋼針上；上；

8、B(i,j)表示把金片表示把金片B從第從第i號(hào)鋼針移到號(hào)鋼針移到j(luò)號(hào)鋼針上。號(hào)鋼針上。共有共有12種操作，分別是：種操作，分別是： A(1，3) A(2，1) A(2，3) A(3，1) A(3，2) B(1，3) B(2，1) B(2，3) B(3，1) B(3，2) (1,1)(2,1)(2,3)(3,3)(1,3)(1,2)(2,2)(3,2)(3,1)A(1,3)B(1,2)A(3,2)l 根據(jù)狀態(tài)和操作符，可構(gòu)成根據(jù)狀態(tài)和操作符，可構(gòu)成二階梵塔問題的狀態(tài)圖二階梵塔問題的狀態(tài)圖最短路最短路徑解徑解l八數(shù)碼游戲（八數(shù)碼問題）描述為：在33組成的九宮格棋盤上，擺有八個(gè)將牌，每一個(gè)將牌都刻有

9、1-8八個(gè)數(shù)碼中的某一個(gè)數(shù)碼。棋盤中留有一個(gè)空格，允許其周圍的某一個(gè)將牌向空格移動(dòng)，這樣通過移動(dòng)將牌就可以不斷改變將牌的布局。這種游戲求解的問題是：給定一種初始的將牌布局或結(jié)構(gòu)（稱初始狀態(tài)）和一個(gè)目標(biāo)的布局（稱目標(biāo)狀態(tài)），問如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。5.3 一般圖搜索算法一般圖搜索算法l無論是狀態(tài)空間，還是與或圖的問題表示，問無論是狀態(tài)空間，還是與或圖的問題表示，問題求解過程都可看作是在題求解過程都可看作是在“圖圖”中進(jìn)行搜索。中進(jìn)行搜索。l基本思想基本思想 不存儲(chǔ)全部搜索圖，而是逐步展開問題求解所需的不存儲(chǔ)全部搜索圖，而是逐步展開問題求解所需的搜索子圖搜索子圖l具體方法具

10、體方法 從初始狀態(tài)開始，不斷擴(kuò)展當(dāng)前節(jié)點(diǎn)，即生成子從初始狀態(tài)開始，不斷擴(kuò)展當(dāng)前節(jié)點(diǎn)，即生成子節(jié)點(diǎn)，直到目標(biāo)狀態(tài)出現(xiàn)在這些子節(jié)點(diǎn)中，或者沒節(jié)點(diǎn)，直到目標(biāo)狀態(tài)出現(xiàn)在這些子節(jié)點(diǎn)中，或者沒有可供擴(kuò)展的節(jié)點(diǎn)為止。有可供擴(kuò)展的節(jié)點(diǎn)為止。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)lOpen表（表（未擴(kuò)展節(jié)點(diǎn)表未擴(kuò)展節(jié)點(diǎn)表） 存放未進(jìn)行過擴(kuò)展的節(jié)點(diǎn)存放未進(jìn)行過擴(kuò)展的節(jié)點(diǎn)lClosed表（表（已擴(kuò)展節(jié)點(diǎn)表已擴(kuò)展節(jié)點(diǎn)表） 存放已經(jīng)擴(kuò)展過的節(jié)點(diǎn)存放已經(jīng)擴(kuò)展過的節(jié)點(diǎn) 節(jié)點(diǎn) 父節(jié)點(diǎn) 編號(hào) 節(jié)點(diǎn) 父節(jié)點(diǎn)Open表：表：Closed表：表：算法步驟算法步驟Step1 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入 Open表，建立僅包含表，建立僅包含S0的圖的圖

11、 G； Step2 從從Open表中取出待擴(kuò)展節(jié)點(diǎn)，放入表中取出待擴(kuò)展節(jié)點(diǎn)，放入Closed表表； （不同搜索策略的區(qū)別主要體現(xiàn)于此）（不同搜索策略的區(qū)別主要體現(xiàn)于此）Step3 對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展，將擴(kuò)展得到的、未在對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展，將擴(kuò)展得到的、未在G中出中出現(xiàn)過的子節(jié)點(diǎn)放入現(xiàn)過的子節(jié)點(diǎn)放入Open表；根據(jù)需要修改表；根據(jù)需要修改G中節(jié)中節(jié)點(diǎn)的指針；點(diǎn)的指針；Step4 重復(fù)重復(fù)Step2-3直到直到 狀態(tài)空間狀態(tài)空間：待擴(kuò)展節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)或：待擴(kuò)展節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)或Open表為空表為空盲目搜索策略盲目搜索策略l廣度（寬度）優(yōu)先搜索廣度（寬度）優(yōu)先搜索 先生成的節(jié)點(diǎn)先擴(kuò)展先生成的節(jié)點(diǎn)先擴(kuò)展l深度優(yōu)

12、先搜索深度優(yōu)先搜索 后生成的節(jié)點(diǎn)先擴(kuò)展后生成的節(jié)點(diǎn)先擴(kuò)展l有界深度優(yōu)先搜索有界深度優(yōu)先搜索 在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先與在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先與深度優(yōu)先之間折衷深度優(yōu)先之間折衷完備完備最小路徑解最小路徑解效率效率2 8 347 6 5S01 2 38 47 6 5Sg盲目搜索例（狀態(tài)空間）盲目搜索例（狀態(tài)空間）: 八數(shù)碼難題八數(shù)碼難題在在 3*3 的方格棋盤上，分別放置了標(biāo)有數(shù)字的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)的八張牌，初始狀態(tài)S0和目標(biāo)狀態(tài)和目標(biāo)狀態(tài)Sg分別如圖所示。可以使用的操作有：分別如圖所示。可以使用的操作

13、有： 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。廣度優(yōu)先搜索算法如下：(1)把初始結(jié)點(diǎn)放入Open表中；(2)如果Open表為空，則問題無解，失敗退出；(3)把Open表的第一個(gè)結(jié)點(diǎn)取出，放入Closed表，并記該結(jié)點(diǎn)為n；(4)擴(kuò)展節(jié)點(diǎn)n，如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第(2)步；(5)把n的所有后繼結(jié)點(diǎn)放入Open表的末尾，并提供從這些后繼結(jié)點(diǎn)回到父結(jié)點(diǎn)(編號(hào)值為n)的指針;(6)如果剛產(chǎn)生的這些后繼結(jié)點(diǎn)中存在一個(gè)目標(biāo)結(jié)點(diǎn)，則找到一個(gè)解。解可從目標(biāo)結(jié)點(diǎn)開始直到初始結(jié)點(diǎn)的返回指針中得到，算法成功退

14、出。否則轉(zhuǎn)(2)繼續(xù)。 SLOMFPQNFFF起始結(jié)點(diǎn)起始把S0放入Open表Open表是否為空失敗把第1個(gè)結(jié)點(diǎn)n，從Open表移出并把它放入Closed表中擴(kuò)展n,把它的后繼結(jié)點(diǎn)放入Open表的末端,提供回到n的指針是否有任何后繼結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)？成功否是否是示意圖示意圖算法框圖算法框圖2 8 31 47 6 5S012 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 47 55 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 62

15、 8 31 6 4 7 52 8 31 6 47 567 89 1011 12138 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 1 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 41415218 32 1 47 6 58 1 32 47 6 522232 8 37 46 1 52 8 37 1 46 524251 2 38 47 6 51 2 3 7 8 4 6 52627Sg解的路徑是：解的路徑是：S S0 0 3 8 16 26( 3 8 16 26(SgSg) )八數(shù)碼難題

16、的廣度優(yōu)先搜索八數(shù)碼難題的廣度優(yōu)先搜索廣度優(yōu)先搜索是一種完備策略，即只要問題有廣度優(yōu)先搜索是一種完備策略，即只要問題有解解,它就一定可以找到解。并且廣度優(yōu)先搜索找它就一定可以找到解。并且廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。到的解，還一定是路徑最短的解。深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索是一種后生成的結(jié)點(diǎn)先擴(kuò)展的策后生成的結(jié)點(diǎn)先擴(kuò)展的策略略。其搜索過程是：從初始結(jié)點(diǎn)S0開始，在其子結(jié)點(diǎn)中選擇一個(gè)最新生成的結(jié)點(diǎn)進(jìn)行考察，如果該子結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子結(jié)點(diǎn)，依此向下搜索，直到某個(gè)子結(jié)點(diǎn)既不是目標(biāo)結(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟結(jié)點(diǎn)進(jìn)行考察。圖示如下：S012376845

17、9起始結(jié)點(diǎn)起始把S0放入Open表S0是否為目標(biāo)結(jié)點(diǎn)是否Open為空表把Open表中的第一個(gè)結(jié)點(diǎn)n移入Closed表結(jié)點(diǎn)n的深度是否等于深度界限擴(kuò)展結(jié)點(diǎn)n，把其后代放入Open表的前端是否有任何后繼結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)成功失敗成功是否是是是否否否示意圖示意圖算法框圖算法框圖深度優(yōu)先搜索算法如下：(1)把初始結(jié)點(diǎn)S0放入Open表中；(2)如果Open表空，則問題無解，失敗退出；(3)把Open表的第一個(gè)結(jié)點(diǎn)取出放入Close表，并記該結(jié)點(diǎn)為n;(4)考察結(jié)點(diǎn)n是否為目標(biāo)結(jié)點(diǎn)，若是，則得到問題的解，成功退出；(5) 若結(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)(2)；(6)擴(kuò)展結(jié)點(diǎn)n，將其子結(jié)點(diǎn)放入Open表的首部，并為每

18、一個(gè)子結(jié)點(diǎn)設(shè)置指向父結(jié)點(diǎn)的指針，然后轉(zhuǎn)(2)。2 8 31 47 6 5S012 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 522 8 31 6 4 7 52 8 31 6 47 532 8 31 67 5 442 81 6 37 5 42 8 31 67 5 452 81 6 37 5 46八數(shù)碼難題的深度優(yōu)先搜索八數(shù)碼難題的深度優(yōu)先搜索 從深度優(yōu)先搜索的算法可以看出,搜索一旦進(jìn)入某個(gè)分支，就將沿這個(gè)分支一直進(jìn)行下去，如果目標(biāo)恰好在這個(gè)分支上,則它可以很快找到解.但是,如果目標(biāo)不在這個(gè)分支上，且分支是一個(gè)無窮分支，則搜索過程就不可能找

19、到解。因此，深度優(yōu)先搜索是一種不完備策略，即使問題有解，它也不一定能夠找到解。解路徑為解路徑為:So：l 11 12 13 14：SgSg 八數(shù)碼難題的有界深度優(yōu)先搜索八數(shù)碼難題的有界深度優(yōu)先搜索2 8 31 47 6 5S012 8 3 1 47 6 522 31 8 47 6 5112 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 62 8 31 6 4 7 52 8 31 6 47 537 138 32 1 47 6 52 8

20、 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 1 4 37 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 4488 32 1 47 6 58 1 32 47 6 5562 8 37 46 1 52 8 37 1 46 59101 2 38 47 6 51 2 3 7 8 4 6 514 12深度限制為深度限制為4上面討論的搜索方法都沒有用到問題本身的特性信息，只是按事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。事實(shí)上，如果能利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對(duì)搜索將是非常有益的。這種利用問題自身的特

21、性來引導(dǎo)搜索過程，提高搜索效提高搜索效率率的搜索策略稱為啟發(fā)式搜索啟發(fā)式搜索或有信息搜索有信息搜索。啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息啟發(fā)性信息，而啟發(fā)性信息又是通過估價(jià)函數(shù)估價(jià)函數(shù)而作用于搜索過程的。5.4啟發(fā)式搜索啟發(fā)式搜索l啟發(fā)式算法啟發(fā)式算法 利用問題的特殊性，選擇待擴(kuò)展的節(jié)點(diǎn)，以縮小利用問題的特殊性，選擇待擴(kuò)展的節(jié)點(diǎn)，以縮小搜索范圍，提高搜索速度。搜索范圍，提高搜索速度。l啟發(fā)信息啟發(fā)信息 可指導(dǎo)搜索過程，且與具體問題求解過程有關(guān)的可指導(dǎo)搜索過程，且與具體問題求解過程有關(guān)的控制性信息。一般有以下三種：控制性信息。一般有以下三種： 幫助確定擴(kuò)展節(jié)點(diǎn)的信息；幫助確定擴(kuò)展節(jié)點(diǎn)的信

22、息； 幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息；幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息； 在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)決定哪些節(jié)點(diǎn)應(yīng)被刪除的信息在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)決定哪些節(jié)點(diǎn)應(yīng)被刪除的信息l估價(jià)函數(shù)估價(jià)函數(shù)f(n)：用于估計(jì)用于估計(jì)節(jié)點(diǎn)代價(jià)節(jié)點(diǎn)代價(jià)的函數(shù)的函數(shù) 定義定義為從初始節(jié)點(diǎn)為從初始節(jié)點(diǎn)S0出發(fā)，經(jīng)過節(jié)點(diǎn)出發(fā)，經(jīng)過節(jié)點(diǎn)n約束后，到達(dá)約束后，到達(dá)目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)Sg的所有路徑中最優(yōu)路徑的代價(jià)估計(jì)值。的所有路徑中最優(yōu)路徑的代價(jià)估計(jì)值。 一般形式一般形式為為 f(n)=g(n)h(n)g(n)是從初始節(jié)點(diǎn)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)。可以從節(jié)的實(shí)際代價(jià)。可以從節(jié)點(diǎn)點(diǎn)n反向跟蹤到初始節(jié)點(diǎn)反向跟蹤到初始節(jié)點(diǎn)S

23、0,得到一條當(dāng)前最小代價(jià)路得到一條當(dāng)前最小代價(jià)路徑，把這條路徑上所有有向邊的代價(jià)相加，就得到徑，把這條路徑上所有有向邊的代價(jià)相加，就得到g(n)的值。的值。 ； h(n)是從節(jié)點(diǎn)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)S0的最優(yōu)路徑的估計(jì)代價(jià)。的最優(yōu)路徑的估計(jì)代價(jià)。需要根據(jù)問題自身的特性來確定，體現(xiàn)了問題自身的需要根據(jù)問題自身的特性來確定，體現(xiàn)了問題自身的啟發(fā)性信息，因此也稱為啟發(fā)性信息，因此也稱為啟發(fā)函數(shù)啟發(fā)函數(shù)。估價(jià)函數(shù)例：估價(jià)函數(shù)例：f(n) = d(n) + W(n)2 8 347 6 5S0節(jié)點(diǎn)節(jié)點(diǎn)n在搜索樹中的深度在搜索樹中的深度n中中“不在位不在位”的數(shù)碼個(gè)數(shù)的數(shù)碼個(gè)數(shù)f(S0) = ?

24、= 0 + 3 = 31 2 38 47 6 5Sgl根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，分為全根據(jù)搜索過程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)搜索。局擇優(yōu)搜索和局部擇優(yōu)搜索。 1. 全局擇優(yōu)全局擇優(yōu) 在在Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展點(diǎn)進(jìn)行擴(kuò)展 2. 局部擇優(yōu)局部擇優(yōu) 在剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)在剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。行擴(kuò)展。局部最佳優(yōu)先搜索算法局部最佳優(yōu)先搜索算法l對(duì)OPEN表中所有節(jié)點(diǎn)的f(n)進(jìn)行比較，按從小到大的順序重排OPEN表。l其算法效率類似于縱向

25、搜索算法，但使用了與問題特性相關(guān)的估價(jià)函數(shù)來確定下一步待擴(kuò)展的節(jié)點(diǎn)，因此是一種啟發(fā)式搜索方法。開始開始把把S放入放入OPEN表，表，計(jì)算估價(jià)函數(shù)計(jì)算估價(jià)函數(shù) f (s)OPEN表為空表？表為空表？把把OPEN表中的第一個(gè)節(jié)點(diǎn)表中的第一個(gè)節(jié)點(diǎn)n放入放入CLOSED表表n為目標(biāo)節(jié)點(diǎn)嗎？為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展擴(kuò)展n，計(jì)算所有子節(jié)點(diǎn)的估價(jià)函數(shù)值，計(jì)算所有子節(jié)點(diǎn)的估價(jià)函數(shù)值，并提供它們返回節(jié)點(diǎn)并提供它們返回節(jié)點(diǎn)n的指針。的指針。失敗失敗成功成功局部最佳優(yōu)先搜索算法框圖局部最佳優(yōu)先搜索算法框圖是是否否是是否否把子節(jié)點(diǎn)送入把子節(jié)點(diǎn)送入OPEN表，并對(duì)其中的所有表，并對(duì)其中的所有節(jié)點(diǎn)按估價(jià)函數(shù)值由小到大重排。節(jié)點(diǎn)

26、按估價(jià)函數(shù)值由小到大重排。l 舉例：八數(shù)碼魔方（八數(shù)碼魔方（8-puzzle problem）12384567（目標(biāo)狀態(tài)）（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）（初始狀態(tài)）57123845671238456712384567 (3) (5) (5)123845671238456712384567 (4) (3) (3)1238456712 384567 (2) (4)1238456712384567 (3) (4)12384567 (1)813245671 2384567 (0)(2)八數(shù)碼魔方的局部八數(shù)碼魔方的局部最佳優(yōu)先搜索樹最佳優(yōu)先搜索樹123846(4)75搜索得到的路徑如黃線所示搜

27、索得到的路徑如黃線所示l本題采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=W(n)其中：W(n)用來計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)。因此，初始節(jié)點(diǎn)棋局的f(n)值等于4。12384567l第步有三種情況,我們選擇其中f(n)最小的: l其它依次類推.最后用了7步得出了結(jié)果. 123845671238456712384567 (3)(5)(5) l最佳優(yōu)先算法有時(shí)無法得到最優(yōu)解，因?yàn)樗墓纼r(jià)函數(shù)f的選取時(shí)，忽略了從初始節(jié)點(diǎn)到目前節(jié)點(diǎn)的代價(jià)值。所以，可考慮對(duì)估價(jià)函數(shù)f(n)進(jìn)行某些修改或限制。 5.5 A*算法算法l對(duì)估價(jià)函數(shù)加上一些限制，以保證得到最優(yōu)解對(duì)估價(jià)函數(shù)加上一些限制，以保證得到最優(yōu)解的啟發(fā)

28、式搜索算法的啟發(fā)式搜索算法l最優(yōu)估價(jià)函數(shù)最優(yōu)估價(jià)函數(shù) f*(n) g*(n) h*(n)初始節(jié)點(diǎn)到節(jié)點(diǎn)初始節(jié)點(diǎn)到節(jié)點(diǎn)n的最小代價(jià)的最小代價(jià)節(jié)點(diǎn)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最小代價(jià)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)l有關(guān)限制有關(guān)限制 1. g(n)是對(duì)是對(duì)g*(n)的估計(jì)，且的估計(jì)，且g(n) 0； 2. h(n)是是h*(n)的下界，即對(duì)任意節(jié)點(diǎn)的下界，即對(duì)任意節(jié)點(diǎn)n均有均有h(n)h*(n)A*算法例算法例1：八數(shù)碼問題：八數(shù)碼問題解解1： h(n) = W(n)。盡管不能確切知道。盡管不能確切知道h*(n) ，但當(dāng)采用單位代價(jià)時(shí)，通過對(duì)但當(dāng)采用單位代價(jià)時(shí)，通過對(duì)“不在位不在位”數(shù)碼數(shù)碼個(gè)數(shù)的估計(jì)，可以得出至少要移

29、動(dòng)個(gè)數(shù)的估計(jì)，可以得出至少要移動(dòng)W(n)步才能步才能到達(dá)目標(biāo)，顯然有到達(dá)目標(biāo)，顯然有W(n)h*(n)，滿足，滿足A*算法的算法的限制條件。限制條件。解解2：h(n) = P(n)，P(n)定義為每一個(gè)數(shù)碼與其定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動(dòng)的總和，同樣可以斷定至少要移動(dòng)P(n)步才能步才能到達(dá)目標(biāo)，因此有到達(dá)目標(biāo)，因此有P(n)h*(n)，即滿足，即滿足A*算法算法的限制條件。的限制條件。2 8 31 47 6 5h=4, f=4S02 31 8 47 6 52 8 31 6 47 52 8 3

30、 1 47 6 52 8 31 47 6 5g=1 2 31 8 47 6 52 31 8 47 6 5g=21 2 38 47 6 51 2 37 8 4 6 5Sgg=4h=5, f=6h=5, f=6h=3, f=4h=5, f=6h=2, f=4h=3, f=51 2 3 8 47 6 5g=3h=1, f=4h=0, f=4h=2, f=6八數(shù)碼難題的的八數(shù)碼難題的的A*搜索圖搜索圖 （h(n) = P(n)）A*算法例算法例2：修道士和野人問題修道士和野人問題設(shè)在河的左岸有三個(gè)修道士、三個(gè)野人和一條設(shè)在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，船

31、，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束：但受以下條件的約束： 1.修道士和野人都會(huì)劃船，但每次船上至多修道士和野人都會(huì)劃船，但每次船上至多可載兩個(gè)人；可載兩個(gè)人； 2.河的任一岸如果野人數(shù)目超過修道士數(shù)，河的任一岸如果野人數(shù)目超過修道士數(shù)，修道士就會(huì)被野人吃掉。修道士就會(huì)被野人吃掉。請(qǐng)給出一個(gè)確保修道士和野人都能過河，且沒請(qǐng)給出一個(gè)確保修道士和野人都能過河，且沒有修道士被野人吃掉的過河規(guī)劃有修道士被野人吃掉的過河規(guī)劃問題表示問題表示：需要考慮兩岸的修道士人數(shù)和野人：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。用三元式表示狀態(tài)：人數(shù)，船的位置。用三元式表示狀態(tài)： S= (m

32、, c, b)其中，其中，m表示左岸修道士人數(shù)，表示左岸修道士人數(shù)，c表示左岸野表示左岸野人人數(shù)，人人數(shù)，b表示左岸船的數(shù)目。表示左岸船的數(shù)目。解解：確定估價(jià)函數(shù)。：確定估價(jià)函數(shù)。 f(n) = g(n) h(n) = d(n) m c 2b其中，其中，d(n)為節(jié)點(diǎn)深度。為節(jié)點(diǎn)深度。h(n)h*(n)，滿足，滿足A*算算法的限制條件。法的限制條件。(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3

33、,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的傳教士和野人問題的A*搜索圖搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)關(guān)于關(guān)于A*算法的一些討論算法的一些討論lA*算法是到目前為止最快的一種計(jì)算最短路徑的算法，但它是一種較優(yōu)算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解，但由于其高效性，使其在實(shí)時(shí)系統(tǒng)、人工智能等方面應(yīng)用極其廣泛。lA*算法結(jié)合了啟發(fā)式方法（這種方法通過充分利用圖給出的信息來動(dòng)態(tài)地作出決定而使搜索次數(shù)大大降低）和形式化方法（這種方法不利用圖給出的信息，而僅通過

34、數(shù)學(xué)的形式分析，如Dijkstra算法）。它通過一個(gè)估價(jià)函數(shù)（Heuristic Function）f(h)來估計(jì)圖中的當(dāng)前點(diǎn)p到終點(diǎn)的距離(帶權(quán)值)，并由此決定它的搜索方向，當(dāng)這條路徑失敗時(shí)，它會(huì)嘗試其它路徑。l我們可以發(fā)現(xiàn)，A*算法成功與否的關(guān)鍵在于估價(jià)函數(shù)的正確選擇，從理論上說，一個(gè)完全正確的估價(jià)函數(shù)是可以非常迅速地得到問題的正確解答，但一般完全正確的估價(jià)函數(shù)是得不到的，因而A*算法不能保證它每次都得到正確解答。一個(gè)不理想的估價(jià)函數(shù)可能會(huì)使它工作得很慢，甚至?xí)o出錯(cuò)誤的解答。l為了提高解答的正確性，我們可以適當(dāng)?shù)亟档凸纼r(jià)函數(shù)的值，從而使之進(jìn)行更多的搜索，但這是以降低它的速度為代價(jià)的，因而

35、我們可以根據(jù)實(shí)際對(duì)解答的速度和正確性的要求而設(shè)計(jì)出不同的方案，使之更具彈性。A*算法的數(shù)據(jù)結(jié)構(gòu)算法的數(shù)據(jù)結(jié)構(gòu)l眾所周知，對(duì)圖的表示可以采用數(shù)組或鏈表，而且這些表示法也各有優(yōu)缺點(diǎn)，數(shù)組可以方便地實(shí)現(xiàn)對(duì)其中某個(gè)元素的存取，但插入和刪除操作卻很困難，而鏈表則利于插入和刪除，但對(duì)某個(gè)特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對(duì)當(dāng)前結(jié)點(diǎn)以下結(jié)點(diǎn)的操作，因而數(shù)組或鏈表都顯得太通用了，用來實(shí)現(xiàn)A*算法會(huì)使速度有所降低。要實(shí)現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，實(shí)踐中如采用簡(jiǎn)單而高效的帶優(yōu)先權(quán)的堆棧，經(jīng)實(shí)驗(yàn)表明，一個(gè)1000個(gè)結(jié)點(diǎn)的圖，插入而且移動(dòng)一個(gè)排序的鏈

36、表平均需500次比較和2次移動(dòng)；未排序的鏈表平均需1000次比較和2次移動(dòng)；而堆僅需10次比較和10次移動(dòng)。需要指出的是，當(dāng)結(jié)點(diǎn)數(shù)n大于10，000時(shí)，堆棧不再是正確的選擇，但這足已滿足我們一般的要求。估價(jià)函數(shù)（估價(jià)函數(shù)（Heuristic Function）l估價(jià)函數(shù)的正確選取將直接關(guān)系到A*算法的成功與否，而函數(shù)的確定卻與實(shí)際情形有著密切的關(guān)系。這里以網(wǎng)格地圖的估價(jià)函數(shù)為例，其它情形需要作不同的分析，但至少估價(jià)函數(shù)應(yīng)為連續(xù)函數(shù)。la. Manhattan Distance，這是一種標(biāo)準(zhǔn)的估價(jià)函數(shù)，h(A) = 10 * (abs(A.x-goal.x) + abs(A.y-goal.y)l

37、b. Diagonal Distance，如果在地圖上允許作斜線方向的運(yùn)動(dòng)，則Mahattan Distance修正為Diagonal Distance：h(A) = max(abs(A.x-goal.x), abs(A.y-goal.y)估價(jià)函數(shù)的判優(yōu)估價(jià)函數(shù)的判優(yōu)l一般情形下，我們只需對(duì)估價(jià)函數(shù)的值進(jìn)行比較而取其大者即可，但在幾個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)值相同的情形下，我們需要采取一定的策略來決定這幾者誰更優(yōu)，從而避免對(duì)多個(gè)點(diǎn)的搜索。從而如下代碼可實(shí)現(xiàn)之：ldouble dx1 = currentX - goalX;ldouble dy1 = currentY - goalY;ldouble dx2 = startX - goalX;ldoubl