知識表示與推理課件

知識表示與推理知識表示與推理1主要內(nèi)容知識表示及其概念知識表示——狀態(tài)圖（或圖）的搜索及問題求解與或圖的搜索及問題求解博弈樹的搜索及問題求解主要內(nèi)容知識表示及其概念2知識點或圖與或圖博弈樹搜索策略問題求解盲目搜索啟發(fā)式搜索希望樹問題求解極大極小法α-β剪枝法圖搜索知識點或圖與或圖博弈樹搜索策略問題求解盲目搜索啟發(fā)式搜索希32.1知識的概念費根鮑姆Feigenbaum：知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。Bernstein：知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。Hayes-roth：知識是事實、信念和啟發(fā)式規(guī)則。從知識庫的觀點看，知識是某領(lǐng)域中所涉及的各有關(guān)方面的一種符號表示。2.1知識的概念費根鮑姆Feigenbaum：知識是經(jīng)過消4知識的分類從不同的角度、不同的側(cè)面對知識有著不同的分類方法。從內(nèi)容上分：原理（客觀）性知識和方法（主觀）性知識。原理（客觀）性知識具有抽象概括性方法（主觀）性知識具有通用性。從形式上分：顯示和隱式。從邏輯思維角度分：邏輯型和直覺型知識。從可靠性上分：理論知識和經(jīng)驗知識。知識的分類從不同的角度、不同的側(cè)面對知識有著不同的分類方法5知識的要素事實：事物的分類、屬性、事物間關(guān)系、科學事實、客觀事實等。規(guī)則：事物的行動、動作和聯(lián)系的因果關(guān)系知識?？刂疲寒斢卸鄠€動作同時被激活時，選擇哪一個動作來執(zhí)行的知識。元知識：怎樣使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序結(jié)構(gòu)等知識。知識的要素事實：事物的分類、屬性、事物間關(guān)系、科學事實、客6知識表示定義知識表示方法是面向計算機的知識描述或表達形式和方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組事物的約定，以把人類知識表示成機器能處理的數(shù)據(jù)結(jié)構(gòu)。知識表示定義知識表示方法是面向計算機的知識描述或表達形式和方7知識表示與推理課件82.2狀態(tài)空間及狀態(tài)圖搜索狀態(tài)空間及其搜索的表示一般圖搜索策略啟發(fā)式搜索算法2.2狀態(tài)空間及狀態(tài)圖搜索狀態(tài)空間及其搜索的表示9狀態(tài)空間圖狀態(tài)空間圖：描述問題的有向圖，簡稱為狀態(tài)圖。狀態(tài)空間：一個問題的全體狀態(tài)及其關(guān)系所構(gòu)成的空間。一般都表示為或圖。節(jié)點：表示狀態(tài)。節(jié)點間的有向弧：表示狀態(tài)變遷?；∩系臉撕灒罕硎緦е聽顟B(tài)轉(zhuǎn)換的規(guī)則，稱為狀態(tài)轉(zhuǎn)換規(guī)則，也稱操作。狀態(tài)空間圖狀態(tài)空間圖：描述問題的有向圖，簡稱為狀態(tài)圖。10狀態(tài)空間圖狀態(tài)——狀態(tài)一般用一組數(shù)據(jù)表示?？赏ㄟ^定義某種數(shù)據(jù)結(jié)構(gòu)來描述，用于記載問題求解（即搜索）過程中某一時刻問題現(xiàn)狀的快照。狀態(tài)轉(zhuǎn)換規(guī)則——可以是某種操作、規(guī)則、行為、變換、關(guān)系、函數(shù)、算子和過程等。狀態(tài)空間圖狀態(tài)——狀態(tài)一般用一組數(shù)據(jù)表示?？赏ㄟ^定義某種數(shù)11狀態(tài)空間圖狀態(tài)圖也可以用一個三元組表示：（S，F(xiàn)，G）S：問題的初始狀態(tài)集合。F：問題的狀態(tài)轉(zhuǎn)換規(guī)則集合。G：問題的目標狀態(tài)集合。狀態(tài)空間圖狀態(tài)圖也可以用一個三元組表示：（S，F(xiàn)，G）12狀態(tài)空間圖例1迷宮問題顯式狀態(tài)圖：寫出全部節(jié)點和邊的狀態(tài)圖。

