第3章圖搜索與問(wèn)題求解

《第3章圖搜索與問(wèn)題求解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、第3章圖搜索與問(wèn)題求解3.1狀態(tài)圖搜索3.2狀態(tài)圖搜索問(wèn)題求解3.3與或圖搜索3.4與或圖搜索問(wèn)題求解3.5博弈樹搜索習(xí)題三3.1狀態(tài)圖搜索3.1.1狀態(tài)圖例3.1走迷宮是人們熟悉的一種游戲,如圖3－1就是一個(gè)迷宮。如果我們把該迷宮的每一個(gè)格子以及入口和出口都作為節(jié)點(diǎn),把通道作為邊,則該迷宮可以由一個(gè)有向圖表示(如圖3-2所示)。那么,走迷宮其實(shí)就是從該有向圖的初始節(jié)點(diǎn)(入口)出發(fā),尋找目標(biāo)節(jié)點(diǎn)(出口)的問(wèn)題,或者是尋找通向目標(biāo)節(jié)點(diǎn)(出口)的路徑的問(wèn)題。圖3-1迷宮圖圖3-2迷宮的有向圖表示例3.2在一個(gè)3×3的方格棋盤上放置著1,2,

2、3,4,5,6,7,8八個(gè)數(shù)碼,每個(gè)數(shù)碼占一格,且有一個(gè)空格。這些數(shù)碼可在棋盤上移動(dòng),其移動(dòng)規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。現(xiàn)在的問(wèn)題是：對(duì)于指定的初始棋局和目標(biāo)棋局(如圖3-3所示),給出數(shù)碼的移動(dòng)序列。該問(wèn)題稱為八數(shù)碼難題或重排九宮問(wèn)題。可以看出,圖中的一條邊(即相鄰兩個(gè)節(jié)點(diǎn)的連線)就對(duì)應(yīng)一次數(shù)碼移動(dòng),反之,一次數(shù)碼移動(dòng)也就對(duì)應(yīng)著圖中的一條邊。而數(shù)碼移動(dòng)是按數(shù)碼的移動(dòng)規(guī)則進(jìn)行的。所以,圖中的一條邊也就代表一個(gè)移動(dòng)規(guī)則或者移動(dòng)規(guī)則的一次執(zhí)行。于是,這個(gè)八數(shù)碼問(wèn)題也就是要在該有向圖中尋找目標(biāo)節(jié)點(diǎn),或找一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路

3、徑問(wèn)題。圖3-3八數(shù)碼問(wèn)題示例3.1.2狀態(tài)圖搜索1.搜索方式用計(jì)算機(jī)來(lái)實(shí)現(xiàn)狀態(tài)圖的搜索,有兩種最基本的方式：樹式搜索和線式搜索。所謂樹式搜索,形象地講就是以“畫樹”的方式進(jìn)行搜索。即從樹根(初始節(jié)點(diǎn))出發(fā),一筆一筆地描出一棵樹來(lái)。準(zhǔn)確地講,樹式搜索就是在搜索過(guò)程中記錄所經(jīng)過(guò)的所有節(jié)點(diǎn)和邊。所以,樹式搜索所記錄的軌跡始終是一棵“樹”,這棵樹也就是搜索過(guò)程中所產(chǎn)生的搜索樹。所謂線式搜索,形象地講就是以“畫線”的方式進(jìn)行搜索。準(zhǔn)確地講,線式搜索在搜索過(guò)程中只記錄那些當(dāng)前認(rèn)為是處在所找路徑上的節(jié)點(diǎn)和邊。所以,線式搜索所記錄的軌跡始終是一條

4、“線”(折線)。線式搜索的基本方式又可分為不回溯的和可回溯的兩種。不回溯的線式搜索就是每到一個(gè)“叉路口”僅沿一條路繼續(xù)前進(jìn),即對(duì)每一個(gè)節(jié)點(diǎn)始終都僅生成一個(gè)子節(jié)點(diǎn)(如果有子節(jié)點(diǎn)的話)。生成一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)也稱對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展。這樣,如果擴(kuò)展到某一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)恰好就是目標(biāo)節(jié)點(diǎn),則搜索成功；如果直到不能再擴(kuò)展時(shí),還未找到目標(biāo)節(jié)點(diǎn),則搜索失敗?？苫厮莸木€式搜索也是對(duì)每一個(gè)節(jié)點(diǎn)都僅擴(kuò)展一條邊,但當(dāng)不能再擴(kuò)展時(shí),則退回一個(gè)節(jié)點(diǎn),然后再擴(kuò)展另一條邊(如果有的話)。這樣,要么最終找到了目標(biāo)節(jié)點(diǎn),搜索成功；要么一直回溯到初始節(jié)點(diǎn)也未找到目標(biāo)節(jié)點(diǎn),則搜

