1、人工智能Artificial Intelligence搜索戰(zhàn)略 主要內(nèi)容概述形狀空間搜索形狀空間的普通搜索過程廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索A*算法問題規(guī)約搜索博弈概述(1)問題求解AI中每個研討領(lǐng)域都有其各自的特點和規(guī)律,但就求解問題的過程看,都可籠統(tǒng)為一個問題求解過程。問題求解過程實踐上是一個搜索,廣義地說,它包含了全部計算機科學(xué)。任何問題求解技術(shù)都包括兩個重要的方面:表示和搜索表示是根本的,搜索必需求在表示的根底上進展。表示關(guān)系到搜索的效率。本章討論的表示主要包括:形狀空間表示問題空間表示概述(2)1974年，Nilsson歸納出的AI研討的根本問題知識的模型化和表示常識性推理、演繹

2、和問題處理啟發(fā)式搜索人工智能系統(tǒng)和言語搜索是人工智能中的一個根本問題,是推理不可分割的一部分,直接關(guān)系到智能系統(tǒng)的性能和運轉(zhuǎn)效率AI為什么要研討search?問題沒有直接的解法;需求探求地求解;搜索(3)什么是搜索根據(jù)問題的實踐情況不斷尋覓可利用的知識,構(gòu)造出一條代價較少的推理道路,使問題得到圓滿處理的過程稱為搜索 包括兩個方面： - 找到從初始現(xiàn)實到問題最終答案的一條推理途徑 - 找到的這條途徑在時間和空間上復(fù)雜度最小搜索(4)盲目搜索:也稱為無信息搜索，即只按預(yù)定的控制戰(zhàn)略進展搜索,在搜索過程中獲得的中間信息不用來改良控制戰(zhàn)略啟發(fā)式搜索: 在搜索中參與了與問題有關(guān)的啟發(fā)性信息,用于指點搜索

3、朝著最有希望的方向進展,加速問題的求解過程并找到最優(yōu)解形狀空間表示法(1)形狀空間表示法：用來表示問題及其搜索過程的一種方法形狀形狀是描畫問題求解過程中任一時辰情況的數(shù)據(jù)構(gòu)造.23751486A，B，C，D2, 3,7 ,0 , 5, 2, 4, 8, 6形狀空間表示法(2)形狀空間:由問題的全部形狀及一切可用算符所構(gòu)成的集合稱為問題的形狀空間.普通表示為: (S, F, G)S:問題一切的初始形狀集合; F:算符集合; G:目的形狀集合算符: 引起形狀中某些分量發(fā)生變化, 從而使問題由一個形狀變?yōu)榱硪粋€形狀的操作稱為算符.形狀空間表示法是用“形狀和“算符表示問題的一種方法形狀空間圖:形狀空間

4、的圖式表示,稱為形狀空間圖.其中節(jié)點表示形狀,有向邊(弧)表示算符.形狀空間表示法(3)途徑形狀序列搜索尋覓從初始形狀到目的形狀的途徑;S0Sg形狀空間表示法4例一:二階梵塔問題設(shè)有三個鋼針,在一號鋼針上穿有A,B兩個金片,A小于B,A位于B的上面.要求把這兩個金片全部移到另一個鋼針上,而且規(guī)定每次只能挪動一片,任何時辰都不能使B位于A的上面設(shè)用Sk=(Sk0,Sk1)表示問題的形狀,SK0表示金片A所在的鋼針號,SK1表示金片B所在的鋼針號,全部能夠的形狀為:S0=(1,1), S1=(1,2), S3=(1,3)S4=(2,1), S5=(2,2), S6=(2,3)S7=(3,1), S

5、8=(3,2), S9=(3,3)問題初始形狀集合S=S0,目的形狀集合G=S4,S8.算符:A( i,j):表示把金片A從第i號針移到第j號針上B(i,j):表示把B從第i號針移到第j號針上共12個算符:A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2)B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)形狀空間表示法5用形狀空間表示,首先必需定義形狀的描畫方式,把問題的一切形狀都表示出來,其次定義算符,完成形狀的轉(zhuǎn)換問題的求解過程就是一個把算符不斷地作用于形狀的過程.假設(shè)在運用某個算符后得到的形狀就是目的形狀,

