智能搜索技術

1

搜索是人工智能中的一個基本問題，并與推理密切相關，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。

4.1搜索概述

4.1.1搜索的含義4.1.2狀態(tài)空間問題求解方法4.1.3問題歸約求解方法4.1.4進化搜索法概述4.2狀態(tài)空間的啟發(fā)式搜索4.3與/或樹的啟發(fā)式搜索4.4博弈樹的啟發(fā)式搜索4.5遺傳算法第4章智能搜索技術2基于搜索空間類型A算法A*算法基于隨機算法演化機制遺傳算法種群尋優(yōu)蟻群算法粒群算法蒙特卡羅算法其它方法爬山搜索算法模擬退火算法4.1.1搜索的含義搜索：依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索智能搜索：是指可以利用搜索過程得到的中間信息來引導搜索項最優(yōu)方向發(fā)展的算法。狀態(tài)空間與/或樹博弈樹問題歸約法極大/極小算法α-β剪枝統(tǒng)計模型免疫算法免疫優(yōu)化34.1.2狀態(tài)空間問題求解方法1.狀態(tài)空間問題表示狀態(tài)(State)

是表示問題求解過程中每一步問題狀況的數(shù)據(jù)結構，它可形式地表示為：

Sk={Sk0,Sk1,…}當對每一個分量都給以確定的值時，就得到了一個具體的狀態(tài)。操作(Operator)

也稱為算符，它是把問題從一種狀態(tài)變換為另一種狀態(tài)的手段。操作可以是一個機械步驟，一個運算，一條規(guī)則或一個過程。操作可理解為狀態(tài)集合上的一個函數(shù)，它描述了狀態(tài)之間的關系。狀態(tài)空間(Statespace)

用來描述一個問題的全部狀態(tài)以及這些狀態(tài)之間的相互關系。常用一個三元組表示為：

(S,F,G)其中，S為問題的所有初始狀態(tài)集合；F為操作的集合；G為目標狀態(tài)的集合。狀態(tài)空間也可用一個賦值的有向圖來表示，該有向圖稱為狀態(tài)空間圖。在狀態(tài)空間圖中，節(jié)點表示問題的狀態(tài)，有向邊表示操作。4狀態(tài)空間法求解問題的基本過程：首先，為問題選擇適當?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后，從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達到目標狀態(tài)為止；最后，由初始狀態(tài)到目標狀態(tài)所使用的算符序列就是該問題的一個解。

4.1.2狀態(tài)空間問題求解方法2.狀態(tài)空間問題求解5

例4.1二階梵塔問題

設有三根鋼針，它們的編號分別是1號、2號和3號。在初始情況下，1號鋼針上穿有A、B兩個金片，A比B小，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大的位于小的上面。

解：設用Sk=(SkA,SkB)表示問題的狀態(tài)，其中，SkA表示金片A所在的鋼針號，SkB表示金片B所在的鋼針號。全部可能的問題狀態(tài)共有以下9種：

S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(1/11)6

ABABAB123123123圖4.1二階梵塔問題的初始狀態(tài)和目標狀態(tài)初始狀態(tài)集合

S={S0}目標狀態(tài)集合

G={S4,S8}

初始狀態(tài)S0和目標狀態(tài)S4、S8如下圖

S0=(1,1)S4=(2,2)S8=(3,3)4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(2/11)7操作

Aij

表示把金片A從第i號鋼針移到j號鋼針上；

Bij

表示把金片B從第i號鋼針一到第j號鋼針上。共有12種操作，它們分別是：

A12A13A21A23A31A32

B12B13B21B23B31B32

根據(jù)上述9種可能的狀態(tài)和12種操作，可構成二階梵塔問題的狀態(tài)空間圖，如下圖所示。4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(3/11)8

從初始節(jié)點(1,1)到目標節(jié)點(2,2)及(3,3)的任何一條路徑都是問題的一個解。其中，最短的路徑長度是3，它由3個操作組成。例如，從(1,1)開始，通過使用操作A13、B12及A32，可到達(3,3)。(1,1)B12A13(2,1)(3,2)(2,3)(3,3)(1,3)(3,1)(1,2)(2,2)A32A12B13A234.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(4/11)圖4.2二階梵塔的狀態(tài)空間圖ABABABAB9

例4.2修道士(Missionaries)和野人(Cannibals)問題(簡稱M-C問題)。

設在河的一岸有3個野人、3個修道士和1條船，修道士想用這條船把所有的人運到河對岸，但受以下條件的約束：第一，修道士和野人都會劃船，但每次船上至多可載2個人；第二，在河的任一岸，如果野人數(shù)目超過修道士數(shù)，修道士會被野人吃掉。如果野人會服從任何一次過河安排，請規(guī)劃一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的安全過河計劃。

解：先選取描述問題狀態(tài)的方法。這里，需要考慮兩岸的修道士人數(shù)和野人數(shù)，還需要考慮船在左岸還是在右岸，故可用如下三元組來表示狀態(tài)

S=(m,c,b)其中，m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)。而右岸的狀態(tài)可由下式確定：右岸修道士數(shù)m'=3-m

右岸野人數(shù)c'=3-c

右岸船數(shù)b'=1-b

在這種表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32種狀態(tài)。

4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(5/11)初始狀態(tài)目標狀態(tài)左岸右岸(3,3,1)(0,0,0)104.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(6/11)11有效狀態(tài)在32種狀中，除去不合法和修道士被野人吃掉的狀態(tài)，有效狀態(tài)只16種：

S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)過河操作過河操作是指用船把修道士或野人從河的左岸運到右岸，或從右岸運到左岸的動作。每個操作都應當滿足如下條件：第一，船上至少有一個人（m或c）操作，離開岸邊的m和c的減少數(shù)目應該等于到達岸邊的m和c的增加數(shù)目；第二，每次操作船上人數(shù)不得超過2個；第三，操作應保證不產(chǎn)生非法狀態(tài)。操作的結構條件：只有當其條件具備時才能使用動作：刻劃了應用此操作所產(chǎn)生的結果。

