知識(shí)表示與推理課件

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

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

CLOSED表編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)

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

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

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

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

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

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

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