第五章搜索策略

1、第五章 搜索策略 5.1 概述 5.2 狀態(tài)空間搜索 5.3 與或樹搜索w2 搜索分為盲目搜索和啟發(fā)式搜索。 盲目搜索是按照預定的控制策略進行搜索，在搜索過程中獲得的中間信息不用來改進控制策略。 啟發(fā)式搜索是在搜索中加入了與問題有關的啟發(fā)性信息，用以指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。w3w問題求解過程可以看作一個搜索過程。狀態(tài)空間表示法是用來表示問題及其搜索過程的一種方法。它是人工智能中最基本的一種形式化方法。w狀態(tài)空間用“狀態(tài)”和“算符”來表示問題。狀態(tài)狀態(tài)用以描述問題求解過程中不同時刻的狀況，是一個數(shù)據(jù)結構，一般用一組變量的有序組合表示：SK=(Sk0,Sk1

2、,)當每一個分量的值確定時，就得到了一個具體的狀態(tài)。算符引起狀態(tài)中某些分量發(fā)生變化，從而使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。在產(chǎn)生式系統(tǒng)中，一條產(chǎn)生式規(guī)則就是一個算符。狀態(tài)空間由問題的全部狀態(tài)及一切可用算符所構成的集合稱為問題的狀態(tài)空間，一般用一個三元組表示：(S,F,G)其中S是問題所有初始狀態(tài)的集合；F是算符的集合；G是目標狀態(tài)的集合。狀態(tài)空間的圖示形式稱為狀態(tài)空間圖。w4設用SK=(Sk0,Sk1)表示問題的狀態(tài)，SK0表示金片A所在的柱號，Sk1表示金片B所在的柱號，全部可能的狀態(tài)有九種：S0=(1,1), S1=(1,2) , S2=(1,3)S3=(2,1), S4=(2

3、,2) , S5=(2,3)S6=(3,1), S7=(3,2) , S8=(3,3)問題的初始狀態(tài)集合為S=S0,目標狀態(tài)集合為G=S4,S8。算符分別用A(i,j)及B(i,j)。A(i,j)表示把A金片從第i號柱移到第j號柱。B(i,j)與之同理。算符共有12個。在狀態(tài)空間圖中，從初始節(jié)點(1,1)到目標節(jié)點(2,2)或(3,3)的任何一條通路都是問題的一個解。其中最短的路徑長度是3，它由3個算符組成。例如:A(1,3),B(1,2),A(3,2)w51,12,13,12,33,23,31,31,22,2A(1,3)B(1,2)A(3,2) 用狀態(tài)空間方法表示問題，首先必須定義狀態(tài)的描述

4、形式，把問題的一切狀態(tài)都表示出來。其次要定義一組算符。 問題的求解過程是一個不斷把算符作用于狀態(tài)的過程。如果在使用某個算符后得到的新狀態(tài)是目標狀態(tài)，就得到了問題的一個解。這個解是從初始狀態(tài)到目標狀態(tài)所用算符構成的序列。 算符的一次使用，就使問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。使用算符最少的解或者總代價最少的解稱為最優(yōu)解。 對任何一個狀態(tài)，可使用的算符可能不止一個。這樣由一個狀態(tài)所生成的后繼狀態(tài)就可能有多個。此時首先對哪一個狀態(tài)進行操作，就取決于搜索策略。w6 與或樹是用于表示問題及其求解過程的又一種形式化方法，通常用于表示比較復雜問題的求解。 對于一個復雜問題，直接求解往往比較困難。此時可通過下述

5、方法進行簡化： 分解把一個復雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分解。重復此過程，直到不需要或者不能再分解為止。如此形成“與”樹。 等價變換利用同構或同態(tài)的等價變換，把原問題變換為若干個較為容易求解的新問題。如此形成“或”樹。w7PP1P2P3與樹PP1P2P3或樹w8 本原問題 不能再分解或變換，而且直接可解的子問題。 端節(jié)點與終止節(jié)點 在與/或樹中，沒有子節(jié)點的節(jié)點統(tǒng)稱為端節(jié)點；本原問題所對應的節(jié)點稱為終止節(jié)點。 可解節(jié)點 在與/或樹中，滿足下列條件之一者，稱為可解節(jié)點： 它是一個終止節(jié)點； 它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點； 它是一個“與”節(jié)點，且其

