第18講-廣度優(yōu)先搜索復(fù)習(xí)過程

1、程序設(shè)計(jì)(chn x sh j)實(shí)習(xí)第十八講 廣度優(yōu)先(yuxin)搜索第一頁，共67頁。內(nèi)容提要(ni rn t yo)o 廣度優(yōu)先(yuxin)搜索的基本思想o POJ1077八數(shù)碼問題o 廣搜o 雙向廣搜(擴(kuò)展，不要求)o A*(擴(kuò)展，不要求)o 小結(jié)：影響搜索效率的因素2第二頁，共67頁。廣度(gungd)優(yōu)先搜索o廣度優(yōu)先搜索也稱為寬度優(yōu)先搜索，它是一種(y zhn)先生成的節(jié)點(diǎn)先擴(kuò)展的策略。適合于判定是否有解和求唯一解的情況o搜索過程是：從初始節(jié)點(diǎn)S0開始逐層向下擴(kuò)展，在第n層節(jié)點(diǎn)還沒有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。o假設(shè)有兩個(gè)表：Open表存放待處理節(jié)點(diǎn)，Close

2、d表存放處理完節(jié)點(diǎn)oOpen表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入Open表的節(jié)點(diǎn)排在前面，后進(jìn)入Open表的節(jié)點(diǎn)排在后面。 第三頁，共67頁。廣度(gungd)優(yōu)先搜索o 兩個(gè)狀態(tài)的集合o: 未處理完的狀態(tài)o: 已處理的狀態(tài)o 從中選擇被演化狀態(tài)的原則：離初態(tài)S0距離最近的狀態(tài)so S0到s的距離：從S0到達(dá)s使用的動(dòng)作數(shù)量o 實(shí)現(xiàn)方法：用queue表示(biosh)o 每次取queue頭部的狀態(tài)演化o 每次演化出的狀態(tài)s若不屬于，則s將壓入queue的尾部第四頁，共67頁。深搜 vs. 廣搜o 深搜1-2-4-8-5-6-3-7o 廣搜1-2-3-4-5-6-7-8第五頁，共67頁。廣搜算

3、法(sun f)o廣度優(yōu)先搜索算法如下：（用 QUEUE）o (1) 把初始節(jié)點(diǎn)S0放入Open表中；o (2) 如果Open表為空，則問題無解，失敗退出(tuch)；o (3) 把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；o (4) 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出(tuch)；o (5) 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；o (6) 擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。第六頁，共67頁。例題：POJ1077八數(shù)碼(shm)問題o 八數(shù)碼問題是人工智能中的經(jīng)典問題o POJ1077八數(shù)

4、碼問題：經(jīng)典搜索問題o 有一個(gè)3*3的棋盤(qpn)，其中有0-8共9個(gè)數(shù)字，0表示空格，其他的數(shù)字可以和0交換位置。求由初始狀態(tài)到達(dá)目標(biāo)狀態(tài)1 2 34 5 67 8 0的步數(shù)最少的解？ 12345678823146577第七頁，共67頁。例題：POJ1077八數(shù)碼(shm)問題o 狀態(tài)(zhungti)空間82341657823415768234165 78241357682341576823416578第八頁，共67頁。廣度(gungd)優(yōu)先搜索o 廣度優(yōu)先搜索（bfs）o 優(yōu)先擴(kuò)展(kuzhn)淺層節(jié)點(diǎn)，逐漸深入第一層第二層第三層8234165782341576823416578241

5、357682341576823416579第九頁，共67頁。廣度(gungd)優(yōu)先搜索o 廣度優(yōu)先搜索o 用隊(duì)列(duli)保存待擴(kuò)展的節(jié)點(diǎn)，從隊(duì)首隊(duì)取出節(jié)點(diǎn)，擴(kuò)展出的新節(jié)點(diǎn)放入隊(duì)尾，直到找到目標(biāo)節(jié)點(diǎn)（問題的解）823416578234157682413576823415768234165710第十頁，共67頁。廣度優(yōu)先(yuxin)搜索o 廣度優(yōu)先(yuxin)搜索的代碼框架BFS()初始化隊(duì)列while(隊(duì)列不為空且未找到目標(biāo)(mbio)節(jié)點(diǎn))取隊(duì)首節(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的節(jié)點(diǎn)放入隊(duì)尾；必要時(shí)要記住每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)；11第十一頁，共67頁。關(guān)鍵問題：判重o 判重o 新擴(kuò)展出的節(jié)點(diǎn)如果和以前擴(kuò)