例2八數(shù)碼難題隱式狀態(tài)圖：僅寫出初始節(jié)點和目標節(jié)點，其余節(jié)點需要用狀態(tài)轉(zhuǎn)換規(guī)則產(chǎn)生的狀態(tài)圖。狀態(tài)空間圖例1迷宮問題13狀態(tài)圖搜索搜索——從初始節(jié)點出發(fā)，沿著與之相連的邊尋找目標節(jié)點的過程。解答路徑——初-目變遷過程中的狀態(tài)序列或相應的操作算子調(diào)用序列。搜索樹（圖）——在搜索解答路徑的過程中只畫出搜索時直接涉及到的節(jié)點和弧線，構(gòu)成所謂的搜索圖。狀態(tài)圖搜索搜索——從初始節(jié)點出發(fā)，沿著與之相連的邊尋找目標14搜索空間示意圖搜索空間示意圖15狀態(tài)圖搜索（1）求任一解路的搜索策略回溯法（Backtracking）寬(廣)度優(yōu)先法（Breadth-first）深度優(yōu)先法（Depth-first）限定范圍搜索法（BeamSearch）局部擇優(yōu)（爬山法HillClimbing）全局擇優(yōu)搜索（最好的優(yōu)先法Best-first）狀態(tài)圖搜索（1）求任一解路的搜索策略16狀態(tài)圖搜索（2）求最佳解路的搜索策略大英博物館法（BritishMuseum）分枝界限法（最小代價優(yōu)先法BranchandBound）動態(tài)規(guī)劃法（DynamicProgramming）最佳圖搜索法（A﹡）狀態(tài)圖搜索（2）求最佳解路的搜索策略17狀態(tài)圖搜索——搜索術(shù)語節(jié)點深度——搜索圖是一種有根圖，根節(jié)點指示初始狀態(tài)，令其節(jié)點深度為0，則搜索圖中的其它節(jié)點的深度dn就可遞歸地定義為其父節(jié)點深度dn-1加1：dn=dn-1+1.路徑——從節(jié)點ni到nk的路徑是由相鄰節(jié)點間的弧線構(gòu)成的折線，通常要求路徑是無環(huán)的，否則會導致搜索過程進入死循環(huán)。節(jié)點擴展——應用轉(zhuǎn)換規(guī)則將上一狀態(tài)（節(jié)點ni）變遷到下一狀態(tài)（節(jié)點nj），ni指示被擴展節(jié)點，nj即是由ni擴展出的子節(jié)點。狀態(tài)圖搜索——搜索術(shù)語節(jié)點深度——搜索圖是一種有根圖，根節(jié)點18狀態(tài)圖搜索——搜索術(shù)語路徑代價——相鄰節(jié)點ni和nj間路徑的代價記為C(ni,nj),由兩部分組成：路徑本身代價——轉(zhuǎn)換規(guī)則的執(zhí)行代價。路徑搜索代價——又分為二部分：路徑建立代價——從節(jié)點ni擴展出節(jié)點nj所付出的代價；路徑選擇代價——選擇這條路徑作為搜索方向（即選擇nj作為下一步搜索起點）所付出的代價。狀態(tài)圖搜索——搜索術(shù)語路徑代價——相鄰節(jié)點ni和nj間路徑的19狀態(tài)圖搜索——搜索方式樹式搜索：在搜索過程中，記錄所經(jīng)過的所有節(jié)點和邊。線式搜索：在搜索過程中，只記錄當前所找路徑上的節(jié)點和邊。狀態(tài)圖搜索——搜索方式樹式搜索：在搜索過程中，記錄所經(jīng)過的所20狀態(tài)圖搜索——搜索策略盲目搜索：就是未利用問題的知識，采用固定的方式生成狀態(tài)的方法。特點：搜索效率是低下的，但方法具有通用性。狀態(tài)圖搜索——搜索策略盲目搜索：就是未利用問題的知識，采用21狀態(tài)圖搜索——搜索策略啟發(fā)式搜索：利用問題的知識，縮小問題的搜索范圍，選擇那些最有可能在（最優(yōu)）解路徑上的狀態(tài)優(yōu)先搜索，以盡快地找到問題的（最優(yōu)）解。特點：搜索效率提高。問題：尋找對求解問題有幫助的知識，以及如何利用這些知識。狀態(tài)圖搜索——搜索策略啟發(fā)式搜索：利用問題的知識，縮小問題22狀態(tài)圖搜索——搜索算法OPEN表和CLOSED表。其中OPEN表記錄的是已經(jīng)被生成出來，但還沒有被擴展的節(jié)點；CLOSED表記錄的是已經(jīng)被擴展過的節(jié)點。OPEN表節(jié)點父節(jié)點編號