6、子節(jié)點全部是可解節(jié)點。 不可解節(jié)點 關于可解節(jié)點的三個條件全部不滿足的節(jié)點w9解樹由可解節(jié)點所構成，并且由這些可解節(jié)點可推出初始節(jié)點為可解節(jié)點的子樹稱為解樹。w10(1,1,1)=(3,3,3)(1,1,1)=(1,2,2)(1,2,2)=(3,2,2)(3,2,2)=(3,3,3)(1,1,1)=(1,1,3)(1,1,3)=(1,2,3)(1,2,3)=(1,2,2)(3,2,2)=(3,2,1)(3,2,1)=(3,3,1)(3,3,1)=(3,3,3)w11狀態(tài)空間搜索策略盲目搜索啟發(fā)式搜索廣度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的深度優(yōu)先搜索局部擇優(yōu)搜索全局

7、擇優(yōu)搜索A*算法w12w盲目搜索的特點：w搜索按規(guī)定的路線進行，不使用與問題有關的啟發(fā)性信息；w適用于其狀態(tài)空間圖是樹狀結構的一類問題。w啟發(fā)式搜索要使用與問題有關的啟發(fā)性信息，并以這些啟發(fā)性信息指導搜索過程，可以高效地求解結構復雜的問題。廣度優(yōu)先搜索按照“先擴展出的節(jié)點先被考察”的原則進行搜索；深度優(yōu)先搜索按照“后擴展出的節(jié)點先被考察”的原則進行搜索；有界深度優(yōu)先搜索的原則與深度優(yōu)先搜索相同，但是它規(guī)定了深度限界，使搜索不得無限制地向縱深方向發(fā)展；代價樹的廣度優(yōu)先搜索按照“哪個節(jié)點到根節(jié)點的代價小就先考察哪個節(jié)點”的原則進行搜索；代價樹的深度優(yōu)先搜索按照“當前節(jié)點的哪個子節(jié)點到其父節(jié)點的代價

8、小就先考察哪個子節(jié)點”的原則進行搜索；局部擇優(yōu)搜索按照“當前節(jié)點的哪個子節(jié)點到目標節(jié)點的估計代價小就先考察哪個子節(jié)點”的原則進行搜索；全局擇優(yōu)搜索按照“哪個節(jié)點到目標節(jié)點的估計代價小就先考察哪個節(jié)點”的原則進行搜索；w13OPEN表和CLOSE表OPEN表用于存放剛生成的節(jié)點。對于不同的搜索策略，節(jié)點在OPEN表中的排列順序是不同的。CLOSE表用于存放將要擴展或者已經(jīng)擴展的節(jié)點。 OPEN表CLOSE表w14狀態(tài)節(jié)點父節(jié)點編號 狀態(tài)節(jié)點 父節(jié)點把初始節(jié)點S0放入OPEN表，并建立目前只包含S0的圖，記為G；檢查OPEN表是否為空，若為空則問題無解，退出；把OPEN表的第一個節(jié)點取出放入CLO

9、SE表，并計該節(jié)點為n；考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出；擴展節(jié)點n，生成一組子節(jié)點。把其中不是節(jié)點n先輩的那些子節(jié)點記做集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中；針對M中子節(jié)點的不同情況，分別進行如下處理： 對于那些未曾在G中出現(xiàn)過的M成員設置一個指向父節(jié)點（即節(jié)點n）的指針，并把它們放入OPEN表； 對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點的指針； 對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針； 按某種搜索策略對OPEN表中的節(jié)點進行排序； 轉第2步。w15上述是一個通用過程，各種搜索策略

10、的主要區(qū)別是對OPEN表中節(jié)點排序的準則不同。一個節(jié)點經(jīng)一個算符操作后一般只生成一個子節(jié)點。但適用于一個節(jié)點的算符可能有多個，此時就會生成一組子節(jié)點。這些子節(jié)點中可能有些是當前擴展節(jié)點的父節(jié)點、祖父節(jié)點等，此時不能把這些先輩節(jié)點作為當前擴展節(jié)點的子節(jié)點。一個新生成的節(jié)點，它可能是第一次被生成的節(jié)點，也可能是先前已作為其它節(jié)點的后繼節(jié)點被生成過，當前又作為另一個節(jié)點的后繼節(jié)點被再次生成。此時，它究竟應作為哪個節(jié)點的不后繼節(jié)點？一般由原始節(jié)點到該節(jié)點的代價來決定，代價小的相應節(jié)點就作為父節(jié)點。在搜索過程中，一旦某個被考察的節(jié)點是目標節(jié)點就得到了一個解。該解是由從初始節(jié)點到該目標節(jié)點路徑上的算符構成