6、展出的節(jié)點(diǎn)相同(xin tn)，則則個(gè)新節(jié)點(diǎn)就不必再考慮o 如何判重？重復(fù)(chngf)?823416578234157682341650782413576823415768234165712第十二頁，共67頁。關(guān)鍵問題：判重o 需要考慮的問題o 狀態(tài)數(shù)目巨大，如何(rh)存儲？o 怎樣才能較快的找到重復(fù)節(jié)點(diǎn)？時(shí)間(shjin)空間(kngjin)13第十三頁，共67頁。判重o 合理編碼，減小存儲代價(jià)o 不同(b tn)的編碼方式所需要的存儲空間會(huì)有較大差別82341657方案一：每個(gè)節(jié)點(diǎn)對應(yīng)于一個(gè)九進(jìn)制數(shù)，則4個(gè)字節(jié)就能表示一個(gè)節(jié)點(diǎn)。 （ 228 99=387,420,489 229）判重需

7、要一個(gè)標(biāo)志位序列，每個(gè)狀態(tài)對應(yīng)于標(biāo)志位序列中的1位，標(biāo)志位為0表示該狀態(tài)尚未擴(kuò)展，為1則說明已經(jīng)擴(kuò)展過了標(biāo)志位序列可以用字符數(shù)組存放。數(shù)組的每個(gè)元素存放8個(gè)狀態(tài)的標(biāo)志位。位序列最多需要99位，因此存放位序列的數(shù)組需要99/8 + 1個(gè)字節(jié) 48,427,562字節(jié)如果某個(gè)狀態(tài)對應(yīng)于一個(gè)9進(jìn)制數(shù)a,則其標(biāo)志位就是(jish)標(biāo)志位序列中的第a位（其所屬的數(shù)組元素下標(biāo)是a/8)14第十四頁，共67頁。判重o 合理編碼，減小存儲代價(jià)o 不同的編碼方式所需要的存儲空間會(huì)有較大(jio d)差別82341657方案一：每個(gè)節(jié)點(diǎn)對應(yīng)于一個(gè)九進(jìn)制數(shù)，則4個(gè)字節(jié)就能表示一個(gè)節(jié)點(diǎn)。此方案需要編寫字符串形式(xn

8、gsh)的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。15第十五頁，共67頁。判重o 合理(hl)編碼，減小存儲代價(jià)o 不同的編碼方式所需要的存儲空間會(huì)有較大差別82341657方案二：為節(jié)點(diǎn)編號把每個(gè)節(jié)點(diǎn)都看一個(gè)排列(pili)，以此排列(pili)在全部排列(pili)中的位置作為其編號排列(pili)總數(shù)：9!=362880只需要一個(gè)整數(shù)(4字節(jié))即可存下一個(gè)節(jié)點(diǎn)判重用的標(biāo)志數(shù)組只需要362,880字節(jié)即可。此方案比方案1省空間此方案需要編寫給定排列(pili)求序號和給定序號求排列(pili)的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。16第十六頁，共67頁。判重

9、o 時(shí)間與空間的權(quán)衡o 對于狀態(tài)數(shù)較小的問題，可以(ky)用最直接的方式編碼以空間換時(shí)間o 對于狀態(tài)數(shù)太大的問題，需要利用好的編碼方法以時(shí)間換空間o 具體問題具體分析17第十七頁，共67頁。輸入數(shù)據(jù)：2 3 4 1 5 x 7 6 8輸出(shch)結(jié)果：ullddrurdllurdruldr 2 3 4 1 5 7 6 8 輸入(shr)數(shù)據(jù)代表：移動(dòng)序列中u 表示(biosh)使空格上移d 表示(biosh)使空格下移r 表示(biosh)使空格右移l 表示(biosh)使空格左移1 2 3 4 5 6 7 8 輸出數(shù)據(jù)是一個(gè)移動(dòng)序列，使得移動(dòng)后結(jié)果變成用廣搜解決八數(shù)碼問題18第十八頁，共