4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(7/11)12操作的表示

Lij

表示有i個修道士和j個野人，從左岸到右岸的操作

Rij

表示有i個修道士和j個野人，從右岸到左岸的操作操作集本問題有10種操作可供選擇，他們的集合稱為操作集，即

A={L01,L10,L11,L02,L20,R01,R10,R11,R02,R20}操作的例子下面以L01和R01為例來說明這些操作的條件和動作。操作符號條件動作

L01b=1,m=0或3,c≥1b=0,c=c-1R01b=0,m=0或3，c≤2b=1,c=c+1

4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(8/11)13abc

例4.3猴子摘香蕉問題。在討論謂詞邏輯知識表示時，我們曾提到過這一問題，現(xiàn)在用狀態(tài)空間法來解決這一問題。

解：問題的狀態(tài)可用4元組（w,x,y,z）表示。其中：

w

表示猴子的水平位置；

x

表示箱子的水平位置；

y

表示猴子是否在箱子上，當猴子在箱子上時，y取1；否則y取0；

z

表示猴子是否拿到香蕉，當拿到香蕉時z取1，否則z取0。4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(9/11)14所有可能的狀態(tài)

S0:(a,b,0,0)初始狀態(tài)

S1:(b,b,0,0)S2:(c,c,0,0)S3:(c,c,1,0)S4:(c,c,1,1)目標狀態(tài)允許的操作為

Goto(u)：猴子走到位置u，即