CLOSED表編號節(jié)點父節(jié)點編號

狀態(tài)圖搜索——搜索算法OPEN表和CLOSED表。其中OPE23狀態(tài)圖搜索——搜索算法①G：＝（＝s），OPEN：＝（s）；G表示圖，s為初始節(jié)點，設(shè)置OPEN表，最初只含初始節(jié)點。②CLOSED：＝（）；設(shè)置CLOSED表，起始設(shè)置為空表。③LOOP：IFOPEN＝（），THENEXIT（FAIL）；④n：＝FIRST（OPEN），REMOVE（n，OPEN），ADD（n，CLOSED）；稱n為當前節(jié)點。⑤IFGOAL（n），THENEXIT（SUCCESS）；由n返回到s路徑上的指針，可給出解路徑。⑥EXPAND（n）→{mi}，G：＝ADD（mi，G）；子節(jié)點集{mi}中不包含n的父輩節(jié)點。狀態(tài)圖搜索——搜索算法①G：＝（＝s），OPEN：＝（s）；24狀態(tài)圖搜索——搜索算法⑦標記和修改指針ADD（mj，OPEN），并標記mj連接到n的指針；mj為OPEN和CLOSED中未出現(xiàn)過的子節(jié)點，{mi}＝{mj}∪{mk}∪{ml}。計算是否要修改mk，ml到n的指針；mk為已出現(xiàn)在OPEN中的子節(jié)點，ml為已出現(xiàn)在CLOSED中的子節(jié)點。計算是否要修改到其后繼節(jié)點的指針；⑧對OPEN中的節(jié)點按某種原則重新排序；⑨GOLOOP；狀態(tài)圖搜索——搜索算法⑦標記和修改指針25狀態(tài)圖搜索——搜索算法mk沒被擴展,在OPEN表中.