10、67頁。八數(shù)碼(shm)例子程序o 采用方案1的非遞歸方案：數(shù)據(jù)結(jié)構(gòu)o 用一個(gè)九進(jìn)制字符串表示一個(gè)節(jié)點(diǎn)，其中有且僅有一個(gè)0（表示空格）-因此若九進(jìn)制串中沒有0，則0一定是在最高位o 設(shè)一個(gè)48427562位字符型標(biāo)志位序列數(shù)組szFlag，標(biāo)識每個(gè)狀態(tài)是否已擴(kuò)展o 設(shè)一個(gè)隊(duì)列MyQueue存放搜索過程中的可能狀態(tài)，根據(jù)問題定義，狀態(tài)總數(shù)362880?？紤]到搜索過程中可能存在的重復(fù)狀態(tài)，其大小設(shè)為400000。o 為簡化計(jì)算，設(shè)置與MyQueue同樣大小的數(shù)組anFather存放父節(jié)點(diǎn)指針、數(shù)組szMoves存放從父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)步驟o 設(shè)置一個(gè)結(jié)果(ji gu)隊(duì)列，為防止溢出，設(shè)置與M

11、yQueue同樣大小19第十九頁，共67頁。八數(shù)碼例子(l zi)程序o 采用方案1的非遞歸方案：關(guān)鍵處理邏輯o Main程序1.將輸入的原始字符串變?yōu)榫胚M(jìn)制字符串;2.用BFS過程看是否可以達(dá)到目標(biāo)狀態(tài);3.若能達(dá)到，通過anFather數(shù)組找到成功的狀態(tài)序列;4.根據(jù)數(shù)組szMoves找到相應(yīng)的移動(dòng)步驟(bzhu)，并輸出.o BFS過程輸入：初始狀態(tài) 輸出：成功/失?。蝗舫晒?， anFather、 szMoves20第二十頁，共67頁。八數(shù)碼例子(l zi)程序o 采用方案1的非遞歸方案：關(guān)鍵處理邏輯o BFS中的關(guān)鍵問題：1）如何進(jìn)行狀態(tài)擴(kuò)展？2）狀態(tài)中0的位置與cMove動(dòng)作間的關(guān)系

12、？3）如何計(jì)算求從nStatus經(jīng)過 cMove 移動(dòng)后得到的新狀態(tài)（定義為函數(shù)NewStatus ）？4）如何判斷擴(kuò)展標(biāo)記已經(jīng)存在(cnzi)？5）對未擴(kuò)展?fàn)顟B(tài)，如何置已擴(kuò)展標(biāo)記(定義為函數(shù)SetBit )？6）字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)（定義為NineToTen和TenToNine）21第二十一頁，共67頁。#include #include using namespace std;int nGoalStatus; /目標(biāo)狀態(tài)bitset Flags; /節(jié)點(diǎn)是否擴(kuò)展的標(biāo)記char szResult400000; /結(jié)果char szMoves400000; /移動(dòng)步驟

13、： u/d/r/l int anFather400000; /父節(jié)點(diǎn)指針int MyQueue400000; /狀態(tài)隊(duì)列，狀態(tài)總數(shù)(zngsh)362880int nQHead; int nQTail;char sz4Moves = udrl;/四種動(dòng)作八數(shù)碼(shm)例子程序22第二十二頁，共67頁。int NineToTen( char * s ) /九進(jìn)制字符串轉(zhuǎn)十進(jìn)制int nResult = 0;for( int i = 0; si; i + ) nResult *= 9;nResult += si - 0;return nResult;23第二十三頁，共67頁。int TenToN

14、ine( int n, char * s) /十進(jìn)制數(shù)轉(zhuǎn)九進(jìn)制字符串?？赡苡星皩?dǎo)0，返回(fnhu)0的位置int nZeroPos;int nBase = 1;int j = 0;while( nBase = 1 );sj = 0;/串結(jié)束符/判斷是否要加前導(dǎo)0，此時(shí)第0位即為0if( j 0; i -)si = si-1;s0 = 0;return 0;return nZeroPos;24第二十四頁，共67頁。int NewStatus( int nStatus, char cMove) /求從nStatus經(jīng)過 cMove 移動(dòng)后得到的新狀態(tài)。若移動(dòng)不可行(kxng)則返回-1char

15、szTmp20;int nZeroPos = TenToNine(nStatus,szTmp);/返回空格的位置switch( cMove) case u: if( nZeroPos - 3 8 ) return -1; /空格在第三行else szTmpnZeroPos = szTmpnZeroPos + 3;szTmpnZeroPos + 3 = 0;break;case l: if( nZeroPos % 3 = 0) return -1; /空格在第一列else szTmpnZeroPos = szTmpnZeroPos -1;szTmpnZeroPos -1 = 0;break;ca