(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推著箱子到水平位置v，即

(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即

(x,x,0,0)→(x,x,1,0)Grasp；猴子拿到香蕉，即

(c,c,1,0)→(c,c,1,1)問題的狀態(tài)空間圖如下圖所示?？梢姡沙跏紶顟B(tài)到目標狀態(tài)的操作序列為：

{Goto(b),Pushbox(c),Climbbox,Grasp}4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(10/11)15猴子摘香蕉問題的狀態(tài)空間圖(a,b,0,0)(b,b,0,0)(c,c,0,0)(b,b,1,0)(c,c,1,0)(a,a,0,0)(c,c,1,1)Goto(b)Pushbox(c)Grasp初始狀態(tài)圖4.3猴子摘香蕉問題的狀態(tài)空間圖Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)4.1.2狀態(tài)空間問題求解方法3.狀態(tài)空間的例子(11/11)Goto(b)目標狀態(tài)16基本思想當一問題較復雜時，可通過分解或變換，將其轉化為一系列較簡單的子問題，然后通過對這些子問題的求解來實現(xiàn)對原問題的求解。分解如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當所有子問題Pi都有解時原問題P才有解，任何一個子問題Pi無解都會導致原問題P無解，則稱此種歸約為問題的分解。即分解所得到的子問題的“與”與原問題P等價。等價變換如果一個問題P可以歸約為一組子問題P1,P2,…,Pn，并且子問題Pi中只要有一個有解則原問題P就有解，只有當所有子問題Pi都無解時原問題P才無解，稱此種歸約為問題的等價變換，簡稱變換。即變換所得到的子問題的“或”與原問題P等價。

4.1.3問題歸約求解方法1.問題的分解與等價變換17PP1P2P3P1P2P3PPP1P2P3P11P12P31P32P33(1)與樹分解(2)或樹等價變換(3)與/或樹4.1.3問題歸約求解方法2.問題歸約的與/或樹表示(1/3)與樹或樹與/或樹18(4)端節(jié)點與終止節(jié)點在與/或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應的節(jié)點稱為終止節(jié)點。可見，終止節(jié)點一定是端節(jié)點，但端節(jié)點卻不一定是終止節(jié)點。(5)可解節(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é)點，只要其子節(jié)點中有一個為不可解節(jié)點，則該與節(jié)點是不可解節(jié)點。4.1.3問題歸約求解方法2.問題歸約的與/或樹表示(2/3)19Pttt

(6)解樹由可解節(jié)點構成，并且由這些可解節(jié)點可以推出初始節(jié)點（它對應著原始問題）為可解節(jié)點的子樹為解樹。在解樹中一定包含初始節(jié)點。

例如，右圖給出的與或樹中，用紅線表示的子樹是一個解樹。在該圖中，節(jié)點P為原始問題節(jié)點，用t標出的節(jié)點是終止節(jié)點。根據(jù)可解節(jié)點的定義，很容易推出原始問題P為可解節(jié)點。問題歸約求解過程就實際上就是生成解樹，即證明原始節(jié)點是可解節(jié)點的過程。這一過程涉及到搜索的問題，對于與/或樹的搜索將在后面詳細討論。4.1.3問題歸約求解方法2.問題歸約的與/或樹表示(3/3)20

解：這個問題也可用狀態(tài)空間法來解，不過本例主要用它來說明如何用歸約法來解決問題。為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設用三元組

(i,j,k)表示問題在任一時刻的狀態(tài)，用“→”表示狀態(tài)的轉換。上述三元組中

i代表金片A所在的鋼針號

j代表金片B所在的鋼針號

k代表金片C所在的鋼針號1231234.1.3問題歸約求解方法3.問題歸約的例子(1/2)ABCABC

例4.4

三階梵塔問題。要求把1號鋼針上的3個金片全部移到3號鋼針上，如下圖所示。21

(1,1,1)→(3,3,3)

(1,1,1)→(2,2,1)(2,2,1)→(2,2,3)(2,2,3)→(3,3,3)(1,1,1)→(3,1,1)(3,1,1)→(3,2,1)(3,2,1)→(2,2,1)(2,2,3)→(1,2,3)(1,2,3)→(1,3,3)(1,3,3)→(3,3,3)

在該與/或樹中，有7個終止節(jié)點，它們分別對應著7個本原問題。如果把這些本原問題從左至右排列起來，即得到了原始問題的解：

(1,1,1)→(3,1,1)(3,1,1)→(3,2,1)(3,2,1)→(2,2,1)(2,2,1)→(2,2,3)(2,2,3)→(1,2,3)(1,2,3)→(1,3,3)(1,3,3)→(3,3,3)

利用問題歸約方法，原問題可分解為以下三個子問題：

(1)把金片A及B移到2號鋼針上的雙金片移動問題。即(1,1,1)→(2,2,1)(2)把金片C移到3號鋼針上的單金片移動問題。即(2,2,1)→(2,2,3)(3)把金片A及B移到3號鋼針的雙金片移動問題。即(2,2,3)→((3,3,3)其中，子問題(1)和(3)都是一個二階梵塔問題，它們都還可以再繼續(xù)進行分解；子問題(2)是本原問題，它已不需要再分解。三階梵塔問題的分解過程可用如下圖與/或樹來表示

4.1.3問題歸約求解方法3.問題歸約的例子(2/2)22

進化搜索以達爾文進化論的“物竟天擇、適者生存”作為算法的進化規(guī)則，并結合孟德爾的遺傳變異理論，將生物進化過程中的繁殖（Reproduction）變異（Mutation）競爭（Competition）選擇（Selection）引入到了算法中。(1)什么是進化搜索4.1.4進化搜索法概述1、進化搜索的概念及其生物學基礎(1/3)進化搜索算法也稱為模擬進化優(yōu)化算法或進化計算（EvolutionaryComputation,EC），是在達爾文進化論和孟德爾遺傳變異理論的基礎上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進化過程與機制進行問題求解的自組織、自適應的隨機搜索技術。主要包括遺傳算法（GeneticAlgorithm，GA）進化策略（EvolutionaryStrategy,ES）進化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）四大分支。23(2)進化計算的生物學基礎

自然界生物進化過程是進化計算的生物學基礎，它主要包括遺傳(Heredity)、變異(Mutation)和進化(Evolution)理論。①遺傳理論

遺傳是指父代（或親代）利用遺傳基因將自身的基因信息傳遞給下一代（或子代），使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種。在自然界，構成生物基本結構與功能的單位是細胞（Cell）。細胞中含有一種包含著所有遺傳信息的復雜而又微小的絲狀化合物，人們稱其為染色體（Chromosome）。在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。染色體的形狀是一種雙螺旋結構，構成染色體的主要物質叫做脫氧核糖核酸(DNA)，每個基因都在DNA長鏈中占有一定的位置。一個細胞中的所有染色體所攜帶的遺傳信息的全體稱為一個基因組(Genome)。

細胞在分裂過程中，其遺傳物質DNA通過復制轉移到新生細胞中，從而實現(xiàn)了生物的遺傳功能。4.1.4進化搜索法概述1.進化搜索的概念及其生物學基礎(2/3)24②變異理論

變異是指子代和父代之間，以及子代的各個不同個體之間產(chǎn)生差異的現(xiàn)象。變異是一種隨機、不可逆現(xiàn)象，是生物多樣性的基礎。引起變異的主要原因：雜交，是指有性生殖生物在繁殖下一代時兩個同源染色體之間的交配重組，即兩個染色體在某一相同處的DNA被切斷后再進行交配重組，形成兩個新的染色體。復制差錯，是指在細胞復制過程中因DNA上某些基因結構的隨機改變而產(chǎn)生出新的染色體。③進化論

進化是指在生物延續(xù)生存過程中，逐漸適應其生存環(huán)境，使得其品質不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進化的基本規(guī)律。

達爾文的自然選擇學說：在生物進化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的基因。這種新基因將依據(jù)其與生存環(huán)境的適應性而決定其增殖能力。通常，適應性強的基因會不斷增多，而適應性差的基因則會逐漸減少。通過這種自然選擇，物種將逐漸向適應于生存環(huán)境的方向進化，甚至會演變成為另一個新的物種，而那些不適應于環(huán)境的物種將會逐漸被淘汰。4.1.4進化搜索法概述1.進化搜索的概念及其生物學基礎(3/3)25

進化搜索自20世紀50年代以來，其發(fā)展過程大致可分為三個階段。

(1)萌芽階段這一階段是從20世紀50年代后期到70年代中期。20世紀50年代后期，一些生物學家在研究如何用計算機模擬生物遺傳系統(tǒng)中，產(chǎn)生了遺傳算法的基本思想，并于1962年由美國密執(zhí)安（Michigan）大學霍蘭德（Holland）提出。1965年德國數(shù)學家雷切伯格（Rechenberg）等人提出了一種只有單個個體參與進化，并且僅有變異這一種進化操作的進化策略。同年，美國學者弗格爾（Fogel）提出了一種具有多個個體和僅有變異一種進化操作的進化規(guī)劃。1969年美國密執(zhí)安（Michigan）大學的霍蘭德（Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調的遺傳算法。至此，進化計算的三大分支基本形成。

(2)成長階段這一階段是從20世紀70年代中期到80年代后期。1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應性（AdaptationinNaturalandArtificialSystem）》，全面介紹了遺傳算法。同年，德國學者施韋費爾（Schwefel）在其博士論文中提出了一種由多個個體組成的群體參與進化的，并且包括了變異和重組這兩種進化操作的進化策略。1989年，霍蘭德的學生戈爾德伯格（Goldberg）博士出版專著《遺傳算法----搜索、優(yōu)化及機器學習（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遺傳算法得到了普及與推廣。4.1.4進化搜索法概述2.進化搜索的產(chǎn)生與發(fā)展(1/2)26(3)發(fā)展階段

這一階段是從20世紀90年代至今。1989年，美國斯坦福（Stanford）大學的科扎（Koza）提出了遺傳規(guī)劃的新概念，并于1992年出版了專著《遺傳規(guī)劃----應用自然選擇法則的計算機程序設計（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》該書全面介紹了遺傳規(guī)劃的基本原理及應用實例，標志著遺傳規(guī)劃作為計算智能的一個分支已基本形成。進入20世紀90年代以來，進化計算得到了眾多研究機構和學者的高度重視，新的研究成果不斷出現(xiàn)、應用領域不斷擴大。目前，進化計算已成為人工智能領域的又一個新的研究熱點。

4.1.4進化搜索法概述2.進化搜索的產(chǎn)生與發(fā)展(2/2)27

進化計算盡管有多個重要分支，并且不同分支的編碼方案、選擇策略和進化操作也有可能不同，但它們卻有著共同的進化框架。若假設P為種群(Population，或稱為群體)，t為進化代數(shù)，P(t)為第t代種群,則進化計算的基本結構可粗略描述如下：

{確定編碼形式并生成搜索空間；初始化各個進化參數(shù)，并設置進化代數(shù)t=0；初始化種群P(0);

對初始種群進行評價（即適應度計算）；

while（不滿足終止條件）do{t=t+1;

利用選擇操作從P(t-1)代中選出P(t)代群體；對P(t)代種群執(zhí)行進化操作；對執(zhí)行完進化操作后的種群進行評價（即適應度計算）；

}}

可以看出，上述基本結構包含了生物進化中所必需的選擇操作、進化操作和適應度評價等過程。4.1.4進化搜索法概述3.進化搜索的基本過程284.1搜索概述4.2狀態(tài)空間的啟發(fā)式搜索4.2.1啟發(fā)信息和估價函數(shù)4.2.2A算法4.2.3A*算法4.2.4A*算法應用舉例4.3與/或樹的啟發(fā)式搜索4.4博弈樹的啟發(fā)式搜索4.5遺傳算法第4章智能搜索技術29啟發(fā)性信息

啟發(fā)性信息是指那種與具體問題求解過程有關的，并可指導搜索過程朝著最有希望方向前進的控制信息。啟發(fā)信息的啟發(fā)能力越強，擴展的無用結點越少。包括以下3種：①有效地幫助確定擴展節(jié)點的信息；②有效的幫助決定哪些后繼節(jié)點應被生成的信息；③能決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪除的信息。估價函數(shù)

用來估計節(jié)點重要性，定義為從初始節(jié)點S0出發(fā)，約束經(jīng)過節(jié)點n到達目標節(jié)點Sg的所有路徑中最小路徑代價的估計值。一般形式：

f(n)=g(n)+h(n)其中，g(n)是從初始節(jié)點S0到節(jié)點n的實際代價；h(n)是從節(jié)點n到目標節(jié)點Sg的最優(yōu)路徑的估計代價。

4.2.1啟發(fā)性信息和估價函數(shù)1.概念30

解：即g(n)=d(n)，h(n)=W(n)。d(n)說明用從S0到n的路徑上的單位代價表示實際代價；W(n)說明用結點n中“不在位”的數(shù)碼個數(shù)作為啟發(fā)信息?？梢姡彻?jié)點中的“不在位”的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠。對初始節(jié)點S0，由于d(S0)=0，W(S0)=3，因此有

f(S0)=0+3=32

831476512384765S0Sg

例4.5八數(shù)碼難題。設問題的初始狀態(tài)S0和目標狀態(tài)Sg如下圖所示，且估價函數(shù)為

f(n)=d(n)+W(n)其中：d(n)表示節(jié)點n在搜索樹中的深度

W(n)表示節(jié)點n中“不在位”的數(shù)碼個數(shù)。請計算初始狀態(tài)S0的估價函數(shù)值f(S0)4.2.1啟發(fā)性信息和估價函數(shù)2.例子31

在狀態(tài)空間搜索中，如果每一步都利用估價函數(shù)f(n)=g(n)+h(n)對Open表中的節(jié)點進行排序，則稱A算法。它是一種為啟發(fā)式搜索算法。類型：全局擇優(yōu)：從Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的進行擴展。局部擇優(yōu)：僅從剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的進行擴展。全局擇優(yōu)搜索A算法描述：

(1)把初始節(jié)點S0放入Open表中，f(S0)=g(S0)+h(S0)；

(2)如果Open表為空，則問題無解，失敗退出；

(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；

(4)考察節(jié)點n是否為目標節(jié)點。若是，則找到了問題的解，成功退出；

(5)若節(jié)點n不可擴展，則轉第(2)步；

(6)擴展節(jié)點n，生成其子節(jié)點ni(i=1,2,…)，計算每一個子節(jié)點的估價值f(ni)(i=1,2,…)，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后將這些子節(jié)點放入Open表中；

(7)根據(jù)各節(jié)點的估價函數(shù)值，對Open表中的全部節(jié)點按從小到大的順序重新進行排序；

(8)轉第(2)步。4.2.2A算法1.概念和算法描述32

例4.6八數(shù)碼難題。設問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示，估價函數(shù)與例4.5相同。請用全局擇優(yōu)搜索解決該問題。解：該問題的全局擇優(yōu)搜索樹如下圖所示。在該圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。例如，對節(jié)點S2，其估價函數(shù)值的計算為：f(S2)=d(S2)+W(S2)=1+3=4

2831476512384765S0Sg4.2.2A算法2.例子（1/2)332831476528314765231

847652831476528316475S0

832147652837146523184765231847651238476512378465123

847654455564644SgS1S2八數(shù)碼難題的全局擇優(yōu)搜索樹該問題的解為：

S0→S1→S2→S3→SgS364.2.2A算法2.例子(2/2)f(n)=d(n)+W(n)34

4.2.3A*算法1.概念A*算法是對A算法的估價函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法假設f*(n)是從初始節(jié)點S0出發(fā)，約束經(jīng)過節(jié)點n到達目標節(jié)點Sg的最小代價，估價函數(shù)f(n)是對f*(n)的估計值。記

f*(n)=g*(n)+h*(n)其中，g*(n)是從S0出發(fā)到達n的最小代價,h*(n)是n到Sg的最小代價如果對A算法（全局擇優(yōu)）中的g(n)和h(n)分別提出如下限制：第一，g(n)是對最小代價g*(n)的估計，且g(n)>0；第二，h(n)是最小代價h*(n)的下界，即對任意節(jié)點n均有h(n)≤h*(n)。則稱滿足上述兩條限制的A算法為A*算法。35

4.2.3A*算法1.A*算法的可納性(1/6)可納性的含義：

對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內找到一條從初始節(jié)點到目標節(jié)點的最佳路徑，并在此路徑上結束，則稱該搜索算法是可采納的。A*算法可納性的證明過程：第一步，對有限圖，A*算法一定能夠成功結束。定理4.1

第二步，對無限圖，A*算法也一定能夠成功結束。引理4.1、4.2和推論4.1,定理4.2

第三步，A*算法一定能夠結束在最佳路徑上。定理4.3和推論4.2

定理4.1

對有限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則算法A*一定成功結束。

證明：首先證明算法必然會結束。

由于搜索圖為有限圖，如果算法能找到解，則成功結束；如果算法找不到解，則必然會由于Open表變空而結束。因此，A*算法必然會結束。

36

然后證明算法一定會成功結束。

由于至少存在一條由初始節(jié)點到目標節(jié)點的路徑，設此路徑為

S0=n0,n1,…,nk=Sg算法開始時，節(jié)點n0在Open表中，且路徑中任一節(jié)點ni離開Open表后，其后繼節(jié)點ni+1必然進入Open表，這樣，在Open表變?yōu)榭罩?，目標?jié)點必然出現(xiàn)在Open表中。因此，算法一定會成功結束。引理4.1

