第五章人工智能搜索策略

1、人工智能Artificial Intelligence主講：楊利英主講：楊利英西安電子科技大學(xué)計(jì)算機(jī)學(xué)院西安電子科技大學(xué)計(jì)算機(jī)學(xué)院E_mail：第五章第五章 搜索策略搜索策略5.1 基本概念基本概念5.2 狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略5.3 與與/或樹的搜索策略或樹的搜索策略5.4 搜索的完備性與效率搜索的完備性與效率5.1 基本概念 采用某種策略，在知識庫中尋找可利用的知采用某種策略，在知識庫中尋找可利用的知識，從而識，從而構(gòu)造一條代價較小的推理路線構(gòu)造一條代價較小的推理路線，使，使問題得到解決的過程稱為搜索。問題得到解決的過程稱為搜索。5.1.1 什么是搜索什么是搜索5.1.1 什

2、么是搜索搜索分為盲目搜索盲目搜索和啟發(fā)式搜索啟發(fā)式搜索。 盲目搜索盲目搜索是按照預(yù)定的控制策略進(jìn)行搜索，在是按照預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間信息不用來改進(jìn)控制策搜索過程中獲得的中間信息不用來改進(jìn)控制策略。略。啟發(fā)式搜索啟發(fā)式搜索是在搜索中加入了與問題有關(guān)的啟發(fā)性是在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速信息，用以指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程并找到最優(yōu)解。問題的求解過程并找到最優(yōu)解。5.1.2 狀態(tài)空間表示法狀態(tài)空間用狀態(tài)空間用“狀態(tài)狀態(tài)”和和“算符算符”來表示問題。來表示問題。n狀態(tài)狀態(tài) 狀態(tài)用以描述問題在求解過程中

3、不同時刻的狀態(tài)，一般用向量表示n算符算符使問題從一個狀態(tài)轉(zhuǎn)變?yōu)榱硪粋€狀態(tài)的操作稱為算符。n狀態(tài)空間狀態(tài)空間由所有可能出現(xiàn)的狀態(tài)及一切可用算符所構(gòu)成的集合稱為問題的狀態(tài)空間?；仡櫥仡櫊顟B(tài)空間示例：十五數(shù)碼難題119151341275861321014119415131275861321014119151341275861321014119415131275861321014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顧回顧5.1.3 與/或樹表示法對于一個復(fù)雜問題，直接求

4、解往往比較困對于一個復(fù)雜問題，直接求解往往比較困難。此時可通過下述方法進(jìn)行簡化：難。此時可通過下述方法進(jìn)行簡化：（1）分解）分解 （2）等價變換）等價變換回顧回顧5.1.3 與/或樹表示法（1）分解把一個復(fù)雜問題分解為若干個較為簡把一個復(fù)雜問題分解為若干個較為簡單的子問題，每個子問題又可繼續(xù)分單的子問題，每個子問題又可繼續(xù)分解。重復(fù)此過程，直到不需要再分解解。重復(fù)此過程，直到不需要再分解或者不能再分解為止。如此形成或者不能再分解為止。如此形成“與與”樹。樹。（2 2）等價變換等價變換利用同構(gòu)或同態(tài)的等價變換，把原問利用同構(gòu)或同態(tài)的等價變換，把原問題變換為若干個較為容易求解的新問題變換為若干個較

5、為容易求解的新問題。如此形成題。如此形成“或或”樹。樹。PP1P2P3與樹PP1P2P3或樹回顧回顧與/或樹P31PP1P2P3與/或樹P11P12P32P33分解與等價變換可以結(jié)合起來使用，這樣形成的圖稱為分解與等價變換可以結(jié)合起來使用，這樣形成的圖稱為“與與/或樹或樹”回顧回顧由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹稱為解樹為可解節(jié)點(diǎn)的子樹稱為解樹(t(t表示終止節(jié)點(diǎn)表示終止節(jié)點(diǎn)) )。解樹中一。解樹中一定包含初始節(jié)點(diǎn)。（它對應(yīng)于原始問題）定包含初始節(jié)點(diǎn)。（它對應(yīng)于原始問題）解樹解樹解樹PtttPttt回顧回顧5.

6、2 狀態(tài)空間的搜索策略5.2 狀態(tài)空間的搜索策略盲目搜索盲目搜索n搜索按規(guī)定的路線進(jìn)行，不使用與問題有關(guān)的搜索按規(guī)定的路線進(jìn)行，不使用與問題有關(guān)的啟發(fā)性信息；啟發(fā)性信息；n適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問題。適用于其狀態(tài)空間圖是樹狀結(jié)構(gòu)的一類問題。啟發(fā)式搜索啟發(fā)式搜索 使用與問題有關(guān)的啟發(fā)性信息，并以這些啟發(fā)性使用與問題有關(guān)的啟發(fā)性信息，并以這些啟發(fā)性信息指導(dǎo)搜索過程，可以高效地求解結(jié)構(gòu)復(fù)雜的信息指導(dǎo)搜索過程，可以高效地求解結(jié)構(gòu)復(fù)雜的問題。問題。5.2.1 狀態(tài)空間的一般搜索過程一個復(fù)雜問題的狀態(tài)空間一般都是一個復(fù)雜問題的狀態(tài)空間一般都是十分龐大十分龐大的。如的。如64階梵塔問題共有階梵塔

7、問題共有3的的64次方個不同的狀態(tài)。次方個不同的狀態(tài)。把問題的所有狀態(tài)空間都進(jìn)行存儲有時候是把問題的所有狀態(tài)空間都進(jìn)行存儲有時候是不可能不可能的。的。把問題的所有狀態(tài)空間都進(jìn)行存儲也是把問題的所有狀態(tài)空間都進(jìn)行存儲也是不必要不必要的。因的。因?yàn)榕c解題有關(guān)的狀態(tài)空間往往只是整個狀態(tài)空間的一為與解題有關(guān)的狀態(tài)空間往往只是整個狀態(tài)空間的一部分，只要能生產(chǎn)并存儲這部分狀態(tài)空間就可以求出部分，只要能生產(chǎn)并存儲這部分狀態(tài)空間就可以求出問題的解。問題的解。5.2.1 狀態(tài)空間的一般搜索過程如何產(chǎn)生問題需要的狀態(tài)空間從而實(shí)現(xiàn)對問題的求解呢？如何產(chǎn)生問題需要的狀態(tài)空間從而實(shí)現(xiàn)對問題的求解呢？答案就是答案就是搜索