5、索失敗。由上所述可以看出,樹式搜索成功后,還需再?gòu)乃阉鳂渲姓页鏊舐窂?而線式搜索只要搜索成功,則“搜索線”就是所找的路徑,即問(wèn)題的解。那么,又怎樣從搜索樹中找出所求路徑呢？這只需在擴(kuò)展節(jié)點(diǎn)時(shí)記住節(jié)點(diǎn)間的父子關(guān)系即可。這樣,當(dāng)搜索成功時(shí),從目標(biāo)節(jié)點(diǎn)反向沿搜索樹按所作標(biāo)記追溯回去一直到初始節(jié)點(diǎn),便得到一條從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑,即問(wèn)題的一個(gè)解。2.搜索策略由于搜索具有探索性,所以要提高搜索效率(盡快地找到目標(biāo)節(jié)點(diǎn)),或要找最佳路徑(最佳解)就必須注意搜索策略。對(duì)于狀態(tài)圖搜索,已經(jīng)提出了許多策略,它們大體可分為盲目搜索和啟發(fā)式(he

6、uristic)搜索兩大類。通俗地講,盲目搜索就是無(wú)“向?qū)А钡乃阉?啟發(fā)式搜索就是有“向?qū)А钡乃阉鳌Ｄ敲?樹式盲目搜索就是窮舉式搜索,即從初始節(jié)點(diǎn)出發(fā),沿連接邊逐一考察各個(gè)節(jié)點(diǎn)(看是否為目標(biāo)節(jié)點(diǎn)),或者反向進(jìn)行；而線式盲目搜索,對(duì)于不回溯的就是隨機(jī)碰撞式搜索,對(duì)于回溯的則也是窮舉式的搜索。啟發(fā)式搜索則是利用“啟發(fā)性信息”引導(dǎo)的搜索。所謂“啟發(fā)性信息”就是與問(wèn)題有關(guān)的有利于盡快找到問(wèn)題解的信息或知識(shí)。例如：“欲速則不達(dá)”、“知已知彼,百戰(zhàn)不殆”、“學(xué)如逆水行舟不進(jìn)則退”等格言,就是指導(dǎo)人們行為的啟發(fā)性信息。常識(shí)告訴我們,如果有向?qū)б?

7、則就會(huì)少走彎路而事半功倍。所以,啟發(fā)式搜索往往會(huì)提高搜索效率,而且可能找到問(wèn)題的最優(yōu)解。根據(jù)啟發(fā)性信息的內(nèi)容和使用方式的不同,啟發(fā)式搜索又可分為許多不同的策略,如全局擇優(yōu)、局部擇優(yōu)、最佳圖搜索等等。按搜索范圍的擴(kuò)展順序的不同,搜索又可分為廣度優(yōu)先和深度優(yōu)先兩種類型。對(duì)于樹式搜索,既可深度優(yōu)先進(jìn)行,也可廣度優(yōu)先進(jìn)行。對(duì)于線式搜索則總是深度優(yōu)先進(jìn)行。3.搜索算法由于搜索的目的是為了尋找初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑,所以在搜索過(guò)程中就得隨時(shí)記錄搜索軌跡。為此,我們用一個(gè)稱為CLOSED表的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)專門記錄考查過(guò)的節(jié)點(diǎn)。顯然,對(duì)于樹式搜索

8、來(lái)說(shuō),CLOSED表中存儲(chǔ)的正是一棵不斷成長(zhǎng)的搜索樹；而對(duì)于線式搜索來(lái)說(shuō),CLOSED表中存儲(chǔ)的是一條不斷伸長(zhǎng)的折線,它可能本身就是所求的路徑(如果能找到目標(biāo)節(jié)點(diǎn)的話)。另一方面,對(duì)于樹式搜索來(lái)說(shuō),還得不