對無限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則算法A*算法不終止的話，則從Open表中選出的節(jié)點必將具有任意大的f值。證明：設d*(n)是A*生成的從初始節(jié)點S0到節(jié)點n的最短路經(jīng)長度，由于搜索圖中每條邊的代價都是一個正數(shù)，令其中的最小的一個數(shù)是e，則有

g*(n)≥d*(n)×e因為g*(n)是最佳路徑的代價，故有

g(n)≥g*(n)≥d*(n)×e又因為h(n)≥0，故有

f(n)=g(n)+h(n)≥g(n)≥d*(n)×e

如果A*算法不終止的話，從Open表中選出的節(jié)點必將具有任意大的d*(n)值，因此，也將具有任意大的f值。

4.2.3A*算法1.A*算法的可納性(2/6)37

引理4.2

在A*算法終止前的任何時刻，Open表中總存在節(jié)點n’，它是從初始節(jié)點S0到目標節(jié)點的最佳路徑上的一個節(jié)點，且滿足f(n’)≤f*(S0)。證明：設從初始節(jié)點S0到目標節(jié)點t的一條最佳路徑序列為

S0=n0,n1,…,nk=Sg算法開始時，節(jié)點S0在Open表中，當節(jié)點S0離開Open表進入Closed表時，節(jié)點n1進入Open表。因此，A*沒有結束以前，在Open表中必存在最佳路徑上的節(jié)點。設這些節(jié)點中排在最前面的節(jié)點為n'，則有