8、技術(shù)搜索技術(shù)。搜索技術(shù)搜索技術(shù)基本思想基本思想：把問題的初始狀態(tài)作為當(dāng)前狀態(tài)，選：把問題的初始狀態(tài)作為當(dāng)前狀態(tài)，選擇適用的算符對其操作，生產(chǎn)一組子狀態(tài)，然后檢查目標(biāo)擇適用的算符對其操作，生產(chǎn)一組子狀態(tài)，然后檢查目標(biāo)狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解，否則按某種搜索策略從已生成的狀態(tài)中再選擇一個的解，否則按某種搜索策略從已生成的狀態(tài)中再選擇一個作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或者不作為當(dāng)前狀態(tài)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符為止。再有可供操作的狀態(tài)及算符為止。5.2.1 狀態(tài)空間的一般

9、搜索過程OPEN表和表和CLOSE表表nOPEN表用于存放剛生成的節(jié)點(diǎn)。對于不同的搜索策略，節(jié)點(diǎn)在表用于存放剛生成的節(jié)點(diǎn)。對于不同的搜索策略，節(jié)點(diǎn)在OPEN表中的排列順序是不同的。表中的排列順序是不同的。nCLOSE表用于存放將要擴(kuò)展的節(jié)點(diǎn)。對一個節(jié)點(diǎn)的擴(kuò)展是指：用所表用于存放將要擴(kuò)展的節(jié)點(diǎn)。對一個節(jié)點(diǎn)的擴(kuò)展是指：用所有可適用的算符對該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn)有可適用的算符對該節(jié)點(diǎn)進(jìn)行操作，生成一組子節(jié)點(diǎn) OPEN表狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號 狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn)CLOSE表搜索的一般過程搜索的一般過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，并建立目前只包含表，并建立目前只包含S0的圖，的圖，記

10、為記為G；w檢查檢查OPEN表是否為空，若為空則問題無解，退出；表是否為空，若為空則問題無解，退出；w把把OPEN表的第一個節(jié)點(diǎn)取出放入表的第一個節(jié)點(diǎn)取出放入CLOSE表，并計(jì)該節(jié)表，并計(jì)該節(jié)點(diǎn)為點(diǎn)為n；w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出；退出；w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的先輩的那些子節(jié)點(diǎn)記做集合那些子節(jié)點(diǎn)記做集合M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的的子節(jié)點(diǎn)加入子節(jié)點(diǎn)加入G中；中；w針對針對M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：中子節(jié)點(diǎn)的不同

11、情況，分別進(jìn)行如下處理：w對于那些未曾在G中出現(xiàn)過的M成員設(shè)置一個指向父節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它們放入OPEN表；（不在OPEN表）w對于那些先前已經(jīng)在G中出現(xiàn)過的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針；（在OPEN表中）w對于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針；（在CLOSE表中）w按某種搜索策略對按某種搜索策略對OPEN表中的節(jié)點(diǎn)進(jìn)行排序；表中的節(jié)點(diǎn)進(jìn)行排序；w轉(zhuǎn)第轉(zhuǎn)第2步。步。搜索的一般過程搜索的一般過程對一般搜索過程的一些說明對一般搜索過程的一些說明一個節(jié)點(diǎn)經(jīng)一個算符操作后一般只生成一個子節(jié)一個節(jié)點(diǎn)經(jīng)一個算符操作后一般只生成

12、一個子節(jié)點(diǎn)。但適用于一個節(jié)點(diǎn)的算符可能有多個，此時點(diǎn)。但適用于一個節(jié)點(diǎn)的算符可能有多個，此時就會生成一組子節(jié)點(diǎn)。這些子節(jié)點(diǎn)中可能有些是就會生成一組子節(jié)點(diǎn)。這些子節(jié)點(diǎn)中可能有些是當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等，此時不能當(dāng)前擴(kuò)展節(jié)點(diǎn)的父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等，此時不能把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)。把這些先輩節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)的子節(jié)點(diǎn)。對一般搜索過程的一些說明對一般搜索過程的一些說明一個新生成的節(jié)點(diǎn)，它可能是第一次被生成的一個新生成的節(jié)點(diǎn)，它可能是第一次被生成的節(jié)點(diǎn)，也可能是先前已作為其它節(jié)點(diǎn)的子節(jié)點(diǎn)節(jié)點(diǎn)，也可能是先前已作為其它節(jié)點(diǎn)的子節(jié)點(diǎn)被生成過，當(dāng)前又作為另一個節(jié)點(diǎn)的子節(jié)點(diǎn)被被生成過，當(dāng)

13、前又作為另一個節(jié)點(diǎn)的子節(jié)點(diǎn)被再次生成。此時，它究竟應(yīng)選擇哪個節(jié)點(diǎn)作為再次生成。此時，它究竟應(yīng)選擇哪個節(jié)點(diǎn)作為父節(jié)點(diǎn)？一般由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價來決父節(jié)點(diǎn)？一般由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的代價來決定，處于代價小的路途上的那個節(jié)點(diǎn)就作為該定，處于代價小的路途上的那個節(jié)點(diǎn)就作為該節(jié)點(diǎn)的父節(jié)點(diǎn)。節(jié)點(diǎn)的父節(jié)點(diǎn)。對一般搜索過程的一些說明在搜索過程中，一旦某個被考察的節(jié)點(diǎn)是目標(biāo)在搜索過程中，一旦某個被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就得到了一個解。該解是由從初始節(jié)點(diǎn)到節(jié)點(diǎn)就得到了一個解。該解是由從初始節(jié)點(diǎn)到該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成。該目標(biāo)節(jié)點(diǎn)路徑上的算符構(gòu)成。如果在搜索中一直找不到目標(biāo)節(jié)點(diǎn)，而且如果在搜索中一直找不到目標(biāo)節(jié)

14、點(diǎn)，而且OPENOPEN表中不再有可供擴(kuò)展的節(jié)點(diǎn)，則搜索失敗。表中不再有可供擴(kuò)展的節(jié)點(diǎn)，則搜索失敗。對一般搜索過程的一些說明通過搜索得到的圖稱為搜索圖，搜索圖是狀態(tài)通過搜索得到的圖稱為搜索圖，搜索圖是狀態(tài)空間圖的一個子集。由搜索圖中的所有節(jié)點(diǎn)及空間圖的一個子集。由搜索圖中的所有節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。反向指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹。根據(jù)搜索樹可給出問題的解。根據(jù)搜索樹可給出問題的解。5.2.2 廣度（寬度）優(yōu)先搜索基本思想基本思想：從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S0開始，逐層地對節(jié)點(diǎn)進(jìn)行擴(kuò)展并開始，逐層地對節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)。在第考察它是否為目標(biāo)節(jié)點(diǎn)。在

