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

《人工智能及專家系統(tǒng)第3章圖搜索技術(shù)課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能及專家系統(tǒng)第3章圖搜索技術(shù)課件（69頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第第3章章圖搜索技術(shù)圖搜索技術(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ù)圖搜索技術(shù)33 啟發(fā)式搜索331 啟發(fā)式搜索的基本概念332 局部擇優(yōu)搜索333 全局擇優(yōu)搜索334 與/或圖的啟發(fā)式搜索335 博弈樹的啟發(fā)式搜索336-剪枝技術(shù) 第第3章章圖搜索技術(shù)圖搜索技術(shù) 3.1.1圖搜索的概念圖搜索的概念圖是節(jié)點(diǎn)及連接它們的弧的集合。搜索具有尋找、搜查、掃描、檢索的意義。它是在圖中尋找目標(biāo)或路徑的

2、基本方法；也就是說，利用已有知識(shí)逐步摸索求解,根據(jù)問題的實(shí)際情況，不斷尋找可利用知識(shí)，使問題得以解決的過程稱為搜索。搜索的目的是以盡可能低的耗費(fèi)求得所需要的解。圖搜索，就是從初始節(jié)點(diǎn)出發(fā)，沿著與之相連的弧試探地前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)的過程(也可以反向進(jìn)行)。樹式搜索和線式搜索樹式搜索就是以“畫樹”的方式進(jìn)行搜索。即從樹根(初始節(jié)點(diǎn))出發(fā)，一筆一筆地描出一棵樹來。線式搜索就是以“畫線”的方式進(jìn)行搜索。線式搜索所記錄的軌跡始終是一條線或折線。一般情況下，樹式搜索成功后，還需再從搜索樹中找出所求路徑，而線式搜索只要搜索成功，則“搜索線”就是所找的路徑，即問題的解。312圖搜索的分類圖搜索的分類1 從求解

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

4、索，即目標(biāo)驅(qū)動(dòng)搜索。方法是先從目標(biāo)入手，看哪些規(guī)則或合法移動(dòng)能產(chǎn)生該目標(biāo)以及應(yīng)用這些規(guī)則產(chǎn)生目標(biāo)時(shí)需要哪些條件。搜索就通過反向的、連續(xù)的子目標(biāo)不斷地進(jìn)行，一直到找到問題給定的條件為止。雙向搜索：同時(shí)從目標(biāo)狀態(tài)和初始狀態(tài)出發(fā)進(jìn)行搜索。正向搜索可用于下列情況:l l問問題題的的初初始始說說明明給給出出了了全全部部或或大大部部分分?jǐn)?shù)數(shù)據(jù)據(jù)的的系系統(tǒng)統(tǒng)。解解釋釋程程序序常常常常如如此此，它它提提供供一一批批采采集集的的數(shù)數(shù)據(jù)據(jù)，要要求求系系統(tǒng)統(tǒng)對(duì)對(duì)此此作作出出進(jìn)進(jìn)一一步步的的解釋。解釋。l l存存在在大大量量可可能能的的目目標(biāo)標(biāo)，但但對(duì)對(duì)實(shí)實(shí)際際問問題題的的條條件件及及給給定定的的信信息息加加以以運(yùn)運(yùn)

5、用用的的方方法法很很少少的的系系統(tǒng)。統(tǒng)。l l 難以形成一個(gè)目標(biāo)或假設(shè)的系統(tǒng)。難以形成一個(gè)目標(biāo)或假設(shè)的系統(tǒng)。對(duì)下列情況建議采用反向搜索:l l問問題題的的說說明明中中給給出出了了目目標(biāo)標(biāo)或或假假設(shè)設(shè)，或或者者很很容容易易用公式來表示它們的系統(tǒng)。用公式來表示它們的系統(tǒng)。l l有有大大量量的的規(guī)規(guī)則則適適用用于于問問題題的的條條件件的的系系統(tǒng)統(tǒng)。在在這這種種情情況況下下，可可以以推推出出許許多多結(jié)結(jié)論論和和結(jié)結(jié)果果，較較早早地地選選好好目目標(biāo)標(biāo)可可剪剪掉掉空空間間中中許許多多分分枝枝，使使反反向向搜索的效率更高。搜索的效率更高。l l問問題題沒沒有有給給出出數(shù)數(shù)據(jù)據(jù)，必必須須在在求求解解中中獲獲取

6、取的的系系統(tǒng)統(tǒng)。這這種種情情況況下下，反反向向搜搜索索可可以以幫幫助助指指導(dǎo)導(dǎo)數(shù)數(shù)據(jù)據(jù)的獲取。的獲取。l l分析特定數(shù)據(jù)的系統(tǒng)。分析特定數(shù)據(jù)的系統(tǒng)。3按照搜索的內(nèi)容分 窮舉式搜索窮舉式搜索 圖搜索圖搜索廣度優(yōu)先搜索廣度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索有界深度優(yōu)先搜索一致代價(jià)搜索一致代價(jià)搜索 啟發(fā)式搜索啟發(fā)式搜索局部擇優(yōu)搜索局部擇優(yōu)搜索全局擇優(yōu)搜索全局擇優(yōu)搜索與與/或圖啟發(fā)式搜索或圖啟發(fā)式搜索極大極小搜索極大極小搜索、剪枝搜索剪枝搜索 313狀態(tài)圖搜索樹狀態(tài)圖搜索樹 圖圖3-1 狀態(tài)圖搜索樹狀態(tài)圖搜索樹 L M E F G H I J K B C D A 樹根樹根樹枝樹枝葉節(jié)點(diǎn)葉