6、就得到了問題的解.這個解就是從初始形狀到目的形狀所用算符構(gòu)成的序列.算符的一次運用,就使問題由一種形狀轉(zhuǎn)變?yōu)榱硪环N形狀.能夠有多個算符序列都可使問題從初始形狀變到目的形狀,這就得到了多個解.對任何一個形狀,可運用的算符能夠不止一個,這樣由一個形狀所生成的后繼形狀能夠有多個.如何選擇下一步的操作,由搜索戰(zhàn)略決議.搜索控制戰(zhàn)略1搜索控制戰(zhàn)略不可撤回的控制戰(zhàn)略;試探性控制戰(zhàn)略回溯型圖搜索搜索控制戰(zhàn)略2不可撤回的控制戰(zhàn)略例：八數(shù)碼問題評價函數(shù):f： 規(guī)定: 評價函數(shù)非增2831647512384765與的差別為4搜索控制戰(zhàn)略3不可撤回的控制戰(zhàn)略28316475283147652318476512384

7、7651238476523184765f=4f=3f=3f=0f=1f=21搜索控制戰(zhàn)略4不可撤回的控制戰(zhàn)略283147652831476583214765813247658132476583214765f=3f=3f=3f=3f=3f=313824765f=213824765f=12搜索控制戰(zhàn)略5不可撤回的控制戰(zhàn)略能夠無解1258476312384765目的f=2搜索控制戰(zhàn)略6回溯戰(zhàn)略例：四皇后問題( )( )Q(1,1)( )QQ(1,1)(1,1) (2,3)( )Q(1,1)(1,1) (2,3)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)( )QQ(1,1)(1,

8、1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)(

9、 )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)Q(1,2) (2,4) (3,1)QQQQ( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)(1,2)(1,2) (2,4)(1,2) (2,4) (3,1)(1,2) (2,4) (3,1) (4,3)與/或樹表示法1根本概念與/或樹是用于表示問題及其求解過程的又一種方式化方法.復(fù)雜問題的簡化方法分解:把一個問題分解到不需再分解或不能再分解為止,然后對每個子問題進展求解,然后把各子問題的解復(fù)合起來,就得到原問題的解.等價

10、變換:利用同構(gòu)或同態(tài)的等價變換,把復(fù)雜問題轉(zhuǎn)換成假設(shè)干個較為容易求解的新問題.假設(shè)新問題中有一個可求解,那么就得到了原問題的解.與/或樹表示法2例子:三階梵塔問題設(shè)有A,B,C三個金片以及三個鋼針,三個金片按自上而下從小到大的順序穿在1號鋼針上,要求把它們?nèi)恳频?號鋼針上,而且每次只能移到一個金片,任何時候都不能把大的金片壓在小的金片上面.用與/或樹表示:問題分解(1)為了把三個金片全部移到3號針上,必需先把C移到3號針上(2)為了移到C,必需把A和B移到2號針上(3)當(dāng)C移到3針后,就可把A和B移到3針上,完成問題求解得到三個子問題(1)把A和B移到2號針的雙金片問題(2)把C移到3號針的

11、單金片問題(3)把A和B移到3號針的雙金片問題度量問題求解的性能普通搜索戰(zhàn)略可以經(jīng)過下面四個準(zhǔn)那么來評價：完備性：假設(shè)存在一個解答，該戰(zhàn)略能否保證可以找到？時間復(fù)雜性：需求多長時間可以找到解答？空間復(fù)雜性：執(zhí)行搜索需求多少存儲空間？最優(yōu)性：假設(shè)存在不同的幾個解答，該戰(zhàn)略能否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索戰(zhàn)略反映了形狀空間或問題空間擴展的方法，也決議了形狀或問題的訪問順序。在AI領(lǐng)域，形狀空間圖由初始形狀和算子隱含地表示，經(jīng)常是無限的，它的復(fù)雜度根據(jù)下面三個值來表達(dá)： 分支因子b：任何節(jié)點的后繼的最大個數(shù)最淺的目的節(jié)點的深度d形狀空間中任何途徑的最大長度m主要內(nèi)容概述形狀空間搜索形狀空間的普通搜索