15、第n層的節(jié)點(diǎn)沒有全層的節(jié)點(diǎn)沒有全部擴(kuò)展并考察之前，不對第部擴(kuò)展并考察之前，不對第n1層的節(jié)點(diǎn)進(jìn)行層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。擴(kuò)展。OPEN表中節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，表中節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。廣度優(yōu)先搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表。表。w如果如果OPEN表為空，則問題無解，退出。表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求

16、得了問題的解，退出。退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的尾尾部，并為每部，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。步。重排九宮的廣度優(yōu)先搜索重排九宮的廣度優(yōu)先搜索操作符：空格左移、上移、右移、下移操作符：空格左移、上移、右移、下移2 8 31 47 6 52 8 3 1 47 6 5 8 32 1 47 6 52 8 37 1 4 6 58 32 1 47 6 52 8 37 1 46 58 3 2 1 4 7 6 58 1 32 47 6 5

17、2 8 37 46 1 5 2 8 3 7 1 46 52 31 8 47 6 5 2 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 5 2 8 31 4 7 6 52 3 1 8 4 7 6 5 2 3 41 8 7 6 52 8 1 4 3 7 6 52 81 4 37 6 5 2 8 3 1 4 57 62 8 31 4 57 62 8 31 6 47 5 2 8 3 1 6 47 6 2 8 36 4 1 7 5 2 8 3 1 6 47 5 2 8 31 6 7 5 4S0Sg1234567891011121314151617181192021222324

18、2526小插曲關(guān)于九宮問題射雕英雄傳射雕英雄傳 瑛姑的問題瑛姑的問題：將一至九這九個數(shù)字排成：將一至九這九個數(shù)字排成三列，不論縱橫斜角，每三字相加都是三列，不論縱橫斜角，每三字相加都是十五，如何排法？十五，如何排法？ 黃蓉的回答黃蓉的回答：九宮之義，法以靈龜，二：九宮之義，法以靈龜，二四為肩，六八為足，左三右七，戴九履四為肩，六八為足，左三右七，戴九履一，五居中央。一，五居中央。幻方問題幻方問題中國人首先發(fā)現(xiàn)了幻方中國人首先發(fā)現(xiàn)了幻方 洛水神龜獻(xiàn)奇圖洛水神龜獻(xiàn)奇圖關(guān)于三階幻方的奧秘關(guān)于三階幻方的奧秘南宋楊輝 研究幻方第一人 幻方問題幻方問題在我國古代稱為“縱橫圖”，又叫“九宮算圖”。南宋大數(shù)學(xué)

19、家楊輝在1275年所著的續(xù)古摘奇算法續(xù)古摘奇算法兩卷中，除了給出洛書中3階幻方的構(gòu)造方法外，還給出了4階至10階的幻方。楊輝對楊輝對3 3階幻方的解釋階幻方的解釋29435761816592117310613812三階幻方(15) 四階幻方(34)歐美的幻方熱德國畫家和文藝?yán)碚摷业聡嫾液臀乃嚴(yán)碚摷襾G勒丟勒在在1514年創(chuàng)年創(chuàng)作的一幅銅版雕刻畫作的一幅銅版雕刻畫憂傷憂傷中就有一中就有一個個4階幻方。階幻方。 名畫名畫憂傷憂傷現(xiàn)在珍藏于現(xiàn)在珍藏于大英博物館。大英博物館。富蘭克林富蘭克林也投入了很大精力研究幻方。也投入了很大精力研究幻方。名畫名畫憂傷憂傷廣度優(yōu)先算法中需要注意的問題1、對于任意一個

20、可擴(kuò)展的節(jié)點(diǎn)，總是按照固定的、對于任意一個可擴(kuò)展的節(jié)點(diǎn)，總是按照固定的操作符的順序?qū)ζ溥M(jìn)行擴(kuò)展（如前面重排九宮例操作符的順序?qū)ζ溥M(jìn)行擴(kuò)展（如前面重排九宮例子中的子中的空格左移、上移、右移、下移空格左移、上移、右移、下移）。）。2、在對任一節(jié)點(diǎn)進(jìn)行擴(kuò)展的時候，如果所得的某、在對任一節(jié)點(diǎn)進(jìn)行擴(kuò)展的時候，如果所得的某個子節(jié)點(diǎn)（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其個子節(jié)點(diǎn)（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復(fù)畫出（不送入放棄，不再重復(fù)畫出（不送入OPEN表）。表）。因此，廣度優(yōu)先搜索的本質(zhì)是：因此，廣度優(yōu)先搜索的本質(zhì)是：以初始節(jié)點(diǎn)為根節(jié)以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成點(diǎn)

21、，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。一棵搜索樹。廣度優(yōu)先搜索的特點(diǎn)優(yōu)點(diǎn)優(yōu)點(diǎn)：只要問題有解，用廣度優(yōu)先搜索總可以得到解，只要問題有解，用廣度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。而且得到的是路徑最短的解。缺點(diǎn)缺點(diǎn)：廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。點(diǎn)較遠(yuǎn)時將會產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。5.2.3 深度優(yōu)先搜索基本思想基本思想：從初始節(jié)點(diǎn)開始，在其子節(jié)點(diǎn)中選擇一個節(jié)：從初始節(jié)點(diǎn)開始，在其子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)

22、，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)近c(diǎn)中選擇一個節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)達(dá)某個子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。擴(kuò)展時，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別：廣度優(yōu)先搜：廣度優(yōu)先搜索是將節(jié)點(diǎn)索是將節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的尾部，而深度優(yōu)表的尾部，而深度優(yōu)先搜索是把節(jié)點(diǎn)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的首部。表的首部。深度優(yōu)先搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0

23、放入放入OPEN表。表。w如果如果OPEN表為空，則問題無解，退出。表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的首首部，并為每部，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。步。重排九宮的深度優(yōu)先搜索2 8 31 47 6 5