f(n')=g(n')+h(n')由于n'在最佳路徑上，故有g(n')=g*(n')，從而

f(n')=g*(n')+h(n')又由于A*算法滿足h(n')≤h*(n')，故有

f(n')≤g*(n')+h*(n')=f*(n')因為在最佳路徑上的所有節(jié)點的f*值都應相等，因此有

f(n')≤f*(S0)4.2.3A*算法1.A*算法的可納性(3/6)38

定理4.2

對無限圖，若從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則A*算法必然會結束。證明：（反證法）假設A*不結束，由引理4.1知Open表中的節(jié)點有任意大的f值，這與引理3.2的結論相矛盾，因此，A*算法只能成功結束。推論4.1

Open表中任一具有f(n)<f*(S0)的節(jié)點n，最終都被A*算法選作為擴展的節(jié)點。

(證明略)

下面給出A*算法的可納性4.2.3A*算法1.A*算法的可納性(4/6)394.2.3A*算法1.A*算法的可納性(5/6)

定理4.3

A*算法是可采納的，即若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑，則A*算法必能結束在最佳路徑上。證明：證明過程分以下兩步進行：

先證明A*算法一定能夠終止在某個目標節(jié)點上。由定理4.1和定理4.2可知，無論是對有限圖還是無限圖，A*算法都能夠找到某個目標節(jié)點而結束。

再證明A*算法只能終止在最佳路徑上。（反證法）假設A*算法未能終止在最佳路徑上，而是終止在某個目標節(jié)點t處，則有

f(t)=g(t)>f*(S0)但由引理4.2可知，在A*算法結束前，必有最佳路徑上的一個節(jié)點n'在Open表中，且有

f(n’)≤f*(S0)<f(t)這時，A*算法一定會選擇n'來擴展，而不可能選擇t，從而也不會去測試目標節(jié)點t，這就與假設A*算法終止在目標節(jié)點t相矛盾。因此，A*算法只能終止在最佳路徑上。40

推論4.2

在A*算法中，對任何被擴展的節(jié)點n，都有f(n)≤f*(S0)。

證明：令n是由A*選作擴展的任一節(jié)點，因此n不會是目標節(jié)點，且搜索沒有結束。由引理4.2可知，在Open表中有滿足

f(n')≤f*(S0)的節(jié)點n'。若n=n'，則有f(n)≤f*(S0)；否則，選擇n擴展，必有

f(n)≤f(n')所以有

f(n)≤f*(S0)4.2.3A*算法1.A*算法的可納性(6/6)41

A*算法的搜索效率很大程度上取決于啟發(fā)函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。A*算法的這一特性被稱為最優(yōu)性。下面通過一個定理來描述這一特性。定理4.4

設有兩個A*算法A1*和A2*，它們有

A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)如果A2*比A1*有更多的啟發(fā)性信息，即對所有非目標節(jié)點均有

h2(n)>h1(n)則在搜索過程中，被A2*擴展的節(jié)點也必然被A1*擴展，即A1*擴展的節(jié)點不會比A2*擴展的節(jié)點少，亦即A2*擴展的節(jié)點集是A1*擴展的節(jié)點集的子集。4.2.3A*算法2.A*算法的最優(yōu)性(1/2)42

4.2.3A*算法2.A*算法的最優(yōu)性(2/2)證明：（用數(shù)學歸納法）

(1)對深度d(n)=0的節(jié)點，即n為初始節(jié)點S0，如n為目標節(jié)點，則A1*和A2*都不擴展n；如果n不是目標節(jié)點，則A1*和A2*都要擴展n。

(2)假設對A2*中d(n)=k的任意節(jié)點n結論成立，即A1*也擴展了這些節(jié)點。

(3)證明A2*中d(n)=k+1的任意節(jié)點n，也要由A1*擴展。（用反證法）假設A2搜索樹上有一個滿足d(n)=k+1的節(jié)點n，A2*擴展了該節(jié)點，但A1*沒有擴展它。根據(jù)第(2)條的假設，知道A1*擴展了節(jié)點n的父節(jié)點。因此，n必定在A1*的Open表中。既然節(jié)點n沒有被A1*擴展，則有

f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)。但由于d=k時，A2*擴展的節(jié)點A1*也一定擴展，故有

g1(n)≤g2(n)因此有h1(n)≥f*(S0)-g2(n)

另一方面，由于A2*擴展了n，因此有

f2(n)≤f*(0)即g2(n)+h2(n)≤f*(S0)，亦即h2(n)≤f*(S0)-g2(n)，所以有h1(n)≥h2(n)

這與我們最初假設的h1(n)<h2(n)矛盾，因此反證法的假設不成立。43

在A*算法中，每當擴展一個節(jié)點n時，都需要檢查其子節(jié)點是否已在Open表或Closed表中。對已在Open表中的子節(jié)點，需要決定是否調整指向其父節(jié)點的指針；對已在Closed表中的子節(jié)點，除需要決定是否調整其指向父節(jié)點的指針外，還需要決定是否調整其子節(jié)點的后繼節(jié)點的父指針。如果能夠保證，每當擴展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，就沒有必要再去作上述檢查為滿足這一要求，我們需要對啟發(fā)函數(shù)h(n)增加單調性限制。定義4.1

如果啟發(fā)函數(shù)滿足以下兩個條件:(1)h(Sg)=0;(2)對任意節(jié)點ni及其任一子節(jié)點nj，都有

0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調限制。4.2.3A*算法3.h(n)的單調限制(1/3)44

定理4.5

如果h滿足單調條件，則當A*算法擴展節(jié)點n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：設A*正要擴展節(jié)點n，而節(jié)點序列

S0=n0,n1,…,nk=n是由初始節(jié)點S0到節(jié)點n的最佳路徑。其中，ni是這個序列中最后一個位于Closed表中的節(jié)點，則上述節(jié)點序列中的ni+1節(jié)點必定在Open表中，則有

g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)由于節(jié)點ni和ni+1都在最佳路徑上，故有

g*(ni+1)=g*(ni)+c(ni,ni+1)所以g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)一直推導下去可得g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)由于節(jié)點ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因為這時A*擴展節(jié)點n而不擴展節(jié)點ni+1，則有

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)但是g*(n)是最小代價值，應當有