12、過程廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索A*算法問題規(guī)約搜索博弈形狀空間搜索過程要點1求解一個可以滿足目的條件的問題可以表達(dá)為搜索一個圖以找到一個滿足目的形狀描畫的節(jié)點問題.搜索過程的要點如下:起始節(jié)點:對應(yīng)于初始形狀描畫后繼節(jié)點:把適用于某個節(jié)點形狀描畫的一些算符用來推算該節(jié)點而得到的新節(jié)點,稱為該節(jié)點的后繼節(jié)點指針:從每個后繼節(jié)點前往指向其父輩節(jié)點檢查各后繼節(jié)點看能否為目的節(jié)點.搜索過程擴展后繼節(jié)點的次序假設(shè)搜索是以接近起始節(jié)點的程度(由節(jié)點之間連結(jié)弧線的數(shù)目來衡量)依次擴展節(jié)點,稱為廣(寬)度優(yōu)先搜索假設(shè)搜索時首先擴展最新產(chǎn)生的節(jié)點,稱為深度優(yōu)先搜索形狀空間搜索過程要點2指針 調(diào)整指針擴展

13、一個節(jié)點生成出該節(jié)點的一切后繼節(jié)點。弧的費用有一條弧銜接ni和nj兩個節(jié)點, 用C(ni, nj)表示運用規(guī)那么從ni到nj的費用(耗散值)。 玉泉路-天安門途徑的耗散值一條途徑的耗散值等于銜接這條途徑各節(jié)點間一切耗散值的總和。用C(ni, nj)表示從ni到nj的途徑的耗散值。形狀空間的普通搜索過程1主要數(shù)據(jù)構(gòu)造OPEN表:存放剛生成的節(jié)點,是還未擴展的節(jié)點.普通是端節(jié)點.CLOSED表:存放將要擴展或已擴展的節(jié)點.或者是已被擴展但還沒有在搜索樹中生成后繼節(jié)點的端節(jié)點,或者是非端節(jié)點形狀空間的普通搜索過程2(1)把初始節(jié)點S0放入OPEN表,并建立目前只包含S0的圖,記為G(2)檢查OPEN

14、表能否為空,假設(shè)為空那么問題無解,退出(3)把OPEN表的第一個節(jié)點取出放入CLOSED表,記該節(jié)點為n(4)調(diào)查n能否為目的節(jié)點.如是,那么問題得解,退出(5)擴展節(jié)點n,生成一組子節(jié)點.把其中不是節(jié)點n先輩的那些節(jié)點記作集合M,并把這些子節(jié)點作為節(jié)點n的子節(jié)點參與G中(6)針對M中子節(jié)點的不同情況,分別進展處置對于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點(即n)的指針,并把它們放入OPEN表對于那些先前已在G中出現(xiàn)過的M成員,確定能否需求修正它指向父節(jié)點的指針對于那些先前已在G中出現(xiàn)并且曾經(jīng)擴展了的M成員,確定能否需求修正其后繼節(jié)點指向父節(jié)點的指針(7)按某種搜索戰(zhàn)略對OPEN表中的

15、節(jié)點進展排序(8)轉(zhuǎn)第(2)步例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 2S13451,2,3 S 3,1,2 S OPENCLOSES 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,4,6,8,1,12,13

16、2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的節(jié)點修正指針2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,

17、5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點修正指針2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 6

18、76,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點(8)的后裔(10)修正指針形狀空間的普通搜索過程(3)注:這是一個通用的搜索過程,后面討論的形狀空間各種搜索戰(zhàn)略都是其特例.各種搜索戰(zhàn)略的主要區(qū)別就是對OPEN表中節(jié)點排序準(zhǔn)那么不同算法終了后，將生成一個圖G，稱為搜索圖。同時由于每個節(jié)點都有一個指針指向父節(jié)點，這些指針指向的節(jié)點構(gòu)成G的一個支撐樹，

19、稱為搜索樹。 從目的節(jié)點開場，將指針指向的形狀回串起來，即找到一條解途徑.樹/不修正指針; 圖/修正指針;修正指針:找最優(yōu)解 形狀空間的普通搜索過程(4)搜索圖2S134567891011121314形狀空間的普通搜索過程(5)搜索樹112S1324567891011121314廣度優(yōu)先搜索1搜索過程如下:(1)把初始節(jié)點S0放入OPEN表(2)假設(shè)OPEN表為空,那么問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出(5)假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步(6)擴展節(jié)點n,將其子節(jié)點放入OPEN