11、。如果在搜索中一直找不到目標節(jié)點，而且OPEN表中不再有可供擴展的節(jié)點，則搜索失敗。w16 基本思想：從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考察它是否為目標節(jié)點。在第n層的節(jié)點沒有全部擴展并考察之前，不對第n1層的節(jié)點進行擴展。 OPEN表中節(jié)點總是按進入的先后順序排列，先進入的節(jié)點排在前面，后進入的排在后面。w17 把初始節(jié)點S0放入OPEN表。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉第2步。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一

12、個子節(jié)點都配置指向父節(jié)點的指針，然后轉第2步。w18w19 優(yōu)點：只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。 缺點：廣度優(yōu)先搜索盲目性較大，當目標節(jié)點距初始節(jié)點較遠時將會產(chǎn)生許多無用節(jié)點，搜索效率低。w20 基本思想：從初始節(jié)點S0開始，在其子節(jié)點中選擇一個節(jié)點進行考察。若不是目標節(jié)點，則再在該子節(jié)點的子節(jié)點中選擇一個節(jié)點進行考察，一直如此向下搜索。當達到某個子節(jié)點，且該子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。 深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到

13、OPEN表的首部。w21 把初始節(jié)點S0放入OPEN表。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉第2步。 擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第2步。w222 8 31 47 6 52 8 3 1 47 6 52 8 31 67 5 42 31 8 47 6 5 2 8 31 4 7 6 52 8 1 6 3 7 5 42 81 6 37 5 42 8 31 6 47 5 2 8 3 1 6 47

14、6 2 8 3 1 6 47 5 2 8 31 6 7 5 4S01234.5w23 在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，它也不一定能求得解。 用深度優(yōu)先求得的解，不一定是路徑最短的解。w24w基本思想：對深度優(yōu)先搜索引入搜索深度的界限（設為dm），當搜索深度達到了深度界限，而尚未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。w搜索過程：把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0。如果OPEN

15、表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n的深度d(節(jié)點n)=dm，則轉第2步。若節(jié)點n不可擴展，則轉第2步。擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第2步。w25 如果問題有解，且其路徑長度dm，則上述搜索過程一定能求得解。但是，若解的路徑長度dm,則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。 要恰當?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。w26先任意設定一個較小的數(shù)作為dm，然

16、后進行上述的有界深度優(yōu)先搜索，當搜索達到了指定的深度界限dm仍未發(fā)現(xiàn)目標節(jié)點，并且CLOSE表中仍有待擴展節(jié)點時，就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。為了找到最優(yōu)解，可增設一個表R，每找到遠程目標節(jié)點Sg后，就把它放入到R的前面，并令dm等于該目標節(jié)點所對應的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以后求得的解一定是最優(yōu)解。w27設深度界限dm4w282 3 1 8 4 7 6 5 2 3 41 8 7 6 5221 2 38 47 6 51 2

17、 37 8 46 5 2 31 8 47 6 51 2 3 8 47 6 52 3 41 87 6 52 3 41 8 57 62 8 3 1 47 6 52 31 8 47 6 52 81 4 37 6 52 4 81 37 6 52 8 31 4 57 62 8 31 57 4 68 32 6 41 7 52 8 36 41 7 52 8 31 67 5 42 81 6 37 5 62 81 4 37 6 52 8 1 4 3 7 6 52 8 31 4 57 6 2 8 3 1 4 57 6 2 8 36 4 1 7 5 2 8 31 6 7 5 4 2 8 3 1 6 47 6 2 8

18、 3 1 6 47 5 2 8 31 4 7 6 52 8 31 6 47 52 8 31 47 6 5S0123Sg789141516232425264561011121317181920212728 盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點較多，搜索空間較大，效率不高。 啟發(fā)式搜索要用到問題自身的某些特性信息，以指導搜索朝著最有希望的方向前進。由于這種搜索針對性較強，因而原則上只需要搜索問題的部分狀態(tài)空間，效率較高。w29 可用于指導搜索過程，且與具體問題求解有關的控制性信息稱為啟發(fā)性信息。 用于估價節(jié)點重要性的函數(shù)稱為估價函數(shù)。其一般形式為：f(x) = g(x)+h(x) 其中g(x)