16、se r: if( nZeroPos % 3 = 2) return -1; /空格在第三列else szTmpnZeroPos = szTmpnZeroPos + 1;szTmpnZeroPos + 1 = 0;break;return NineToTen(szTmp);25第二十五頁，共67頁。bool Bfs(int nStatus)int nNewStatus;nQHead = 0;nQTail = 1;MyQueuenQHead = nStatus;while ( nQHead != nQTail) /隊(duì)列不為空nStatus = MyQueuenQHead;if( nStatus

17、= nGoalStatus ) /找到目標(biāo)(mbio)狀態(tài) return true;for( int i = 0;i = 0; i - ) cout szResulti;elsecout unsolvable endl; return 0;27第二十七頁，共67頁。問題(wnt)o 前述程序中，是否有狀態(tài)被重復(fù)擴(kuò)展？o 初始狀態(tài)。為避免(bmin)此重復(fù)， 應(yīng)在BFS初始化時(shí)對初始狀態(tài)進(jìn)行置位o 前述程序中，8數(shù)碼問題的有解性判定o 如果所有結(jié)點(diǎn)都擴(kuò)展完還沒有達(dá)到目標(biāo)狀態(tài)，則問題無解，失敗退出o 是否有更節(jié)省存儲空間的做法，例如可以不用幾個(gè)大數(shù)組？o 一種可能方案：使用2個(gè)鏈表分別存隊(duì)列和結(jié)果

18、28第二十八頁，共67頁。廣搜的解法(ji f)二：鏈表表示o 基本思想：定義8數(shù)碼結(jié)點(diǎn)類CEight,它有兩個(gè)指針open_next和parent，分別指向BFS擴(kuò)展結(jié)點(diǎn)的下一個(gè)open節(jié)點(diǎn)和父結(jié)點(diǎn)（若當(dāng)前結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)，通過parent可以得到解路徑）o 不需要設(shè)置標(biāo)志位序列數(shù)組szFlago 用鏈表來表示狀態(tài)隊(duì)列MyQueueo 其他要求o 目標(biāo)結(jié)點(diǎn)可以支持重新設(shè)定，這樣可以用于計(jì)算任意(rny)兩個(gè)結(jié)點(diǎn)間的距離o 輸出結(jié)果將解路徑打印出來第二十九頁，共67頁。八數(shù)碼問題：任意兩結(jié)點(diǎn)(ji din)間路徑第三十頁，共67頁。實(shí)現(xiàn)(shxin)細(xì)節(jié)(1)o 8數(shù)碼結(jié)點(diǎn)類CEighto =：