20、表的尾部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第(2)步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 51256731 2 3 8 47 6 5目的82 3 41 8 7 6 54廣度優(yōu)先搜索2Complete? Yes (假設(shè) b 是有

21、限的)Time? 1+b+b2+b3+ +bd + b(bd-1) = O(bd+1)Space? O(bd+1)Optimal? Yes (假設(shè)每步代價為1)空間是大問題(和時間相比)特點缺陷當(dāng)目的節(jié)點間隔初始節(jié)點較遠(yuǎn)時會產(chǎn)生許多無用的節(jié)點,搜索效率低優(yōu)點只需問題有解,那么總可以得到解,而且是最短途徑的解深度優(yōu)先搜索1搜索過程如下:(1)把初始節(jié)點S0放入OPEN表(2)假設(shè)OPEN表為空,那么問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出(5)假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步(6)擴展節(jié)

22、點n,將其子節(jié)點放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第(2)步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 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 5

23、2 81 4 37 6 52 8 31 4 57 623456789abcd1 2 3 8 47 6 5目的深度優(yōu)先搜索2Complete? No: 當(dāng)空間為無限深度時Time? O(bm): 假設(shè) m 比d大很多那么比較嚴(yán)重Space? O(bm), 線性空間Optimal? No特點缺陷假設(shè)目的節(jié)點不在搜索所進入的分支上,而該分支又是一個無窮分支,那么就得不到解.因此該算法是不完備的優(yōu)點假設(shè)目的節(jié)點不在搜索所進入的分支上,那么可以較快地得到解有界深度優(yōu)先搜索定義搜索深度的界限dm,當(dāng)搜索深度到達(dá)了深度界限,而尚未出現(xiàn)目的節(jié)點時,就換一個分支進展搜索搜索過程如下:(1)把初始節(jié)點S0放入OP

24、EN表,置S0的深度d(S0)=0(2)假設(shè)OPEN表為空,那么問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出(5)假設(shè)節(jié)點n的深度d(節(jié)點n)=dm,那么轉(zhuǎn)第(2)步(6)假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步(7)擴展節(jié)點n,將其子節(jié)點放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第(2)步迭代加深搜索1對于有界深度搜索戰(zhàn)略，有下面幾點需求闡明： 1在有界深度搜索算法中，深度限制dm是一個很重要的參數(shù)。 2深度限制dm不能太大。 3有界深度搜索的主要問題是深度限制值dm的選取

25、。 問題：但是對很多問題，我們并不知道該值究竟為多少，直到該問題求解完成了，才可以確定出深度限制dm。迭代加深搜索2改良方法-迭代加深搜索算法 ：先恣意給定一個較小的數(shù)作為dm，然后按有界深度算法搜索，假設(shè)在此深度限制內(nèi)找到了解，那么算法終了；如在此限制內(nèi)沒有找到問題的解，那么增大深度限制dm，繼續(xù)搜索。 迭代加深搜索是一種逃避選擇最優(yōu)深度限制問題的戰(zhàn)略，它是試圖嘗試一切能夠的深度限制：首先深度為0，然后深度為1，然后為2，等等，不斷進展下去。 問題：迭代加深搜索看起來會很浪費，由于很多節(jié)點都要擴展多次。 迭代加深搜索3迭代加深搜索4迭代加深搜索5迭代加深搜索6迭代加深搜索6深度為d，分支因子

26、為b的深度優(yōu)先搜索生成的節(jié)點數(shù)為：NDLS = b0 + b1 + b2 + + bd-2 + bd-1 + bd 深度為d，分支因子為b的迭代加深搜索生成的節(jié)點數(shù)為NIDS = (d+1)b0 + d b1 + (d-1)b2 + + 3bd-2 +2bd-1 + 1bd 對于 b = 10, d = 5,NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456添加 = (123,456 - 111,111)/111,111

27、= 11%迭代加深搜索7Complete? YesTime? (d+1)b0 + d b1 + (d-1)b2 + + bd = O(bd)Space? O(bd)Optimal? Yes, 假設(shè)每步代價為1代價樹的廣度優(yōu)先搜索邊上標(biāo)有代價(或費用)的樹稱為代價樹g(x)表示從初始節(jié)點S0到節(jié)點x的代價,c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價,那么有 g(x2)=g(x1)+c(x1,x2)搜索過程如下:把初始節(jié)點S0放入OPEN表,令g(S0)=0假設(shè)OPEN表為空,那么問題無解,退出把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,

