人工智能及專家系統(tǒng)第3章--圖搜索技術(shù)課件

1、第3章 圖搜索技術(shù) 31 圖搜索及其分類311 圖搜索的概念312 圖搜索的分類313 狀態(tài)圖搜索樹314 狀態(tài)空間搜索算法315 搜索效率32 窮舉式搜索321 廣度優(yōu)先搜索322 深度優(yōu)先搜索323 有界深度優(yōu)先搜索324 代價(jià)驅(qū)動(dòng)搜索 第3章 圖搜索技術(shù)33 啟發(fā)式搜索331 啟發(fā)式搜索的基本概念332 局部擇優(yōu)搜索333 全局擇優(yōu)搜索334 與/或圖的啟發(fā)式搜索335 博弈樹的啟發(fā)式搜索336 -剪枝技術(shù) 第3章 圖搜索技術(shù) 3.1.1 圖搜索的概念圖是節(jié)點(diǎn)及連接它們的弧的集合。 搜索具有尋找、搜查、掃描、檢索的意義。它是在圖中尋找目標(biāo)或路徑的基本方法；也就是說(shuō)，利用已有知識(shí)逐步摸索求

2、解,根據(jù)問(wèn)題的實(shí)際情況，不斷尋找可利用知識(shí)，使問(wèn)題得以解決的過(guò)程稱為搜索。搜索的目的是以盡可能低的耗費(fèi)求得所需要的解。圖搜索，就是從初始節(jié)點(diǎn)出發(fā)，沿著與之相連的弧試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過(guò)程(也可以反向進(jìn)行)。 樹式搜索和線式搜索樹式搜索就是以“畫樹”的方式進(jìn)行搜索。即從樹根(初始節(jié)點(diǎn))出發(fā)，一筆一筆地描出一棵樹來(lái)。 線式搜索就是以“畫線”的方式進(jìn)行搜索。線式搜索所記錄的軌跡始終是一條線或折線。一般情況下，樹式搜索成功后，還需再?gòu)乃阉鳂渲姓页鏊舐窂?，而線式搜索只要搜索成功，則“搜索線”就是所找的路徑，即問(wèn)題的解。312 圖搜索的分類1 從求解要求看，可分為三種情況： 最佳值搜索。在這種情況

3、下，值附在圖的各終節(jié)點(diǎn)，搜索的目的就是去找出具有最佳值的終節(jié)點(diǎn)，例如博弈問(wèn)題的搜索就是屬于這一類問(wèn)題。 最短路徑搜索。搜索的目的是找出從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑。例如，巡回售貨員問(wèn)題。 滿足性搜索。有些問(wèn)題可能有多個(gè)解，有些問(wèn)題只有一個(gè)解，采用滿足性搜索，即只要找到一個(gè)解即可。例如，定理證明和大多數(shù)問(wèn)題求解。2.按搜索方向分，有三種情況：正向搜索：是從初始狀態(tài)向目標(biāo)狀態(tài)的方向搜索，有時(shí)也稱為數(shù)據(jù)驅(qū)動(dòng)搜索。搜索的過(guò)程即應(yīng)用規(guī)則從給定條件產(chǎn)生新條件，再用規(guī)則從新條件產(chǎn)生更多的新條件。反向搜索：是從目標(biāo)狀態(tài)向初始狀態(tài)的方向搜索，即目標(biāo)驅(qū)動(dòng)搜索。方法是先從目標(biāo)入手，看哪些規(guī)則或合法移動(dòng)能產(chǎn)生該目標(biāo)

4、以及應(yīng)用這些規(guī)則產(chǎn)生目標(biāo)時(shí)需要哪些條件。搜索就通過(guò)反向的、連續(xù)的子目標(biāo)不斷地進(jìn)行，一直到找到問(wèn)題給定的條件為止。雙向搜索：同時(shí)從目標(biāo)狀態(tài)和初始狀態(tài)出發(fā)進(jìn)行搜索。 正向搜索可用于下列情況: l問(wèn)題的初始說(shuō)明給出了全部或大部分?jǐn)?shù)據(jù)的系統(tǒng)。解釋程序常常如此，它提供一批采集的數(shù)據(jù)，要求系統(tǒng)對(duì)此作出進(jìn)一步的解釋。l存在大量可能的目標(biāo)，但對(duì)實(shí)際問(wèn)題的條件及給定的信息加以運(yùn)用的方法很少的系統(tǒng)。l 難以形成一個(gè)目標(biāo)或假設(shè)的系統(tǒng)。 對(duì)下列情況建議采用反向搜索:l問(wèn)題的說(shuō)明中給出了目標(biāo)或假設(shè)，或者很容易用公式來(lái)表示它們的系統(tǒng)。l有大量的規(guī)則適用于問(wèn)題的條件的系統(tǒng)。在這種情況下，可以推出許多結(jié)論和結(jié)果，較早地選好目