24、2 8 3 1 47 6 52 8 31 67 5 42 31 8 47 6 5 2 8 31 4 7 6 52 8 1 6 3 7 5 42 81 6 37 5 42 8 31 6 47 5 2 8 3 1 6 47 6 2 8 3 1 6 47 5 2 8 31 6 7 5 4S01234.5操作符：空格左移、上移、右移、下移深度優(yōu)先搜索的特點(diǎn)在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個分支，就將沿著該在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該

25、較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是先搜索是不完備不完備的，即使問題有解，它也不一定能求得解。的，即使問題有解，它也不一定能求得解。用深度優(yōu)先求得的解，不一定是路徑最短的解。用深度優(yōu)先求得的解，不一定是路徑最短的解。本質(zhì)：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照深度優(yōu)本質(zhì)：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。先的原則，生成一棵搜索樹。5.2.4 有界深度優(yōu)先搜索 基本思想基本思想：n對深度優(yōu)先搜索引入搜索深度界限（設(shè)為對深度優(yōu)先搜索引入搜索深

26、度界限（設(shè)為dm），），當(dāng)搜索深度達(dá)到了深度界限，而仍未出現(xiàn)目標(biāo)節(jié)當(dāng)搜索深度達(dá)到了深度界限，而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時，就換一個分支進(jìn)行搜索點(diǎn)時，就換一個分支進(jìn)行搜索。n“有界有界”是為了解決深度優(yōu)先搜索不完備的問題，是為了解決深度優(yōu)先搜索不完備的問題，避免陷入無窮分支的死循環(huán)。避免陷入無窮分支的死循環(huán)。有界深度優(yōu)先搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表中，置表中，置S0的深度的深度d(S0)=0。w如果如果OPEN表為空，則問題無解，退出。表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)

27、n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n的深度的深度d(n)=dm，則轉(zhuǎn)第，則轉(zhuǎn)第2步（此時節(jié)點(diǎn)步（此時節(jié)點(diǎn)n位于位于CLOSE表，但并未進(jìn)行擴(kuò)展）。表，但并未進(jìn)行擴(kuò)展）。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。1.擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的首首部，為每一個部，為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，將每一個子節(jié)點(diǎn)的深度子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，將每一個子節(jié)點(diǎn)的深度設(shè)置為設(shè)置為d(n)+1，然后轉(zhuǎn)第，然后轉(zhuǎn)第2步。步。對有界深度優(yōu)先搜索的說明如果問題有解，且其路徑長

28、度如果問題有解，且其路徑長度ddm m，則上，則上述搜索過程一定能求得解。但是，若解的述搜索過程一定能求得解。但是，若解的路徑長度路徑長度ddm m, ,則上述搜索過程就得不到解。則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，這說明在有界深度優(yōu)先搜索中，深度界限深度界限的選擇是很重要的的選擇是很重要的。要恰當(dāng)?shù)亟o出要恰當(dāng)?shù)亟o出d dm m的值是比較困難的。即使的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。能求出解，它也不一定是最優(yōu)解。有界深度優(yōu)先搜索的改進(jìn)w先任意設(shè)定一個較小的數(shù)作為先任意設(shè)定一個較小的數(shù)作為dm，然后進(jìn)行上，然后進(jìn)行上述的有界深度優(yōu)先搜索，當(dāng)搜索達(dá)到了指定的述的

29、有界深度優(yōu)先搜索，當(dāng)搜索達(dá)到了指定的深度界限深度界限dm仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，并且仍未發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，并且CLOSE表表中仍有待擴(kuò)展節(jié)點(diǎn)時，就將這些節(jié)點(diǎn)送回中仍有待擴(kuò)展節(jié)點(diǎn)時，就將這些節(jié)點(diǎn)送回OPEN表，同時增大深度界限表，同時增大深度界限dm，繼續(xù)向下搜索。如，繼續(xù)向下搜索。如此不斷地增大此不斷地增大dm，只要問題有解，就一定可以，只要問題有解，就一定可以找到它。但此時找到的解不一定是最優(yōu)解。找到它。但此時找到的解不一定是最優(yōu)解。有界深度優(yōu)先搜索的改進(jìn)2. 為了找到最優(yōu)解，可增設(shè)一個表為了找到最優(yōu)解，可增設(shè)一個表R，每找到目，每找到目標(biāo)節(jié)點(diǎn)標(biāo)節(jié)點(diǎn)Sg后，就把它放入到后，就把它放入到R的前面，并令的

30、前面，并令dm等于該目標(biāo)節(jié)點(diǎn)所對應(yīng)的路徑長度，然后等于該目標(biāo)節(jié)點(diǎn)所對應(yīng)的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以最后求得超過先求得的解的路徑長度，所以最后求得的解一定是最優(yōu)解。的解一定是最優(yōu)解。重排九宮的有界深度優(yōu)先搜索設(shè)深度界限dm42 3 1 8 4 7 6 5 2 3 41 8 7 6 5221 2 38 47 6 51 2 37 8 46 5 2 31 8 47 6 51 2 3 8 47 6 52 3 41 87 6 52 3 41 8 57 62 8 3 1 47 6 52 31 8 47 6 52 8

31、1 4 37 6 52 4 81 37 6 52 8 31 4 57 62 8 31 57 4 68 32 6 41 7 52 8 36 41 7 52 8 31 67 5 42 81 6 37 5 62 81 4 37 6 52 8 1 4 3 7 6 52 8 31 4 57 6 2 8 3 1 4 57 6 2 8 36 4 1 7 5 2 8 31 6 7 5 4 2 8 3 1 6 47 6 2 8 3 1 6 47 5 2 8 31 4 7 6 52 8 31 6 47 52 8 31 47 6 5S0123Sg78914151623242526456101112131718192

32、02127285.2.5 代價樹的廣度優(yōu)先搜索邊上標(biāo)有代價邊上標(biāo)有代價(或費(fèi)用或費(fèi)用)的樹稱為的樹稱為代價樹代價樹。用用g(x)表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)x的代價，的代價，用用c(x1,x2)表示從父節(jié)點(diǎn)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)到子節(jié)點(diǎn)x2的的代價，則有：代價，則有：g(x2)=g(x1)+c(x1,x2)5.2.5 代價樹的廣度優(yōu)先搜索每次從每次從OPENOPEN表中選擇節(jié)點(diǎn)往表中選擇節(jié)點(diǎn)往CLOSECLOSE表傳送時，總是表傳送時，總是選擇其中代價最小的節(jié)點(diǎn)。也就是說，選擇其中代價最小的節(jié)點(diǎn)。也就是說，OPENOPEN表中的表中的節(jié)點(diǎn)在任一時刻都是按其代價從小到大排序的。