28、那么求得了問題的解,退出假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步擴展節(jié)點n,將其子節(jié)點放入OPEN表中,并為每一個子節(jié)點都配置指向父節(jié)點的指針;計算各子節(jié)點的代價,并按各節(jié)點的代價對OPEN表中全部節(jié)點進展排序(按從小到大的順序),然后轉(zhuǎn)第(2)步代價樹的深度優(yōu)先搜索搜索過程如下:把初始節(jié)點S0放入OPEN表假設(shè)OPEN表為空,那么問題無解,退出把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步擴展節(jié)點n,將其子節(jié)點按邊代價從小到大的順序放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的

29、指針,然后轉(zhuǎn)第(2)步啟發(fā)式搜索1前面討論的方法都是盲目的搜索方法,即都沒有利用問題本身的特性信息,在決議要被擴展的節(jié)點時,都沒有思索該節(jié)點在解的途徑上的能夠性有多大,它能否有利于問題求解以及求出的解能否為最優(yōu)啟發(fā)式搜索要用到問題本身的某些特性信息,以指點搜索朝著最有希望的方向前進啟發(fā)信息的強度強：降低搜索任務(wù)量，但能夠?qū)е抡也坏阶顑?yōu)解弱：普通導(dǎo)致任務(wù)量加大，極限情況下變?yōu)槊つ克阉鳎軌蚩梢哉业阶顑?yōu)解啟發(fā)式搜索2啟發(fā)性信息和估價函數(shù)用于指點搜索過程,且與詳細(xì)問題有關(guān)的控制性信息稱為為啟發(fā)性信息用于評價節(jié)點重要性的函數(shù)稱為估價函數(shù).記為 f(x) = g(x) + h(x)g(x)為從初始節(jié)點

30、S0到節(jié)點x曾經(jīng)實踐付出的代價h(x)是從節(jié)點x到目的節(jié)點Sg的最優(yōu)途徑的估價代價,表達(dá)了問題的啟發(fā)性信息,稱為啟發(fā)函數(shù)f(x)表示從初始節(jié)點經(jīng)過節(jié)點x到達(dá)目的節(jié)點的最優(yōu)途徑的代價估價值,其作用是用來評價OPEN表中各節(jié)點的重要性,決議其次序啟發(fā)式搜索3例：八數(shù)碼問題，評價函數(shù)f(n) = d(n) + W(n)d(n): 節(jié)點n的深度;W(n):與目的相比, 錯位的數(shù)字?jǐn)?shù)目;1238476528316475初始形狀目的形狀 2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 3

31、1 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目的123456啟發(fā)式搜索4啟發(fā)式就是要猜測：從節(jié)點n開場，找到最優(yōu)解的能夠性有多大？ 從起始節(jié)點開場，經(jīng)過節(jié)點n，到達(dá)目的節(jié)點的最正確途徑的費用是多少？ gh部分擇優(yōu)搜索(瞎子爬山法)1搜索過程如下:(1)把初始節(jié)點S0放入OPEN表,計算f(S0)(2)假設(shè)OPEN表為空,那

32、么問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出(5)假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步(6)擴展節(jié)點n,用估價函數(shù)f(x)計算每個子節(jié)點的估價值,并按估價值從小到大的順序依次放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉(zhuǎn)第(2)步部分擇優(yōu)搜索(瞎子爬山法)2爬山法的三個問題：部分最大： 高地：也稱為平頂，在某一部分點周圍f(x)為常量。此時，搜索就無法確定要搜索的最正確方向，會產(chǎn)生隨機走動，這使得搜索效率降低。 山脊：山脊能夠具有峻峭的斜面，所以搜索可以比較容易地到達(dá)山脊的

33、頂部，但是山脊的頂部到山峰之間能夠傾斜的很平緩。除非正好有適宜的操作符直接沿著山脊的頂部挪動，該搜索能夠會在山脊的兩面來回震蕩，搜索的前提高伐會很小。全局擇優(yōu)搜索(有序搜索/最好優(yōu)先)搜索過程如下:(1)把初始節(jié)點S0放入OPEN表,計算f(S0)(2)假設(shè)OPEN表為空,那么問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)調(diào)查節(jié)點n能否為目的節(jié)點.假設(shè)是,那么求得了問題的解,退出(5)假設(shè)節(jié)點n不可擴展,那么轉(zhuǎn)第(2)步(6)擴展節(jié)點n,用估價函數(shù)f(x)計算每個子節(jié)點的估價值,并為每一個子節(jié)點都配置指向父節(jié)點的指針,把這些子節(jié)點都送入OPEN表,然后