ml已被擴展,在CLOSED表中.當n被擴展時，它生成了節(jié)點mi.mj是新出現(xiàn)的節(jié)點.mj狀態(tài)圖搜索——搜索算法mk沒被擴展,在OPEN表中.mj26狀態(tài)圖搜索——寬度優(yōu)先步1、把初始節(jié)點S0放入OPEN表中；步2、若OPEN表為空，則搜索失敗；退出。步3、取OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序號n；步4、若目標節(jié)點Sg=N，則搜索成功，結(jié)束。步5、若N不可擴展，則轉(zhuǎn)步2；步6、擴展N，將其所有子節(jié)點配上指向N的指針，依次放入OPEN表尾部，轉(zhuǎn)步2。OPEN表是一個隊列。狀態(tài)圖搜索——寬度優(yōu)先步1、把初始節(jié)點S0放入OPEN表中；27狀態(tài)圖搜索——寬度優(yōu)先寬度優(yōu)先特點當問題有解時，寬度優(yōu)先算法不但能一定找到解，能找到最優(yōu)解，盲目性大，可能產(chǎn)生許多無用的中間頂點，效率低。狀態(tài)圖搜索——寬度優(yōu)先寬度優(yōu)先特點28狀態(tài)圖搜索——深度優(yōu)先步1、把初始節(jié)點S0放入OPEN表中；步2、若OPEN表為空，則搜索失敗；退出。步3、取OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序號n；步4、若目標節(jié)點Sg=N，則搜索成功，結(jié)束。步5、若N不可擴展，則轉(zhuǎn)步2；步6、擴展N，將其所有子節(jié)點配上指向N的指針，依次放入OPEN表首部，轉(zhuǎn)步2。OPEN表是一個棧。狀態(tài)圖搜索——深度優(yōu)先步1、把初始節(jié)點S0放入OPEN表中；29狀態(tài)圖搜索——深度優(yōu)先深度優(yōu)先特點效率較高。一般情況下，當問題有解時，不一定能找到解，且解一般不是最優(yōu)解。如果問題的狀態(tài)空間是有限的，則可以保證找到解，當問題的狀態(tài)空間是無限的時，則可能陷入“深淵”，而找不到解。狀態(tài)圖搜索——深度優(yōu)先深度優(yōu)先特點30狀態(tài)圖搜索——有界深度優(yōu)先步1、把初始節(jié)點S0放入OPEN表中；步2、若OPEN表為空，則搜索失??；退出。步3、取OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序號n；步4、若目標節(jié)點Sg=N，則搜索成功，結(jié)束。步5、若N的深度d(N)=dm(深度限制值)，或者N不可擴展，則轉(zhuǎn)步2；步6、擴展N，將其所有子節(jié)點配上指向N的指針，依次放入OPEN表首部，置d(Ni)=d(N)+1,轉(zhuǎn)步2。狀態(tài)圖搜索——有界深度優(yōu)先步1、把初始節(jié)點S0放入OPEN表31狀態(tài)圖搜索——有界深度優(yōu)先算法：對于深度優(yōu)先算法中需放入OPEN中的頂點若其深度不超過規(guī)定的上界d，則放入OPEN的頭部，并為每一個頂點配置指向父頂點的指針。特點：不一定能找到解，且解一般不是最優(yōu)解。效率較高。關(guān)鍵：d的選擇狀態(tài)圖搜索——有界深度優(yōu)先算法：對于深度優(yōu)先算法中需放入OP32狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)式搜索就是利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。目的：引入與應用領(lǐng)域相關(guān)的啟發(fā)式知識來指導OPEN表中節(jié)點的排序，使最有希望出現(xiàn)在較短解答路徑上的節(jié)點優(yōu)先考察，就能顯著提高搜索的有效性。狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)式搜索就是利用知識來引導搜索，達33狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)性信息用途：(1)決定擴展節(jié)點的先后順序；(2)決定生成后續(xù)節(jié)點的多少；(3)決定刪除哪些無用的節(jié)點。狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)性信息用途：34狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)函數(shù)（Heuristicfunction）啟發(fā)函數(shù)是用來估計搜索樹上節(jié)點x與目標節(jié)點Sg接近程度的一種函數(shù)，通常記為h(x)。如何定義一個啟發(fā)函數(shù)一個節(jié)點處在最佳路徑上的概率；求出任意一個節(jié)點與目標節(jié)點集之間的距離度量或差異度量；根據(jù)格局（博弈問題）或狀態(tài)的特點來打分。即根據(jù)問題的啟發(fā)信息，從概率角度、差異角度或記分法給出計算啟發(fā)函數(shù)的方法。狀態(tài)圖搜索——啟發(fā)式搜索啟發(fā)函數(shù)（Heuristicfun35狀態(tài)圖搜索——全局擇優(yōu)搜索

對OPEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。步1、把初始節(jié)點S0放入OPEN表中，計算h(S0)；步2、若OPEN表為空，則搜索失??；退出。步3、取OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序號n；步4、若目標節(jié)點Sg=N，則搜索成功，結(jié)束。步5、若N不可擴展，則轉(zhuǎn)步2；步6、擴展N，計算每個子節(jié)點的函數(shù)值h(x)，將所有子節(jié)點配上指向N的指針，依次放入OPEN表中，再對OPEN表中的所有子節(jié)點按其函數(shù)值大小升序排列，轉(zhuǎn)步2。狀態(tài)圖搜索——全局擇優(yōu)搜索對OPEN表中的所有節(jié)點排序，使36狀態(tài)圖搜索——局部擇優(yōu)這是對于上述深度優(yōu)先法的改進，僅對新擴展出來的子節(jié)點排序，使這些節(jié)點中最有希望者能優(yōu)先取出考察和擴展。步1、把初始節(jié)點S0放入OPEN表中，計算h(S0)；步2、若OPEN表為空，則搜索失??；退出。步3、取OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序號n；步4、若目標節(jié)點Sg=N，則搜索成功，結(jié)束。步5、若N不可擴展，則轉(zhuǎn)步2；步6、擴展N，計算每個子節(jié)點的函數(shù)值h(x)，將子節(jié)點配上指向N的指針，按其函數(shù)值大小升序排列依次放入OPEN表首部，轉(zhuǎn)步2。狀態(tài)圖搜索——局部擇優(yōu)這是對于上述深度優(yōu)先法的改進，僅對新37加權(quán)狀態(tài)圖加權(quán)狀態(tài)圖：具有權(quán)值的狀態(tài)圖。代價樹：屬性的加權(quán)狀態(tài)圖。代價：表示兩點之間的距離、交通費用或所需的時間。通常用g(x)表示從初始節(jié)點S0到節(jié)點x的代價，用c(xi,xj)表示父節(jié)點xi到子節(jié)點xj的代價，即邊(xi,xj)的代價。g(xj)=g(xi)+c(xi,xj)g(S0)=0加權(quán)狀態(tài)圖加權(quán)狀態(tài)圖：具有權(quán)值的狀態(tài)圖。38加權(quán)狀態(tài)圖搜索——分支界限法分支界限法是優(yōu)先擴展當前具有最小代價分支路徑的端節(jié)點n，其啟發(fā)函數(shù)為f(n)=g(n)。算法的基本思想建立一個局部路徑（或分支）的隊列表，每次都選代價最小的那個分支上的端節(jié)點來擴展，直到生成出含有目標節(jié)點的路徑為止。加權(quán)狀態(tài)圖搜索——分支界限法分支界限法是優(yōu)先擴展當前具有最39加權(quán)狀態(tài)圖搜索——最近擇優(yōu)法最近擇優(yōu)法（瞎子爬山法）：類似于局部擇優(yōu)法h(n)。特點：只能向上，不準后退，從而簡化了搜索算法；爬山法對于單一極值問題（登單一山峰）十分有效而又簡便。對于具有多極值的問題無能為力——會錯登上次高峰而失敗：不能到達最高峰。加權(quán)狀態(tài)圖搜索——最近擇優(yōu)法最近擇優(yōu)法（瞎子爬山法）：類似于40啟發(fā)式圖搜索——估價函數(shù)估價函數(shù)（Evaluationfunction）估價函數(shù)f設(shè)計為：f(n)=g(n)+h(n)n——搜索圖中的某個當前被擴展的節(jié)點；f(n)——從初始狀態(tài)節(jié)點s,經(jīng)由節(jié)點n到達目標節(jié)點ng，，估計的最小路徑代價；g(n)——從s到n,估計的最小路徑代價；h(n)——從n到ng,估計的最小路徑代價。啟發(fā)式圖搜索——估價函數(shù)估價函數(shù)（Evaluationf41啟發(fā)式圖搜索——A算法利用估價函數(shù)f（n）＝g（n）＋h（n）來排列OPEN表節(jié)點順序的圖搜索算法稱為算法A。g(n)值——取至今已發(fā)現(xiàn)的自s到n的最短路徑.h(n)值——依賴于啟發(fā)式知識來加以估算.每次按照f(n)值的大小對OPEN表中的元素進行排序，f值小的節(jié)點放在前面，而f值大的節(jié)點則被放在OPEN表的后面，這樣每次擴展節(jié)點時，都是選擇當前f值最小的節(jié)點來優(yōu)先擴展。啟發(fā)式圖搜索——A算法利用估價函數(shù)f（n）＝g（n）＋h42最佳圖搜索算法——A*算法當在算法A的估價函數(shù)中，使用的啟發(fā)函數(shù)h(n)是處在h*(n)的下界范圍，即滿足h(n)≤h*(n)時，則我們把這個算法稱為算法A*。h*(n)：表示從節(jié)點n到目標節(jié)點g的最小代價。最佳圖搜索算法——A*算法當在算法A的估價函數(shù)中，使用的啟432.3問題歸約法問題歸約描述先把問題分解為子問題和子-子問題，然后解決較小的問題。對該問題的某個具體子集的解答就意味著對原始問題的一個解答。問題歸約表示的組成部分：一個初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。問題歸約的實質(zhì)：從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。2.3問題歸約法問題歸約描述44與或圖表示

用一個類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，這種結(jié)構(gòu)圖叫做問題歸約圖，或叫與或圖。

