深度、廣度和雙向搜索優(yōu)化及其應(yīng)用

1、 ABCD E FGHI的每個(gè)元素是一個(gè)動作(action)的集合Fn將初態(tài)S0變換為另一個(gè)狀態(tài)F(S0)nF中各動作的執(zhí)行順序不影響F(S0)n如果F(S0)是符合要求的S*, 那么F是真解, 否則是偽解nBool Dfs(int nUnusedSticks, int nLeft ) ;nFunction dfs(nUnusedSticks:longint, nLeft:longint):longintn 表示: 當(dāng)前有nUnusedSticks根未用木棒，而且當(dāng)前正在拼的那根棍子比假定的棍子長度短了nLeft, 那么在這種情況下能否全部拼成功。nboolDfs(int nUnusedSti

2、cks, int nLeft) n.n if( nLeft = 0 ) /一根剛剛拼完nnLeft := L; /開始拼新的一根n找一根長度不超過nLeft的木棒（假設(shè)長為len）拼在當(dāng)前棍子上，然后nexit Dfs(nUnusedSticks 1, nLeft len );nnboolDfs(int nUnusedSticks, int nLeft ) nif( nUnusedSticks = 0 and nLeft = 0 )nexit true;n if( nLeft = 0 ) /一根剛剛拼完nnLeft := L; /開始拼新的一根n找一根長度不超過nLeft的木棒（假設(shè)長為len

3、）拼在當(dāng)前棍子上，然后nexit Dfs(nUnusedSticks 1, nLeft len )；nn拼每一根棍子的時(shí)候，應(yīng)該確保已經(jīng)拼好的部分，長度是從長到短排列的n由于取木棒是從長到短的，所以如果長得在前，短的在后不可行的話，那么相反的一定不可行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 52 8 31 4 57 68 32 1 47 6 52

4、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 51S023456789101112131415161718192021222324252627SgnBFS()nn初始化隊(duì)列nwhile(隊(duì)列不為空且未找到目標(biāo)節(jié)點(diǎn))nn取隊(duì)首節(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的節(jié)點(diǎn)放入隊(duì)尾；n必要時(shí)要記住每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)；nnn為節(jié)點(diǎn)編號n把每個(gè)節(jié)點(diǎn)都看一個(gè)排列，以此排列在全部排列中的位置作為其編號n排列總數(shù)：9!=362880n只需要一個(gè)整數(shù)(4字節(jié))即可存下一個(gè)節(jié)點(diǎn)n一個(gè)boolean標(biāo)志數(shù)組flag 記錄當(dāng)前狀態(tài)是否重復(fù)n判重用的標(biāo)志數(shù)組只需要362,880字節(jié)即可。n此方案需要編寫給定排列求序號和給定序號求排列的函數(shù)，這些函數(shù)的執(zhí)行速度慢于字符串形式的9進(jìn)制數(shù)到其整型值的互相轉(zhuǎn)換函數(shù)。n輸入數(shù)據(jù)：n2 3 4 1 5 x 7 6 8n輸出結(jié)果