19、兩對象賦值，或用數(shù)組給對象賦值o =：兩對象是否相等，或?qū)ο蠛鸵挥脭?shù)組存儲的結(jié)點(diǎn)是否相等o 普通(ptng)函數(shù)o 四類移動(dòng)操作move_left/right/up/downo 判斷有無重復(fù)existed：鏈表遍歷o 判定是否有解icansolve第三十一頁，共67頁。八數(shù)碼問題(wnt)有解性的判定o 八數(shù)碼問題的一個(gè)狀態(tài)實(shí)際上是09的一個(gè)排列，對于任意給定的初始狀態(tài)和目標(biāo)，不一定有解，即從初始狀態(tài)不一定能到達(dá)目標(biāo)狀態(tài)。o 因?yàn)榕帕杏衅媾帕泻团寂帕袃深?，從奇排列不能轉(zhuǎn)化成偶排列或相反。 o 如果一個(gè)數(shù)字08的隨機(jī)排列，用F(X)表示數(shù)字X前面比它小的數(shù)的個(gè)數(shù)，全部數(shù)字的F(X)之和為Y=(F

20、(X)，如果Y為奇數(shù)則稱該排列是奇排列，如果Y為偶數(shù)則稱該排列是偶排列。o 871526340排列的 Y=0+0+0+1+1+3+2+3+0=10，10是偶數(shù)，所以是偶排列。o 871625340排列的Y=0+0+0+1+1+2+2+3+0=9 9是奇數(shù)，所以是奇排列。 o 因此，可以在運(yùn)行程序前檢查(jinch)初始狀態(tài)和目標(biāo)狀態(tài)的奇偶性是否相同，相同則問題可解，應(yīng)當(dāng)能搜索到路徑。否則無解。第三十二頁，共67頁。實(shí)現(xiàn)(shxin)細(xì)節(jié)(2)o 廣搜過程o讓鏈表頭指針open_head和尾指針open_tos指向初始(ch sh)節(jié)點(diǎn)S；owhile(open_head不為空且找到標(biāo)志為假)o

21、if(*open_head=Target) 找到標(biāo)志為真; break;oRepeat 四種動(dòng)作o o 分別執(zhí)行一種動(dòng)作；o if (動(dòng)作執(zhí)行成功&移動(dòng)后新狀態(tài)在鏈表中無重復(fù))o o 1. 從該新狀態(tài)生成新的CEight對象，使其父結(jié)點(diǎn)為 *open_head，使其open_next為NULL；o 2. 通過尾指針open_tos將新CEight對象加入隊(duì)列；o oo移動(dòng)open_head指針;o 第三十三頁，共67頁。#include iostreamusing namespace std;static int target9=1,2,3,4,5,6,7,8,0;class CEightpr

22、ivate:int num9; /結(jié)點(diǎn)數(shù)組int deapth; /深度public:CEight* parent; /父指針(zhzhn)CEight* open_next; /擴(kuò)展指針(zhzhn)CEight(int init_num9); /用數(shù)組構(gòu)造對象CEight(void); /構(gòu)造函數(shù)，使用缺省初始化 int get_deapth(void); /取深度void get_numbers_to(int other_num9); /將數(shù)序列拷貝到另一數(shù)組void set_num(int other_num9); /將另一數(shù)組的數(shù)序列設(shè)置對象void show(void); /輸出結(jié)

23、果CEight& operator=(CEight&); /兩對象賦值CEight& operator=(int other_num9); /用數(shù)組給對象賦值int operator=(CEight&); /兩對象是否相等int operator=(int other_num9); /對象和數(shù)組是否相等;注意：本解法與POJ要求(yoqi)不完全相同，但很容易修改和移植第三十四頁，共67頁。CEight:CEight(int init_num9)for (int i=0;i9;i+)numi=init_numi;CEight:CEight()for (int i=0;i9;i+)numi=i;

24、int CEight: get_deapth(void)return deapth;void CEight:get_numbers_to(int other_num9)for (int i=0;i9;i+)other_numi=numi;void CEight:set_num(int other_num9)for (int i=0;i9;i+)numi=other_numi;第三十五頁，共67頁。void CEight:show() for (int i=0;i9;i+) coutnumi; if (i+1)%3) cout ; else coutn; /賦值運(yùn)算符重載(zhn zi)CEig