與或圖表示用一個類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替45與或圖搜索與或圖基本概念與或圖搜索啟發(fā)式與或樹搜索解樹代價計算方法最大代價法和代價法與或樹的有序搜索與或圖搜索與或圖基本概念46與或圖基本概念與或圖：圖中既有與關(guān)系又有或關(guān)系，與關(guān)系的邊之間用弧線表示，或關(guān)系不用弧線表示。與或圖與狀態(tài)圖的關(guān)系：與或圖是狀態(tài)圖的推廣，狀態(tài)圖是與或圖的特例。解圖（解樹）：與或圖的解是一個圖或路徑，因此稱為解圖或解樹。即由可解節(jié)點形成的一個子圖（樹）。與或圖基本概念與或圖：圖中既有與關(guān)系又有或關(guān)系，與關(guān)系的邊之47與或圖基本概念本原問題：直接可解的簡單問題。終止節(jié)點：本原問題對應的節(jié)點稱為終止節(jié)點?？山獾亩斯?jié)點。端節(jié)點：無子節(jié)點的節(jié)點。與節(jié)點：一個節(jié)點的子節(jié)點如果是“與”關(guān)系，該節(jié)點稱為與節(jié)點。或節(jié)點：一個節(jié)點的子節(jié)點如果是“或”關(guān)系，該節(jié)點稱為或節(jié)點。終止節(jié)點和端節(jié)點的關(guān)系：終止節(jié)點一定是端節(jié)點，端節(jié)點不一定是終止節(jié)點。與或圖基本概念本原問題：直接可解的簡單問題。48與或圖搜索——可解性判別節(jié)點可解的判斷，滿足下列條件之一：終止節(jié)點是可解的。一個與節(jié)點是可解的，當且僅當其子節(jié)點全部都可解。一個或節(jié)點是可解的，只要其子節(jié)點至少有一個可解。與或圖搜索——可解性判別節(jié)點可解的判斷，滿足下列條件之一：49與或圖搜索——不可解性判別節(jié)點不可解的判斷，滿足下列條件之一：非終止節(jié)點是不可解的。一個與節(jié)點是不可解的，只要其子節(jié)點至少有一個不可解。一個或節(jié)點是可解的，當且僅當其子節(jié)點全部都不可解。與或圖搜索——不可解性判別節(jié)點不可解的判斷，滿足下列條件之一50與或圖搜索搜索方式同狀態(tài)圖一樣。樹式搜索線式搜索與或圖搜索搜索方式51與或圖搜索——搜索策略盲目搜索窮舉搜索深度優(yōu)先和廣度優(yōu)先盲目碰撞搜索啟發(fā)式搜索與或圖搜索——搜索策略盲目搜索52與或圖搜索算法注意：考察節(jié)點的可解性。CLOSED表中放的是可解節(jié)點。與或圖搜索算法注意：53啟發(fā)式與或樹搜索有序搜索根據(jù)代價決定搜索路線的方法稱為與或樹的有序搜索。解樹的代價（樹根的代價）：從樹葉開始自下而上逐層計算。與狀態(tài)圖剛好相反。