19、為從初始節(jié)點S0到節(jié)點x已經(jīng)實際付出的代價；h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的估計代價，它體現(xiàn)了問題的啟發(fā)性信息，其形式要根據(jù)問題的特性確定。例如它可以是節(jié)點x到目標節(jié)點的距離，或者節(jié)點x處于最優(yōu)路徑上的概率等等。h(x)稱為啟發(fā)函數(shù)。 g(x)指出了搜索的橫向趨勢。它有利于搜索的完備性，但影響搜索的效率。如果我們只關心到達目標節(jié)點的路徑，并且希望有較高的搜索效率，則g(x)可以忽略，但此時會影響搜索的完備性。w30設有如下結構的移動牌游戲：該游戲規(guī)則：當一個牌移入相鄰的空位置時，費用為一個單位。一個牌至多可跳過兩個牌進入空位置，其費用等于跳過的牌數(shù)加1。要求把所有的B都移至W的右邊

20、，請設計估價函數(shù)中的h(x)。解：根據(jù)要求可知，W左邊的B越少越接近目標，因此可用W左邊B的個數(shù)作為h(x),即h(x)=3(每個W左邊B個數(shù)的總和)這里乘以系數(shù)3是為了擴大h(x)在f(x)中的比重。w31BBBWWWE基本思想：當一個節(jié)點被擴展以后，按f(x)對每一個子節(jié)點計算估價值，并選擇最小者作為下一個要考察的節(jié)點。搜索過程：把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表?？疾旃?jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉第2步。擴展節(jié)點n，用估價函數(shù)f(x)計

21、算每個子節(jié)點的估價值，并按估價值從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第2步。w深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索以及局部擇優(yōu)搜索都是以子節(jié)點作為考察范圍的。但是前二者可以看作局部擇優(yōu)搜索的特例。w32基本思想：在代價樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點中選擇一個代價最小的節(jié)點送入CLOSE表進行考察。而代價樹的深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選一個代價最小的節(jié)點送入CLOSE表進行考察。搜索過程：把初始節(jié)點S0放入OPEN表，令g(S0)=0。如果OPEN表為空，則問題無解，退出。把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CL

22、OSE表。考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。若節(jié)點n不可擴展，則轉第2步。擴展節(jié)點n，將其子節(jié)點按代價從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉第2步。1.代價樹的深度有限搜索是不完備的。w33w34基本思想：每當要選擇一個節(jié)點進行考察時，局部擇優(yōu)搜索只是從剛生成的子節(jié)點中進行選擇，選擇的范圍比較狹窄。全局擇優(yōu)搜索每次總是從OPEN表的全體節(jié)點中選擇一個估價值最小的節(jié)點。搜索過程：w把初始節(jié)點S0放入OPEN表，計算f(S0)。w如果OPEN表為空，則問題無解，退出。w把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。w

23、考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。w若節(jié)點n不可擴展，則轉第2步。w擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉第2步。w廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索以及全局擇優(yōu)搜索都是以當前所有節(jié)點作為考察范圍的。但是前二者可以看作全局擇優(yōu)搜索的特例。設估價函數(shù)為f(x)=d(x)+h(x)其中，d(x)表示節(jié)點x的深度，h(x)表示節(jié)點x的格局與目標節(jié)點格局不相同的牌數(shù)。w351 2 38 47 6 51 2 37 8 46 5 2

24、 31 8 47 6 51 2 3 8 47 6 52 8 3 1 47 6 52 31 8 47 6 5 2 8 31 4 7 6 52 8 31 6 47 52 8 31 47 6 5S035Sg556748 3 2 1 4 7 6 5 2 8 3 7 1 46 5672 3 1 8 4 7 6 5765 邊上標有代價(或費用)的樹稱為代價樹。 用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價則有：g(x2)=g(x1)+c(x1,x2) 基本思想：每次從OPEN表中選擇節(jié)點往CLOSE表傳送時，總是選擇其代價最小的節(jié)點。也就是說，OPEN表