7、節(jié)點(diǎn)I、J、K是是D的子節(jié)點(diǎn)的子節(jié)點(diǎn)D是是I、J、K的父節(jié)點(diǎn)的父節(jié)點(diǎn)A是是I、J、K的先輩節(jié)點(diǎn)的先輩節(jié)點(diǎn)中間節(jié)點(diǎn)中間節(jié)點(diǎn)一層一層二層二層三層三層例、巡回推銷員問題。B A D C 4 7 10 6 10 5圖圖3-2 4城市路線城市路線圖圖3-3 巡回推銷員問題狀態(tài)圖搜索樹巡回推銷員問題狀態(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

8、 33 25 33 26路徑長度路徑長度314狀態(tài)空間搜索算法狀態(tài)空間搜索算法解決問題時(shí)，有以下的因素需要考慮解決問題時(shí)，有以下的因素需要考慮:1計(jì)算機(jī)無法保存其全部狀態(tài)空間；計(jì)算機(jī)無法保存其全部狀態(tài)空間；2與與解解有有關(guān)關(guān)的的狀狀態(tài)態(tài)空空間間一一般般僅僅是是全全部部狀狀態(tài)態(tài)空空間間的的一一部分。部分。3是否一定能找到一個(gè)解？是否一定能找到一個(gè)解？4是否能終止運(yùn)行，或是否會(huì)陷入一個(gè)死循環(huán)？是否能終止運(yùn)行，或是否會(huì)陷入一個(gè)死循環(huán)？5是否找到的是最好解？是否找到的是最好解？6搜索過程的時(shí)間與空間復(fù)雜性如何？搜索過程的時(shí)間與空間復(fù)雜性如何？7怎樣才能最有效地降低搜索的復(fù)雜性？怎樣才能最有效地降低搜索

9、的復(fù)雜性？8 怎樣設(shè)計(jì)才能最有效地利用描述語言怎樣設(shè)計(jì)才能最有效地利用描述語言?Open表和Closed表 Closed表表編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)12345 Open表表節(jié)點(diǎn)節(jié)點(diǎn) 父節(jié)點(diǎn)父節(jié)點(diǎn) 編號(hào)編號(hào)315搜索效率搜索效率搜搜索索效效率率P定定義義為為：P=L/TL從初始狀態(tài)到目標(biāo)狀態(tài)的路長從初始狀態(tài)到目標(biāo)狀態(tài)的路長T節(jié)點(diǎn)的總數(shù)節(jié)點(diǎn)的總數(shù) (不包括初始節(jié)點(diǎn)不包括初始節(jié)點(diǎn))另另一一種種度度量量方方法法稱稱有有效效的的分分枝枝因因素素B。它它代代表表在在搜搜索索過過程程中中每每個(gè)個(gè)有有效效節(jié)節(jié)點(diǎn)點(diǎn)平平均均生生成成子子節(jié)節(jié)點(diǎn)點(diǎn)數(shù)數(shù)目。設(shè)目。設(shè)L是節(jié)點(diǎn)的深度是節(jié)點(diǎn)的深度 (或路長或路長

10、)，則，則T=B+B2+B3+BL=(BBBL)/(1B)從而可得從而可得P=L/T=L(1B)/(BBBL)32窮舉式搜索窮舉式搜索 特特點(diǎn)點(diǎn)搜搜索索效效率率低低，控控制制策策略略差差，占占用用較較大大的的存存儲(chǔ)儲(chǔ)空空間間；但但它它控控制制性性知知識(shí)識(shí)簡簡單單，是是啟啟發(fā)發(fā)式式搜搜索索的的基基礎(chǔ)礎(chǔ)。為為了了簡簡化化問問題題的的討討論論，對(duì)對(duì)下面幾種窮舉式搜索方法作如下假設(shè)：下面幾種窮舉式搜索方法作如下假設(shè)：1搜搜索索空空間間是是一一棵棵樹樹，即即只只有有一一個(gè)個(gè)初初始始節(jié)節(jié)點(diǎn)，任意兩個(gè)節(jié)點(diǎn)之間的路徑是唯一的。點(diǎn)，任意兩個(gè)節(jié)點(diǎn)之間的路徑是唯一的。2.任何一個(gè)節(jié)點(diǎn)擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)包含任何一個(gè)節(jié)

11、點(diǎn)擴(kuò)展時(shí)，其后繼節(jié)點(diǎn)包含有返回父節(jié)點(diǎn)的指針。當(dāng)目標(biāo)節(jié)點(diǎn)產(chǎn)生時(shí)，有返回父節(jié)點(diǎn)的指針。當(dāng)目標(biāo)節(jié)點(diǎn)產(chǎn)生時(shí)，利用此特征很易求得解答。利用此特征很易求得解答。321廣度優(yōu)先搜索廣度優(yōu)先搜索概念與特點(diǎn)概念與特點(diǎn)廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種按廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種按“先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”原則進(jìn)行的搜索，也即一層原則進(jìn)行的搜索，也即一層一層進(jìn)行的搜索。搜索過程是一層進(jìn)行的搜索。搜索過程是:從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)So開始逐開始逐層向下擴(kuò)展，先生成下一級(jí)各子節(jié)點(diǎn)，按順序?qū)酉蛳聰U(kuò)展，先生成下一級(jí)各子節(jié)點(diǎn)，按順序(先生先生成的子節(jié)點(diǎn)，優(yōu)先檢查，優(yōu)先擴(kuò)展成的子節(jié)點(diǎn)，優(yōu)先檢查

12、，優(yōu)先擴(kuò)展)檢查是否出現(xiàn)目檢查是否出現(xiàn)目標(biāo)節(jié)點(diǎn)標(biāo)節(jié)點(diǎn)Sg。按此方法，若在第按此方法，若在第n層節(jié)點(diǎn)（此層無目標(biāo)層節(jié)點(diǎn)（此層無目標(biāo)節(jié)點(diǎn)）還沒有全部搜索完之前，不進(jìn)入第節(jié)點(diǎn)）還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)層節(jié)點(diǎn)的搜索。也就是說，廣度優(yōu)先的搜索樹是自頂向下的搜索。也就是說，廣度優(yōu)先的搜索樹是自頂向下一層一層逐漸生成的，一直到找到目標(biāo)節(jié)點(diǎn)為止。一層一層逐漸生成的，一直到找到目標(biāo)節(jié)點(diǎn)為止。廣度優(yōu)先搜索節(jié)點(diǎn)的擴(kuò)展順序廣度優(yōu)先搜索節(jié)點(diǎn)的擴(kuò)展順序 圖3-5 節(jié)點(diǎn)擴(kuò)展順序G H Sg C D E F A BSo搜索算法流程圖搜索算法流程圖 否否否否否否是是是是是是 啟動(dòng)啟動(dòng) 把把So放入放入Open