34、對OPEN表中的全部節(jié)點按估價值從小到大的順序進展陳列(7)轉(zhuǎn)第(2)步A*算法1將形狀空間普通搜索過程進展如下的限制,就是A*算法把OPEN表中的節(jié)點按估價函數(shù) f(x) = g(x) + h(x)的值從小到大進展排序g(x)是對g*(x)的估價,g(x)0h(x)是h*(x)的下界,即對一切的x, h(x)=h*(x)其中: g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價 h*(x)是從節(jié)點x到目的節(jié)點的最小代價,假設(shè)有多個目的節(jié)點,那么為 其中最小的一個nSg*(n)h*(n) gA*算法2f*(S)f*(S) = g*(S)+h*(S) = h*(S)從S無約束地到達(dá)目的的最正確路經(jīng)上的

35、耗散值;g(n)普通取實踐走過的途徑的費用和.g(n) g*(n)隨著算法的執(zhí)行，由于指針的變動，g(n)會下降. h0沒有啟發(fā)式信息;A*算法38數(shù)碼問題h(n) = “不在位的將牌數(shù)h(n) = 將牌“不在位的間隔和2 8 31 6 47 51 2 3457 6 8將牌1：1將牌2：1將牌6：1將牌8：2A*算法4A*算法5寬度優(yōu)先: 當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解;f(n) = g(n) + h(n)g(n)h(n) = 0 h*(n)A*算法可納性對于可解形狀圖(即從初始節(jié)點到目的節(jié)點有途徑存在)所說,假設(shè)一個搜索算法能在有限步內(nèi)終止,并且能找到最優(yōu)解,那么稱該搜索

36、算法是可納的. 定理:A*算法是可納的,即在有限步內(nèi)終止,并且找到最優(yōu)解證明思緒對于有限圖,A*算法一定會在有限步內(nèi)終止對應(yīng)無限圖,只需從初始節(jié)點到目的節(jié)點有途徑存在,A*算法也必然終止A*算法一定終止在最優(yōu)途徑上A*算法的最優(yōu)性和單調(diào)性最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x),在滿足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所攜帶的啟發(fā)性信息越多,搜索時所擴展的節(jié)點數(shù)越少,搜索效率就越高單調(diào)性限制單調(diào)性限制是指h(x)滿足如下兩個條件h(Sg)=0設(shè)xj是節(jié)點xi 的恣意子節(jié)點,那么有 h(xi)-h(xj)=c(xi,xj) 其中:Sg是目的節(jié)點,c(xi,xj

37、)是節(jié)點xi到子節(jié)點xj的邊代價A*算法的h(x)滿足單調(diào)性限制時,可有下面的結(jié)論假設(shè)A*算法選擇節(jié)點xn進展擴展,那么g(xn)=g*(x)由A*算法所擴展的節(jié)點序列其f值是非遞減的主要內(nèi)容概述形狀空間搜索形狀空間的普通搜索過程廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索A*算法問題規(guī)約搜索博弈問題規(guī)約搜索(1)問題歸約法是不同于形狀空間法的另一種問題描畫和求解的方法。 啟發(fā)式搜索可以運用的第二個問題是AND-OR圖的反向推理問題。AND-OR圖的反向推理過程可以看作是一個問題歸約過程，即是說在問題求解過程中，將一個大的問題變換成假設(shè)干個子問題，子問題又可以分解成更小的子問題，這樣不斷分解到可以直接求

38、解為止，全部子問題的解就是原問題的解。并稱原問題為初始問題，可直接求解的問題為本原問題 問題規(guī)約搜索(2)問題歸約的描畫 :普通說來，問題歸約可以用三元組表示：S0，O，P，其中S0是初始問題，即要求解的問題。P是本原問題集，其中的每一個問題是不用證明的，自然成立的，如公理、知現(xiàn)實等，或已證明過的問題。 O是操作算子集，它是一組變換規(guī)那么，經(jīng)過一個操作算子把一個問題化成假設(shè)干個子問題。這樣，問題歸約表示方法就是由初始問題出發(fā)，運用操作算子產(chǎn)生一些子問題，對子問題再運用操作算子產(chǎn)生子問題的子問題，這樣不斷進展到產(chǎn)生的問題均為本原問題，那么問題得解。問題規(guī)約搜索(3)將問題求解歸約為AND-OR圖

