第七講搜索-資料下載頁
2025-10-02 13:01本頁面
【導(dǎo)讀】影響搜索效率的因素。逐一判斷所有可能的方案是否是問題的解。例1：求出A-I這九個字母對應(yīng)的數(shù)字（1-9），枚舉ABCDE的值，計(jì)算乘積，判斷是否符合要求。有順序有策略地枚舉狀態(tài)空間中的結(jié)點(diǎn)，尋找問題的解。優(yōu)先擴(kuò)展淺層結(jié)點(diǎn)，逐漸深入。用隊(duì)列保存待擴(kuò)展的結(jié)點(diǎn)，從隊(duì)首隊(duì)取出結(jié)點(diǎn)，擴(kuò)展出。廣度優(yōu)先搜索的代碼框架。取隊(duì)首結(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的結(jié)點(diǎn)放入隊(duì)尾；必要時要記住每個結(jié)點(diǎn)的父結(jié)點(diǎn)；深度優(yōu)先搜索的棧實(shí)現(xiàn)（非遞歸）框架。個新節(jié)點(diǎn)就不必再考慮。怎樣才能較快的找到重復(fù)結(jié)點(diǎn)？每個字符8個bit，可以存放8個狀態(tài)標(biāo)志位。位序列最多需要99位，因。合理編碼，減小存儲代價。方案一：每個節(jié)點(diǎn)對應(yīng)于一個九進(jìn)制數(shù)，則4個字節(jié)。就能表示一個節(jié)點(diǎn)。把每個結(jié)點(diǎn)都看一個排列，以此排列在全部排列。判重用的標(biāo)志數(shù)組只需要362880字節(jié)即可。時間與空間的權(quán)衡。對于狀態(tài)數(shù)較小的問題，可以用最直接的方式編碼以空。具體問題具體分析。輸出數(shù)據(jù)是一個移動序列，
【正文】 ) { cin S。 if( S == 0 ) break。 int nTotalLen = 0。 for( int i = 0。 i S。 i ++ ) { cin anLength[i]。 nTotalLen += anLength[i]。 } qsort(anLength,S,sizeof(int),MyCompare)。 for( L = anLength[0]。 L = nTotalLen / 2。 L ++ ) { if( nTotalLen % L) continue。 memset( anUsed, 0,sizeof(anUsed))。 if( Dfs( S,L)) { cout L endl。 break。 } } if( L nTotalLen / 2 ) cout nTotalLen endl。 } // while } 上一根同樣長度的木棒為什么還沒用？必然是因?yàn)閯倓傆眠^，并且發(fā)現(xiàn)用了后不行，才將其 anUsed標(biāo)志置回 0 int Dfs( int nUnusedSticks, int nLeft) // nLeft表示當(dāng)前正在拼的棍子和 L 比還缺的長度 { if( nUnusedSticks == 0 amp。amp。 nLeft == 0 ) return true。 if( nLeft == 0 ) //一根剛剛拼完 nLeft = L。 //開始拼新的一根 for( int i = 0。i S。i ++) { if( !anUsed[i] amp。amp。 anLength[i] = nLeft) { if( i 0 ) { if( anUsed[i1] == false amp。amp。 anLength[i] == anLength[i1]) continue。 //剪枝 3 } anUsed[i] = 1。 if ( Dfs( nUnusedSticks 1, nLeft anLength[i])){ return true。 }else { anUsed[i] = 0。//說明本次不能用第 i根 //第 i根以后還有用 if( anLength[i] == nLeft || nLeft == L) return false。 //剪枝 1 } } } return false。 } 剪枝 4： 拼每一根棍子的時候，應(yīng)該確保已經(jīng)拼好的部分，長度是從長到短排列的，即拼的過程中要排除類似下面這種情況： 1 未完成的棍子 i 2 3 木棒 3 比木棒 2長，這種情況的出現(xiàn)是一種浪費(fèi)。因?yàn)橐沁@樣往下能成功，那么 2, 3 對調(diào)的拚法肯定也能成功。由于取木棒是從長到短的，所以能走到這一步，就意味著當(dāng)初將 3放在 2的位置時，是不成功的 剪枝 4： 排除辦法：每次找一根木棒的時候，只要這不是一根棍子的第一條木棒，就不應(yīng)該從下標(biāo)為 0的木棒開始找，而應(yīng)該從剛剛 (最近）接上去的那條木棒的下一條開始找。這樣，就不會往 2后面接更長的 3了 1 2 3 為此，要設(shè)置一個全局變量 nLastStickNo ，記住最近拼上去的那條木棒的下標(biāo)。 int Dfs( int nUnusedSticks, int nLeft) // nLeft表示當(dāng)前正在拼的棍子和 L 比還缺的長度 { if( nUnusedSticks == 0 amp。amp。 nLeft == 0 ) return true。 if( nLeft == 0 ) //一根剛剛拼完 nLeft = L。 //開始拼新的一根 int nStartNo = 0。 if( nLeft != L ) //剪枝 4 nStartNo = nLastStickNo + 1。 for( int i = nStartNo。i S。i ++) { if( !anUsed[i] amp。amp。 anLength[i] = nLeft) { if( i 0 ) { if( anUsed[i1] == false amp。amp。 anLength[i] == anLength[i1]) continue。 //剪枝 3 } anUsed[i] = 1。 nLastStickNo = i。 if ( Dfs( nUnusedSticks 1, nLeft anLength[i])) return true。 else { anUsed[i] = 0。//說明本次不能用第 i根 //第 i根以后還有用 if( anLength[i] == nLeft || nLeft == L) return false。//剪枝 1 } } } return false。 } 作業(yè) ? ai2787 算 24
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1