g(n)≥g*(n)所以有g(n)=g*(n)4.2.3A*算法3.h(n)的單調限制(2/3)45

定理4.6

如果h(n)滿足單調限制，則A*算法擴展的節(jié)點序列的f值是非遞減的，即f(ni)≤f(ni+1)。證明：假設節(jié)點ni+1在節(jié)點ni之后立即擴展，由單調限制條件可知

h(ni)-h(ni+1)≤c(ni,ni+1)即

f(ni)-g(ni)-f(ni+1)+g(ni+1)≤c(ni,ni+1)亦即

f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以

f(ni)-f(ni+1)≤0即

f(ni)≤f(ni+1)

以上兩個定理都是在h(n)滿足單調性限制的前提下才成立的。如果h(n)不滿足單調性限制，則它們不一定成立。在h(n)滿足單調性限制下的A*算法常被稱為改進的A*算法。4.2.3A*算法3.h(n)的單調限制(3/3)46例4.7

八數(shù)碼難題。

28314765283147652318476528314765283164752318476523184765123847651237846512384765S0f=6g*=1h*=3f=6f=6g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6Sg八數(shù)碼難題h(n)=P(n)的搜索樹f(n)=d(n)+P(n)d(n)深度P(n)與目標距離顯然滿足P(n)≤h*(n)即f*=g*+h*f=44.2.4A*算法應用舉例八數(shù)碼難題h*=4f=447例4.8修道士和野人問題解：用m表示左岸的修道士人數(shù)，c表示左岸的野人數(shù)，b表示左岸的船數(shù)，用三元組(m,c,b)表示問題的狀態(tài)。對A*算法，首先需要確定估價函數(shù)。設g(n)=d(n)，h(n)=m+c-2b，則有

f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)為節(jié)點的深度。通過分析可知h(n)≤h*(n)，滿足A*算法的限制條件。

M-C問題的搜索過程如下圖所示。