13、表中表中取取Open表中最前面的節(jié)點(diǎn)表中最前面的節(jié)點(diǎn)N放入放入Closed表中，并冠以順序號(hào)表中，并冠以順序號(hào)Open為空嗎？為空嗎？N=Sg？成功成功N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N，將其子節(jié)點(diǎn)依次放入將其子節(jié)點(diǎn)依次放入Open表的末表的末尾，并配上指向尾，并配上指向N的返回指針的返回指針失敗失敗圖圖3-6 廣度優(yōu)先搜索流程圖廣度優(yōu)先搜索流程圖示例 例例3-2重排九宮問題：如圖重排九宮問題：如圖3-7所示，在所示，在33的方格棋盤上，放置的方格棋盤上，放置8個(gè)標(biāo)有數(shù)碼的紙牌個(gè)標(biāo)有數(shù)碼的紙牌(1、2、8)，并留下一個(gè)空格。只允許把空，并留下一個(gè)空格。只允許把空格上、下、左、右的紙牌移入空格。

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

15、度優(yōu)先搜索 節(jié)點(diǎn)擴(kuò)展順序節(jié)點(diǎn)擴(kuò)展順序前已搜索前已搜索 無無解解 SgSg6 6 C 7 5 3C 7 5 34 24 2A B 1 A B 1 SoSo搜索算法流程圖搜索算法流程圖 24否否否否否否是是是是是是 啟動(dòng)啟動(dòng)把把So放入放入Open表中表中取取Open表中最前面的節(jié)點(diǎn)表中最前面的節(jié)點(diǎn)N放入放入Closed表中，并冠以順序號(hào)表中，并冠以順序號(hào)Open為空嗎？為空嗎？N=Sg？成功成功N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N，將其子節(jié)點(diǎn)依次放入，將其子節(jié)點(diǎn)依次放入Open表的首表的首部，并配上指向部，并配上指向N的返回指針的返回指針失敗失敗圖圖3-10 深度優(yōu)先搜索流程圖深度優(yōu)先搜索流程圖示

16、例示例 例例3-3利用深度優(yōu)先搜索求解如圖利用深度優(yōu)先搜索求解如圖3-11所示所示的重排九宮問題。的重排九宮問題。初始狀態(tài)初始狀態(tài)So 目標(biāo)狀態(tài)目標(biāo)狀態(tài)Sg圖圖3-11 重排九宮問題重排九宮問題生成的搜索樹圖圖3-12 3-12 重排九宮問題的深度優(yōu)先搜索樹重排九宮問題的深度優(yōu)先搜索樹深度優(yōu)先搜索策深度優(yōu)先搜索策略是不完備的，略是不完備的，帶有一定的冒險(xiǎn)帶有一定的冒險(xiǎn)性。另外，應(yīng)用性。另外，應(yīng)用此策略得到的解此策略得到的解不一定是最佳解不一定是最佳解(最短路徑最短路徑)。323有界深度優(yōu)先搜索有界深度優(yōu)先搜索 在深度優(yōu)先搜在深度優(yōu)先搜索法中，要給索法中，要給出一個(gè)深度限出一個(gè)深度限制制dm。當(dāng)

17、從初。當(dāng)從初始節(jié)點(diǎn)出發(fā)沿始節(jié)點(diǎn)出發(fā)沿某一分枝擴(kuò)展某一分枝擴(kuò)展到到dm深度，但深度，但還沒有找到目還沒有找到目標(biāo)時(shí)，就不能標(biāo)時(shí)，就不能再繼續(xù)向下擴(kuò)再繼續(xù)向下擴(kuò)展，而只能改展，而只能改變方向繼續(xù)搜變方向繼續(xù)搜索。索。圖圖3-13 3-13 有界深度搜索節(jié)點(diǎn)擴(kuò)展順序有界深度搜索節(jié)點(diǎn)擴(kuò)展順序 SgSg C C 6 5 3 6 5 34 24 2A B 1 A B 1 SoSod d =d=dm m=3,=3,強(qiáng)迫返回強(qiáng)迫返回d(d(深度深度)1 12 2 3 3搜索算法流程圖搜索算法流程圖圖圖3-14 3-14 有界深度優(yōu)先搜索流程圖有界深度優(yōu)先搜索流程圖是是否否否否是是啟動(dòng)啟動(dòng)把把SoSo放入放入O

18、penOpen表中，置深度表中，置深度d d（SoSo）=0=0取取OpenOpen表中最前面的節(jié)點(diǎn)表中最前面的節(jié)點(diǎn)N N放入放入ClosedClosed表中，并冠以順序號(hào)表中，并冠以順序號(hào)OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功失敗失敗是是否否d d（N N）=d=dm m？否否是是N N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N N，將其子節(jié)點(diǎn)依次放入，將其子節(jié)點(diǎn)依次放入OpenOpen表的表的首部，并配上指向首部，并配上指向N N的返回指針置的返回指針置 d d（N N）=d=d（N N）+1+1示例示例 例例3-4用有界深度優(yōu)先搜索法求解圖用有界深度優(yōu)先搜索法求解圖3-11重排

19、重排九宮問題，取深度限界九宮問題，取深度限界dm=4。初始狀態(tài)初始狀態(tài)So 目標(biāo)狀態(tài)目標(biāo)狀態(tài)Sg圖圖3-11 重排九宮問題重排九宮問題生成的搜索樹搜索效率搜索效率P=L/T=4/270.148圖圖3-15 3-15 重排九宮問題的有界深度優(yōu)先搜索搜索樹重排九宮問題的有界深度優(yōu)先搜索搜索樹324一致代價(jià)搜索一致代價(jià)搜索 1.1.一致代價(jià)搜索的概念一致代價(jià)搜索的概念 在狀態(tài)空間中，通常把代價(jià)記在狀態(tài)空間中，通常把代價(jià)記在邊在邊(弧弧)上在代價(jià)樹中，用上在代價(jià)樹中，用C(n1，n2)表表示從父節(jié)點(diǎn)示從父節(jié)點(diǎn)n1到其子節(jié)點(diǎn)到其子節(jié)點(diǎn)n2的代價(jià)，用的代價(jià)，用g(n1)表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)So到節(jié)

