第七講搜索-閱讀頁(yè)
2024-10-31 13:01本頁(yè)面
【正文】 es = 0。 do { szResult[nMoves++] = szMoves[nPos]。 } while( nPos)。 i = 0。 } } else cout unsolvable endl。如用遞歸實(shí)現(xiàn)，不作特殊處理的話，很容易就導(dǎo)致遞歸層數(shù)太多而棧溢出。這可以避免棧溢出。 用深搜解決八數(shù)碼問(wèn)題 廣搜與深搜的比較 ? 廣搜一般用于狀態(tài)表示比較簡(jiǎn)單、求最優(yōu)策略的問(wèn)題 ? 需要保存所有擴(kuò)展出的狀態(tài)，占用的空間大； ? 每次擴(kuò)展出結(jié)點(diǎn)時(shí)所走過(guò)的路徑均是最短路； ? 深搜幾乎可以用于任何問(wèn)題 ? 只需要保存從起始狀態(tài)到當(dāng)前狀態(tài)路徑上的結(jié)點(diǎn)； ? 根據(jù)題目要求憑借自己的經(jīng)驗(yàn)和對(duì)兩個(gè)搜索的熟練程度做出選擇。然后他又想把這些木棒恢復(fù)到裁截前的狀態(tài)，但忘記了棍子的初始長(zhǎng)度。每一節(jié)木棒的長(zhǎng)度都用大于零的整數(shù)表示。第一行是一個(gè)不超過(guò) 64的整數(shù)，表示裁截之后共有多少節(jié)木棒。在最后一個(gè)案例之后，是零。 輸入樣例 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0 輸出樣例 6 5 解題思路 ? 初始狀態(tài)：有 N節(jié)木棒 ? 最終狀態(tài)：這 N節(jié)木棒恰好被拼接成若干根等長(zhǎng)的棍子 (裁前的東西稱為棍子） ? 枚舉什么？ 枚舉所有有可能的棍子長(zhǎng)度。 ? 在拼接過(guò)程中，要給用過(guò)的木棒做上標(biāo)記，以免重復(fù)使用。 ? 搜索題，首先要解決一個(gè)問(wèn)題：按什么順序搜索？ ? 把木棒按長(zhǎng)度排序。為什么？ ? 因?yàn)槎棠景舯容^容易用來(lái)填補(bǔ)空缺。 ? 搜索題，還要解決一個(gè)問(wèn)題：如何剪枝（就本題而言，即盡可能快地發(fā)現(xiàn)一根拼好的棍子需要被拆掉，以及盡量少做結(jié)果不能成功的嘗試。對(duì)此決不后悔。如果在此情況下怎么都無(wú)法成功，那么就要推翻第 i1根棍子的拚法。那么我們?cè)绕吹?i根棍子時(shí) , 就可以用和棍子 k同樣的構(gòu)成法來(lái)拼，照這種構(gòu)成法拼好第 i根棍子，繼續(xù)下去最終也應(yīng)該能夠全部拼成功。 1 2 3 假設(shè)由于后續(xù)拼接無(wú)法成功，導(dǎo)致準(zhǔn)備拆除已經(jīng)拼好的某根棍子，如下： 將 3 拆掉，留下的空用其他短木棒來(lái)填，是徒勞的 棍子 i 剪枝 2： 1 2 假設(shè)替換 3后最終能夠成功，那么 3必然出現(xiàn)在后面的某個(gè)棍子 k里。這就和 i原來(lái)的拚法會(huì)導(dǎo)致不成功矛盾。 剪枝 3： bool Dfs(int nUnusedSticks, int nLeft ) 。 Dfs的基本遞推關(guān)系： bool Dfs(int nUnusedSticks, int nLeft) { ….. 找一根長(zhǎng)度不超過(guò) nLeft的木棒 (假設(shè)長(zhǎng)為 len)，拼在當(dāng)前棍子上，然后 return Dfs(nUnusedSticks – 1,nLeft – len )。amp。 } include include include int T, S。 int anLength[65]。 int i,j,k。 int MyCompare( const void * e1, const void * e2) { int * p1, * p2。 p2 = (int * ) e2。 } main() { while(1) { cin S。 int nTotalLen = 0。 i S。 nTotalLen += anLength[i]。 for( L = anLength[0]。 L ++ ) { if( nTotalLen % L) continue。 if( Dfs( S,L)) { cout L endl。 } } if( L nTotalLen / 2 ) cout nTotalLen endl。amp。 if( nLeft == 0 ) //一根剛剛拼完 nLeft = L。i S。amp。amp。 //剪枝 3 } anUsed[i] = 1。 }else { anUsed[i] = 0。 //剪枝 1 } } } return false。因?yàn)橐沁@樣往下能成功，那么 2, 3 對(duì)調(diào)的拚法肯定也能成功。這樣，就不會(huì)往 2后面接更長(zhǎng)的 3了 1 2 3 為此，要設(shè)置一個(gè)全局變量 nLastStickNo ，記住最近拼上去的那條木棒的下標(biāo)。amp。 if( nLeft == 0 ) //一根剛剛拼完 nLeft = L。 if( nLeft != L ) //剪枝 4 nStartNo = nLastStickNo + 1。i S。amp。amp。 //剪枝 3 } anUsed[i] = 1。 if ( Dfs( nUnusedSticks 1, nLeft anLength[i])) return true。//說(shuō)明本次不能用第 i根 //第 i根以后還有用 if( anLength[i] == nLeft || nLeft == L) return false。 } 作業(yè) ? ai2787 算 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1