25、ht& CEight:operator=(CEight& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;deapth=another_8num.deapth+1;return *this;CEight& CEight:operator=(int other_num9)for (int i=0;i9;i+)numi=other_numi;return *this;第三十六頁，共67頁。/相等(xingdng)關(guān)系運(yùn)算符重載int CEight:operator=(CEight& another_8num)int match=1;fo

26、r (int i=0;i9;i+)if(numi!=another_8num.numi) match=0; break; if (match=0) return 0;else return 1;int CEight:operator=(int other_num9)int match=1;for (int i=0;i9;i+)if(numi!=other_numi)match=0; break;if (match=0)return 0;else return 1;第三十七頁，共67頁。int move_up(int num9) /空格(kn )向上移 int i;for (i=0;i9;i+)

27、/找空格(kn )位置if (numi=0) break;if (i3) return 0;else /空格(kn )不在第一行時(shí)移動(dòng)numi=numi-3;numi-3=0; return 1;int move_down(int num9) /空格(kn )向下移 int i;for (i=0;i5) return 0;else /空格(kn )不在第三行時(shí)移動(dòng)numi=numi+3;numi+3=0; return 1;第三十八頁，共67頁。int move_left(int num9) /空格向左移 int i;for (i=0;i9;i+) /找空格位置(wi zhi)if (numi

28、=0) break;if (i=0|i=3|i=6)return 0;else /空格不在第一列時(shí)移動(dòng)numi=numi-1;numi-1=0; return 1;int move_right(int num9) /空格向右移 int i;for (i=0;i9;i+) /找空格位置(wi zhi)if (numi=0) break;if (i=2|i=5|i=8)return 0;else /空格不在第三列時(shí)移動(dòng)numi=numi+1;numi+1=0;return 1;第三十九頁，共67頁。int icansolve(int num9,int target9) /判斷可否(k fu)解出i

29、nt i,j;int count_num = 0;int count_target = 0;for (i=0;i9;i+)for (j=0;ji;j+)if(numjnumi&numj!=0)count_num+;if(targetjparent)if(*p=num) return 1;return 0;第四十頁，共67頁。int main(void)int step=0;int num9;int flag=0;/是否輸入錯(cuò)誤標(biāo)志，1表示輸入錯(cuò)誤int bingo=0;/是否查找成功(chnggng)標(biāo)志，1表示成功(chnggng)int i,j;coutPlease input the n

30、umber(0 for the blank):n; /輸入數(shù)據(jù)for (i=0;inumi;for(j=0;ji;j+)if(numi=numj)flag=1;if (numi8|flag=1)i-;coutIllegle number!tReinput!n;第四十一頁，共67頁。coutinput;if (input=y|input=Y)coutnPlease input the new target:n;for (i=0;itargeti;for(j=0;ji;j+) if(targeti=targetj)flag=1;if (targeti8|flag=1)i-;coutIllegle

31、number!tReinput!n“; CEight S(num),Target(target);S.parent=S.open_next=NULL;coutNow the initial numbers are:n; S.show();coutAnd the Target is:n; Target.show();if(!icansolve(num,target) /判斷是否可解coutNo one can solve it!n;return 1;第四十二頁，共67頁。CEight *open_head=&S,*open_tos=&S,*new_8num; /BFS搜索(su su)while

32、(open_head!=NULL&bingo!=1) if(*open_head=Target) bingo=1; break;for (int i=0;iget_numbers_to(num); bool bRec = false; switch(i) case 0: bRec = move_up(num); break; case 1: bRec = move_down(num); break; case 2: bRec = move_left(num); break; case 3: bRec = move_right(num); break; if(bRec&!existed(num,

33、open_head) new_8num=new CEight; new_8num-set_num(num); new_8num-parent=open_head; new_8num-open_next=NULL; open_tos-open_next=new_8num; open_tos=new_8num; open_head=open_head-open_next; 第四十三頁，共67頁。 /輸出(shch)結(jié)果if(bingo=1)CEight *p;for (p=open_head-parent;p!=NULL;p=p-parent)coutshow();step+;coutTotaly

34、 covered steps:stepn;elsecoutFail to find!;return 0;第四十四頁，共67頁。廣搜的解法(ji f)二：小結(jié)o 定義8數(shù)碼結(jié)點(diǎn)類CEight，及一些普通的功能函數(shù)(hnsh)（如移動(dòng)、是否有解、是否重復(fù)等）o 用鏈表表示隊(duì)列，設(shè)置鏈表頭指針open_head和尾指針open_toso 用遍歷鏈表來查找是否有重復(fù)擴(kuò)展結(jié)點(diǎn)o 較為低效o 通過鏈表運(yùn)算來實(shí)現(xiàn)BFS第四十五頁，共67頁。用深度優(yōu)先搜索(su su)求解8數(shù)碼問題o 基本思想：優(yōu)先深入遍歷靠前的節(jié)點(diǎn)o 也可以通過鏈表實(shí)現(xiàn)，對上述(shngsh)算法中簡單修改即可82341657823415

35、7682341650782413576823415768234165746第四十六頁，共67頁。用深度優(yōu)先搜索求解8數(shù)碼(shm)問題o 參考代碼o 與前述BFS的代碼為同一架構(gòu)o 深度受限的情況(qngkung)下（如最大深度為20）：可能處理時(shí)間較長，且不一定能找到解第四十七頁，共67頁。度量問題求解(qi ji)的性能o完備性：當(dāng)問題有解時(shí)，這個(gè)算法是否能夠保證找到一個(gè)解o最優(yōu)性：這個(gè)搜索策略是否能夠找到最優(yōu)解o時(shí)間復(fù)雜度：找到一個(gè)解需要花費(fèi)(hufi)多長時(shí)間o空間復(fù)雜度：在執(zhí)行搜索的過程中需要多少內(nèi)存第四十八頁，共67頁。廣搜與深搜的比較(bjio)o 廣搜一般用于狀態(tài)表示比較簡單、

36、求最優(yōu)策略的問題o 優(yōu)點(diǎn)：是一種完備策略，即只要問題有解，它就一定可以找到解。并且，廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。o 缺點(diǎn)：盲目性較大(jio d)，尤其是當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，將產(chǎn)生許多無用的節(jié)點(diǎn)，因此其搜索效率較低。需要保存所有擴(kuò)展出的狀態(tài)，占用的空間大o 深搜幾乎可以用于任何問題o 只需要保存從起始狀態(tài)到當(dāng)前狀態(tài)路徑上的節(jié)點(diǎn)o 根據(jù)題目要求憑借自己的經(jīng)驗(yàn)和對兩個(gè)搜索的熟練程度做出選擇49第四十九頁，共67頁。擴(kuò)展(kuzhn)問題：是否有更快的做法？o 雙向廣度優(yōu)先搜索：從兩個(gè)方向以廣度優(yōu)先的順序(shnx)同時(shí)擴(kuò)展o A*：啟發(fā)式搜索搜索50第五十頁，共67頁。雙向

37、廣度優(yōu)先(yuxin)搜索(DBFS)o DBFS算法是對BFS算法的一種擴(kuò)展。o BFS算法從起始節(jié)點(diǎn)以廣度優(yōu)先的順序不斷擴(kuò)展，直到遇到目的節(jié)點(diǎn)o DBFS算法從兩個(gè)方向以廣度優(yōu)先的順序同時(shí)擴(kuò)展，一個(gè)是從起始節(jié)點(diǎn)開始擴(kuò)展，另一個(gè)是從目的節(jié)點(diǎn)擴(kuò)展，直到一個(gè)擴(kuò)展隊(duì)列中出現(xiàn)另外一個(gè)隊(duì)列中已經(jīng)擴(kuò)展的節(jié)點(diǎn)，也就相當(dāng)于兩個(gè)擴(kuò)展方向出現(xiàn)了交點(diǎn)，那么可以認(rèn)為我們找到了一條路徑。o 比較o DBFS算法相對(xingdu)于BFS算法來說，由于采用了從兩個(gè)跟開始擴(kuò)展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時(shí)間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！第五十一頁，共67頁。DBFS的框架(kun ji)(1

38、)o 一、主控函數(shù):o void solve()o o 1. 將起始節(jié)點(diǎn)(ji din)放入隊(duì)列q1,將目的節(jié)點(diǎn)(ji din)放入隊(duì)列q2；o 2. 當(dāng) 兩個(gè)隊(duì)列都未空時(shí)，作如下循環(huán)：o 1) 如果隊(duì)列q1里的未處理節(jié)點(diǎn)(ji din)比q2中的少（即tail0-head0 = tail1-head1時(shí))；o 3. 如果隊(duì)列q1未空，循環(huán)擴(kuò)展（expand()）q1直到為空；o 4. 如果隊(duì)列q2未空，循環(huán)擴(kuò)展（expand()）q2直到為空；o 第五十二頁，共67頁。DBFS的框架(kun ji)(2)o 二、擴(kuò)展函數(shù)o int expand(i) /其中i為隊(duì)列的編號(表示q0或者(hu

39、zh)q1)o o 取隊(duì)列qi的頭結(jié)點(diǎn)H；o 對頭節(jié)點(diǎn)H的每一個(gè)相鄰節(jié)點(diǎn)adj，作如下循環(huán)：o 1 如果adj已經(jīng)在隊(duì)列qi之前的某個(gè)位置出現(xiàn)，則o 拋棄節(jié)點(diǎn)adj；o 2 如果adj在隊(duì)列qi中不存在函數(shù) isduplicate(i)o 1） 將adj放入隊(duì)列qi；o 2) 如果adj 在隊(duì)列(q(1-i)，也就是另外一個(gè)o 隊(duì)列中出現(xiàn)函數(shù) isintersect()；o 輸出 找到路徑 ；o 第五十三頁，共67頁。DBFS的框架(kun ji)(3)o 三、判斷當(dāng)前擴(kuò)展出的節(jié)點(diǎn)是否在另外一個(gè)(y )隊(duì)列出現(xiàn)，也就是判斷相交的函數(shù)：o int isintersect(i,j) /i為隊(duì)列編號

40、，j為當(dāng)前節(jié)點(diǎn)在隊(duì)列中的指針o o 遍歷隊(duì)列,判斷是否存在o o /【線性遍歷的時(shí)間復(fù)雜度為O（N)，如果用HashTable優(yōu)化，時(shí)間復(fù)雜度可以降到O(1)】第五十四頁，共67頁。DBFS參考(cnko)代碼o 見附件(fjin)o 進(jìn)一步提高查找效率，采用hash函數(shù)優(yōu)化線性查找o 見附件(fjin)第五十五頁，共67頁。A*算法(sun f)o 針對八數(shù)碼問題，提出了人工智能史上很有名的A*算法(啟發(fā)式搜索算法)o 廣度優(yōu)先算法：當(dāng)目標(biāo)的深度較深時(shí)，產(chǎn)生很多冗余節(jié)點(diǎn)，空間消耗很大o 有限深度優(yōu)先算法：在時(shí)間或空間復(fù)雜度上均沒有明顯的優(yōu)勢，但如果目標(biāo)深度較深而且路徑選擇得當(dāng)?shù)脑?，可以較快地

41、得到解答；當(dāng)問題復(fù)雜時(shí)時(shí)間消耗很多o A*算法：可以消耗較少的空間解決問題，但是由于(yuy)每次選擇均需要尋找估價(jià)函數(shù)最小的節(jié)點(diǎn)，因此當(dāng)深度增加相應(yīng)的節(jié)點(diǎn)數(shù)目增加時(shí)，A*算法在時(shí)間上并不占優(yōu)勢。然而，A*算法總可以在有限的時(shí)間內(nèi)得到問題的解。56第五十六頁，共67頁。A*算法(sun f)的基本思想oA*算法基本上與BFS算法相同，但是在擴(kuò)展出一結(jié)點(diǎn)后，要根據(jù)估價(jià)函數(shù)對待擴(kuò)展的結(jié)點(diǎn)排序，從而保證每次擴(kuò)展的結(jié)點(diǎn)都是估價(jià)函數(shù)最小的結(jié)點(diǎn)。o估價(jià)函數(shù)： f(n) = g(n) + h(n) 這里f(n)是估價(jià)函數(shù)，g(n)是起點(diǎn)到終點(diǎn)(zhngdin)的最短路徑值（也稱為最小耗費(fèi)或最小代價(jià)），h(n

42、)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。o由于這個(gè)f(n)其實(shí)是無法預(yù)先知道的，所以實(shí)際上使用“不在位”數(shù)和當(dāng)前層數(shù)之和第五十七頁，共67頁。A*算法的基本(jbn)步驟o建立一個(gè)隊(duì)列，計(jì)算初始結(jié)點(diǎn)的估價(jià)函數(shù)f，并將初始結(jié)點(diǎn)入隊(duì)，設(shè)置隊(duì)列頭和尾指針。 o取出隊(duì)列頭（隊(duì)列頭指針?biāo)福┑慕Y(jié)點(diǎn)，如果該結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)，則輸出路徑，程序結(jié)束。否則對結(jié)點(diǎn)進(jìn)行擴(kuò)展。 o檢查擴(kuò)展的新結(jié)點(diǎn)是否與隊(duì)列中的結(jié)點(diǎn)重復(fù)o若與不能再擴(kuò)展的結(jié)點(diǎn)重復(fù)（位于隊(duì)列頭指針之前），則將它拋棄；o若新結(jié)點(diǎn)與待擴(kuò)展的結(jié)點(diǎn)重復(fù)（位于隊(duì)列頭指針之后），則比較兩個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)中g(shù)的大小，保留(boli)較小g值的結(jié)點(diǎn)。跳至第五步。 o如果擴(kuò)展出的新