20、點(diǎn)到節(jié)點(diǎn)n1的代價(jià)。的代價(jià)。這樣，對(duì)這樣，對(duì)So到節(jié)點(diǎn)到節(jié)點(diǎn)n2的總代價(jià)為的總代價(jià)為 g(n2)=g(n1)十十C(n1，n2)2.一致代價(jià)廣度優(yōu)先搜索法一致代價(jià)廣度優(yōu)先搜索法 一致代價(jià)的廣度優(yōu)先搜索也稱為分枝一致代價(jià)的廣度優(yōu)先搜索也稱為分枝界限法，在同一級(jí)各節(jié)點(diǎn)中，取代價(jià)界限法，在同一級(jí)各節(jié)點(diǎn)中，取代價(jià)最小的節(jié)點(diǎn)優(yōu)先擴(kuò)展，從而求得總代最小的節(jié)點(diǎn)優(yōu)先擴(kuò)展，從而求得總代價(jià)最小的路徑。價(jià)最小的路徑。一致代價(jià)廣度優(yōu)先搜索方法是完備的。一致代價(jià)廣度優(yōu)先搜索方法是完備的。如果問題有解，就一定能夠找到解，如果問題有解，就一定能夠找到解，并且找到的一定是最優(yōu)解。并且找到的一定是最優(yōu)解。搜索算法流程圖搜索算法

21、流程圖 圖圖3-16 3-16 代價(jià)驅(qū)動(dòng)廣度優(yōu)先搜索流程圖代價(jià)驅(qū)動(dòng)廣度優(yōu)先搜索流程圖否否把把SoSo放入放入OpenOpen表中，置表中，置g(Sog(So)=0)=0否否否否是是是是是是 啟動(dòng)啟動(dòng)取取OpenOpen表中最前面的節(jié)點(diǎn)表中最前面的節(jié)點(diǎn)N N放入放入ClosedClosed表中，并冠以順序號(hào)表中，并冠以順序號(hào)OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功N N可擴(kuò)展可擴(kuò)展 嗎？嗎？失敗失敗擴(kuò)展擴(kuò)展N N，將其子節(jié)點(diǎn)，將其子節(jié)點(diǎn)N Ni i放入放入OpenOpen表中，表中，配上指向配上指向N N的返回指針，計(jì)算并按的返回指針，計(jì)算并按g(Ng(Ni i)重新對(duì)重新對(duì)O

22、penOpen表排序表排序(小的在前小的在前)示例示例 2 23 34 43 36 62 25 5B BC CA AD DE E圖圖3-17 53-17 5城市交通路線城市交通路線圖圖3-18 53-18 5城市交通路線代價(jià)樹城市交通路線代價(jià)樹E E4 4B B1 1A AB BC CC C1 1E E1 1E E2 2 E E3 3D D1 1E E5 5D D2 2 3 32 26 6 6 63 32 25 54 4SoSo3 34 43.一致代價(jià)深度優(yōu)先搜索一致代價(jià)深度優(yōu)先搜索 一致代價(jià)深度優(yōu)先搜索和一致代價(jià)廣度優(yōu)一致代價(jià)深度優(yōu)先搜索和一致代價(jià)廣度優(yōu)先搜索的區(qū)別在于每次選擇最小代價(jià)節(jié)點(diǎn)先

23、搜索的區(qū)別在于每次選擇最小代價(jià)節(jié)點(diǎn)的方法不同。后者每次都是從的方法不同。后者每次都是從Open表的全表的全體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，而前體節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)，而前者則是從剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)者則是從剛擴(kuò)展的子節(jié)點(diǎn)中選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)。最小的節(jié)點(diǎn)。33啟發(fā)式搜索啟發(fā)式搜索 3 33 31 1 啟發(fā)式搜索的基本概念啟發(fā)式搜索的基本概念 盡管有些問題是處在完備知識(shí)的環(huán)境盡管有些問題是處在完備知識(shí)的環(huán)境中，其解是完全確定了的，理論上也能找中，其解是完全確定了的，理論上也能找到解決問題的算法，但在工程實(shí)踐中，這到解決問題的算法，但在工程實(shí)踐中，這些算法不是效率太低，就是無法實(shí)

24、現(xiàn)。為些算法不是效率太低，就是無法實(shí)現(xiàn)。為此，不得不放棄理論性算法，改用經(jīng)驗(yàn)性此，不得不放棄理論性算法，改用經(jīng)驗(yàn)性的啟發(fā)式方法。的啟發(fā)式方法。1.啟發(fā)式搜索的基本思想啟發(fā)式搜索的基本思想 啟發(fā)式搜索是在控制性知識(shí)中增加關(guān)于啟發(fā)式搜索是在控制性知識(shí)中增加關(guān)于被解問題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信被解問題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信息來確定節(jié)點(diǎn)的生成、擴(kuò)展和搜索順序，以便指息來確定節(jié)點(diǎn)的生成、擴(kuò)展和搜索順序，以便指導(dǎo)搜索向最有希望的方向前進(jìn)。導(dǎo)搜索向最有希望的方向前進(jìn)。下一步展開哪個(gè)節(jié)點(diǎn)？下一步展開哪個(gè)節(jié)點(diǎn)？是部分展開還是全部展開？是部分展開還是全部展開？使用哪個(gè)規(guī)則使用哪個(gè)規(guī)則(算子算

25、子)？怎樣決定舍棄還是保留新生成的節(jié)點(diǎn)？怎樣決定舍棄還是保留新生成的節(jié)點(diǎn)？怎樣決定舍棄還是保留一棵子樹？怎樣決定舍棄還是保留一棵子樹？怎樣決定停止或繼續(xù)搜索？怎樣決定停止或繼續(xù)搜索？如何定義啟發(fā)函數(shù)如何定義啟發(fā)函數(shù)(估值函數(shù)估值函數(shù))？如何決定搜索方向？如何決定搜索方向？2.啟發(fā)式搜索的特點(diǎn) 大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度方向小范圍前進(jìn)；希望的路徑，向深度方向小范圍前進(jìn)；在多條路可走時(shí)，建議該走哪條路徑，從而指在多條路可走時(shí)，建議該走哪條路徑，從而指導(dǎo)搜索過程朝最有利的方向前進(jìn)；導(dǎo)搜索過程朝最有利的方向前進(jìn)；利用問題求解的先驗(yàn)

26、知識(shí)，使問題盡快找到解；利用問題求解的先驗(yàn)知識(shí)，使問題盡快找到解；可采用估值的方法進(jìn)行搜索指導(dǎo)；可采用估值的方法進(jìn)行搜索指導(dǎo)；生成的狀態(tài)空間小、搜索時(shí)間短且效率高、控生成的狀態(tài)空間小、搜索時(shí)間短且效率高、控制性好，易于使問題得到解決。制性好，易于使問題得到解決。3.啟發(fā)性信息的類型 啟發(fā)性信息一般有以下三種啟發(fā)性信息一般有以下三種:有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息全全局擇優(yōu)搜索法局擇優(yōu)搜索法 。有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息的信息局部擇優(yōu)搜索法局部擇優(yōu)搜索法 能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從

