廣度優(yōu)先搜索

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

2、 兩個狀態(tài)的集合n : 未處理完的狀態(tài)n : 已處理的狀態(tài)o 從中選擇被演化狀態(tài)的原則：離初態(tài)S0距離最近的狀態(tài)sn S0到s的距離：從S0到達(dá)s使用的動作數(shù)量o 實現(xiàn)方法：用queue表示n 每次取queue頭部的狀態(tài)演化n 每次演化出的狀態(tài)s若不屬于，則s將壓入queue的尾部深搜 vs. 廣搜o 深搜1-2-4-8-5-6-3-7o 廣搜1-2-3-4-5-6-7-8廣搜算法o廣度優(yōu)先搜索算法如下：（用 QUEUE） (1) 把初始節(jié)點S0放入Open表中； (2) 如果Open表為空，則問題無解，失敗退出； (3) 把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n； (4

3、) 考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則得到問題的解，成功退出； (5) 若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步； (6) 擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每一個子節(jié)點設(shè)置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。例題：POJ1077八數(shù)碼問題o 八數(shù)碼問題是人工智能中的經(jīng)典問題o POJ1077八數(shù)碼問題：經(jīng)典搜索問題n 有一個3*3的棋盤，其中有0-8共9個數(shù)字，0表示空格，其他的數(shù)字可以和0交換位置。求由初始狀態(tài)到達(dá)目標(biāo)狀態(tài)1 2 34 5 67 8 0的步數(shù)最少的解？ 12345678823146577例題：POJ1077八數(shù)碼問題o 狀態(tài)空間82341657823415768234

4、165 78241357682341576823416578廣度優(yōu)先搜索o 廣度優(yōu)先搜索（bfs）n 優(yōu)先擴展淺層節(jié)點，逐漸深入第一層第二層第三層8234165782341576823416578241357682341576823416579n 用隊列保存待擴展的節(jié)點，從隊首隊取出節(jié)點，擴展出的新節(jié)點放入隊尾，直到找到目標(biāo)節(jié)點（問題的解）823416578234157682413576823415768234165710廣度優(yōu)先搜索o 廣度優(yōu)先搜索的代碼框架Void BFS( )初始化隊列while(隊列不為空且未找到目標(biāo)節(jié)點)取隊首節(jié)點擴展，并將擴展出的節(jié)點放入隊尾；必要時要記住每個節(jié)點的

5、父節(jié)點；11關(guān)鍵問題：判重o 判重n 新擴展出的節(jié)點如果和以前擴展出的節(jié)點相同，則則個新節(jié)點就不必再考慮n 如何判重？重復(fù)?823416578234157682341650782413576823415768234165712關(guān)鍵問題：判重o 需要考慮的問題n 狀態(tài)數(shù)目巨大，如何存儲？n 怎樣才能較快的找到重復(fù)節(jié)點？時間空間13判重o 合理編碼，減小存儲代價n 不同的編碼方式所需要的存儲空間會有較大差別82341657方案一：每個節(jié)點對應(yīng)于一個九進(jìn)制數(shù)，則4個字節(jié)就能表示一個節(jié)點。 （ 228 99=387,420,489 229）判重需要一個標(biāo)志位序列，每個狀態(tài)對應(yīng)于標(biāo)志位序列中的1位，標(biāo)志

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

7、較大差別82341657方案二：為節(jié)點編號把每個節(jié)點都看一個排列，以此排列在全部排列中的位置作為其編號排列總數(shù)：9!=362880只需要一個整數(shù)(4字節(jié))即可存下一個節(jié)點判重用的標(biāo)志數(shù)組只需要362,880字節(jié)即可。此方案比方案1省空間此方案需要編寫給定排列求序號和給定序號求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。16判重o 時間與空間的權(quán)衡n 對于狀態(tài)數(shù)較小的問題，可以用最直接的方式編碼以空間換時間n 對于狀態(tài)數(shù)太大的問題，需要利用好的編碼方法以時間換空間n 具體問題具體分析17輸入數(shù)據(jù)：2 3 4 1 5 x 7 6 8輸出結(jié)果：ullddrurdl