43、結(jié)點(diǎn)與隊(duì)列中的結(jié)點(diǎn)不重復(fù)，則按照它的估價(jià)函數(shù)f大小將它插入隊(duì)列中的頭結(jié)點(diǎn)后待擴(kuò)展結(jié)點(diǎn)的適當(dāng)位置，使它們按從小到大的順序排列，最后更新隊(duì)列尾指針o如果隊(duì)列頭的結(jié)點(diǎn)還可以擴(kuò)展，直接返回第二步。否則將隊(duì)列頭指針指向下一結(jié)點(diǎn)，再返回第二步。第五十八頁，共67頁。#include iostream using namespace std;static int target9=1,2,3,4,5,6,7,8,0;class CEightprivate:int num9; int deapth;int not_in_position_num; int eva_function;public:CEight*

44、parent; CEight* open_next;CEight* leaf_pre;CEight(int init_num9);CEight(void);void get_numbers_to(int other_num9);int get_deapth(void); void cul_para(void); int get_nipn(void); int get_evafun(void);void set_num(int other_num9);void show(void);CEight& operator=(CEight&);CEight& operator=(int other_nu

45、m9);/修改(xigi)int operator=(CEight&);int operator=(int other_num9);第五十九頁，共67頁。int CEight:get_nipn(void) return not_in_position_num;int CEight: get_evafun(void)return eva_function;void CEight:cul_para(void)int i;int temp_nipn=0;for (i=0;iparent=NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_num+deapth;CEight& CEigh