25、中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置。 如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。w36 把初始節(jié)點S0放入OPEN表，令g(S0)=0。 如果OPEN表為空，則問題無解，退出。 把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSE表。 考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。 若節(jié)點n不可擴展，則轉第2步。 擴展節(jié)點n，將其子節(jié)點放入OPEN表中，并為每一個子節(jié)點都配置指向父節(jié)點的指針。計算各子節(jié)點的代價，并按各節(jié)點的代價對OPEN表中的全部節(jié)點進行排序(按從

26、小到大的順序)，然后轉第2步。w37ABCDE432345交通圖w38AC1B1D1E2B2E4D2E1C2E33423454523交通圖的代價樹如果使一般搜索過程滿足如下限制，則它就稱為A*算法：1、把OPEN表中的節(jié)點按估價函數(shù)f(x)=g(x)+h(x)的值從小至大進行排序（一般搜索過程的第7步）。2、g(x)是對g*(x)的估計，g(x)0。3、h(x)是h*(x)的下界，即對所有的x均有：h(x)h*(x)其中，g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價；h*(x)是從節(jié)點x到目標節(jié)點的最小代價，若有多個目標節(jié)點，則為其中最小的一個。w39 在A*算法中，g(x)實際上就是從初始節(jié)

27、點S0到節(jié)點x的路徑代價，恒有g(x)g*(x)。而且在算法執(zhí)行過程中隨著更多搜索信息的獲得，g(x)的值呈下降的趨勢。例如： H(x)的確定依賴于具體問題領域的啟發(fā)性信息，其中h(x)h*(x)的限制十分重要，它保證A*算法能找到最優(yōu)解。w40S0X1X2X33732可納性對于可解狀態(tài)空間圖(即從初始節(jié)點到目標節(jié)點有路徑存在)來說，如果一個搜索算法能在有限步那終止，并且能找到最優(yōu)解，則稱該搜索算法是可納的。A*算法是可納的。A*算法的最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x)，在滿足h(x)h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它攜帶的啟發(fā)性信息越多，搜索時

28、擴展的節(jié)點數(shù)越少，搜索的效率越高。h(x)的單調性限制在A*算法中，每當要擴展一個節(jié)點時都要先檢查其子節(jié)點是否已在OPEN表或CLOSE表中，有時還要調整指向父節(jié)點的指針，這就增加了搜索的代價。如果對啟發(fā)函數(shù)h(x)加上單調性限制，就可減少檢查及調整的工作量，從而減少搜索代價。w41所謂單調性限制是指h(x)滿足如下兩個條件：1、h(Sg)=0;2、設xj是節(jié)點xi的任意子節(jié)點，則有h(xi)-h(xj)c(xi,xj)，即h(xi)h(xj)+c(xi,xj)其中，Sg是目標節(jié)點；c(xi,xj)是節(jié)點xi到其子節(jié)點xj的代價?？梢宰C明，當A*算法的啟發(fā)函數(shù)h(x)滿足單調性限制時，可得到如

29、下兩個結論：1、若A*算法選擇節(jié)點xn進行擴展，則g(xn)=g*(xn)2、由A*算法所擴展的節(jié)點序列其f值是非遞減的。這兩個結論都是在h(x)滿足單調性限制時才成立的。否則，它們不一定成立。w425.3.1 與或樹的一般搜索過程5.3.2 與或樹的廣度優(yōu)先搜索5.3.3 與或樹的深度優(yōu)先搜索5.3.4 與或樹的有序搜索5.3.5 博弈樹的啟發(fā)式搜索5.3.6 剪枝技術w43 完備性 對于一類可解的問題和一個搜索過程，如果運用該搜索過程一定能求得該類問題的解，則稱該搜索過程為完備的，否則為不完備的。 廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索、改進后的有界深度優(yōu)先搜索以及A*算法都是完備的搜索過程，

30、其它搜索過程都是不完備的。w44一個搜索過程的搜索效率不僅取決于過程自身的啟發(fā)能力，而且還與被解問題的有關屬性等多種因素有關。目前雖已有多種定義和計算搜索效率的方法，但都有一定的局限性。外顯率外顯率定義為P=L/T其中，L為從初始節(jié)點到目標節(jié)點的路徑長度；T為整個搜索過程中所生成的節(jié)點總數(shù)。外顯率反映了搜索過程中從初始節(jié)點向目標節(jié)點前進時搜索區(qū)域的寬度。當L=T時，P=1，表示搜索過程中每次只生成一個節(jié)點，它恰好是解路徑上的節(jié)點，搜索效率最高。P越小表示搜索時產(chǎn)生的無用節(jié)點愈多，搜索效率愈低。w45 有效分枝因數(shù)B定義為B+B2+BL=T其中，B是有效分枝因數(shù)，它表示在整個搜索過程中每個有效節(jié)