8、lurdruldr 2 3 4 1 5 7 6 8 輸入數(shù)據(jù)代表：移動序列中u 表示使空格上移d 表示使空格下移r 表示使空格右移l 表示使空格左移1 2 3 4 5 6 7 8 輸出數(shù)據(jù)是一個移動序列，使得移動后結(jié)果變成用廣搜解決八數(shù)碼問題18八數(shù)碼例子程序o 采用方案1的非遞歸方案：數(shù)據(jù)結(jié)構(gòu)n用一個九進(jìn)制字符串表示一個節(jié)點，其中有且僅有一個0（表示空格）-因此若九進(jìn)制串中沒有0，則0一定是在最高位n設(shè)一個48427562位字符型標(biāo)志位序列數(shù)組szFlag，標(biāo)識每個狀態(tài)是否已擴展n設(shè)一個隊列MyQueue存放搜索過程中的可能狀態(tài)，根據(jù)問題定義，狀態(tài)總數(shù)362880?？紤]到搜索過程中可能存在的

9、重復(fù)狀態(tài)，其大小設(shè)為400000。n為簡化計算，設(shè)置與MyQueue同樣大小的數(shù)組anFather存放父節(jié)點指針、數(shù)組szMoves存放從父節(jié)點到當(dāng)前節(jié)點的移動步驟n設(shè)置一個結(jié)果隊列，為防止溢出，設(shè)置與MyQueue同樣大小19八數(shù)碼例子程序o 采用方案1的非遞歸方案：關(guān)鍵處理邏輯n 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)的移動步驟，并輸出.n BFS過程輸入：初始狀態(tài) 輸出：成功/失敗；若成功， anFather、 szMoves20八數(shù)碼例子程序

10、o 采用方案1的非遞歸方案：關(guān)鍵處理邏輯n BFS中的關(guān)鍵問題：1）如何進(jìn)行狀態(tài)擴展？2）狀態(tài)中0的位置與cMove動作間的關(guān)系？3）如何計算求從nStatus經(jīng)過 cMove 移動后得到的新狀態(tài)（定義為函數(shù)NewStatus ）？4）如何判斷擴展標(biāo)記已經(jīng)存在？5）對未擴展?fàn)顟B(tài)，如何置已擴展標(biāo)記(定義為函數(shù)SetBit )？6）字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)（定義為NineToTen和TenToNine）21#include #include using namespace std;int nGoalStatus; /目標(biāo)狀態(tài)bitset Flags; /節(jié)點是否擴展的標(biāo)記cha

11、r szResult400000; /結(jié)果char szMoves400000; /移動步驟 ： u/d/r/l int anFather400000; /父節(jié)點指針int MyQueue400000; /狀態(tài)隊列，狀態(tài)總數(shù)362880int nQHead; int nQTail;char sz4Moves = udrl;/四種動作八數(shù)碼例子程序22int 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

12、;23int TenToNine( int n, char * s) /十進(jìn)制數(shù)轉(zhuǎn)九進(jìn)制字符串。可能有前導(dǎo)0，返回0的位置int nZeroPos;int nBase = 1;int j = 0;while( nBase = 1 );sj = 0;/串結(jié)束符/判斷是否要加前導(dǎo)0，此時第0位即為0if( j 0; i -)si = si-1;s0 = 0;return 0;return nZeroPos;24int NewStatus( int nStatus, char cMove) /求從nStatus經(jīng)過 cMove 移動后得到的新狀態(tài)。若移動不可行則返回-1char szTmp20;in

13、t 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;case r: if(

14、nZeroPos % 3 = 2) return -1; /空格在第三列else szTmpnZeroPos = szTmpnZeroPos + 1;szTmpnZeroPos + 1 = 0;break;return NineToTen(szTmp);25bool Bfs(int nStatus)int nNewStatus;nQHead = 0;nQTail = 1;MyQueuenQHead = nStatus;while ( nQHead != nQTail) /隊列不為空nStatus = MyQueuenQHead;if( nStatus = nGoalStatus ) /找到目標(biāo)