27、搜索樹上刪除（或剪掉）的信息搜索樹上刪除（或剪掉）的信息剪枝技剪枝技術(shù)術(shù) 。4.估價(jià)函數(shù)估價(jià)函數(shù) 一般形式是一般形式是:f(n)=g(n)+h(n)其中其中g(shù)(n)是從是從So到到n的實(shí)際代價(jià)，的實(shí)際代價(jià)，h(n)是從節(jié)點(diǎn)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)Sg的估的估計(jì)代價(jià)。計(jì)代價(jià)。332局部擇優(yōu)搜索局部擇優(yōu)搜索1.基本思想基本思想局部擇優(yōu)搜索法又稱爬山法，其基本思想是，局部擇優(yōu)搜索法又稱爬山法，其基本思想是，搜索到一個(gè)節(jié)點(diǎn)后，只從其所有后繼子節(jié)點(diǎn)搜索到一個(gè)節(jié)點(diǎn)后，只從其所有后繼子節(jié)點(diǎn)中，按中，按f(x)選擇最優(yōu)者，也就是在后繼子節(jié)點(diǎn)選擇最優(yōu)者，也就是在后繼子節(jié)點(diǎn)的局部范圍內(nèi)選擇最優(yōu)者進(jìn)行擴(kuò)展，選

28、取最的局部范圍內(nèi)選擇最優(yōu)者進(jìn)行擴(kuò)展，選取最有希望逼近目標(biāo)節(jié)點(diǎn)的方向，逐級(jí)沿縱向深有希望逼近目標(biāo)節(jié)點(diǎn)的方向，逐級(jí)沿縱向深度進(jìn)行搜索。由于是小范圍內(nèi)的局部優(yōu)選，度進(jìn)行搜索。由于是小范圍內(nèi)的局部優(yōu)選，故稱之為局部擇優(yōu)搜索法。故稱之為局部擇優(yōu)搜索法。適用于單峰極值、單因素問題。局部擇優(yōu)搜適用于單峰極值、單因素問題。局部擇優(yōu)搜索法，是不完備的推理方法。索法，是不完備的推理方法。算法流程圖 N N可擴(kuò)展可擴(kuò)展 嗎？嗎？N=N=SgSg？圖圖3-19 3-19 局部擇優(yōu)搜索流程圖局部擇優(yōu)搜索流程圖是是否否是是否否失敗失敗 啟動(dòng)啟動(dòng)成功成功 把把SoSo放入放入ClosedClosed表，置表，置N=SoN=

29、So擴(kuò)展擴(kuò)展N N，用，用f f（x x）選擇）選擇N N的最優(yōu)子節(jié)點(diǎn)的最優(yōu)子節(jié)點(diǎn)N N并放并放入入ClosedClosed表，設(shè)返回指針，令表，設(shè)返回指針，令N=NN=N示例示例 例例3-6用局部擇優(yōu)搜索重排九宮問題用局部擇優(yōu)搜索重排九宮問題 。定義估價(jià)函數(shù)定義估價(jià)函數(shù)f（n）=h（n）為：取節(jié)點(diǎn)為：取節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)Sg兩個(gè)格局中兩個(gè)格局中位置不符合的將牌數(shù)目。位置不符合的將牌數(shù)目。初始狀態(tài)初始狀態(tài)So 目標(biāo)狀態(tài)目標(biāo)狀態(tài)Sg圖圖3-11 重排九宮問題重排九宮問題生成的搜索樹 圖圖3-20 3-20 重排九宮局部擇優(yōu)搜索樹重排九宮局部擇優(yōu)搜索樹搜索效率搜索效率 P=L/T P=L/

30、T =8/17 =8/17 0.47 0.47333全局擇優(yōu)搜索全局擇優(yōu)搜索 1.概念概念全局擇優(yōu)搜索又稱最好優(yōu)先搜索和有序搜索。它避全局擇優(yōu)搜索又稱最好優(yōu)先搜索和有序搜索。它避免爬山法的缺點(diǎn)，不是在局部節(jié)點(diǎn)中擇優(yōu)，而是在免爬山法的缺點(diǎn)，不是在局部節(jié)點(diǎn)中擇優(yōu)，而是在全部節(jié)點(diǎn)中擇優(yōu)。它在全部節(jié)點(diǎn)中擇優(yōu)。它在OPEN表中保留了所有已生表中保留了所有已生成但尚未擴(kuò)展的節(jié)點(diǎn)，并用估價(jià)函數(shù)成但尚未擴(kuò)展的節(jié)點(diǎn)，并用估價(jià)函數(shù)f(n)對(duì)它們?nèi)珜?duì)它們?nèi)慷歼M(jìn)行估值。不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹的任何部都進(jìn)行估值。不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹的任何地方，都從中選出最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展。地方，都從中選出最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展。最

31、好優(yōu)先搜索法比爬山法更有希望接近找到最最好優(yōu)先搜索法比爬山法更有希望接近找到最佳解；但也不一定完備。原因在于估價(jià)函數(shù)佳解；但也不一定完備。原因在于估價(jià)函數(shù)f(n)的的設(shè)計(jì)不一定是最佳的，按設(shè)計(jì)不一定是最佳的，按f（n）找出的最好解不一）找出的最好解不一定是實(shí)際上的最佳解。定是實(shí)際上的最佳解。算法流程圖 圖圖3-21 3-21 全局擇優(yōu)搜索流程圖全局擇優(yōu)搜索流程圖否否否否否否是是是是是是 啟動(dòng)啟動(dòng)把把SoSo放入放入OpenOpen表中，計(jì)算表中，計(jì)算f(So)f(So)取取OpenOpen表中最前面的節(jié)點(diǎn)表中最前面的節(jié)點(diǎn)N N放入放入ClosedClosed表中，并冠以順序號(hào)表中，并冠以順序號(hào)