31、點平均生成的子節(jié)點數(shù)目；L為路徑長度；T為節(jié)點總數(shù)。 當B1時，L=T，此時所生成的節(jié)點數(shù)最少，搜索效率最高。 不難證明，有效分枝因數(shù)與外顯率之間由如下關系：P=(L(B-1)/(B(BL-1)T=B(BL-1)/(B-1)由此可以看出，當B一定時，L愈大則P愈??；當L一定時，B愈大則P愈??；對同一個L而言，B愈大則T愈大。w4647 與與/ /或樹的搜索策略就是確定節(jié)點是否為可解或不可解節(jié)點?；驑涞乃阉鞑呗跃褪谴_定節(jié)點是否為可解或不可解節(jié)點。在整個確定過程中，會循環(huán)用到兩個過程，分別為：在整個確定過程中，會循環(huán)用到兩個過程，分別為：可解標示過程：可解標示過程： 由可解子節(jié)點來確定父節(jié)點、祖父

32、節(jié)點等為可解節(jié)點由可解子節(jié)點來確定父節(jié)點、祖父節(jié)點等為可解節(jié)點的回溯向上過程的回溯向上過程不可解標示過程：不可解標示過程： 由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可由不可解子節(jié)點來確定其父節(jié)點、祖父節(jié)點等為不可解節(jié)點的回溯向上過程解節(jié)點的回溯向上過程這兩個過程都是自下而上進行的，即由子節(jié)點的可解性這兩個過程都是自下而上進行的，即由子節(jié)點的可解性確定父確定父( (或祖先或祖先) )節(jié)點的可解性節(jié)點的可解性5.3.1 5.3.1 與與/ /或樹的搜索策略或樹的搜索策略48與與/ /或樹的搜索策略或樹的搜索策略把原始問題作為初始節(jié)點把原始問題作為初始節(jié)點S S0 0，并把它作為當前節(jié)點，并把它

33、作為當前節(jié)點應用分解或等價變換算符對當前節(jié)點進行擴展。應用分解或等價變換算符對當前節(jié)點進行擴展。為每個子節(jié)點設置指向父節(jié)點的指針。為每個子節(jié)點設置指向父節(jié)點的指針。選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第選擇合適的子節(jié)點作為當前節(jié)點，反復執(zhí)行第2 2）步和第步和第3 3）步，在此期間要多次調用）步，在此期間要多次調用可解標示過程可解標示過程和和不不可解標示過程可解標示過程，直到初始節(jié)點被標示為可解節(jié)點或不，直到初始節(jié)點被標示為可解節(jié)點或不可解節(jié)點為止?？山夤?jié)點為止。49與與/ /或樹搜索的兩個特性：或樹搜索的兩個特性：(1)(1)如果已確定某個節(jié)點是可解節(jié)點，則刪去其不可如果已確定某個節(jié)點是可

34、解節(jié)點，則刪去其不可解的后裔節(jié)點解的后裔節(jié)點(2)(2)如果已確定某個節(jié)點是不可解節(jié)點，刪去其全部如果已確定某個節(jié)點是不可解節(jié)點，刪去其全部后裔節(jié)點，保留該結點后裔節(jié)點，保留該結點505.3.2 5.3.2 與與/ /或樹的寬度優(yōu)先搜索或樹的寬度優(yōu)先搜索搜索過程：搜索過程： 與狀態(tài)空間的寬度優(yōu)先搜索類似，按照與狀態(tài)空間的寬度優(yōu)先搜索類似，按照“先產(chǎn)生先產(chǎn)生的節(jié)點先擴展的節(jié)點先擴展”的原則進行搜索，在整個搜索過程的原則進行搜索，在整個搜索過程中多次調用可解標示過程和不可解標示過程。中多次調用可解標示過程和不可解標示過程。51例例設有如圖所示的與設有如圖所示的與/ /或樹，節(jié)點按圖中所標注的順或樹

35、，節(jié)點按圖中所標注的順序號進行擴展。其中標有序號進行擴展。其中標有t t1 1、 t t2 2、 t t3 3、 t t4 4的節(jié)點均為的節(jié)點均為終止節(jié)點終止節(jié)點，A A和和B B為不可解的為不可解的端節(jié)點端節(jié)點。1 12 23 34 4t1t15 5B BA At2t2t4t4t5t5525.3.3 5.3.3 與與/ /或樹的有界深度優(yōu)先搜索或樹的有界深度優(yōu)先搜索其搜索過程：其搜索過程： 與與/ /或樹的深度優(yōu)先搜索過程和與或樹的深度優(yōu)先搜索過程和與/ /或樹的寬度優(yōu)或樹的寬度優(yōu)先搜索過程基本相同，只是將擴展節(jié)點的子節(jié)點放入先搜索過程基本相同，只是將擴展節(jié)點的子節(jié)點放入OPENOPEN表的

36、表的首部首部，并為每個子節(jié)點配置指向父節(jié)點的，并為每個子節(jié)點配置指向父節(jié)點的指針。指針。 與與/ /或樹的有界深度優(yōu)先搜索同樣也規(guī)定一個深度或樹的有界深度優(yōu)先搜索同樣也規(guī)定一個深度界限，使搜索在規(guī)定的范圍內進行界限，使搜索在規(guī)定的范圍內進行535.3.4 5.3.4 與與/ /或樹的有序搜索或樹的有序搜索 與與/ /或樹的有序搜索可用來求取代價最小的解樹，是一種啟或樹的有序搜索可用來求取代價最小的解樹，是一種啟發(fā)式搜索策略發(fā)式搜索策略 1. 1. 解樹的代價解樹的代價 可通過計算樹中節(jié)點的代價得到。可通過計算樹中節(jié)點的代價得到。 設設c(x,y)c(x,y)表示節(jié)點表示節(jié)點x x到其子節(jié)點到其

37、子節(jié)點y y的代價，計算節(jié)點的代價，計算節(jié)點x x代價的方代價的方法如下：法如下：1 1）如果）如果x x是終止節(jié)點，則定義節(jié)點是終止節(jié)點，則定義節(jié)點x x的代價的代價h(x)=0;h(x)=0;2 2）如果）如果x x是是“或或”節(jié)點，節(jié)點，y y1 1, y, y2 2, , y, yn n是它的子節(jié)點，則節(jié)點是它的子節(jié)點，則節(jié)點x x的代價為的代價為 h(x)=minc(x, yh(x)=minc(x, yi i)+h(y)+h(yi i) ) 1in1in541. 1. 解樹的代價解樹的代價3 3）如果）如果x x是是“與與”節(jié)點，則節(jié)點節(jié)點，則節(jié)點x x的代價有兩種計算的代價有兩種計

38、算方法：和代價法與最大代價法。方法：和代價法與最大代價法。若按和代價法計算，則有：若按和代價法計算，則有： n n h(x)= h(x)= ( (c(x, yc(x, yi i)+h(y)+h(yi i) ) i=1i=1若按最大代價法計算，則有：若按最大代價法計算，則有： h(x)=maxc(x, yh(x)=maxc(x, yi i)+h(y)+h(yi i) ) 1in1in4 4）如果）如果x x是不可擴展，且又不是終止節(jié)點，則定義是不可擴展，且又不是終止節(jié)點，則定義h(x)=h(x)= 。55例例 圖為一棵與圖為一棵與/ /或樹，其中包括兩棵解樹，一棵解或樹，其中包括兩棵解樹，一棵解

39、樹由樹由S S0 0，A A，t t1 1和和t t2 2組成；另一棵解樹由組成；另一棵解樹由S S0 0，B B，D D，G G，t t4 4和和t t5 5組成。在此與組成。在此與/ /或樹中或樹中, t, t1 1、t t2 2 、t t3 3 、t t4 4 、t t5 5 為終止節(jié)點；為終止節(jié)點；E E、F F是端節(jié)點，其代價為是端節(jié)點，其代價為 ；邊上的；邊上的數(shù)字是邊的代價。數(shù)字是邊的代價。56S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0左邊的解樹左邊的解樹右邊的解樹右邊的解樹57 1) 1)若按

40、和代價計算，右解樹是最優(yōu)解樹，若按和代價計算，右解樹是最優(yōu)解樹，其代價為其代價為8 8； 2)2)若按最大代價計算，右解樹仍然是最優(yōu)解樹，若按最大代價計算，右解樹仍然是最優(yōu)解樹，其代價為其代價為7 7。 有時用不同的計算代價方法得到的最優(yōu)解樹不相同。有時用不同的計算代價方法得到的最優(yōu)解樹不相同。S S0 0A At1t1t2t26 65 52 2B BD DG Gt4t4t5t52 22 21 11 12 2S S0 0由左邊的解樹可得：由左邊的解樹可得： 按和代價：按和代價： h(A)=11, h(Sh(A)=11, h(S0 0)=13)=13 按最大代價：按最大代價： h(A)=6, h