5、標(biāo)可剪掉空間中許多分枝，使反向搜索的效率更高。l問(wèn)題沒有給出數(shù)據(jù)，必須在求解中獲取的系統(tǒng)。這種情況下，反向搜索可以幫助指導(dǎo)數(shù)據(jù)的獲取。l分析特定數(shù)據(jù)的系統(tǒng)。3按照搜索的內(nèi)容分 窮舉式搜索 圖搜索廣度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索一致代價(jià)搜索 啟發(fā)式搜索局部擇優(yōu)搜索全局擇優(yōu)搜索與/或圖啟發(fā)式搜索極大極小搜索、剪枝搜索 313 狀態(tài)圖搜索樹 圖3-1 狀態(tài)圖搜索樹 L M E F G H I J K B C D A 樹根樹枝葉節(jié)點(diǎn)I、J、K是D的子節(jié)點(diǎn)D是I、J、K的父節(jié)點(diǎn)A是I、J、K的先輩節(jié)點(diǎn)中間節(jié)點(diǎn)一層二層三層例、巡回推銷員問(wèn)題。 B A D C 4 7 10 6 10 5圖3-2 4

6、城市路線圖3-3 巡回推銷員問(wèn)題狀態(tài)圖搜索樹 A 4 6 10AB AC AD 7 10 7 5 10 5ABC ABD ACB ACD ADB ADC 5 5 10 10 7 7ABCD ABDC ACBD ACDB ADBC ADCB 10 6 10 4 6 4ABCDA ABDCAACBDAACDBA ADBCA ADCBA 26 25 33 25 33 26路徑長(zhǎng)度314 狀態(tài)空間搜索算法解決問(wèn)題時(shí)，有以下的因素需要考慮:1計(jì)算機(jī)無(wú)法保存其全部狀態(tài)空間；2與解有關(guān)的狀態(tài)空間一般僅是全部狀態(tài)空間的一部分。3是否一定能找到一個(gè)解？4是否能終止運(yùn)行，或是否會(huì)陷入一個(gè)死循環(huán)？5是否找到的是最好

7、解？6搜索過(guò)程的時(shí)間與空間復(fù)雜性如何？7怎樣才能最有效地降低搜索的復(fù)雜性？8 怎樣設(shè)計(jì)才能最有效地利用描述語(yǔ)言? Open表和Closed表 Closed表編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)12345 Open表節(jié)點(diǎn) 父節(jié)點(diǎn) 編號(hào)315 搜索效率搜索效率P定義為： P = L / T L從初始狀態(tài)到目標(biāo)狀態(tài)的路長(zhǎng)T節(jié)點(diǎn)的總數(shù) (不包括初始節(jié)點(diǎn)) 另一種度量方法稱有效的分枝因素B。它代表在搜索過(guò)程中每個(gè)有效節(jié)點(diǎn)平均生成子節(jié)點(diǎn)數(shù)目。設(shè)L是節(jié)點(diǎn)的深度 (或路長(zhǎng))，則T = B+B2+B3+BL=(BBBL)/(1 B) 從而可得P=L/T = L(1 B)/(B BBL) 32 窮舉式搜索 特點(diǎn)搜索效率低，控制策略

8、差，占用較大的存儲(chǔ)空間；但它控制性知識(shí)簡(jiǎn)單，是啟發(fā)式搜索的基礎(chǔ)。為了簡(jiǎn)化問(wèn)題的討論，對(duì)下面幾種窮舉式搜索方法作如下假設(shè)：1搜索空間是一棵樹，即只有一個(gè)初始節(jié)點(diǎn)，任意兩個(gè)節(jié)點(diǎn)之間的路徑是唯一的。2. 任何一個(gè)節(jié)點(diǎn)擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)包含有返回父節(jié)點(diǎn)的指針。當(dāng)目標(biāo)節(jié)點(diǎn)產(chǎn)生時(shí)，利用此特征很易求得解答。 321 廣度優(yōu)先搜索概念與特點(diǎn)廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種按“先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”原則進(jìn)行的搜索，也即一層一層進(jìn)行的搜索。搜索過(guò)程是:從初始節(jié)點(diǎn)So開始逐層向下擴(kuò)展，先生成下一級(jí)各子節(jié)點(diǎn)，按順序(先生成的子節(jié)點(diǎn)，優(yōu)先檢查，優(yōu)先擴(kuò)展)檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)Sg。按此方法，若在第n層節(jié)點(diǎn)（此層無(wú)目