33、代節(jié)點(diǎn)在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點(diǎn)排在前面，代價大的節(jié)點(diǎn)排在后面。價小的節(jié)點(diǎn)排在前面，代價大的節(jié)點(diǎn)排在后面。如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求如果問題有解，代價樹的廣度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。得解，并且求出的是最優(yōu)解。該算法應(yīng)用的條件該算法應(yīng)用的條件: :該算法是針對代價樹的算法。該算法是針對代價樹的算法。為了采用該算法對圖進(jìn)行搜索，必須先將圖轉(zhuǎn)換為為了采用該算法對圖進(jìn)行搜索，必須先將圖轉(zhuǎn)換為代價樹。代價樹。代價樹廣度優(yōu)先搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，令表，令g(S0)=0。w如果如果OPEN表為空，則問題無解，退出。

34、表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，并，為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，并將各子節(jié)點(diǎn)放入將各子節(jié)點(diǎn)放入OPEN表中；計(jì)算各子節(jié)點(diǎn)的代價，按各節(jié)表中；計(jì)算各子節(jié)點(diǎn)的代價，按各節(jié)點(diǎn)的代價對點(diǎn)的代價對OPEN表中的全部節(jié)點(diǎn)進(jìn)行排序表中的全部節(jié)點(diǎn)進(jìn)行排序(按從小到大的按從小到大的

35、順序順序)，然后轉(zhuǎn)第，然后轉(zhuǎn)第2步。步。代價樹示例ABCDE432345交通圖AC1B1D1E2B2E4D2E1C2E33423454523交通圖的代價樹圖到代價樹的轉(zhuǎn)換求A到E的最小費(fèi)用交通路線代價樹的廣度優(yōu)先搜索5.2.6 代價樹的深度優(yōu)先搜索在代價樹的廣度優(yōu)先搜索中，每次都是從在代價樹的廣度優(yōu)先搜索中，每次都是從OPEN表的全體節(jié)點(diǎn)中選擇一個代價最小的節(jié)表的全體節(jié)點(diǎn)中選擇一個代價最小的節(jié)點(diǎn)送入點(diǎn)送入CLOSE表進(jìn)行考察表進(jìn)行考察在代價樹的深度優(yōu)先搜索中，是從剛擴(kuò)展出的在代價樹的深度優(yōu)先搜索中，是從剛擴(kuò)展出的子節(jié)點(diǎn)中選擇一個代價最小的節(jié)點(diǎn)送入子節(jié)點(diǎn)中選擇一個代價最小的節(jié)點(diǎn)送入CLOSE表進(jìn)

36、行考察表進(jìn)行考察代價樹的深度優(yōu)先搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，令表，令g(S0)=0。w如果如果OPEN表為空，則問題無解，退出。表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。解，退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)按，將其子節(jié)點(diǎn)按“邊邊”代價從小到大的順代價從小到大的順序放到序放到OPEN表中的首部，并為每一個子節(jié)點(diǎn)都配表中的首

37、部，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。步。1.代價樹的深度優(yōu)先搜索是不完備的。代價樹的深度優(yōu)先搜索是不完備的。 總總 結(jié)結(jié) 1、上述各種搜索方法的本質(zhì)是，以初始節(jié)、上述各種搜索方法的本質(zhì)是，以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，按照既定的策略對狀態(tài)空間圖點(diǎn)為根節(jié)點(diǎn)，按照既定的策略對狀態(tài)空間圖進(jìn)行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。進(jìn)行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。 2、由于對狀態(tài)空間圖遍歷的策略是既定的，、由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。因此這些方法統(tǒng)稱為盲目搜索方法。5.2.7 啟發(fā)式搜索盲目搜索具有較大的盲目性，產(chǎn)生的無用

38、盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點(diǎn)較多，效率不高。節(jié)點(diǎn)較多，效率不高。啟發(fā)式搜索采用問題自身的特性信息，以啟發(fā)式搜索采用問題自身的特性信息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。這種指導(dǎo)搜索朝著最有希望的方向前進(jìn)。這種搜索針對性較強(qiáng)，因而效率較高。搜索針對性較強(qiáng)，因而效率較高。1.啟發(fā)性信息與估價函數(shù)可用于指導(dǎo)搜索過程，且與具體問題有關(guān)的信息稱為可用于指導(dǎo)搜索過程，且與具體問題有關(guān)的信息稱為啟發(fā)性信息。啟發(fā)性信息。用于評估節(jié)點(diǎn)重要性的函數(shù)稱為估價函數(shù)。其一般形用于評估節(jié)點(diǎn)重要性的函數(shù)稱為估價函數(shù)。其一般形式為：式為：f(x) = g(x)+h(x)其中其中g(shù)(x)g(x)表示從初始節(jié)點(diǎn)表示從

39、初始節(jié)點(diǎn)S S0 0到節(jié)點(diǎn)到節(jié)點(diǎn)x x的代價；的代價；h(x)h(x)是從是從節(jié)點(diǎn)節(jié)點(diǎn)x x到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)S Sg g的最優(yōu)路徑的代價的估計(jì)，它體的最優(yōu)路徑的代價的估計(jì)，它體現(xiàn)了問題的啟發(fā)性信息，稱為啟發(fā)函數(shù)。現(xiàn)了問題的啟發(fā)性信息，稱為啟發(fā)函數(shù)。 f(x) f(x) 決定決定節(jié)點(diǎn)在節(jié)點(diǎn)在OPENOPEN表中的次序。表中的次序。1.啟發(fā)性信息與估價函數(shù)g(x) 指出了搜索的橫向趨勢，有利于搜索的完備指出了搜索的橫向趨勢，有利于搜索的完備性，但影響搜索的效率。性，但影響搜索的效率。h(x)指出了搜索的縱向趨勢，有利于提高搜索的指出了搜索的縱向趨勢，有利于提高搜索的效率，但影響搜索的完備性。效