32、OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功N N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N N并用并用f(x)f(x)估計(jì)每個(gè)子節(jié)點(diǎn)估計(jì)每個(gè)子節(jié)點(diǎn)N Ni i，依次放入，依次放入OpenOpen表及配上指向表及配上指向N N的返回指針，利用的返回指針，利用f(x)f(x)對(duì)對(duì)OpenOpen表重新排序，小的在前表重新排序，小的在前失敗失敗示例示例 例例3-7應(yīng)用全局擇優(yōu)搜索法求解重應(yīng)用全局擇優(yōu)搜索法求解重排九宮問題排九宮問題 初始狀態(tài)初始狀態(tài)So 目標(biāo)狀態(tài)目標(biāo)狀態(tài)Sg圖圖3-11 重排九宮問題重排九宮問題算法流程圖 圖圖3-22 重排九宮全局擇優(yōu)搜索樹重排九宮全局擇優(yōu)搜索樹估價(jià)函數(shù)的一個(gè)

33、較好的定義 h(n)=P(n)+3S(n)其中其中P(n)是每個(gè)將牌離是每個(gè)將牌離“家家”（Sg格局中的位置）格局中的位置）最短距離的總和。如圖最短距離的總和。如圖3-22所示，所示，So格局格局P(n)得分得分為：為：So中的中的 12345678P(So)=2+1+1+1+0+0+0+2=7(分分)初始狀態(tài)初始狀態(tài)So 目標(biāo)狀態(tài)目標(biāo)狀態(tài)Sg圖圖3-22 重排九宮問題重排九宮問題S（n）的計(jì)算S（n）是這樣來計(jì)算的，沿著周圍那些非中心方格上依順）是這樣來計(jì)算的，沿著周圍那些非中心方格上依順時(shí)針方向檢查時(shí)針方向檢查n格局中的每一個(gè)將牌，如果其后緊跟著的將格局中的每一個(gè)將牌，如果其后緊跟著的將牌

34、正好是目標(biāo)格局中該將牌的后續(xù)者的話，該將牌得牌正好是目標(biāo)格局中該將牌的后續(xù)者的話，該將牌得0分，分，否則得否則得2分，在正中方格中的將牌得分，在正中方格中的將牌得1分。所有將牌得分之分。所有將牌得分之和為和為S（n）。如圖）。如圖3-22中，中，So格局格局S（So）得分為：）得分為：So中的將牌：中的將牌：12345678S(So)=2+2+2+1+0+0+2+0=9(分分)所以所以 h(So)=P(So)+3S(So)=7+39=34(分分)在更一般的情況下，估價(jià)函數(shù)可取以下形式：在更一般的情況下，估價(jià)函數(shù)可取以下形式：f(n)=g(n)+Wh(n)其中其中W是一個(gè)起調(diào)整作用的正實(shí)數(shù)。是一

35、個(gè)起調(diào)整作用的正實(shí)數(shù)。W提高則強(qiáng)調(diào)啟發(fā)信息提高則強(qiáng)調(diào)啟發(fā)信息的作用，的作用，W降低則強(qiáng)調(diào)先寬度搜索向后縱深的搜索趨勢(shì)。經(jīng)降低則強(qiáng)調(diào)先寬度搜索向后縱深的搜索趨勢(shì)。經(jīng)驗(yàn)表明，驗(yàn)表明，W值與樹的深度成反比時(shí)可以提高搜索效率。值與樹的深度成反比時(shí)可以提高搜索效率。334與與/或圖的啟發(fā)式搜索或圖的啟發(fā)式搜索1.1.與與/或圖一般搜索或圖一般搜索 與與/或樹的一般搜索過程實(shí)際上是一個(gè)不斷尋找解或樹的一般搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下樹的過程。其一般搜索過程如下:把原始問題作為初始節(jié)點(diǎn)把原始問題作為初始節(jié)點(diǎn)So，并把它作為當(dāng)，并把它作為當(dāng)前節(jié)點(diǎn)；前節(jié)點(diǎn)；應(yīng)用分解或等價(jià)變換操作，

36、擴(kuò)展當(dāng)前節(jié)點(diǎn)或由應(yīng)用分解或等價(jià)變換操作，擴(kuò)展當(dāng)前節(jié)點(diǎn)或由估計(jì)函數(shù)估計(jì)函數(shù)f指示的優(yōu)先節(jié)點(diǎn)，如果其子節(jié)點(diǎn)是幾組指示的優(yōu)先節(jié)點(diǎn)，如果其子節(jié)點(diǎn)是幾組具有與關(guān)系的子節(jié)點(diǎn)集合的或，就分二級(jí)擴(kuò)展；具有與關(guān)系的子節(jié)點(diǎn)集合的或，就分二級(jí)擴(kuò)展；為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第2步和第步和第3步步 。與或樹的二級(jí)擴(kuò)展 a a1 1a a2 2a a3 3 b b1 1 b b2 2 b b3 3 b b4 4 b b5 5 b b6 6 b b7 7 b b8 8圖圖3-24 3-24 與與/或節(jié)點(diǎn)

37、的擴(kuò)展或節(jié)點(diǎn)的擴(kuò)展b b1 1 b b2 2 b b3 3 b b4 4 b b5 5 b b6 6 b b7 7 b b8 8與或圖的解樹由導(dǎo)致根節(jié)點(diǎn)為可解節(jié)點(diǎn)的有關(guān)可解由導(dǎo)致根節(jié)點(diǎn)為可解節(jié)點(diǎn)的有關(guān)可解節(jié)點(diǎn)及樹枝所組成的子樹，稱為該問節(jié)點(diǎn)及樹枝所組成的子樹，稱為該問題解樹。題解樹。與與/或樹的啟發(fā)式搜索過程是一種利用或樹的啟發(fā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋找最搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。即試圖找到一個(gè)最有優(yōu)解樹的過程。即試圖找到一個(gè)最有希望成為代價(jià)最小的那棵解樹。希望成為代價(jià)最小的那棵解樹。2.與/或圖解樹的代價(jià) 與節(jié)點(diǎn)代價(jià)的計(jì)算與節(jié)點(diǎn)代價(jià)的計(jì)算 若若n為

38、與節(jié)點(diǎn)，且子節(jié)點(diǎn)為為與節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1、n2、nk，則，則n的代價(jià)有兩種計(jì)算方法：的代價(jià)有兩種計(jì)算方法：最大代價(jià)最大代價(jià)其中其中c(n，ni)是節(jié)點(diǎn)是節(jié)點(diǎn)n到其子節(jié)點(diǎn)到其子節(jié)點(diǎn)ni的邊代價(jià)，的邊代價(jià)，h（ni)是對(duì)節(jié)點(diǎn)是對(duì)節(jié)點(diǎn)ni的估計(jì)代價(jià)。的估計(jì)代價(jià)。和代價(jià)和代價(jià)取它們的和作為代價(jià)取它們的和作為代價(jià)h（n）。）?；蚬?jié)點(diǎn)代價(jià)的計(jì)算 若若n為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為為或節(jié)點(diǎn)，且子節(jié)點(diǎn)為n1、n2、nk，則則n的代價(jià)為的代價(jià)為:即取它們的最小值作為代價(jià)即取它們的最小值作為代價(jià)h（n）。）。其他特殊節(jié)點(diǎn)代價(jià)的計(jì)算 若若n是可解節(jié)點(diǎn)，即為終止節(jié)點(diǎn)，則其是可解節(jié)點(diǎn)，即為終止節(jié)點(diǎn)，則其代價(jià)代價(jià)h(n)=0。