15、狀態(tài) return true;for( int i = 0;i = 0; i - ) cout szResulti;elsecout unsolvable endl; return 0;27問題o 前述程序中，是否有狀態(tài)被重復(fù)擴展？n 初始狀態(tài)。為避免此重復(fù)， 應(yīng)在BFS初始化時對初始狀態(tài)進(jìn)行置位o 前述程序中，8數(shù)碼問題的有解性判定n 如果所有結(jié)點都擴展完還沒有達(dá)到目標(biāo)狀態(tài)，則問題無解，失敗退出o 是否有更節(jié)省存儲空間的做法，例如可以不用幾個大數(shù)組？n 一種可能方案：使用2個鏈表分別存隊列和結(jié)果28廣搜的解法二：鏈表表示o 基本思想：定義8數(shù)碼結(jié)點類CEight,它有兩個指針open_nex

16、t和parent，分別指向BFS擴展結(jié)點的下一個open節(jié)點和父結(jié)點（若當(dāng)前結(jié)點為目標(biāo)結(jié)點，通過parent可以得到解路徑）n 不需要設(shè)置標(biāo)志位序列數(shù)組szFlagn 用鏈表來表示狀態(tài)隊列MyQueueo 其他要求n 目標(biāo)結(jié)點可以支持重新設(shè)定，這樣可以用于計算任意兩個結(jié)點間的距離n 輸出結(jié)果將解路徑打印出來2 8 3 1 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 52 31 8 47 6 52 31 8 47 6 52 8 31 6 47 52 8 31 6 47 52 81 4 37 6 5

17、2 8 31 4 57 68 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 3 6 41 7 52 8 31 67 5 42 81 4 37 6 52 8 31 4 57 68 32 1 47 6 58 1 32 47 6 52 8 37 46 4 52 8 37 1 46 51 2 37 8 4 6 51 2 38 47 6 5圖3.4八數(shù)碼難題的寬度優(yōu)先搜索樹2 8 31 47 6 51S023456789101112131415161718192021222324252627Sg八數(shù)碼問題：任意兩結(jié)點間路徑實現(xiàn)細(xì)節(jié)(1)o

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

19、為奇數(shù)則稱該排列是奇排列，如果Y為偶數(shù)則稱該排列是偶排列。n871526340排列的 Y=0+0+0+1+1+3+2+3+0=10，10是偶數(shù)，所以是偶排列。n871625340排列的Y=0+0+0+1+1+2+2+3+0=9 9是奇數(shù)，所以是奇排列。 n因此，可以在運行程序前檢查初始狀態(tài)和目標(biāo)狀態(tài)的奇偶性是否相同，相同則問題可解，應(yīng)當(dāng)能搜索到路徑。否則無解。實現(xiàn)細(xì)節(jié)(2)o 廣搜過程讓鏈表頭指針open_head和尾指針open_tos指向初始節(jié)點S；while(open_head不為空且找到標(biāo)志為假)if(*open_head=Target) 找到標(biāo)志為真; break;Repeat 四種

20、動作 分別執(zhí)行一種動作； if (動作執(zhí)行成功&移動后新狀態(tài)在鏈表中無重復(fù)) 1. 從該新狀態(tài)生成新的CEight對象，使其父結(jié)點為 *open_head，使其open_next為NULL； 2. 通過尾指針open_tos將新CEight對象加入隊列； 移動open_head指針; #include iostreamusing namespace std;static int target9=1,2,3,4,5,6,7,8,0;class CEightprivate:int num9; /結(jié)點數(shù)組int deapth; /深度public:CEight* parent; /父指針CE