40、率，但影響搜索的完備性。確定確定f(x) 時要使時要使g(x)+h(x)各占適當(dāng)比重。各占適當(dāng)比重。啟發(fā)函數(shù)示例設(shè)有如下結(jié)構(gòu)的移動將牌游戲：設(shè)有如下結(jié)構(gòu)的移動將牌游戲：游戲規(guī)則游戲規(guī)則：w當(dāng)一個牌移入相鄰的空位置時，費(fèi)用為一個單位。當(dāng)一個牌移入相鄰的空位置時，費(fèi)用為一個單位。w一個牌至多可跳過兩個牌進(jìn)入空位置，其費(fèi)用等于跳過的牌數(shù)加一個牌至多可跳過兩個牌進(jìn)入空位置，其費(fèi)用等于跳過的牌數(shù)加1。要求要求：把所有的：把所有的B都移至都移至W的右邊，請?jiān)O(shè)計(jì)啟發(fā)函數(shù)的右邊，請?jiān)O(shè)計(jì)啟發(fā)函數(shù)h(x)。解解：根據(jù)要求可知，：根據(jù)要求可知，W左邊的左邊的B越少越接近目標(biāo)，因此可用越少越接近目標(biāo)，因此可用W左邊左

41、邊B的的個數(shù)作為個數(shù)作為h(x),即即h(x)=3(每個每個W左邊左邊B的個數(shù)的總和的個數(shù)的總和)這里乘以系數(shù)這里乘以系數(shù)3是為了擴(kuò)大是為了擴(kuò)大h(x)在在f(x)中的比重。中的比重。BBBWWWEBEBW W BW例如下面這一狀態(tài)：h(x)=3(2+2+3)=212.局部擇優(yōu)搜索 局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對深度優(yōu)先搜索方法的一種改進(jìn)。是對深度優(yōu)先搜索方法的一種改進(jìn)。 基本思想：當(dāng)一個節(jié)點(diǎn)被擴(kuò)展以后，按基本思想：當(dāng)一個節(jié)點(diǎn)被擴(kuò)展以后，按f(x)對每一個子節(jié)點(diǎn)計(jì)算估價值，并選對每一個子節(jié)點(diǎn)計(jì)算估價值，并選擇最小者作為下一個要考察的節(jié)點(diǎn)。擇最小者作為下

42、一個要考察的節(jié)點(diǎn)。局部擇優(yōu)搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，計(jì)算表，計(jì)算f(S0)。w如果如果OPEN表為空，則問題無解，退出。表為空，則問題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，用估價函數(shù)，用估價函數(shù)f(x)計(jì)算每個子節(jié)點(diǎn)的估價值，計(jì)算每個子節(jié)點(diǎn)的估價值，并按估價值從小到大的順序放到并按估價值從小到大的順序放

43、到OPEN表中的首部，并表中的首部，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第2步。步。2.局部擇優(yōu)搜索在局部擇優(yōu)搜索中，若令在局部擇優(yōu)搜索中，若令f(x) = g(x)，則，則局局部擇優(yōu)搜索就成為代價樹的深度優(yōu)先搜索。部擇優(yōu)搜索就成為代價樹的深度優(yōu)先搜索。在局部擇優(yōu)搜索中，若令在局部擇優(yōu)搜索中，若令f(x) =d(x)，這里，這里d(x) 表示節(jié)點(diǎn)表示節(jié)點(diǎn)x的深度，則的深度，則局部擇優(yōu)搜索就成局部擇優(yōu)搜索就成為深度優(yōu)先搜索。為深度優(yōu)先搜索。因此：因此：深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索均深度優(yōu)先搜索、代價樹的深度優(yōu)先搜索均為局部擇優(yōu)搜索的特

44、例。為局部擇優(yōu)搜索的特例。3.全局擇優(yōu)搜索每當(dāng)要選擇下一個節(jié)點(diǎn)進(jìn)行考察時，局部擇優(yōu)每當(dāng)要選擇下一個節(jié)點(diǎn)進(jìn)行考察時，局部擇優(yōu)搜索只是從剛生成的子節(jié)點(diǎn)中選擇一個估價值搜索只是從剛生成的子節(jié)點(diǎn)中選擇一個估價值最小的節(jié)點(diǎn)。其選擇范圍比較窄。最小的節(jié)點(diǎn)。其選擇范圍比較窄。每當(dāng)要選擇下一個節(jié)點(diǎn)進(jìn)行考察時，全局擇優(yōu)每當(dāng)要選擇下一個節(jié)點(diǎn)進(jìn)行考察時，全局擇優(yōu)搜索每次總是從搜索每次總是從OPEN表的全體節(jié)點(diǎn)中選擇一表的全體節(jié)點(diǎn)中選擇一個估價值最小的節(jié)點(diǎn)。個估價值最小的節(jié)點(diǎn)。全局擇優(yōu)搜索過程w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，計(jì)算表，計(jì)算f(S0)。w如果如果OPEN表為空，則問題無解，退出。表為空，則問

45、題無解，退出。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問題的解，退出。退出。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。1.擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，用估價函數(shù)，用估價函數(shù)f(x)計(jì)算每個子節(jié)點(diǎn)的估價值，計(jì)算每個子節(jié)點(diǎn)的估價值，并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子并為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子節(jié)點(diǎn)都送入節(jié)點(diǎn)都送入OPEN表中，然后對表中，然后對OPEN表中的全部節(jié)點(diǎn)按表中的全部節(jié)點(diǎn)按估價值從小至大的順序進(jìn)行

46、排序，然后轉(zhuǎn)第估價值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第2步。步。3.全局擇優(yōu)搜索在全局擇優(yōu)搜索中，若令在全局擇優(yōu)搜索中，若令f(x) = g(x)，則，則它就它就成為代價樹的廣度優(yōu)先搜索。成為代價樹的廣度優(yōu)先搜索。在全局擇優(yōu)搜索中，若令在全局擇優(yōu)搜索中，若令f(x) =d(x)，這里，這里d(x) 表示節(jié)點(diǎn)表示節(jié)點(diǎn)x的深度，則的深度，則它就成為廣度優(yōu)先搜索。它就成為廣度優(yōu)先搜索。因此：廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索是因此：廣度優(yōu)先搜索、代價樹的廣度優(yōu)先搜索是全局擇優(yōu)搜索的兩個特例。全局擇優(yōu)搜索的兩個特例。重排九宮問題的全局擇優(yōu)搜索樹設(shè)估價函數(shù)為 f(x)=d(x)+h(x)，其中，d(x)表