39、若端節(jié)點(diǎn)若端節(jié)點(diǎn)n為不可解節(jié)點(diǎn)，又不是終止為不可解節(jié)點(diǎn)，又不是終止節(jié)點(diǎn)，不可擴(kuò)展，其代價(jià)定義為節(jié)點(diǎn)，不可擴(kuò)展，其代價(jià)定義為h(n)=。根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。根節(jié)點(diǎn)的代價(jià)即為解樹的代價(jià)。示例例3-8 求圖3-25與/或圖解樹的總代價(jià)，其中t表示終止節(jié)點(diǎn)，表示不可解節(jié)點(diǎn)。S S0 0 t t t t t tt t t t4 44 45 6 2 45 6 2 41 1 2 2 3 3 4 4圖圖3-25 3-25 與與/或圖的解樹或圖的解樹a ba bc d e fc d e fg pg p 2 4 4 3 2 1 5 73.希望解樹 在與在與/或樹的啟發(fā)式搜索中，希望解樹是對(duì)最佳解或樹的啟發(fā)

40、式搜索中，希望解樹是對(duì)最佳解樹的近根部分的某種估計(jì)。樹的近根部分的某種估計(jì)。0的定義如下：的定義如下：初始節(jié)點(diǎn)初始節(jié)點(diǎn)S0在希望解樹在希望解樹0中；中；如果如果n是具有子節(jié)點(diǎn)是具有子節(jié)點(diǎn)n1、n2、nk的或節(jié)點(diǎn)，的或節(jié)點(diǎn)，則則n的某個(gè)子節(jié)點(diǎn)的某個(gè)子節(jié)點(diǎn)ni在希望解樹在希望解樹0中的充分必要條中的充分必要條件是：件是：如果如果n是與節(jié)點(diǎn)，則是與節(jié)點(diǎn)，則n的全部子節(jié)點(diǎn)的全部子節(jié)點(diǎn)n1、n2、nk都在希望解樹都在希望解樹0中。中。4.與/或圖的啟發(fā)式搜索算法流程圖 圖圖3-26 3-26 與與/或圖啟發(fā)式搜索流程圖或圖啟發(fā)式搜索流程圖把把SoSo放入放入OpenOpen表中，估算表中，估算h(So)

41、h(So)啟動(dòng)啟動(dòng) 依次把依次把OpenOpen表中表中0 0的端節(jié)點(diǎn)的端節(jié)點(diǎn)N N選出選出 放入放入ClosedClosed表中，并冠以順序編號(hào)表中，并冠以順序編號(hào)N N是終止節(jié)點(diǎn)嗎？是終止節(jié)點(diǎn)嗎？擴(kuò)展擴(kuò)展N N，將其子節(jié)點(diǎn)，將其子節(jié)點(diǎn)N Ni i放放入入OpenOpen表中，配上指向表中，配上指向N N的返回指針，估算子的返回指針，估算子節(jié)點(diǎn)及父節(jié)點(diǎn)的節(jié)點(diǎn)及父節(jié)點(diǎn)的h h（x x）由由h(x)h(x)估算估算0 0標(biāo)記標(biāo)記N N為可解節(jié)點(diǎn)，并對(duì)為可解節(jié)點(diǎn)，并對(duì)0 0應(yīng)用可解標(biāo)記過程應(yīng)用可解標(biāo)記過程是是成功成功SoSo可解嗎？可解嗎？從從OpenOpen表中除去有表中除去有可解父節(jié)點(diǎn)的節(jié)點(diǎn)可

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