9、標(biāo)節(jié)點(diǎn)）還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。也就是說(shuō)，廣度優(yōu)先的搜索樹是自頂向下一層一層逐漸生成的，一直到找到目標(biāo)節(jié)點(diǎn)為止。 廣度優(yōu)先搜索節(jié)點(diǎn)的擴(kuò)展順序 圖3-5 節(jié)點(diǎn)擴(kuò)展順序G H Sg C D E F A BSo搜索算法流程圖 否否否是是是 啟動(dòng) 把So放入Open表中取Open表中最前面的節(jié)點(diǎn)N放入Closed表中，并冠以順序號(hào)Open為空嗎？ N= Sg ？成功N可擴(kuò)展 嗎？擴(kuò)展N，將其子節(jié)點(diǎn)依次放入Open表的末尾，并配上指向N的返回指針失敗圖3-6 廣度優(yōu)先搜索流程圖示例 例3-2 重排九宮問(wèn)題：如圖3-7所示，在33的方格棋盤上，放置8個(gè)標(biāo)有數(shù)碼的紙牌(1、2、8)

10、，并留下一個(gè)空格。只允許把空格上、下、左、右的紙牌移入空格。要求尋找一條從初始狀態(tài)So到目標(biāo)狀態(tài)Sg的最短移動(dòng)路線。 初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-7 重排九宮問(wèn)題生成的搜索樹 2348 9 10 11 12616 17 18 19 20Sg圖3-8 重排九宮問(wèn)題的廣度優(yōu)先搜索搜索樹 24322 深度優(yōu)先搜索深度優(yōu)先搜索法的概念 深度優(yōu)先搜索是一種后生成的節(jié)點(diǎn)先擴(kuò)展、不撞墻不回頭的搜索方法。在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)。圖3-9 深度優(yōu)先搜索 節(jié)點(diǎn)擴(kuò)展順序前已搜索 無(wú)解 Sg6 C 7 5 34 2A B 1 So搜索算法流程圖 24否否否是是是 啟動(dòng)把So放入O

11、pen表中取Open表中最前面的節(jié)點(diǎn)N放入Closed表中，并冠以順序號(hào)Open為空嗎？N= Sg ？成功N可擴(kuò)展 嗎？擴(kuò)展N，將其子節(jié)點(diǎn)依次放入Open表的首部，并配上指向N的返回指針失敗圖3-10 深度優(yōu)先搜索流程圖示例 例3-3 利用深度優(yōu)先搜索求解如圖3-11所示的重排九宮問(wèn)題。初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-11 重排九宮問(wèn)題生成的搜索樹圖3-12 重排九宮問(wèn)題的深度優(yōu)先搜索樹深度優(yōu)先搜索策略是不完備的，帶有一定的冒險(xiǎn)性。另外，應(yīng)用此策略得到的解不一定是最佳解(最短路徑)。 323 有界深度優(yōu)先搜索 在深度優(yōu)先搜索法中，要給出一個(gè)深度限制dm。當(dāng)從初始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展到dm深度

12、，但還沒有找到目標(biāo)時(shí)，就不能再繼續(xù)向下擴(kuò)展，而只能改變方向繼續(xù)搜索。 圖3-13 有界深度搜索節(jié)點(diǎn)擴(kuò)展順序 Sg C 6 5 34 2A B 1 Sod =dm=3,強(qiáng)迫返回d (深度) 12 3搜索算法流程圖圖3-14 有界深度優(yōu)先搜索流程圖是否否是啟動(dòng)把So放入Open表中，置深度d（So）=0取Open表中最前面的節(jié)點(diǎn)N放入Closed表中，并冠以順序號(hào)Open為空嗎？N= Sg ？成功失敗是否d（N）= dm？否是N可擴(kuò)展 嗎？擴(kuò)展N，將其子節(jié)點(diǎn)依次放入Open表的首部，并配上指向N的返回指針置 d（N）= d（N）+ 1示例 例3-4 用有界深度優(yōu)先搜索法求解圖3-11重排九宮問(wèn)題，