47、示節(jié)點(diǎn)x的深度，h(x)表示節(jié)點(diǎn)x的格局與目標(biāo)節(jié)點(diǎn)格局不相同的牌數(shù)。1 2 38 47 6 51 2 37 8 46 5 2 31 8 47 6 51 2 3 8 47 6 52 8 3 1 47 6 52 31 8 47 6 5 2 8 31 4 7 6 52 8 31 6 47 52 8 31 47 6 5S035Sg556748 3 2 1 4 7 6 5 2 8 3 7 1 46 5672 3 1 8 4 7 6 57655.3 與/或樹的搜索策略5.3.1 與與/或樹的一般搜索過程或樹的一般搜索過程5.3.2 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索5.3.3 剪枝技術(shù)剪枝技術(shù)5.3 與

48、/或樹的搜索策略5.3 與/或樹的搜索策略 用用與與/或樹方法求解問題時，首先要定義問題的描述方法及或樹方法求解問題時，首先要定義問題的描述方法及分解和變換問題的算符，然后就可以用它們通過搜索生成與分解和變換問題的算符，然后就可以用它們通過搜索生成與/或樹，從而求得原始問題的解?；驑洌瑥亩蟮迷紗栴}的解。在與在與/或樹中，由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等或樹中，由可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為可解節(jié)點(diǎn)的過程稱為為可解節(jié)點(diǎn)的過程稱為可解標(biāo)示過程可解標(biāo)示過程；由不可解子節(jié)點(diǎn)來確；由不可解子節(jié)點(diǎn)來確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過程稱為定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)等為不可解節(jié)點(diǎn)的過程稱

49、為不可解標(biāo)不可解標(biāo)示過程示過程；在與在與/或樹搜索過程中，將反復(fù)使用可解和不可解標(biāo)示過程，或樹搜索過程中，將反復(fù)使用可解和不可解標(biāo)示過程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。5.3.1 與與/或樹的一般搜索過程或樹的一般搜索過程w把原始問題作為初始節(jié)點(diǎn)把原始問題作為初始節(jié)點(diǎn)S0，并把，并把S0作為當(dāng)前節(jié)作為當(dāng)前節(jié)點(diǎn)；點(diǎn)；w應(yīng)用分解或等價算法對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；應(yīng)用分解或等價算法對當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；w為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；為每個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；w選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第

50、2和第和第3步，期間步，期間將反復(fù)使用可解和不可解標(biāo)示過將反復(fù)使用可解和不可解標(biāo)示過程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為程，直到初始節(jié)點(diǎn)被標(biāo)示為可解或不可解節(jié)點(diǎn)為止。止。w由這個搜索過程形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索由這個搜索過程形成的節(jié)點(diǎn)和指針結(jié)構(gòu)稱為搜索樹。樹。與與/或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表。表。w把把OPEN表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w若節(jié)點(diǎn)若節(jié)點(diǎn)n可擴(kuò)展，則做如下工作?？蓴U(kuò)展，則做如下工作。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的尾部，并為每

51、個子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的表的尾部，并為每個子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用。指針，以備標(biāo)示過程使用。w考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用可解標(biāo)示過程對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)用可解標(biāo)示過程對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示也被標(biāo)示為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節(jié)點(diǎn)，則為可解節(jié)點(diǎn)，則從從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。表中刪去具有可解先輩的節(jié)點(diǎn)

52、。w轉(zhuǎn)第轉(zhuǎn)第2步。步。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則做如下工作。不可擴(kuò)展，則做如下工作。w標(biāo)示節(jié)點(diǎn)標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。為不可解節(jié)點(diǎn)。w用不可解標(biāo)示過程對用不可解標(biāo)示過程對n的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也也被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定S0為不可解節(jié)點(diǎn)，則從為不可解節(jié)點(diǎn)，則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。表中刪去具有不可解先輩的節(jié)點(diǎn)。w轉(zhuǎn)第轉(zhuǎn)第2步。步。與與/或樹的（有界）深度優(yōu)先搜索或樹的（有界）深度優(yōu)先搜索w把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPE

53、N表。表。w把把OPEN表的第個節(jié)一點(diǎn)（記為節(jié)點(diǎn)表的第個節(jié)一點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSE表。表。w若節(jié)點(diǎn)若節(jié)點(diǎn)n的深度大于等于深度界限的深度大于等于深度界限，則轉(zhuǎn)第，則轉(zhuǎn)第5步中的第步中的第。w若節(jié)點(diǎn)若節(jié)點(diǎn)n可擴(kuò)展，則做如下工作。可擴(kuò)展，則做如下工作。w擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的首首部，并為每個子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)部，并為每個子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，以備標(biāo)示過程使用。的指針，以備標(biāo)示過程使用。w考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并考察這些子節(jié)點(diǎn)中是否有終止節(jié)點(diǎn)。如有，則標(biāo)示這些終止節(jié)點(diǎn)為可解節(jié)點(diǎn)，并用

54、可解標(biāo)示過程對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)用可解標(biāo)示過程對其先輩節(jié)點(diǎn)中的可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)S0也被標(biāo)示也被標(biāo)示為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定為可解節(jié)點(diǎn)，則得到了解樹，搜索成功，退出；如果不能確定S0為可解節(jié)點(diǎn)，則為可解節(jié)點(diǎn)，則從從OPEN表中刪去具有可解先輩的節(jié)點(diǎn)。表中刪去具有可解先輩的節(jié)點(diǎn)。w轉(zhuǎn)第轉(zhuǎn)第2步。步。w若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則做如下工作。不可擴(kuò)展，則做如下工作。w標(biāo)示節(jié)點(diǎn)標(biāo)示節(jié)點(diǎn)n為不可解節(jié)點(diǎn)。為不可解節(jié)點(diǎn)。w用不可解標(biāo)示過程對用不可解標(biāo)示過程對n的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如果初始節(jié)點(diǎn)的先輩節(jié)點(diǎn)中的不可解節(jié)點(diǎn)進(jìn)行標(biāo)示。如