41、(Sh(A)=6, h(S0 0)=8)=8由右邊的解樹可得：由右邊的解樹可得： 按和代價：按和代價： h(G)=3, h(D)=4, h(B)=6, h(Sh(G)=3, h(D)=4, h(B)=6, h(S0 0)=8)=8按最大代價：按最大代價： h(G)=2, h(D)=3, h(B)=5, h(Sh(G)=2, h(D)=3, h(B)=5, h(S0 0)=7)=7582. 2. 希望樹希望樹定義：定義： 每次選擇欲擴展的節(jié)點時希望成為最優(yōu)解樹一部分的節(jié)點每次選擇欲擴展的節(jié)點時希望成為最優(yōu)解樹一部分的節(jié)點進行擴展。由這些節(jié)點及其先輩節(jié)點所構成的與進行擴展。由這些節(jié)點及其先輩節(jié)點所

42、構成的與/ /或樹或樹 ，稱為，稱為希望樹希望樹1 1）初始節(jié)點）初始節(jié)點S S0 0在希望樹在希望樹T T中。中。2 2）如果節(jié)點）如果節(jié)點x x在希望樹在希望樹T T中，則一定有：中，則一定有：如果如果x x是具有子節(jié)點是具有子節(jié)點y y1 1,y,y2 2, ,y,yn n的的“或或”節(jié)點節(jié)點, ,則具有則具有: : minc(x, y minc(x, yi i)+h(y)+h(yi i) 1in) 1in值的那個子節(jié)點值的那個子節(jié)點y yi i也應在也應在T T中。中。如果如果x x是是“與與”節(jié)點，則它的全部子節(jié)點都應在節(jié)點，則它的全部子節(jié)點都應在T T中。中。59 博弈問題（或對抗

