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

第第3章章圖搜索技術(shù)圖搜索技術(shù) 31 圖搜索及其分類311 圖搜索的概念312 圖搜索的分類313 狀態(tài)圖搜索樹314 狀態(tài)空間搜索算法315 搜索效率32 窮舉式搜索321 廣度優(yōu)先搜索322 深度優(yōu)先搜索323 有界深度優(yōu)先搜索324 代價驅(qū)動搜索 第第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é)點及連接它們的弧的集合。搜索具有尋找、搜查、掃描、檢索的意義。它是在圖中尋找目標(biāo)或路徑的基本方法；也就是說，利用已有知識逐步摸索求解,根據(jù)問題的實際情況，不斷尋找可利用知識，使問題得以解決的過程稱為搜索。搜索的目的是以盡可能低的耗費(fèi)求得所需要的解。圖搜索，就是從初始節(jié)點出發(fā)，沿著與之相連的弧試探地前進(jìn)，尋找目標(biāo)節(jié)點的過程(也可以反向進(jìn)行)。樹式搜索和線式搜索樹式搜索就是以“畫樹”的方式進(jìn)行搜索。即從樹根(初始節(jié)點)出發(fā)，一筆一筆地描出一棵樹來。線式搜索就是以“畫線”的方式進(jìn)行搜索。線式搜索所記錄的軌跡始終是一條線或折線。一般情況下，樹式搜索成功后，還需再從搜索樹中找出所求路徑，而線式搜索只要搜索成功，則“搜索線”就是所找的路徑，即問題的解。312圖搜索的分類圖搜索的分類1 從求解要求看，可分為三種情況：從求解要求看，可分為三種情況：最佳值搜索。在這種情況下，值附在圖的各終節(jié)點，搜索的目的就是去找出具有最佳值的終節(jié)點，例如博弈問題的搜索就是屬于這一類問題。最短路徑搜索。搜索的目的是找出從初始節(jié)點到目標(biāo)節(jié)點的最短路徑。例如，巡回售貨員問題。滿足性搜索。有些問題可能有多個解，有些問題只有一個解，采用滿足性搜索，即只要找到一個解即可。例如，定理證明和大多數(shù)問題求解。2.按搜索方向分，有三種情況：正向搜索：是從初始狀態(tài)向目標(biāo)狀態(tài)的方向搜索，有時也稱為數(shù)據(jù)驅(qū)動搜索。搜索的過程即應(yīng)用規(guī)則從給定條件產(chǎn)生新條件，再用規(guī)則從新條件產(chǎn)生更多的新條件。反向搜索：是從目標(biāo)狀態(tài)向初始狀態(tài)的方向搜索，即目標(biāo)驅(qū)動搜索。方法是先從目標(biāo)入手，看哪些規(guī)則或合法移動能產(chǎn)生該目標(biāo)以及應(yīng)用這些規(guī)則產(chǎn)生目標(biāo)時需要哪些條件。搜索就通過反向的、連續(xù)的子目標(biāo)不斷地進(jìn)行，一直到找到問題給定的條件為止。雙向搜索：同時從目標(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)對對此此作作出出進(jìn)進(jìn)一一步步的的解釋。解釋。l l存存在在大大量量可可能能的的目目標(biāo)標(biāo)，但但對對實實際際問問題題的的條條件件及及給給定定的的信信息息加加以以運(yùn)運(yùn)用用的的方方法法很很少少的的系系統(tǒng)。統(tǒng)。l l 難以形成一個目標(biāo)或假設(shè)的系統(tǒng)。難以形成一個目標(biāo)或假設(shè)的系統(tǒng)。對下列情況建議采用反向搜索: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ù)，必必須須在在求求解解中中獲獲取取的的系系統(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)先搜索一致代價搜索一致代價搜索 啟發(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é)點葉節(jié)點I、J、K是是D的子節(jié)點的子節(jié)點D是是I、J、K的父節(jié)點的父節(jié)點A是是I、J、K的先輩節(jié)點的先輩節(jié)點中間節(jié)點中間節(jié)點一層一層二層二層三層三層例、巡回推銷員問題。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 33 25 33 26路徑長度路徑長度314狀態(tài)空間搜索算法狀態(tài)空間搜索算法解決問題時，有以下的因素需要考慮解決問題時，有以下的因素需要考慮:1計算機(jī)無法保存其全部狀態(tài)空間；計算機(jī)無法保存其全部狀態(tài)空間；2與與解解有有關(guān)關(guān)的的狀狀態(tài)態(tài)空空間間一一般般僅僅是是全全部部狀狀態(tài)態(tài)空空間間的的一一部分。部分。3是否一定能找到一個解？是否一定能找到一個解？4是否能終止運(yùn)行，或是否會陷入一個死循環(huán)？是否能終止運(yùn)行，或是否會陷入一個死循環(huán)？5是否找到的是最好解？是否找到的是最好解？6搜索過程的時間與空間復(fù)雜性如何？搜索過程的時間與空間復(fù)雜性如何？7怎樣才能最有效地降低搜索的復(fù)雜性？怎樣才能最有效地降低搜索的復(fù)雜性？8 怎樣設(shè)計才能最有效地利用描述語言怎樣設(shè)計才能最有效地利用描述語言?Open表和Closed表 Closed表表編號節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號12345 Open表表節(jié)點節(jié)點 父節(jié)點父節(jié)點 編號編號315搜索效率搜索效率搜搜索索效效率率P定定義義為為：P=L/TL從初始狀態(tài)到目標(biāo)狀態(tài)的路長從初始狀態(tài)到目標(biāo)狀態(tài)的路長T節(jié)點的總數(shù)節(jié)點的總數(shù) (不包括初始節(jié)點不包括初始節(jié)點)另另一一種種度度量量方方法法稱稱有有效效的的分分枝枝因因素素B。它它代代表表在在搜搜索索過過程程中中每每個個有有效效節(jié)節(jié)點點平平均均生生成成子子節(jié)節(jié)點點數(shù)數(shù)目。設(shè)目。設(shè)L是節(jié)點的深度是節(jié)點的深度 (或路長或路長)，則，則T=B+B2+B3+BL=(BBBL)/(1B)從而可得從而可得P=L/T=L(1B)/(BBBL)32窮舉式搜索窮舉式搜索 特特點點搜搜索索效效率率低低，控控制制策策略略差差，占占用用較較大大的的存存儲儲空空間間；但但它它控控制制性性知知識識簡簡單單，是是啟啟發(fā)發(fā)式式搜搜索索的的基基礎(chǔ)礎(chǔ)。為為了了簡簡化化問問題題的的討討論論，對對下面幾種窮舉式搜索方法作如下假設(shè)：下面幾種窮舉式搜索方法作如下假設(shè)：1搜搜索索空空間間是是一一棵棵樹樹，即即只只有有一一個個初初始始節(jié)節(jié)點，任意兩個節(jié)點之間的路徑是唯一的。點，任意兩個節(jié)點之間的路徑是唯一的。2.任何一個節(jié)點擴(kuò)展時，其后繼節(jié)點包含任何一個節(jié)點擴(kuò)展時，其后繼節(jié)點包含有返回父節(jié)點的指針。當(dāng)目標(biāo)節(jié)點產(chǎn)生時，有返回父節(jié)點的指針。當(dāng)目標(biāo)節(jié)點產(chǎn)生時，利用此特征很易求得解答。利用此特征很易求得解答。321廣度優(yōu)先搜索廣度優(yōu)先搜索概念與特點概念與特點廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種按廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種按“先產(chǎn)生的節(jié)點先擴(kuò)展先產(chǎn)生的節(jié)點先擴(kuò)展”原則進(jìn)行的搜索，也即一層原則進(jìn)行的搜索，也即一層一層進(jìn)行的搜索。搜索過程是一層進(jìn)行的搜索。搜索過程是:從初始節(jié)點從初始節(jié)點So開始逐開始逐層向下擴(kuò)展，先生成下一級各子節(jié)點，按順序?qū)酉蛳聰U(kuò)展，先生成下一級各子節(jié)點，按順序(先生先生成的子節(jié)點，優(yōu)先檢查，優(yōu)先擴(kuò)展成的子節(jié)點，優(yōu)先檢查，優(yōu)先擴(kuò)展)檢查是否出現(xiàn)目檢查是否出現(xiàn)目標(biāo)節(jié)點標(biāo)節(jié)點Sg。按此方法，若在第按此方法，若在第n層節(jié)點（此層無目標(biāo)層節(jié)點（此層無目標(biāo)節(jié)點）還沒有全部搜索完之前，不進(jìn)入第節(jié)點）還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點層節(jié)點的搜索。也就是說，廣度優(yōu)先的搜索樹是自頂向下的搜索。也就是說，廣度優(yōu)先的搜索樹是自頂向下一層一層逐漸生成的，一直到找到目標(biāo)節(jié)點為止。一層一層逐漸生成的，一直到找到目標(biāo)節(jié)點為止。廣度優(yōu)先搜索節(jié)點的擴(kuò)展順序廣度優(yōu)先搜索節(jié)點的擴(kuò)展順序 圖3-5 節(jié)點擴(kuò)展順序G H Sg C D E F A BSo搜索算法流程圖搜索算法流程圖 否否否否否否是是是是是是 啟動啟動 把把So放入放入Open表中表中取取Open表中最前面的節(jié)點表中最前面的節(jié)點N放入放入Closed表中，并冠以順序號表中，并冠以順序號Open為空嗎？為空嗎？N=Sg？成功成功N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N，將其子節(jié)點依次放入將其子節(jié)點依次放入Open表的末表的末尾，并配上指向尾，并配上指向N的返回指針的返回指針失敗失敗圖圖3-6 廣度優(yōu)先搜索流程圖廣度優(yōu)先搜索流程圖示例 例例3-2重排九宮問題：如圖重排九宮問題：如圖3-7所示，在所示，在33的方格棋盤上，放置的方格棋盤上，放置8個標(biāo)有數(shù)碼的紙牌個標(biāo)有數(shù)碼的紙牌(1、2、8)，并留下一個空格。只允許把空，并留下一個空格。只允許把空格上、下、左、右的紙牌移入空格。要求格上、下、左、右的紙牌移入空格。要求尋找一條從初始狀態(tài)尋找一條從初始狀態(tài)So到目標(biāo)狀態(tài)到目標(biāo)狀態(tài)Sg的最短的最短移動路線。移動路線。初始狀態(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é)點先擴(kuò)展、不撞墻不回頭的搜索方法。在搜索樹的每一層始終先只擴(kuò)展一個子節(jié)點，不斷地向縱深前進(jìn)。圖圖3-9 3-9 深度優(yōu)先搜索深度優(yōu)先搜索 節(jié)點擴(kuò)展順序節(jié)點擴(kuò)展順序前已搜索前已搜索 無無解解 SgSg6 6 C 7 5 3C 7 5 34 24 2A B 1 A B 1 SoSo搜索算法流程圖搜索算法流程圖 24否否否否否否是是是是是是 啟動啟動把把So放入放入Open表中表中取取Open表中最前面的節(jié)點表中最前面的節(jié)點N放入放入Closed表中，并冠以順序號表中，并冠以順序號Open為空嗎？為空嗎？N=Sg？成功成功N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N，將其子節(jié)點依次放入，將其子節(jié)點依次放入Open表的首表的首部，并配上指向部，并配上指向N的返回指針的返回指針失敗失敗圖圖3-10 深度優(yōu)先搜索流程圖深度優(yōu)先搜索流程圖示例示例 例例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)先搜索策略是不完備的，略是不完備的，帶有一定的冒險帶有一定的冒險性。另外，應(yīng)用性。另外，應(yīng)用此策略得到的解此策略得到的解不一定是最佳解不一定是最佳解(最短路徑最短路徑)。323有界深度優(yōu)先搜索有界深度優(yōu)先搜索 在深度優(yōu)先搜在深度優(yōu)先搜索法中，要給索法中，要給出一個深度限出一個深度限制制dm。當(dāng)從初。當(dāng)從初始節(jié)點出發(fā)沿始節(jié)點出發(fā)沿某一分枝擴(kuò)展某一分枝擴(kuò)展到到dm深度，但深度，但還沒有找到目還沒有找到目標(biāo)時，就不能標(biāo)時，就不能再繼續(xù)向下擴(kuò)再繼續(xù)向下擴(kuò)展，而只能改展，而只能改變方向繼續(xù)搜變方向繼續(xù)搜索。索。圖圖3-13 3-13 有界深度搜索節(jié)點擴(kuò)展順序有界深度搜索節(jié)點擴(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)先搜索流程圖是是否否否否是是啟動啟動把把SoSo放入放入OpenOpen表中，置深度表中，置深度d d（SoSo）=0=0取取OpenOpen表中最前面的節(jié)點表中最前面的節(jié)點N N放入放入ClosedClosed表中，并冠以順序號表中，并冠以順序號OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功失敗失敗是是否否d d（N N）=d=dm m？否否是是N N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N N，將其子節(jié)點依次放入，將其子節(jié)點依次放入OpenOpen表的表的首部，并配上指向首部，并配上指向N N的返回指針置的返回指針置 d d（N N）=d=d（N N）+1+1示例示例 例例3-4用有界深度優(yōu)先搜索法求解圖用有界深度優(yōu)先搜索法求解圖3-11重排重排九宮問題，取深度限界九宮問題，取深度限界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一致代價搜索一致代價搜索 1.1.一致代價搜索的概念一致代價搜索的概念 在狀態(tài)空間中，通常把代價記在狀態(tài)空間中，通常把代價記在邊在邊(弧弧)上在代價樹中，用上在代價樹中，用C(n1，n2)表表示從父節(jié)點示從父節(jié)點n1到其子節(jié)點到其子節(jié)點n2的代價，用的代價，用g(n1)表示從初始節(jié)點表示從初始節(jié)點So到節(jié)點到節(jié)點n1的代價。的代價。這樣，對這樣，對So到節(jié)點到節(jié)點n2的總代價為的總代價為 g(n2)=g(n1)十十C(n1，n2)2.一致代價廣度優(yōu)先搜索法一致代價廣度優(yōu)先搜索法 一致代價的廣度優(yōu)先搜索也稱為分枝一致代價的廣度優(yōu)先搜索也稱為分枝界限法，在同一級各節(jié)點中，取代價界限法，在同一級各節(jié)點中，取代價最小的節(jié)點優(yōu)先擴(kuò)展，從而求得總代最小的節(jié)點優(yōu)先擴(kuò)展，從而求得總代價最小的路徑。價最小的路徑。一致代價廣度優(yōu)先搜索方法是完備的。一致代價廣度優(yōu)先搜索方法是完備的。如果問題有解，就一定能夠找到解，如果問題有解，就一定能夠找到解，并且找到的一定是最優(yōu)解。并且找到的一定是最優(yōu)解。搜索算法流程圖搜索算法流程圖 圖圖3-16 3-16 代價驅(qū)動廣度優(yōu)先搜索流程圖代價驅(qū)動廣度優(yōu)先搜索流程圖否否把把SoSo放入放入OpenOpen表中，置表中，置g(Sog(So)=0)=0否否否否是是是是是是 啟動啟動取取OpenOpen表中最前面的節(jié)點表中最前面的節(jié)點N N放入放入ClosedClosed表中，并冠以順序號表中，并冠以順序號OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功N N可擴(kuò)展可擴(kuò)展 嗎？嗎？失敗失敗擴(kuò)展擴(kuò)展N N，將其子節(jié)點，將其子節(jié)點N Ni i放入放入OpenOpen表中，表中，配上指向配上指向N N的返回指針，計算并按的返回指針，計算并按g(Ng(Ni i)重新對重新對OpenOpen表排序表排序(小的在前小的在前)示例示例 2 23 34 43 36 62 25 5B BC CA AD DE E圖圖3-17 53-17 5城市交通路線城市交通路線圖圖3-18 53-18 5城市交通路線代價樹城市交通路線代價樹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.一致代價深度優(yōu)先搜索一致代價深度優(yōu)先搜索 一致代價深度優(yōu)先搜索和一致代價廣度優(yōu)一致代價深度優(yōu)先搜索和一致代價廣度優(yōu)先搜索的區(qū)別在于每次選擇最小代價節(jié)點先搜索的區(qū)別在于每次選擇最小代價節(jié)點的方法不同。后者每次都是從的方法不同。后者每次都是從Open表的全表的全體節(jié)點中選擇一個代價最小的節(jié)點，而前體節(jié)點中選擇一個代價最小的節(jié)點，而前者則是從剛擴(kuò)展的子節(jié)點中選擇一個代價者則是從剛擴(kuò)展的子節(jié)點中選擇一個代價最小的節(jié)點。最小的節(jié)點。33啟發(fā)式搜索啟發(fā)式搜索 3 33 31 1 啟發(fā)式搜索的基本概念啟發(fā)式搜索的基本概念 盡管有些問題是處在完備知識的環(huán)境盡管有些問題是處在完備知識的環(huán)境中，其解是完全確定了的，理論上也能找中，其解是完全確定了的，理論上也能找到解決問題的算法，但在工程實踐中，這到解決問題的算法，但在工程實踐中，這些算法不是效率太低，就是無法實現(xiàn)。為些算法不是效率太低，就是無法實現(xiàn)。為此，不得不放棄理論性算法，改用經(jīng)驗性此，不得不放棄理論性算法，改用經(jīng)驗性的啟發(fā)式方法。的啟發(fā)式方法。1.啟發(fā)式搜索的基本思想啟發(fā)式搜索的基本思想 啟發(fā)式搜索是在控制性知識中增加關(guān)于啟發(fā)式搜索是在控制性知識中增加關(guān)于被解問題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信被解問題和相應(yīng)任務(wù)的某些特性，利用啟發(fā)性信息來確定節(jié)點的生成、擴(kuò)展和搜索順序，以便指息來確定節(jié)點的生成、擴(kuò)展和搜索順序，以便指導(dǎo)搜索向最有希望的方向前進(jìn)。導(dǎo)搜索向最有希望的方向前進(jìn)。下一步展開哪個節(jié)點？下一步展開哪個節(jié)點？是部分展開還是全部展開？是部分展開還是全部展開？使用哪個規(guī)則使用哪個規(guī)則(算子算子)？怎樣決定舍棄還是保留新生成的節(jié)點？怎樣決定舍棄還是保留新生成的節(jié)點？怎樣決定舍棄還是保留一棵子樹？怎樣決定舍棄還是保留一棵子樹？怎樣決定停止或繼續(xù)搜索？怎樣決定停止或繼續(xù)搜索？如何定義啟發(fā)函數(shù)如何定義啟發(fā)函數(shù)(估值函數(shù)估值函數(shù))？如何決定搜索方向？如何決定搜索方向？2.啟發(fā)式搜索的特點 大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有大多是深度優(yōu)先搜索的改進(jìn)，即盡量沿著最有希望的路徑，向深度方向小范圍前進(jìn)；希望的路徑，向深度方向小范圍前進(jìn)；在多條路可走時，建議該走哪條路徑，從而指在多條路可走時，建議該走哪條路徑，從而指導(dǎo)搜索過程朝最有利的方向前進(jìn)；導(dǎo)搜索過程朝最有利的方向前進(jìn)；利用問題求解的先驗知識，使問題盡快找到解；利用問題求解的先驗知識，使問題盡快找到解；可采用估值的方法進(jìn)行搜索指導(dǎo)；可采用估值的方法進(jìn)行搜索指導(dǎo)；生成的狀態(tài)空間小、搜索時間短且效率高、控生成的狀態(tài)空間小、搜索時間短且效率高、控制性好，易于使問題得到解決。制性好，易于使問題得到解決。3.啟發(fā)性信息的類型 啟發(fā)性信息一般有以下三種啟發(fā)性信息一般有以下三種:有效地幫助確定擴(kuò)展節(jié)點的信息有效地幫助確定擴(kuò)展節(jié)點的信息全全局擇優(yōu)搜索法局擇優(yōu)搜索法 。有效的幫助決定哪些后繼節(jié)點應(yīng)被生成有效的幫助決定哪些后繼節(jié)點應(yīng)被生成的信息的信息局部擇優(yōu)搜索法局部擇優(yōu)搜索法 能決定在擴(kuò)展一個節(jié)點時哪些節(jié)點應(yīng)從能決定在擴(kuò)展一個節(jié)點時哪些節(jié)點應(yīng)從搜索樹上刪除（或剪掉）的信息搜索樹上刪除（或剪掉）的信息剪枝技剪枝技術(shù)術(shù) 。4.估價函數(shù)估價函數(shù) 一般形式是一般形式是:f(n)=g(n)+h(n)其中其中g(shù)(n)是從是從So到到n的實際代價，的實際代價，h(n)是從節(jié)點是從節(jié)點n到目標(biāo)節(jié)點到目標(biāo)節(jié)點Sg的估的估計代價。計代價。332局部擇優(yōu)搜索局部擇優(yōu)搜索1.基本思想基本思想局部擇優(yōu)搜索法又稱爬山法，其基本思想是，局部擇優(yōu)搜索法又稱爬山法，其基本思想是，搜索到一個節(jié)點后，只從其所有后繼子節(jié)點搜索到一個節(jié)點后，只從其所有后繼子節(jié)點中，按中，按f(x)選擇最優(yōu)者，也就是在后繼子節(jié)點選擇最優(yōu)者，也就是在后繼子節(jié)點的局部范圍內(nèi)選擇最優(yōu)者進(jìn)行擴(kuò)展，選取最的局部范圍內(nèi)選擇最優(yōu)者進(jìn)行擴(kuò)展，選取最有希望逼近目標(biāo)節(jié)點的方向，逐級沿縱向深有希望逼近目標(biāo)節(jié)點的方向，逐級沿縱向深度進(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)搜索流程圖是是否否是是否否失敗失敗 啟動啟動成功成功 把把SoSo放入放入ClosedClosed表，置表，置N=SoN=So擴(kuò)展擴(kuò)展N N，用，用f f（x x）選擇）選擇N N的最優(yōu)子節(jié)點的最優(yōu)子節(jié)點N N并放并放入入ClosedClosed表，設(shè)返回指針，令表，設(shè)返回指針，令N=NN=N示例示例 例例3-6用局部擇優(yōu)搜索重排九宮問題用局部擇優(yōu)搜索重排九宮問題 。定義估價函數(shù)定義估價函數(shù)f（n）=h（n）為：取節(jié)點為：取節(jié)點n與目標(biāo)節(jié)點與目標(biāo)節(jié)點Sg兩個格局中兩個格局中位置不符合的將牌數(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/T =8/17 =8/17 0.47 0.47333全局擇優(yōu)搜索全局擇優(yōu)搜索 1.概念概念全局擇優(yōu)搜索又稱最好優(yōu)先搜索和有序搜索。它避全局擇優(yōu)搜索又稱最好優(yōu)先搜索和有序搜索。它避免爬山法的缺點，不是在局部節(jié)點中擇優(yōu)，而是在免爬山法的缺點，不是在局部節(jié)點中擇優(yōu)，而是在全部節(jié)點中擇優(yōu)。它在全部節(jié)點中擇優(yōu)。它在OPEN表中保留了所有已生表中保留了所有已生成但尚未擴(kuò)展的節(jié)點，并用估價函數(shù)成但尚未擴(kuò)展的節(jié)點，并用估價函數(shù)f(n)對它們?nèi)珜λ鼈內(nèi)慷歼M(jìn)行估值。不管這個節(jié)點出現(xiàn)在搜索樹的任何部都進(jìn)行估值。不管這個節(jié)點出現(xiàn)在搜索樹的任何地方，都從中選出最優(yōu)的節(jié)點進(jìn)行擴(kuò)展。地方，都從中選出最優(yōu)的節(jié)點進(jìn)行擴(kuò)展。最好優(yōu)先搜索法比爬山法更有希望接近找到最最好優(yōu)先搜索法比爬山法更有希望接近找到最佳解；但也不一定完備。原因在于估價函數(shù)佳解；但也不一定完備。原因在于估價函數(shù)f(n)的的設(shè)計不一定是最佳的，按設(shè)計不一定是最佳的，按f（n）找出的最好解不一）找出的最好解不一定是實際上的最佳解。定是實際上的最佳解。算法流程圖 圖圖3-21 3-21 全局擇優(yōu)搜索流程圖全局擇優(yōu)搜索流程圖否否否否否否是是是是是是 啟動啟動把把SoSo放入放入OpenOpen表中，計算表中，計算f(So)f(So)取取OpenOpen表中最前面的節(jié)點表中最前面的節(jié)點N N放入放入ClosedClosed表中，并冠以順序號表中，并冠以順序號OpenOpen為空嗎？為空嗎？N=N=SgSg？成功成功N N可擴(kuò)展可擴(kuò)展 嗎？嗎？擴(kuò)展擴(kuò)展N N并用并用f(x)f(x)估計每個子節(jié)點估計每個子節(jié)點N Ni i，依次放入，依次放入OpenOpen表及配上指向表及配上指向N N的返回指針，利用的返回指針，利用f(x)f(x)對對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)搜索樹估價函數(shù)的一個較好的定義 h(n)=P(n)+3S(n)其中其中P(n)是每個將牌離是每個將牌離“家家”（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）的計算S（n）是這樣來計算的，沿著周圍那些非中心方格上依順）是這樣來計算的，沿著周圍那些非中心方格上依順時針方向檢查時針方向檢查n格局中的每一個將牌，如果其后緊跟著的將格局中的每一個將牌，如果其后緊跟著的將牌正好是目標(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(分分)在更一般的情況下，估價函數(shù)可取以下形式：在更一般的情況下，估價函數(shù)可取以下形式：f(n)=g(n)+Wh(n)其中其中W是一個起調(diào)整作用的正實數(shù)。是一個起調(diào)整作用的正實數(shù)。W提高則強(qiáng)調(diào)啟發(fā)信息提高則強(qiáng)調(diào)啟發(fā)信息的作用，的作用，W降低則強(qiáng)調(diào)先寬度搜索向后縱深的搜索趨勢。經(jīng)降低則強(qiáng)調(diào)先寬度搜索向后縱深的搜索趨勢。經(jīng)驗表明，驗表明，W值與樹的深度成反比時可以提高搜索效率。值與樹的深度成反比時可以提高搜索效率。334與與/或圖的啟發(fā)式搜索或圖的啟發(fā)式搜索1.1.與與/或圖一般搜索或圖一般搜索 與與/或樹的一般搜索過程實際上是一個不斷尋找解或樹的一般搜索過程實際上是一個不斷尋找解樹的過程。其一般搜索過程如下樹的過程。其一般搜索過程如下:把原始問題作為初始節(jié)點把原始問題作為初始節(jié)點So，并把它作為當(dāng)，并把它作為當(dāng)前節(jié)點；前節(jié)點；應(yīng)用分解或等價變換操作，擴(kuò)展當(dāng)前節(jié)點或由應(yīng)用分解或等價變換操作，擴(kuò)展當(dāng)前節(jié)點或由估計函數(shù)估計函數(shù)f指示的優(yōu)先節(jié)點，如果其子節(jié)點是幾組指示的優(yōu)先節(jié)點，如果其子節(jié)點是幾組具有與關(guān)系的子節(jié)點集合的或，就分二級擴(kuò)展；具有與關(guān)系的子節(jié)點集合的或，就分二級擴(kuò)展；為每個子節(jié)點設(shè)置指向父節(jié)點的指針；為每個子節(jié)點設(shè)置指向父節(jié)點的指針；選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第選擇合適的子節(jié)點作為當(dāng)前節(jié)點，反復(fù)執(zhí)行第2步和第步和第3步步 。與或樹的二級擴(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é)點的擴(kuò)展或節(jié)點的擴(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é)點為可解節(jié)點的有關(guān)可解由導(dǎo)致根節(jié)點為可解節(jié)點的有關(guān)可解節(jié)點及樹枝所組成的子樹，稱為該問節(jié)點及樹枝所組成的子樹，稱為該問題解樹。題解樹。與與/或樹的啟發(fā)式搜索過程是一種利用或樹的啟發(fā)式搜索過程是一種利用搜索過程所得到的啟發(fā)性信息尋找最搜索過程所得到的啟發(fā)性信息尋找最優(yōu)解樹的過程。即試圖找到一個最有優(yōu)解樹的過程。即試圖找到一個最有希望成為代價最小的那棵解樹。希望成為代價最小的那棵解樹。2.與/或圖解樹的代價 與節(jié)點代價的計算與節(jié)點代價的計算 若若n為與節(jié)點，且子節(jié)點為為與節(jié)點，且子節(jié)點為n1、n2、nk，則，則n的代價有兩種計算方法：的代價有兩種計算方法：最大代價最大代價其中其中c(n，ni)是節(jié)點是節(jié)點n到其子節(jié)點到其子節(jié)點ni的邊代價，的邊代價，h（ni)是對節(jié)點是對節(jié)點ni的估計代價。的估計代價。和代價和代價取它們的和作為代價取它們的和作為代價h（n）。）?；蚬?jié)點代價的計算 若若n為或節(jié)點，且子節(jié)點為為或節(jié)點，且子節(jié)點為n1、n2、nk，則則n的代價為的代價為:即取它們的最小值作為代價即取它們的最小值作為代價h（n）。）。其他特殊節(jié)點代價的計算 若若n是可解節(jié)點，即為終止節(jié)點，則其是可解節(jié)點，即為終止節(jié)點，則其代價代價h(n)=0。若端節(jié)點若端節(jié)點n為不可解節(jié)點，又不是終止為不可解節(jié)點，又不是終止節(jié)點，不可擴(kuò)展，其代價定義為節(jié)點，不可擴(kuò)展，其代價定義為h(n)=。根節(jié)點的代價即為解樹的代價。根節(jié)點的代價即為解樹的代價。示例例3-8 求圖3-25與/或圖解樹的總代價，其中t表示終止節(jié)點，表示不可解節(jié)點。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ā)式搜索中，希望解樹是對最佳解或樹的啟發(fā)式搜索中，希望解樹是對最佳解樹的近根部分的某種估計。樹的近根部分的某種估計。0的定義如下：的定義如下：初始節(jié)點初始節(jié)點S0在希望解樹在希望解樹0中；中；如果如果n是具有子節(jié)點是具有子節(jié)點n1、n2、nk的或節(jié)點，的或節(jié)點，則則n的某個子節(jié)點的某個子節(jié)點ni在希望解樹在希望解樹0中的充分必要條中的充分必要條件是：件是：如果如果n是與節(jié)點，則是與節(jié)點，則n的全部子節(jié)點的全部子節(jié)點n1、n2、nk都在希望解樹都在希望解樹0中。中。4.與/或圖的啟發(fā)式搜索算法流程圖 圖圖3-26 3-26 與與/或圖啟發(fā)式搜索流程圖或圖啟發(fā)式搜索流程圖把把SoSo放入放入OpenOpen表中，估算表中，估算h(So)h(So)啟動啟動 依次把依次把OpenOpen表中表中0 0的端節(jié)點的端節(jié)點N N選出選出 放入放入ClosedClosed表中，并冠以順序編號表中，并冠以順序編號N N是終止節(jié)點嗎？是終止節(jié)點嗎？擴(kuò)展擴(kuò)展N N，將其子節(jié)點，將其子節(jié)點N Ni i放放入入OpenOpen表中，配上指向表中，配上指向N N的返回指針，估算子的返回指針，估算子節(jié)點及父節(jié)點的節(jié)點及父節(jié)點的h h（x x）由由h(x)h(x)估算估算0 0標(biāo)記標(biāo)記N N為可解節(jié)點，并對為可解節(jié)點，并對0 0應(yīng)用可解標(biāo)記過程應(yīng)用可解標(biāo)記過程是是成功成功SoSo可解嗎？可解嗎？從從OpenOpen表中除去有表中除去有可解父節(jié)點的節(jié)點可解父節(jié)點的節(jié)點否否從從OpenOpen表中除去有不表中除去有不可解父節(jié)點的節(jié)點可解父節(jié)點的節(jié)點N N可擴(kuò)展可擴(kuò)展 嗎？嗎？標(biāo)記標(biāo)記N N為不可解節(jié)點，并對為不可解節(jié)點，并對0 0應(yīng)用不可解標(biāo)記過程應(yīng)用不可解標(biāo)記過程是是失敗失敗SoSo不可解嗎？不可解嗎？否否否否否否是是是是5.與/或圖啟發(fā)式搜索示例例例3-9用啟發(fā)式搜索法求圖用啟發(fā)式搜索法求圖3-27所示與所示與/或或圖最小代價的最優(yōu)解樹。規(guī)定每邊的代價圖最小代價的最優(yōu)解樹。規(guī)定每邊的代價為為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(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 2 V 9 7 6B 3 C 3 E 7 F 2A 8 D 11S0 90(c)擴(kuò)展C后的與/或樹335博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索1.博弈的基本概念博弈的基本概念 博弈博弈(GamePlaying)是一類富有智能行為的競爭活動，是一類富有智能行為的競爭活動，是一類對策性游戲。典型的博弈如下棋、打橋牌、競技等。是一類對策性游戲。典型的博弈如下棋、打橋牌、競技等。廣義的博弈涉及到人類各方面的對策問題，如軍事沖突、廣義的博弈涉及到人類各方面的對策問題，如軍事沖突、政治斗爭、經(jīng)濟(jì)競爭等。博弈樹是一種特殊的與政治斗爭、經(jīng)濟(jì)競爭等。博弈樹是一種特殊的與/或樹，或樹，前面討論的一些與前面討論的一些與/或樹搜索策略，都可以應(yīng)用到博弈問或樹搜索策略，都可以應(yīng)用到博弈問題的求解中來。題的求解中來。簡單的基本博弈為簡單的基本博弈為“全信息、非偶然、二人零和全信息、非偶然、二人零和”博弈。博弈。即：即：1+2=0，其中，其中1表示我方贏得的利益，表示我方贏得的利益，2表示敵方表示敵方贏得的利益；我勝或敵負(fù)時贏得的利益；我勝或敵負(fù)時10或或2=-10；反之我負(fù)；反之我負(fù)或敵勝時或敵勝時10或或2=-10；平局時，；平局時，1=2=0。贏得函數(shù) 我方對策的贏得函數(shù)為：我方對策的贏得函數(shù)為：敵方對策的贏得函數(shù)為：敵方對策的贏得函數(shù)為：其中：是我方的對策；是敵方的對策；（，）是保險策略；是我方的對策的集合；是敵方的對策的集合。2.博弈樹的主要特點“與與”節(jié)點、節(jié)點、“或或”節(jié)點逐級交替出現(xiàn)，節(jié)點逐級交替出現(xiàn)，從我方觀點，所以，所有敵方節(jié)點都是從我方觀點，所以，所有敵方節(jié)點都是“與與”節(jié)點。節(jié)點。從我方的觀點，所有屬于我方的節(jié)點都是從我方的觀點，所有屬于我方的節(jié)點都是“或或”節(jié)點。節(jié)點。所有能使自己一方獲勝的終局都是本原問題，所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點。局都是不可解節(jié)點。先走步的一方的初始伏態(tài)對應(yīng)著博弈樹的先走步的一方的初始伏態(tài)對應(yīng)著博弈樹的“根根節(jié)點節(jié)點”。3.極大極小搜索法 2 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 極大極小搜索倒推值的計算極大極小搜索倒推值的計算MAXMAXMAXMINMIN4.示例 例例3-10一字棋游戲。設(shè)有一個三行三列的一字棋游戲。設(shè)有一個三行三列的棋盤，兩個棋手輪流走步，輪到誰走棋誰棋盤，兩個棋手輪流走步，輪到誰走棋誰就往空格上放一只自己的棋子，誰先使自就往空格上放一只自己的棋子，誰先使自己的棋子成三子一線誰就取得了勝利。設(shè)己的棋子成三子一線誰就取得了勝利。設(shè)MAX方的棋子用方的棋子用標(biāo)記，標(biāo)記，MIN方的棋子用方的棋子用標(biāo)記，并規(guī)定標(biāo)記，并規(guī)定MAX方先走步。試用極大極方先走步。試用極大極小搜索求雙方的最佳策略。小搜索求雙方的最佳策略。解解:這個問題的狀態(tài)空間有這個問題的狀態(tài)空間有9！個節(jié)點，令得！個節(jié)點，令得分的靜態(tài)估值函數(shù)分的靜態(tài)估值函數(shù)f(n)=h(n)。啟發(fā)式函數(shù)的設(shè)計若若n是非終局節(jié)點，則是非終局節(jié)點，則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是是方獲勝的終局節(jié)點，方獲勝的終局節(jié)點，h1(n)=+，如圖，如圖3-29（c）。）。若若n是是方獲勝的終局節(jié)點，方獲勝的終局節(jié)點，h1(n)=-如圖如圖3-29（d）。）。圖圖3-29 3-29 一字棋幾種典型格局靜態(tài)得分估值函數(shù)一字棋幾種典型格局靜態(tài)得分估值函數(shù)h h1 1(n)(n)的計算的計算 （a）（b）（c）（d）h1(n)=2 h1(n)=0 h1(n)=+h1(n)=-h1(n)可得第一步走棋生成的博弈樹 第二回合以S4為起點，MAX的走步 h(n)更精確的定義 h2(n)=（方的一階路方的一階路 方的一階路）方的一階路）+4（方的二階路方的二階路 方的二階路）方的二階路）+a+2若若方出子占領(lǐng)了方出子占領(lǐng)了方的二階路方的二階路其中其中 a=-2若若方出子占領(lǐng)了方出子占領(lǐng)了方的二階路方的二階路 0其他其他 方（或方（或方）的一階路是指在一條路上僅有方）的一階路是指在一條路上僅有一個一個方（或方（或方）的棋子占位。所謂方）的棋子占位。所謂方（或方（或方）的二階路是指在一條路上有二個方）的二階路是指在一條路上有二個方（或方（或方）方）的棋子占位。的棋子占位。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