55、果初始節(jié)點(diǎn)S0也也被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定被標(biāo)示為不可解節(jié)點(diǎn)，則搜索失敗，退出；如果不能確定S0為不可解節(jié)點(diǎn)，則從為不可解節(jié)點(diǎn)，則從OPEN表中刪去具有不可解先輩的節(jié)點(diǎn)。表中刪去具有不可解先輩的節(jié)點(diǎn)。w轉(zhuǎn)第轉(zhuǎn)第2步。步。與/或樹的廣度和深度優(yōu)先搜索舉例A廣度優(yōu)先的擴(kuò)展順序：廣度優(yōu)先的擴(kuò)展順序：.5深度優(yōu)先的擴(kuò)展順序（規(guī)定深度界限為深度優(yōu)先的擴(kuò)展順序（規(guī)定深度界限為4）：）：1.3.B.5.2.4A,B為不可解的端節(jié)點(diǎn)為不可解的端節(jié)點(diǎn)t1,t2,t3,t4為終止節(jié)點(diǎn)為終止節(jié)點(diǎn)1t2t1t4t354B325.3.2 博弈樹的啟發(fā)式搜索博弈樹的啟發(fā)式搜索1.博

56、弈樹的基本概念博弈樹的基本概念博弈：博弈：諸如下棋、打牌、戰(zhàn)爭等一類競爭性諸如下棋、打牌、戰(zhàn)爭等一類競爭性智能活動智能活動?！岸肆愫?、全信息、非偶然二人零和、全信息、非偶然”博弈博弈（1）對壘的雙方）對壘的雙方A、B輪流采取行動，博弈的結(jié)果只有三輪流采取行動，博弈的結(jié)果只有三種情況：種情況：A勝勝B敗，敗，A敗敗B勝，平局。勝，平局。（2）對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷）對壘過程中，任何一方都了解當(dāng)前的格局及過去的歷史。史。（3）雙方都是理智的決定自己的行動的。）雙方都是理智的決定自己的行動的。博弈樹博弈樹描述博弈過程的與描述博弈過程的與/或樹稱為博弈樹，它具有如或樹稱為博弈

57、樹，它具有如下特點(diǎn)：下特點(diǎn)： （1 1）博弈的初始格局是初始節(jié)點(diǎn)。）博弈的初始格局是初始節(jié)點(diǎn)。 （2 2）在博弈樹中，或節(jié)點(diǎn)和與節(jié)點(diǎn)是交替出現(xiàn)）在博弈樹中，或節(jié)點(diǎn)和與節(jié)點(diǎn)是交替出現(xiàn)的。己方擴(kuò)展的節(jié)點(diǎn)之間是或關(guān)系，對方擴(kuò)展的。己方擴(kuò)展的節(jié)點(diǎn)之間是或關(guān)系，對方擴(kuò)展的節(jié)點(diǎn)之間是與關(guān)系。雙方輪流擴(kuò)展。的節(jié)點(diǎn)之間是與關(guān)系。雙方輪流擴(kuò)展。 （3 3）所有能使己方獲勝的終局都是可解節(jié)點(diǎn)，）所有能使己方獲勝的終局都是可解節(jié)點(diǎn)，使對方獲勝的終局是不可解節(jié)點(diǎn)。使對方獲勝的終局是不可解節(jié)點(diǎn)。 博弈樹是始終站在一方的立場上得出的。博弈樹是始終站在一方的立場上得出的。2. 極大極小分析法極大極小分析法是在二人博弈中，為

58、了使己方獲勝而采用的極大極小分析法是在二人博弈中，為了使己方獲勝而采用的分析方法。基本思想如下：分析方法?；舅枷肴缦拢海?）為博弈雙方中的一方尋找一個最優(yōu)行動方案。）為博弈雙方中的一方尋找一個最優(yōu)行動方案。（2）要考慮每一方案實(shí)施后對方可能采取的所有行動，并計(jì)算）要考慮每一方案實(shí)施后對方可能采取的所有行動，并計(jì)算可能的得分?？赡艿牡梅?。（3）為計(jì)算得分，需要定義一個估價函數(shù)，用來估算當(dāng)前博弈）為計(jì)算得分，需要定義一個估價函數(shù)，用來估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分（樹端節(jié)點(diǎn)的得分（靜態(tài)估算值靜態(tài)估算值）。）。（4）由端節(jié)點(diǎn)的得分估算父節(jié)點(diǎn)的得分（）由端節(jié)點(diǎn)的得分估算父節(jié)點(diǎn)的得分（倒推值倒推值）：對或

59、節(jié)點(diǎn)，）：對或節(jié)點(diǎn)，選子節(jié)點(diǎn)中最大的得分給父節(jié)點(diǎn)；對與節(jié)點(diǎn)，選子節(jié)點(diǎn)中最選子節(jié)點(diǎn)中最大的得分給父節(jié)點(diǎn)；對與節(jié)點(diǎn)，選子節(jié)點(diǎn)中最小的得分給父節(jié)點(diǎn)。小的得分給父節(jié)點(diǎn)。（5）如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最）如果一個行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的方案。好的方案。極大極小分析法面臨的問題試圖用完整的博弈樹來進(jìn)行極大極小分析是困試圖用完整的博弈樹來進(jìn)行極大極小分析是困難的。難的?？尚械姆椒尚械姆椒ǎ荷梢欢ㄉ疃鹊牟┺臉?，而后進(jìn)：生成一定深度的博弈樹，而后進(jìn)行極大極小分析法，找出當(dāng)前最好的方案。此行極大極小分析法，找出當(dāng)前最好的方案。此后再在已經(jīng)選定的分支上擴(kuò)展一定深度，

60、再選后再在已經(jīng)選定的分支上擴(kuò)展一定深度，再選最好的方案。如此進(jìn)行下去，直到取得勝敗的最好的方案。如此進(jìn)行下去，直到取得勝敗的結(jié)果為止。結(jié)果為止。5.3.3 剪枝技術(shù)剪枝技術(shù)在極大極小分析法中，總是先生成一定深度的在極大極小分析法中，總是先生成一定深度的博弈樹，對端節(jié)點(diǎn)進(jìn)行估值，然后計(jì)算上層節(jié)博弈樹，對端節(jié)點(diǎn)進(jìn)行估值，然后計(jì)算上層節(jié)點(diǎn)的倒推值。這樣做效率并不高。點(diǎn)的倒推值。這樣做效率并不高。鑒于博弈樹具有或節(jié)點(diǎn)和與節(jié)點(diǎn)交替出現(xiàn)的特鑒于博弈樹具有或節(jié)點(diǎn)和與節(jié)點(diǎn)交替出現(xiàn)的特點(diǎn)，如果能夠邊生成節(jié)點(diǎn)邊估值，就有可能刪點(diǎn)，如果能夠邊生成節(jié)點(diǎn)邊估值，就有可能刪去一些不必要的節(jié)點(diǎn)。剪枝技術(shù)就是基于此提去一些不