13、取深度限界dm = 4。初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-11 重排九宮問(wèn)題生成的搜索樹搜索效率P = L / T = 4 / 27 0.148 圖3-15 重排九宮問(wèn)題的有界深度優(yōu)先搜索搜索樹324 一致代價(jià)搜索 1. 一致代價(jià)搜索的概念 在狀態(tài)空間中，通常把代價(jià)記在邊(弧)上在代價(jià)樹中，用C(n1，n2)表示從父節(jié)點(diǎn)n1到其子節(jié)點(diǎn)n2的代價(jià)，用g(n1)表示從初始節(jié)點(diǎn)So 到節(jié)點(diǎn)n1的代價(jià)。這樣，對(duì)So到節(jié)點(diǎn)n2的總代價(jià)為 g(n2)=g(n1)十C(n1，n2) 2. 一致代價(jià)廣度優(yōu)先搜索法 一致代價(jià)的廣度優(yōu)先搜索也稱為分枝界限法，在同一級(jí)各節(jié)點(diǎn)中，取代價(jià)最小的節(jié)點(diǎn)優(yōu)先擴(kuò)展，從而求得總代價(jià)

14、最小的路徑。一致代價(jià)廣度優(yōu)先搜索方法是完備的。如果問(wèn)題有解，就一定能夠找到解，并且找到的一定是最優(yōu)解。 搜索算法流程圖 圖3-16 代價(jià)驅(qū)動(dòng)廣度優(yōu)先搜索流程圖否把So放入Open表中，置g(So)=0否否是是是 啟動(dòng)取Open表中最前面的節(jié)點(diǎn)N放入Closed表中，并冠以順序號(hào)Open為空嗎？N= Sg ？成功N可擴(kuò)展 嗎？失敗擴(kuò)展N，將其子節(jié)點(diǎn)Ni放入Open表中，配上指向N的返回指針，計(jì)算并按g(Ni)重新對(duì)Open表排序(小的在前)示例 2343625BCADE圖3-17 5城市交通路線圖3-18 5城市交通路線代價(jià)樹E4B1ABCC1E1E2 E3D1E5D2 326 63254So3

15、43. 一致代價(jià)深度優(yōu)先搜索 一致代價(jià)深度優(yōu)先搜索和一致代價(jià)廣度優(yōu)先搜索的區(qū)別在于每次選擇最小代價(jià)節(jié)點(diǎn)的方法不同。后者每次都是從Open表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，而前者則是從剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)。 33 啟發(fā)式搜索 331 啟發(fā)式搜索的基本概念 盡管有些問(wèn)題是處在完備知識(shí)的環(huán)境中，其解是完全確定了的，理論上也能找到解決問(wèn)題的算法，但在工程實(shí)踐中，這些算法不是效率太低，就是無(wú)法實(shí)現(xiàn)。為此，不得不放棄理論性算法，改用經(jīng)驗(yàn)性的啟發(fā)式方法。 1. 啟發(fā)式搜索的基本思想 啟發(fā)式搜索是在控制性知識(shí)中增加關(guān)于被解問(wèn)題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信息來(lái)確定節(jié)點(diǎn)的生成、擴(kuò)展和搜

16、索順序，以便指導(dǎo)搜索向最有希望的方向前進(jìn)。 下一步展開哪個(gè)節(jié)點(diǎn)？是部分展開還是全部展開？使用哪個(gè)規(guī)則(算子)？怎樣決定舍棄還是保留新生成的節(jié)點(diǎn)？怎樣決定舍棄還是保留一棵子樹？怎樣決定停止或繼續(xù)搜索？如何定義啟發(fā)函數(shù)(估值函數(shù))？如何決定搜索方向？ 2. 啟發(fā)式搜索的特點(diǎn) 大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度方向小范圍前進(jìn)； 在多條路可走時(shí)，建議該走哪條路徑，從而指導(dǎo)搜索過(guò)程朝最有利的方向前進(jìn)； 利用問(wèn)題求解的先驗(yàn)知識(shí)，使問(wèn)題盡快找到解； 可采用估值的方法進(jìn)行搜索指導(dǎo)； 生成的狀態(tài)空間小、搜索時(shí)間短且效率高、控制性好，易于使問(wèn)題得到解決。3. 啟發(fā)性信息的類型 啟發(fā)性信息一