39、搜索時，將初始節(jié)點表示初始問題描畫，對應(yīng)于本原問題的節(jié)點稱為葉節(jié)點。在AND-OR圖上執(zhí)行的搜索過程，其目的在于闡明起始節(jié)點是有解的，AND-OR圖中一個可解節(jié)點可遞歸地定義如下： 1葉節(jié)點是可解節(jié)點。 2假設(shè)某節(jié)點為或子節(jié)點，那么該節(jié)點可解當(dāng)且僅當(dāng)至少有一個子節(jié)點為可解節(jié)點。 3假設(shè)某節(jié)點為與子節(jié)點，那么該節(jié)點可解當(dāng)且僅當(dāng)一切子節(jié)點均為可解節(jié)點。不可解節(jié)點可遞歸定義如下： 1沒有后裔節(jié)點的非葉節(jié)點是不可解節(jié)點； 2或節(jié)點是不可解節(jié)點，當(dāng)且僅當(dāng)它的一切子節(jié)點都是不可解節(jié)點； 3與節(jié)點是不可解節(jié)點，當(dāng)且僅當(dāng)它的子節(jié)點中至少有一個是不可解節(jié)點。能導(dǎo)致初始節(jié)點可解的那些可解節(jié)點及有關(guān)連線組成的子圖稱

40、為該AND-OR圖的解圖。問題規(guī)約搜索(4)對OR圖搜索，假設(shè)搜索到某個節(jié)點n時，不論n能否生成了后繼節(jié)點，n的費用是由其本身形狀決議的，但對于AND-OR圖不同，其費用計算規(guī)那么為：n未生成后繼節(jié)點，那么費用由n本身決議；n曾經(jīng)生成了后繼節(jié)點，那么費用由n的后繼節(jié)點的費用決議。問題規(guī)約搜索(5)問題規(guī)約搜索(6)問題規(guī)約搜索(7)主要內(nèi)容概述形狀空間搜索形狀空間的普通搜索過程廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索A*算法問題規(guī)約搜索博弈博弈1博弈問題也稱為對抗搜索,是由假設(shè)干行為主體參與的競爭性智能活動.如下棋,打牌等等.和普通搜索相比，解答是對對手能夠走的每一步都給出本人的戰(zhàn)略。這里討論的問題

41、是最簡單的又最具代表性的“二人零和,全信息,非偶爾博弈,有弈雙方的利益是完全對立的:(1)對壘的A,B雙方輪番采取行動,博弈的結(jié)果只能有三種情況:A勝,B敗;A敗,B省;和局(2)在對壘過程中,任何一方都了解當(dāng)前的格局和過去的歷史(3)任何一方在采取行動前都要根據(jù)當(dāng)前的實踐情況,進展得失分析,選擇對本人最為有利而對對方最不利的對策,不存在“碰運氣的偶爾要素.即雙方都很明智地決議本人的行動.博弈(2)博弈問題是一種特殊的與/或樹問題,它具有如下的特點:博弈的初始格局是初始節(jié)點在博弈樹中,“或和“與節(jié)點是逐層交替出現(xiàn)的.本人一方擴展的節(jié)點之間是“或關(guān)系,對方擴展的節(jié)點之間是“與關(guān)系.雙方輪番擴展節(jié)點所用能使本人一方獲勝的結(jié)局都是本原問題,相應(yīng)的節(jié)點是可解節(jié)點;所用使對方獲勝的結(jié)局都是不可解節(jié)點.博弈中的優(yōu)化決策(1)博弈問題普通難以求解:游戲要求在即使無法計算出最優(yōu)決策的情況下也能做出某種決策的才干博弈問題可以定義為下述搜索問題：初始形狀：包括棋盤的局面和確定該哪個玩家出招后繼函數(shù)：前往move 招數(shù),state形狀對的列表，其中每一對表示一個合法的招數(shù)及其結(jié)果形狀終止函數(shù)：測試博弈能否終了