啟發(fā)式與或樹搜索有序搜索54解樹代價計算方法終止節(jié)點的代價為0；或節(jié)點的代價為各子節(jié)點到該節(jié)點的最小代價。與節(jié)點的代價有兩種計算方法：和代價法：各子節(jié)點到該節(jié)點的代價之和；最大代價法：各子節(jié)點到該節(jié)點的最大代價。解樹代價計算方法終止節(jié)點的代價為0；55啟發(fā)式與或樹搜索——希望樹最有希望成為最優(yōu)解樹一部分的節(jié)點及其先輩節(jié)點所構(gòu)成的與或樹稱為希望樹。啟發(fā)式與或樹搜索——希望樹最有希望成為最優(yōu)解樹一部分的節(jié)點及56與或樹的有序搜索過程類似于加權(quán)狀態(tài)圖中的全局擇優(yōu)搜索法，有兩點區(qū)別：考察節(jié)點的可解性；重新計算代價。與或樹的有序搜索過程類似于加權(quán)狀態(tài)圖中的全局擇優(yōu)搜索法，有兩57博弈博弈的概念極小極大分析法（Minimax）α－β剪枝法（Alpha-betaPruning）博弈博弈的概念58博弈的概念雙人對弈，對壘的雙方輪流走步。全信息，對壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。零和。即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利、或均無利的棋。對弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。博弈的概念雙人對弈，對壘的雙方輪流走步。59博弈樹的概念描述博弈過程的與或樹稱為博弈樹。特點：博弈的初始格局是初始節(jié)點。在博弈中，“或”節(jié)點和“與”節(jié)點逐層交替出現(xiàn)。自己一方擴展的節(jié)點是“或”關(guān)系，對方擴展的節(jié)點是“與”關(guān)系。雙方輪流地擴展節(jié)點。所有自己一方獲勝的終局都是本原問題，相應的節(jié)點是可解節(jié)點，所有使對方獲勝的終局都是不可解節(jié)點。博弈樹的概念描述博弈過程的與或樹稱為博弈樹。60博弈樹的搜索——極小極大分析法（Minimax）極小極大搜索方法是博弈樹搜索的基本方法。按照一定的搜索深度生成出給定深度d以內(nèi)的所有狀態(tài)，計算所有葉節(jié)點的評價函數(shù)值。博弈樹的搜索——極小極大分析法（Minimax）極小極大搜索61博弈樹的搜索——極小極大分析法（Minimax）從d-1層節(jié)點開始逆向計算：對于我方要走的節(jié)點（用MAX標記，稱為極大節(jié)點）取其子節(jié)點中的最大值為該節(jié)點的值（因為我方總是選擇對我方有利的棋）；對于對方要走的節(jié)點（用MIN標記，稱為極小節(jié)點）取其子節(jié)點中的最小值為該節(jié)點的值（對方總是選擇對我方不利的棋）。一直到計算出根節(jié)點的值為止。獲得根節(jié)點取值的那一分枝，即為所選擇的最佳走步。

博弈樹的搜索——極小極大分析法（Minimax）從d-1層節(jié)62博弈樹的搜索——極小極大分析法靜態(tài)估計函數(shù)f功能：對棋局的勢態(tài)（節(jié)點）作出優(yōu)劣估值。定義方法：根據(jù)勢態(tài)優(yōu)劣特征來定義（主要用于對端節(jié)點的“價值”進行度量）。一般規(guī)定有利于MAX的勢態(tài)，f（p）取正值，有利于MIN的勢態(tài)，f（p）取負值；勢均力敵的勢態(tài)，f（p）取0值；若f（p）＝＋∞，則表示MAX贏；若f（p）＝－∞，則表示MIN贏。博弈樹的搜索——極小極大分析法靜態(tài)估計函數(shù)f功能：63博弈樹的搜索倒推值計算方法由靜態(tài)估計函數(shù)求得父節(jié)點的倒推值方法是：從下往上逐層交替使用極小和極大的選值方法，故稱極小極大過程。博弈樹的搜索倒推值計算方法由靜態(tài)估計函數(shù)求得父節(jié)點的倒推值方64極小極大分析法例子——3×3棋盤的一字棋設(shè)程序方MAX的棋子用（×）表示，對手MIN的棋子用（○）表示，MAX先走。靜態(tài)估計函數(shù)f(p)規(guī)定如下：若p對任何一方來說都不是獲勝的格局，則f(p)＝(所有空格都放上MAX的棋子之后，MAX的三子成線(行、列、對角）的總數(shù)－(所有空格都放上MIN的棋子之后，MIN的三子成線(行、列、對角)的總數(shù))若p是MAX獲勝的格局，則f(p)＝∞；若p是MIN獲勝的格局，則f(p)＝－∞。例如，當p的格局如上時，則可得f(p)＝6－4＝2極小極大分析法例子——3×3棋盤的一字棋設(shè)程序方MAX的棋65極小極大分析法例子——3×3棋盤的一字棋第一階段搜索樹極小極大分析法例子——3×3棋盤的一字棋第一階段66第二階段搜索樹第二階段搜索樹67第三階段搜索樹第三階段搜索樹68博弈樹的搜索——α－β剪枝法（Alpha-betaPruning）極小極大搜索方法存在的問題：把搜索樹的生成和格局估值這兩個過程分開來進行，即先生成全部搜索樹，然后再進行端節(jié)點靜態(tài)估值和倒推值計算，這顯然會導致低效率。要先生成指定深度以內(nèi)的所有節(jié)點，其節(jié)點數(shù)將隨著搜索深度的增加呈現(xiàn)指數(shù)增長的