17、般有以下三種: 有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息全局擇優(yōu)搜索法 。 有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息局部擇優(yōu)搜索法 能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹上刪除（或剪掉）的信息剪枝技術(shù) 。 4. 估價(jià)函數(shù) 一般形式是: f(n)=g(n)+h(n)其中g(shù)(n)是從So到n的實(shí)際代價(jià)，h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)Sg的估計(jì)代價(jià)。 332 局部擇優(yōu)搜索1. 基本思想局部擇優(yōu)搜索法又稱爬山法，其基本思想是，搜索到一個(gè)節(jié)點(diǎn)后，只從其所有后繼子節(jié)點(diǎn)中，按f(x)選擇最優(yōu)者，也就是在后繼子節(jié)點(diǎn)的局部范圍內(nèi)選擇最優(yōu)者進(jìn)行擴(kuò)展，選取最有希望逼近目標(biāo)節(jié)點(diǎn)的方向，逐級(jí)沿縱向深度進(jìn)行搜索。由于是小范圍內(nèi)的局部

18、優(yōu)選，故稱之為局部擇優(yōu)搜索法。適用于單峰極值、單因素問(wèn)題。局部擇優(yōu)搜索法，是不完備的推理方法。 算法流程圖 N可擴(kuò)展 嗎？N= Sg ？圖3-19 局部擇優(yōu)搜索流程圖是否是否失敗 啟動(dòng)成功 把So放入Closed表，置N= So擴(kuò)展N，用f（x）選擇N的最優(yōu)子節(jié)點(diǎn)N并放入Closed表，設(shè)返回指針，令N=N示例 例3-6 用局部擇優(yōu)搜索重排九宮問(wèn)題 。 定義估價(jià)函數(shù)f（n）= h（n）為：取節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)Sg兩個(gè)格局中位置不符合的將牌數(shù)目。 初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-11 重排九宮問(wèn)題生成的搜索樹 圖3-20 重排九宮局部擇優(yōu)搜索樹搜索效率 P = L / T = 8 / 17 0.4

19、7333 全局擇優(yōu)搜索 1. 概念全局擇優(yōu)搜索又稱最好優(yōu)先搜索和有序搜索。它避免爬山法的缺點(diǎn)，不是在局部節(jié)點(diǎn)中擇優(yōu)，而是在全部節(jié)點(diǎn)中擇優(yōu)。它在OPEN表中保留了所有已生成但尚未擴(kuò)展的節(jié)點(diǎn)，并用估價(jià)函數(shù)f(n)對(duì)它們?nèi)慷歼M(jìn)行估值。不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹的任何地方，都從中選出最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展。 最好優(yōu)先搜索法比爬山法更有希望接近找到最佳解；但也不一定完備。原因在于估價(jià)函數(shù)f(n)的設(shè)計(jì)不一定是最佳的，按f（n）找出的最好解不一定是實(shí)際上的最佳解。 算法流程圖 圖3-21 全局擇優(yōu)搜索流程圖否否否是是是 啟動(dòng)把So放入Open表中，計(jì)算f (So)取Open表中最前面的節(jié)點(diǎn)N放入Closed表

20、中，并冠以順序號(hào)Open為空嗎？N= Sg ？成功N可擴(kuò)展 嗎？擴(kuò)展N并用f (x)估計(jì)每個(gè)子節(jié)點(diǎn)Ni，依次放入Open表及配上指向N的返回指針，利用f (x)對(duì)Open表重新排序，小的在前失敗示例 例3-7 應(yīng)用全局擇優(yōu)搜索法求解重排九宮問(wèn)題 初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-11 重排九宮問(wèn)題算法流程圖 圖3-22 重排九宮全局擇優(yōu)搜索樹估價(jià)函數(shù)的一個(gè)較好的定義 h(n) = P(n) + 3S(n)其中P(n)是每個(gè)將牌離“家”（Sg格局中的位置）最短距離的總和。如圖3-22所示，So格局P(n)得分為：So中的 1 2 3 4 5 6 7 8P(So) = 2 + 1 + 1 + 1 +