4.2.4A*算法應用舉例修道士和野人過河問題（1/6）48h=4f=4問題狀態(tài)：(m,c,b)估價函數(shù)：k(n)=g(n)+h(n)g(n)=d(n)h(n)=m+c-2bf(n)=d(n)+m+c-2b(3,2,0)(3,1,0)(3,3,1)h=5f=6h=4f=5(2,2,0)h=2f=7L01L11R01L02h=4f=5R10(3,0,0)(3,2,1)h=3f=5(3,1,1)R01L02h=3f=6(1,1,0)L20h=2f=6(2,2,1)R11h=2f=9(0,2,0)L20h=2f=8R01h=1f=9(0,3,1)(0,2,1)L02h=1f=10(0,1,0)R01h=1f=11(0,0,0)L02h=0f=114.2.4A*算法應用舉例修道士和野人過河問題（2/6）初始狀態(tài)左岸左岸右岸右岸(3,0,0)(3,2,1)(3,1,0)(3,3,1)L02R01L02R01R01494.2.4A*算法應用舉例修道士和野人過河問題（3/6）右岸左岸右岸(0,2,0)(2,2,1)(1,1,0)(3,1,1)L20R11左岸R01R11L20R01504.2.4A*算法應用舉例修道士和野人過河問題（4/6）左岸右岸左岸右岸(0,0,0)(0,2,1)(0,1,0)(0,3,1)R01L02R01R01L02514.2.4A*算法應用舉例修道士和野人過河問題（5/6）右岸目標狀態(tài)(0,0,0)操作序列：L02→R01→L02→R01→L20→R11→L20→R01→L02524.2.4A*算法應用舉例修道士和野人過河問題（6/6）534.1搜索概述4.2狀態(tài)空間的啟發(fā)式搜索4.3與/或樹的啟發(fā)式搜索

4.3.1解樹的代價和希望樹

4.3.2與/或樹的啟發(fā)式搜索過程4.4博弈樹的啟發(fā)式搜索4.5遺傳算法第4章智能搜索技術544.3與/或樹的啟發(fā)式搜索

與/或樹的啟發(fā)式搜索過程實際上是一種利用搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。算法的每一步都試圖找到一個最有希望成為最優(yōu)解樹的子樹。最優(yōu)解樹是指代價最小的那棵解樹。它涉及到解樹的代價與希望樹。55解樹的代價可按如下方法計算：

(1)若n為終止節(jié)點，則其代價h(n)=0；

(2)若n為或節(jié)點，且子節(jié)點為n1,n2,…,nk，則n的代價為：其中，c(n,ni)是節(jié)點n到其子節(jié)點ni的邊代價。

(3)若n為與節(jié)點，且子節(jié)點為n1,n2,…,nk，則n的代價可用和代價法或最大代價法。若用和代價法，則其計算公式為：若用最大代價法，則其計算公式為：

(4)若n是端節(jié)點，但又不是終止節(jié)點，則n不可擴展，其代價定義為h(n)=∝。

(5)根節(jié)點的代價即為解樹的代價。4.3.1解樹的代價與希望樹1.解樹的代價（1/2）56

例4.11

設下圖是一棵與/或樹，它包括兩棵解樹，左邊的解樹由S0、A、t1、C及t2組成；右邊的解樹由S0、B、t2、D及t4組成。在該樹中，t1、t2、t3、t4為終止節(jié)點；E、F是端節(jié)點；邊上的數(shù)字是該邊的代價。請計算解樹的代價。解：先計算左邊的解樹按和代價：h(S0)=2+4+6+2=14按最大代價：h(S0)=(2+6)+2=10再計算右邊的解樹按和代價：h(S0)=1+5+3+2=11按最大代價：h(S0)=(1+5)+2=8

S02At1

Ct2

Dt3Et4F

與/或樹的代價24623154.3.1解樹的代價與希望樹1.解樹的代價（2/2）B57

希望樹是指搜索過程中最有可能成為最優(yōu)解樹的那棵樹。

與/或樹的啟發(fā)式搜索過程就是不斷地選擇、修正希望樹的過程，在該過程中，希望樹是不斷變化的。定義4.2

希望解樹

(1)初始節(jié)點S0在希望樹T(2)如果n是具有子節(jié)點n1,n2,…,nk的或節(jié)點，則n的某個子節(jié)點ni在希望樹T中的充分必要條件是4.3.1解樹的代價與希望樹2.希望樹

(3)如果n是與節(jié)點，則n的全部子節(jié)點都在希望樹T中。58

與/或樹的啟發(fā)式搜索過程如下：

(1)把初始節(jié)點S0放入Open表中，計算h(S0)；

(2)計算希望樹T；

(3)依次在Open表中取出T的端節(jié)點放入Closed表，并記該節(jié)點為n；

(4)如果節(jié)點n為終止節(jié)點，則做下列工作：①標記節(jié)點n為可解節(jié)點；②在T上應用可解標記過程，對n的先輩節(jié)點中的所有可解解節(jié)點進行標記；

③如果初始解節(jié)點S0能夠被標記為可解節(jié)點，則T就是最優(yōu)解樹，成功退出；④否則，從Open表中刪去具有可解先輩的所有節(jié)點。⑤轉第(2)步。4.3.2與/或樹的啟發(fā)式搜索過程1.算法描述(1/2)59

(5)如果節(jié)點n不是終止節(jié)點，但可擴展，則做下列工作：①擴展節(jié)點n，生成n的所有子節(jié)點；②把這些子節(jié)點都放入Open表中，并為每一個子節(jié)點設置指向父節(jié)點n的指針③計算這些子節(jié)點及其先輩節(jié)點的h值；④轉第(2)步。