21、ight* open_next; /擴展指針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é)果CEight& operator=(CEight&); /兩對象賦值CEight& operator=(int other_num9

22、); /用數(shù)組給對象賦值int operator=(CEight&); /兩對象是否相等int operator=(int other_num9); /對象和數(shù)組是否相等;注意：本解法與POJ要求不完全相同，但很容易修改和移植CEight:CEight(int init_num9)for (int i=0;i9;i+)numi=init_numi;CEight:CEight()for (int i=0;i9;i+)numi=i;int CEight: get_deapth(void)return deapth;void CEight:get_numbers_to(int other_n

23、um9)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;void CEight:show() for (int i=0;i9;i+) coutnumi; if (i+1)%3) cout ; else coutn; /賦值運算符重載CEight& CEight:operator=(CEight& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;deapth=

24、another_8num.deapth+1;return *this;CEight& CEight:operator=(int other_num9)for (int i=0;i9;i+)numi=other_numi;return *this;/相等關(guān)系運算符重載int CEight:operator=(CEight& another_8num)int match=1;for (int i=0;i9;i+)if(numi!=another_8num.numi) match=0; break;if (match=0) return 0;else return 1;int CEi

25、ght: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;int move_up(int num9) /空格向上移 int i;for (i=0;i9;i+)/找空格位置if (numi=0) break;if (i3) return 0;else /空格不在第一行時移動numi=numi-3;numi-3=0; return 1;int move_down(int num9) /空格向下移 i

26、nt i;for (i=0;i5) return 0;else/空格不在第三行時移動numi=numi+3;numi+3=0; return 1;int move_left(int num9) /空格向左移 int i;for (i=0;i9;i+) /找空格位置if (numi=0) break;if (i=0|i=3|i=6)return 0;else /空格不在第一列時移動numi=numi-1;numi-1=0; return 1;int move_right(int num9) /空格向右移 int i;for (i=0;i9;i+) /找空格位置if (numi=0) break;

27、if (i=2|i=5|i=8)return 0;else /空格不在第三列時移動numi=numi+1;numi+1=0;return 1;int icansolve(int num9,int target9) /判斷可否解出int 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;int main(void)int step=0;i

28、nt num9;int flag=0;/是否輸入錯誤標(biāo)志，1表示輸入錯誤int bingo=0;/是否查找成功標(biāo)志，1表示成功int i,j;coutPlease input the number(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;coutinput;if (input=y|input=Y)coutnPlease input the new target:n;for (i=0;ita

29、rgeti;for(j=0;ji;j+) if(targeti=targetj)flag=1;if (targeti8|flag=1)i-;coutIllegle 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;r

30、eturn 1;CEight *open_head=&S,*open_tos=&S,*new_8num; /BFS搜索while(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_le

31、ft(num); break; case 3: bRec = move_right(num); break; if(bRec&!existed(num,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; /輸出結(jié)果if(bingo=1)CEight *p;for (p=o

32、pen_head-parent;p!=NULL;p=p-parent)coutshow();step+;coutTotaly covered steps:stepn;elsecoutFail to find!;return 0;廣搜的解法二：小結(jié)o 定義8數(shù)碼結(jié)點類CEight，及一些普通的功能函數(shù)（如移動、是否有解、是否重復(fù)等）o 用鏈表表示隊列，設(shè)置鏈表頭指針open_head和尾指針open_toso 用遍歷鏈表來查找是否有重復(fù)擴展結(jié)點n 較為低效o 通過鏈表運算來實現(xiàn)BFS用深度優(yōu)先搜索求解8數(shù)碼問題o 基本思想：優(yōu)先深入遍歷靠前的節(jié)點n 也可以通過鏈表實現(xiàn)，對上述算法中簡單修改即可8

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

34、還一定是路徑最短的解。n 缺點：盲目性較大，尤其是當(dāng)目標(biāo)節(jié)點距初始節(jié)點較遠(yuǎn)時，將產(chǎn)生許多無用的節(jié)點，因此其搜索效率較低。需要保存所有擴展出的狀態(tài)，占用的空間大o 深搜幾乎可以用于任何問題n 只需要保存從起始狀態(tài)到當(dāng)前狀態(tài)路徑上的節(jié)點o 根據(jù)題目要求憑借自己的經(jīng)驗和對兩個搜索的熟練程度做出選擇49擴展問題：是否有更快的做法？o 雙向廣度優(yōu)先搜索：從兩個方向以廣度優(yōu)先的順序同時擴展o A*：啟發(fā)式搜索搜索50雙向廣度優(yōu)先搜索(DBFS)o DBFS算法是對BFS算法的一種擴展。n BFS算法從起始節(jié)點以廣度優(yōu)先的順序不斷擴展，直到遇到目的節(jié)點n DBFS算法從兩個方向以廣度優(yōu)先的順序同時擴展，一個

35、是從起始節(jié)點開始擴展，另一個是從目的節(jié)點擴展，直到一個擴展隊列中出現(xiàn)另外一個隊列中已經(jīng)擴展的節(jié)點，也就相當(dāng)于兩個擴展方向出現(xiàn)了交點，那么可以認(rèn)為我們找到了一條路徑。o 比較n DBFS算法相對于BFS算法來說，由于采用了從兩個跟開始擴展的方式，搜索樹的深度得到了明顯的減少，所以在算法的時間復(fù)雜度和空間復(fù)雜度上都有較大的優(yōu)勢！DBFS的框架(1)o 一、主控函數(shù):void solve()1. 將起始節(jié)點放入隊列q1,將目的節(jié)點放入隊列q2；2. 當(dāng) 兩個隊列都未空時，作如下循環(huán)： 1) 如果隊列q1里的未處理節(jié)點比q2中的少（即tail0-head0 = tail1-head1時)；3. 如果隊

36、列q1未空，循環(huán)擴展（expand()）q1直到為空；4. 如果隊列q2未空，循環(huán)擴展（expand()）q2直到為空；DBFS的框架(2)o 二、擴展函數(shù)int expand(i) /其中i為隊列的編號(表示q0或者q1) 取隊列qi的頭結(jié)點H； 對頭節(jié)點H的每一個相鄰節(jié)點adj，作如下循環(huán)： 1 如果adj已經(jīng)在隊列qi之前的某個位置出現(xiàn)，則 拋棄節(jié)點adj； 2 如果adj在隊列qi中不存在函數(shù) isduplicate(i) 1） 將adj放入隊列qi； 2) 如果adj 在隊列(q(1-i)，也就是另外一個 隊列中出現(xiàn)函數(shù) isintersect()； 輸出 找到路徑 ；DBFS的框架

37、(3)o 三、判斷當(dāng)前擴展出的節(jié)點是否在另外一個隊列出現(xiàn)，也就是判斷相交的函數(shù)：int isintersect(i,j) /i為隊列編號，j為當(dāng)前節(jié)點在隊列中的指針 遍歷隊列,判斷是否存在/【線性遍歷的時間復(fù)雜度為O（N)，如果用HashTable優(yōu)化，時間復(fù)雜度可以降到O(1)】DBFS參考代碼o 見附件o 進(jìn)一步提高查找效率，采用hash函數(shù)優(yōu)化線性查找n 見附件A*算法o 針對八數(shù)碼問題，提出了人工智能史上很有名的A*算法(啟發(fā)式搜索算法)n 廣度優(yōu)先算法：當(dāng)目標(biāo)的深度較深時，產(chǎn)生很多冗余節(jié)點，空間消耗很大n 有限深度優(yōu)先算法：在時間或空間復(fù)雜度上均沒有明顯的優(yōu)勢，但如果目標(biāo)深度較深而且

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

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

40、待擴展結(jié)點的適當(dāng)位置，使它們按從小到大的順序排列，最后更新隊列尾指針o如果隊列頭的結(jié)點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步。#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* parent; CEight* open_next;CEight* leaf_pre;CEigh

41、t(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_num9);/修改int operator=(CEight&);int operator=(int other_num9);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_n