21、 0 + 0 + 0 + 2 = 7(分) 初始狀態(tài)So 目標(biāo)狀態(tài)Sg圖3-22 重排九宮問(wèn)題S（n）的計(jì)算S（n）是這樣來(lái)計(jì)算的，沿著周圍那些非中心方格上依順時(shí)針方向檢查n格局中的每一個(gè)將牌，如果其后緊跟著的將牌正好是目標(biāo)格局中該將牌的后續(xù)者的話，該將牌得0分，否則得2分，在正中方格中的將牌得1分。所有將牌得分之和為S（n）。如圖3-22中，So格局S（So）得分為：So中的將牌：1 2 3 4 5 6 7 8 S(So) = 2 + 2 + 2 + 1 + 0 + 0 + 2 + 0 = 9(分)所以 h(So) = P(So) + 3S(So) = 7 + 3 9 = 34(分)在更一般

22、的情況下，估價(jià)函數(shù)可取以下形式： f(n) = g(n) + W h(n) 其中W是一個(gè)起調(diào)整作用的正實(shí)數(shù)。W提高則強(qiáng)調(diào)啟發(fā)信息的作用，W降低則強(qiáng)調(diào)先寬度搜索向后縱深的搜索趨勢(shì)。經(jīng)驗(yàn)表明，W值與樹的深度成反比時(shí)可以提高搜索效率。 334 與/或圖的啟發(fā)式搜索1. 與/或圖一般搜索 與/或樹的一般搜索過(guò)程實(shí)際上是一個(gè)不斷尋找解樹的過(guò)程。其一般搜索過(guò)程如下: 把原始問(wèn)題作為初始節(jié)點(diǎn)So ，并把它作為當(dāng)前節(jié)點(diǎn)； 應(yīng)用分解或等價(jià)變換操作，擴(kuò)展當(dāng)前節(jié)點(diǎn)或由估計(jì)函數(shù)f指示的優(yōu)先節(jié)點(diǎn)，如果其子節(jié)點(diǎn)是幾組具有與關(guān)系的子節(jié)點(diǎn)集合的或，就分二級(jí)擴(kuò)展； 為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針； 選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)

23、點(diǎn)，反復(fù)執(zhí)行第2步和第3步 。與或樹的二級(jí)擴(kuò)展 a1a2a3 b1 b2 b3 b4 b5 b6 b7 b8圖3-24 與/或節(jié)點(diǎn)的擴(kuò)展b1 b2 b3 b4 b5 b6 b7 b8與或圖的解樹由導(dǎo)致根節(jié)點(diǎn)為可解節(jié)點(diǎn)的有關(guān)可解節(jié)點(diǎn)及樹枝所組成的子樹，稱為該問(wèn)題解樹。 與/或樹的啟發(fā)式搜索過(guò)程是一種利用搜索過(guò)程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過(guò)程。即試圖找到一個(gè)最有希望成為代價(jià)最小的那棵解樹。2. 與/或圖解樹的代價(jià) 與節(jié)點(diǎn)代價(jià)的計(jì)算 若n為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1、n2、nk，則n的代價(jià)有兩種計(jì)算方法： 最大代價(jià)其中c(n，ni)是節(jié)點(diǎn)n到其子節(jié)點(diǎn)ni的邊代價(jià)，h（ni)是對(duì)節(jié)點(diǎn)ni的估計(jì)代價(jià)。

24、 和代價(jià)取它們的和作為代價(jià)h（n）。 或節(jié)點(diǎn)代價(jià)的計(jì)算 若n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1、n2、nk，則n的代價(jià)為: 即取它們的最小值作為代價(jià)h（n）。 其他特殊節(jié)點(diǎn)代價(jià)的計(jì)算 若n是可解節(jié)點(diǎn)，即為終止節(jié)點(diǎn)，則其代價(jià)h(n) = 0。 若端節(jié)點(diǎn)n為不可解節(jié)點(diǎn)，又不是終止節(jié)點(diǎn)，不可擴(kuò)展，其代價(jià)定義為h(n) = 。 根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。示例例3-8 求圖3-25與/或圖解樹的總代價(jià)，其中t表示終止節(jié)點(diǎn)，表示不可解節(jié)點(diǎn)。 S0 t t t t t4 45 6 2 41 2 3 4圖3-25 與/或圖的解樹a bc d e fg p 2 4 4 3 2 1 5 73. 希望解樹 在與/或樹的啟發(fā)