(6)如果節(jié)點n不是終止節(jié)點，且不可擴展，則做下列工作：①標記節(jié)點n為不可解節(jié)點；②在T上應用不可解標記過程，對n的先輩節(jié)點中的所有不可解解節(jié)點進行標記；③如果初始節(jié)點S0能夠被標記為不可解，則問題無解，失敗退出；④否則，從Open表中刪去具有不可解先輩的所有節(jié)點。⑤轉第(2)步。4.3.2與/或樹的啟發(fā)式搜索過程1.算法描述(2/2)60例子要求搜索過程每次擴展節(jié)點時都同時擴展兩層，且按一層或節(jié)點、一層與節(jié)點的間隔方式進行擴展。它實際上就是下一節(jié)將要討論的博弈樹的結構。設初始節(jié)點為S0，對S0擴展后得到的與/或樹如右圖所示。其中，端節(jié)點B、C、E、F，下面的數(shù)字是用啟發(fā)函數(shù)估算出的h值，節(jié)點S0、A、D旁邊的數(shù)字是按和代價法計算出來的節(jié)點代價。此時，S0的右子樹是當前的希望樹。S08A8D7BCEF3332按和代價法：例:：節(jié)點S0的值=3+1+2+1+1=8擴展S0后得到的與/或樹4.3.2與/或樹的啟發(fā)式搜索過程2.例子(1/4)或結點與結點61擴展節(jié)點E，得到如右圖所示的與/或樹。此時，由右子樹求出的h(S0)=12。但是，由左子樹求出的h(S0)=9。顯然，左子樹的代價小。因此，當前的希望樹應改為左子樹。S09A8D11BCEF3372322276擴展節(jié)點E后得到的與/或樹4.3.2與/或樹的啟發(fā)式搜索過程2.例子(2/4)或結點與結點或結點與結點62

對節(jié)點B進行擴展，擴展兩層后得到的與/或樹如下圖所示。由于節(jié)點H和I是可解節(jié)點，故調用可解標記過程，得節(jié)點G、B也為可解節(jié)點，但不能標記S0為可解節(jié)點，須繼續(xù)擴展。當前的希望樹仍然是左子樹。S09A8D11BCEF3372322276GJHIKL002226擴展節(jié)點B后得到的與/或樹4.3.2與/或樹的啟發(fā)式搜索過程2.例子(3/4)或結點或結點與結點與結點63

對節(jié)點C進行擴展，擴展兩層后得到的與/或樹如右圖所示。由于節(jié)點N和P是可解節(jié)點，故調用可解標記過程，得節(jié)點M、C、A也為可解節(jié)點，進而可標記S0為可解節(jié)點，這就的到了代價最小的解樹。按和代價法，該最優(yōu)解的代價為9。S09A8D11BCEF3372322276GJHIKL002226擴展節(jié)點C后得到的與/或樹4.3.2與/或樹的啟發(fā)式搜索過程2.例子(4/4)或結點或結點與結點與結點29MPN005264第4章智能搜索技術4.1搜索概述4.2狀態(tài)空間的啟發(fā)式搜索4.3與/或樹的啟發(fā)式搜索4.4博弈樹的啟發(fā)式搜索4.4.1博弈概述

4.4.2極/大極小過程

4.4.3α-β剪枝4.5遺傳算法654.4.1博弈概述博弈的概念博弈是一類具有智能行為的競爭活動，如下棋、戰(zhàn)爭等。博弈的類型

雙人完備信息博弈：兩位選手（例如MAX和MIN

）對壘，輪流走步，每一方不僅知道對方已經(jīng)走過的棋步，而且還能估計出對方未來的走步。機遇性博弈：存在不可預測性的博弈，例如擲幣等。博弈樹若把雙人完備信息博弈過程用圖表示出來，就得到一棵與/或樹，這種與/或樹被稱為博弈樹。在博弈樹中，那些下一步該MAX走步的節(jié)點稱為MAX節(jié)點，下一步該MIN走步的節(jié)點稱為MIN

節(jié)點。博弈樹的特點

(1)博弈的初始狀態(tài)是初始節(jié)點；

(2)博弈樹中的“或”節(jié)點和“與”節(jié)點是逐層交替出現(xiàn)的；

(3)整個博弈過程始終站在某一方的立場上，例如MAX方。所有能使自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點。664.4.2極大極小過程概念

對簡單的博弈問題，可生成整個博弈樹，找到必勝的策略。對于復雜的博弈問題，不可能生成整個搜索樹，如國際象棋，大約有10120個節(jié)點。一種可行的方法是用當前正在考察的節(jié)點生成一棵部分博弈樹，并利用估價函數(shù)f(n)對葉節(jié)點進行靜態(tài)估值。對葉節(jié)點的估值方法是：那些對MAX有利的節(jié)點，其估價函數(shù)取正值；那些對MIN有利的節(jié)點，其估價函數(shù)取負值；那些使雙方均等的節(jié)點，其估價函數(shù)取接近于0的值。為非葉節(jié)點的值，必須從葉節(jié)點開始向上倒退。其倒退方法是：對于MAX節(jié)點，由于MAX方總是選擇估值最大的走步，因此，MAX節(jié)點的倒退值應該取其后繼節(jié)點估值的最大值。對于MIN節(jié)點，由于MIN方總是選擇使估值最小的走步，因此MIN節(jié)點的倒推值應取其后繼節(jié)點估值的最小值。這樣一步一步的計算倒推值，直至求出初始節(jié)點的倒推值為止。這一過程稱為極大極小過程。67

例4.9一子棋游戲

設有一個三行三列的棋盤，如下圖所示，兩個棋手輪流走步，每個棋手走步時往空格上擺一個自己的棋子，誰先使自己的棋子成三子一線為贏。設MAX方的棋子用×標記，MIN方的棋子用○標記，并規(guī)定MAX方先走步。一子棋棋盤棋局1

解：估價函數(shù)e(+P)：P上有可能使×成三子為一線的數(shù)目；

e(-P)：P上有可能使○成三子為一線的數(shù)目；當MAX必勝e(P)為正無窮大；

MIN必勝e(P)為負無窮大。e(P)=e(+P)-e(-P)4.4.2極大極小過程例子(1/3)68

棋局即估價函數(shù)

具有對稱性的棋盤可認為是同一棋盤。如下圖所示：其e(P)=e(+P)-e(-P)=5-4=14.4.2極大極小過程例子(2/3)×為MAX方的棋子○為MIN方的棋子69S01S1S2S3-16-5=15-5=06-5=15-5=04-5=-15-4=16-4=25-6=-15-5=05-6=-16-6=04-6=-2

一子棋的極大極小搜索S4S5-21搜索過程：設MAX方