43、性搜索）為什么可以用與博弈問題（或對抗性搜索）為什么可以用與/ /或圖表示呢？或圖表示呢？ 可以這樣來看待這個問題：可以這樣來看待這個問題： 當輪到我方走棋時，只需從若干個可以走的棋中，選擇當輪到我方走棋時，只需從若干個可以走的棋中，選擇一個棋走就可以了。從這個意義上說，若干個可以走的棋一個棋走就可以了。從這個意義上說，若干個可以走的棋是是“或或”的關系。而對于輪到對方走棋時，對于我方來說，的關系。而對于輪到對方走棋時，對于我方來說，必須能夠應付對手的每一種走棋。這就相當于這些棋與必須能夠應付對手的每一種走棋。這就相當于這些棋與/ /或或的關系。因此，博弈問題可以看成是一個與的關系。因此，博弈

44、問題可以看成是一個與/ /或圖，但是與或圖，但是與一般的與一般的與/ /或圖并不一樣，是一種特殊的與或圖并不一樣，是一種特殊的與/ /或圖或圖5.3.5 5.3.5 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索60 描述博弈過程的與描述博弈過程的與/ /或樹或樹1 1）博弈的初始格局是初始節(jié)點）博弈的初始格局是初始節(jié)點2 2）在博弈樹中，）在博弈樹中，“或或”節(jié)點和節(jié)點和“與與”節(jié)點是逐層交節(jié)點是逐層交替出現(xiàn)的。自己一方擴展的節(jié)點之間是替出現(xiàn)的。自己一方擴展的節(jié)點之間是“或或”關系，關系，對方擴展的節(jié)點之間是對方擴展的節(jié)點之間是“與與”關系。雙方輪流地擴展關系。雙方輪流地擴展節(jié)點節(jié)點3 3）所有能使自

45、己一方獲勝的終局都是本原問題，相）所有能使自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解節(jié)點，所有使對方獲勝的終局都是不應的節(jié)點是可解節(jié)點，所有使對方獲勝的終局都是不可解節(jié)點可解節(jié)點612. 2. 極大極小分析法極大極小分析法621 1）設博弈的雙方中一方為）設博弈的雙方中一方為A A，另一方為，另一方為B B。極大極小分析法是為其中的一。極大極小分析法是為其中的一方（例如方（例如A A）尋找一個最優(yōu)行動方案的方法。）尋找一個最優(yōu)行動方案的方法。2 2）為了找到當前的最優(yōu)行動方案，需要對各個方案可能產(chǎn)生的后果進行）為了找到當前的最優(yōu)行動方案，需要對各個方案可能產(chǎn)生的后果進行比較。具體地說，就是要考慮每一個方案