25、式搜索中，希望解樹是對(duì)最佳解樹的近根部分的某種估計(jì)。0的定義如下： 初始節(jié)點(diǎn)S0在希望解樹0中； 如果n是具有子節(jié)點(diǎn)n1、n2、nk的或節(jié)點(diǎn)，則n的某個(gè)子節(jié)點(diǎn)ni在希望解樹0中的充分必要條件是： 如果n是與節(jié)點(diǎn)，則n的全部子節(jié)點(diǎn)n1、n2、nk都在希望解樹0中。 4. 與/或圖的啟發(fā)式搜索算法流程圖 圖3-26 與/或圖啟發(fā)式搜索流程圖把So放入Open表中，估算h (So) 啟動(dòng) 依次把Open表中0的端節(jié)點(diǎn)N選出 放入Closed表中，并冠以順序編號(hào)N是終止節(jié)點(diǎn)嗎？擴(kuò)展N，將其子節(jié)點(diǎn)Ni放入Open表中，配上指向N的返回指針，估算子節(jié)點(diǎn)及父節(jié)點(diǎn)的h（x）由h (x) 估算0標(biāo)記N為可解節(jié)點(diǎn)

26、，并對(duì)0應(yīng)用可解標(biāo)記過(guò)程是成功So可解嗎？ 從Open表中除去有可解父節(jié)點(diǎn)的節(jié)點(diǎn)否從Open表中除去有不可解父節(jié)點(diǎn)的節(jié)點(diǎn)N可擴(kuò)展 嗎？標(biāo)記N為不可解節(jié)點(diǎn)，并對(duì)0應(yīng)用不可解標(biāo)記過(guò)程是失敗So不可解嗎？否否否是是5. 與/或圖啟發(fā)式搜索示例例3-9 用啟發(fā)式搜索法求圖3-27所示與/或圖最小代價(jià)的最優(yōu)解樹。規(guī)定每邊的代價(jià)為1，每次擴(kuò)展深度為2。 0S0 8A 8 D 7B C E F 3 3 3 2(a) 擴(kuò)展S0后的與/或樹0S0 9A 8 D 11B C E 7 F 3 3 2 7 6 3 2 2 2(b) 擴(kuò)展E后的與/或樹GHIJKL5. 與/或圖啟發(fā)式搜索示例 圖3-27 與/或圖啟發(fā)式

27、搜索產(chǎn)生的解樹0S0 9A 8 D 11B 3 C E 7 F 2M 2 N 7 6P Q R S I J 0 0 2 2 3 2 2 2(c) 擴(kuò)展B后的與/或樹P Q R S W X0 0 2 2 0 0 5 2 3 2 2 2 M 2 N 6 U 2 V 9 7 6B 3 C 3 E 7 F 2A 8 D 11S0 90(c) 擴(kuò)展C后的與/或樹335 博弈樹的啟發(fā)式搜索1. 博弈的基本概念 博弈(Game Playing)是一類富有智能行為的競(jìng)爭(zhēng)活動(dòng)，是一類對(duì)策性游戲。典型的博弈如下棋、打橋牌、競(jìng)技等。廣義的博弈涉及到人類各方面的對(duì)策問(wèn)題，如軍事沖突、政治斗爭(zhēng)、經(jīng)濟(jì)競(jìng)爭(zhēng)等。博弈樹是一種

28、特殊的與/或樹，前面討論的一些與/或樹搜索策略，都可以應(yīng)用到博弈問(wèn)題的求解中來(lái)。簡(jiǎn)單的基本博弈為“全信息、非偶然、二人零和”博弈。即：1+2=0，其中1表示我方贏得的利益，2表示敵方贏得的利益；我勝或敵負(fù)時(shí)10或2=-10；反之我負(fù)或敵勝時(shí)10或2=-10；平局時(shí)，1=2=0。 贏得函數(shù) 我方對(duì)策的贏得函數(shù)為：敵方對(duì)策的贏得函數(shù)為： 其中： 是我方的對(duì)策； 是敵方的對(duì)策；（ ， ）是保險(xiǎn)策略； 是我方的對(duì)策的集合； 是敵方的對(duì)策的集合。2. 博弈樹的主要特點(diǎn)“與”節(jié)點(diǎn)、“或”節(jié)點(diǎn)逐級(jí)交替出現(xiàn)， 從我方觀點(diǎn)，所以，所有敵方節(jié)點(diǎn)都是“與”節(jié)點(diǎn)。從我方的觀點(diǎn)，所有屬于我方的節(jié)點(diǎn)都是“或”節(jié)點(diǎn)。所有能使自己一方獲勝的終局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都是不可解節(jié)點(diǎn)。先