43、(a)(a)擴(kuò)展擴(kuò)展S0S0后的與后的與/或樹或樹0 0S S0 0 9 9A 8 D 11A 8 D 11B C E 7 F B C E 7 F 3 3 23 3 2 7 67 6 3 2 2 23 2 2 2(b)(b)擴(kuò)展擴(kuò)展E E后的與后的與/或樹或樹G GH HI IJ JK KL L5.與/或圖啟發(fā)式搜索示例 圖3-27 與/或圖啟發(fā)式搜索產(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

44、 2 V 9 7 6B 3 C 3 E 7 F 2A 8 D 11S0 90(c)擴(kuò)展C后的與/或樹335博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索1.博弈的基本概念博弈的基本概念 博弈博弈(GamePlaying)是一類富有智能行為的競爭活動(dòng)，是一類富有智能行為的競爭活動(dòng)，是一類對(duì)策性游戲。典型的博弈如下棋、打橋牌、競技等。是一類對(duì)策性游戲。典型的博弈如下棋、打橋牌、競技等。廣義的博弈涉及到人類各方面的對(duì)策問題，如軍事沖突、廣義的博弈涉及到人類各方面的對(duì)策問題，如軍事沖突、政治斗爭、經(jīng)濟(jì)競爭等。博弈樹是一種特殊的與政治斗爭、經(jīng)濟(jì)競爭等。博弈樹是一種特殊的與/或樹，或樹，前面討論的一些與前面討論的一

45、些與/或樹搜索策略，都可以應(yīng)用到博弈問或樹搜索策略，都可以應(yīng)用到博弈問題的求解中來。題的求解中來。簡單的基本博弈為簡單的基本博弈為“全信息、非偶然、二人零和全信息、非偶然、二人零和”博弈。博弈。即：即：1+2=0，其中，其中1表示我方贏得的利益，表示我方贏得的利益，2表示敵方表示敵方贏得的利益；我勝或敵負(fù)時(shí)贏得的利益；我勝或敵負(fù)時(shí)10或或2=-10；反之我負(fù)；反之我負(fù)或敵勝時(shí)或敵勝時(shí)10或或2=-10；平局時(shí)，；平局時(shí)，1=2=0。贏得函數(shù) 我方對(duì)策的贏得函數(shù)為：我方對(duì)策的贏得函數(shù)為：敵方對(duì)策的贏得函數(shù)為：敵方對(duì)策的贏得函數(shù)為：其中：是我方的對(duì)策；是敵方的對(duì)策；（，）是保險(xiǎn)策略；是我方的對(duì)策的

46、集合；是敵方的對(duì)策的集合。2.博弈樹的主要特點(diǎn)“與與”節(jié)點(diǎn)、節(jié)點(diǎn)、“或或”節(jié)點(diǎn)逐級(jí)交替出現(xiàn)，節(jié)點(diǎn)逐級(jí)交替出現(xiàn)，從我方觀點(diǎn)，所以，所有敵方節(jié)點(diǎn)都是從我方觀點(diǎn)，所以，所有敵方節(jié)點(diǎn)都是“與與”節(jié)點(diǎn)。節(jié)點(diǎn)。從我方的觀點(diǎn)，所有屬于我方的節(jié)點(diǎn)都是從我方的觀點(diǎn)，所有屬于我方的節(jié)點(diǎn)都是“或或”節(jié)點(diǎn)。節(jié)點(diǎn)。所有能使自己一方獲勝的終局都是本原問題，所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都是不可解節(jié)點(diǎn)。局都是不可解節(jié)點(diǎn)。先走步的一方的初始伏態(tài)對(duì)應(yīng)著博弈樹的先走步的一方的初始伏態(tài)對(duì)應(yīng)著博弈樹的“根根節(jié)點(diǎn)節(jié)點(diǎn)”。3.極大極小搜索法 2

47、9 3 1 -1 -1 3 6 8 -1 2 0 3 -5 7 4 -2 6 -1 8 -7 -1 0 3 2 A -1 -1 6 -1 0 -5 -2 -1 -7 -1 2 B 6 0 -1 -1 2 -1 2 S0 最佳最佳 圖圖3-28 極大極小搜索倒推值的計(jì)算極大極小搜索倒推值的計(jì)算MAXMAXMAXMINMIN4.示例 例例3-10一字棋游戲。設(shè)有一個(gè)三行三列的一字棋游戲。設(shè)有一個(gè)三行三列的棋盤，兩個(gè)棋手輪流走步，輪到誰走棋誰棋盤，兩個(gè)棋手輪流走步，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自就往空格上放一只自己的棋子，誰先使自己的棋子成三子一線誰就取得了勝利。設(shè)己的棋子成三子一

48、線誰就取得了勝利。設(shè)MAX方的棋子用方的棋子用標(biāo)記，標(biāo)記，MIN方的棋子用方的棋子用標(biāo)記，并規(guī)定標(biāo)記，并規(guī)定MAX方先走步。試用極大極方先走步。試用極大極小搜索求雙方的最佳策略。小搜索求雙方的最佳策略。解解:這個(gè)問題的狀態(tài)空間有這個(gè)問題的狀態(tài)空間有9！個(gè)節(jié)點(diǎn)，令得！個(gè)節(jié)點(diǎn)，令得分的靜態(tài)估值函數(shù)分的靜態(tài)估值函數(shù)f(n)=h(n)。啟發(fā)式函數(shù)的設(shè)計(jì)若若n是非終局節(jié)點(diǎn)，則是非終局節(jié)點(diǎn)，則h1(n)=(方所占據(jù)的路數(shù)方所占據(jù)的路數(shù) 方所占據(jù)的路數(shù)方所占據(jù)的路數(shù))如圖如圖3-29（a）所示，）所示，h1(n)=4-2=2。若若n是和局，是和局，h1(n)=0，如圖，如圖3-29（b）所示。）所示。若若n

49、是是方獲勝的終局節(jié)點(diǎn)，方獲勝的終局節(jié)點(diǎn)，h1(n)=+，如圖，如圖3-29（c）。）。若若n是是方獲勝的終局節(jié)點(diǎn)，方獲勝的終局節(jié)點(diǎn)，h1(n)=-如圖如圖3-29（d）。）。圖圖3-29 3-29 一字棋幾種典型格局靜態(tài)得分估值函數(shù)一字棋幾種典型格局靜態(tài)得分估值函數(shù)h h1 1(n)(n)的計(jì)算的計(jì)算 （a）（b）（c）（d）h1(n)=2 h1(n)=0 h1(n)=+h1(n)=-h1(n)可得第一步走棋生成的博弈樹 第二回合以S4為起點(diǎn)，MAX的走步 h(n)更精確的定義 h2(n)=（方的一階路方的一階路 方的一階路）方的一階路）+4（方的二階路方的二階路 方的二階路）方的二階路）+a

50、+2若若方出子占領(lǐng)了方出子占領(lǐng)了方的二階路方的二階路其中其中 a=-2若若方出子占領(lǐng)了方出子占領(lǐng)了方的二階路方的二階路 0其他其他 方（或方（或方）的一階路是指在一條路上僅有方）的一階路是指在一條路上僅有一個(gè)一個(gè)方（或方（或方）的棋子占位。所謂方）的棋子占位。所謂方（或方（或方）的二階路是指在一條路上有二個(gè)方）的二階路是指在一條路上有二個(gè)方（或方（或方）方）的棋子占位。的棋子占位。336-剪枝技術(shù)剪枝技術(shù) 圖圖3-32 3-32 -剪枝的搜索過程剪枝的搜索過程 2 D1 F-1 I 6 L 0 -5 2 D1 F-1 I 6 L 0 -5 2 2 6 0 0 2 2 6 0 0 2 02 0 2 22 2 2 9 3 1-1 2 9 3 1-1-1-1 3 6 8 -1 2 0 3 -5 7 4-2 6-1 8-7-1 0 3 3 6 8 -1 2 0 3 -5 7 4-2 6-1 8-7-1 0 3 MAXMAXMAXMAXMAXMAXMINMINMINMINA A B B C CH HE EJ J K KP PQ QG GM MU U S S0 0剪剪 剪剪N NV V