第七講搜索(參考版)
2024-10-15 13:01本頁面
【正文】 //剪枝 1 } } } return false。 else { anUsed[i] = 0。 nLastStickNo = i。 anLength[i] == anLength[i1]) continue。 anLength[i] = nLeft) { if( i 0 ) { if( anUsed[i1] == false amp。i ++) { if( !anUsed[i] amp。 for( int i = nStartNo。 //開始拼新的一根 int nStartNo = 0。 nLeft == 0 ) return true。 int Dfs( int nUnusedSticks, int nLeft) // nLeft表示當(dāng)前正在拼的棍子和 L 比還缺的長度 { if( nUnusedSticks == 0 amp。由于取木棒是從長到短的，所以能走到這一步，就意味著當(dāng)初將 3放在 2的位置時(shí)，是不成功的 剪枝 4： 排除辦法：每次找一根木棒的時(shí)候，只要這不是一根棍子的第一條木棒，就不應(yīng)該從下標(biāo)為 0的木棒開始找，而應(yīng)該從剛剛 (最近）接上去的那條木棒的下一條開始找。 } 剪枝 4： 拼每一根棍子的時(shí)候，應(yīng)該確保已經(jīng)拼好的部分，長度是從長到短排列的，即拼的過程中要排除類似下面這種情況： 1 未完成的棍子 i 2 3 木棒 3 比木棒 2長，這種情況的出現(xiàn)是一種浪費(fèi)。//說明本次不能用第 i根 //第 i根以后還有用 if( anLength[i] == nLeft || nLeft == L) return false。 if ( Dfs( nUnusedSticks 1, nLeft anLength[i])){ return true。 anLength[i] == anLength[i1]) continue。 anLength[i] = nLeft) { if( i 0 ) { if( anUsed[i1] == false amp。i ++) { if( !anUsed[i] amp。 //開始拼新的一根 for( int i = 0。 nLeft == 0 ) return true。 } // while } 上一根同樣長度的木棒為什么還沒用？必然是因?yàn)閯倓傆眠^，并且發(fā)現(xiàn)用了后不行，才將其 anUsed標(biāo)志置回 0 int Dfs( int nUnusedSticks, int nLeft) // nLeft表示當(dāng)前正在拼的棍子和 L 比還缺的長度 { if( nUnusedSticks == 0 amp。 break。 memset( anUsed, 0,sizeof(anUsed))。 L = nTotalLen / 2。 } qsort(anLength,S,sizeof(int),MyCompare)。 i ++ ) { cin anLength[i]。 for( int i = 0。 if( S == 0 ) break。 return * p2 * p1。 p1 = (int * ) e1。 int Dfs(int nUnusedSticks, int nLeft)。 int anUsed[65]。 int L。 nLeft == 0) return true。 } Dfs的終止條件之一： bool Dfs(int nUnusedSticks, int nLeft ) { if( nUnusedSticks == 0 amp。 表示 : 當(dāng)前有 nUnusedSticks根未用木棒，而且當(dāng)前正在拼的那根棍子比假定的棍子長度短了 nLeft, 那么在這種情況下能全部否拼成功。 棍子 i 3 棍子 k 已拼接部分 未拼接部分 長度為 L的棍子 長度為 L1的未拼接木棒，共有 N1根 長度為 L2的未拼接木棒，共有 N2根 長度為 L3的未拼接木棒，共有 N3根 ? 如果某次拼接選擇長度為 L1的木棒，導(dǎo)致最終失敗，則在 同一位置 嘗試下一根木棒時(shí)，要跳過所有長度為L1的木棒。將棍子 k中的 3和棍子 i中用來替換 3的幾根木棒對調(diào)，結(jié)果當(dāng)然一樣是成功的。 1 棍子 k 剪枝 2： 不要希望通過僅僅替換已拼好棍子的最后一根木棒就能夠改變失敗的局面。如果不存在第 i1根棍子，那么就推翻本次假設(shè)的棍子長度，嘗試下一個(gè)長度 1 2 3 棍子 i 可以考慮把 2,3換掉重拼棍子 i,但是把 1換掉是沒有意義的 剪枝 1： 為什么替換第 i根棍子的第一根木棒是沒用的？ 因?yàn)榧僭O(shè)替換后能全部拼成功，那么這被換下來的第一根木棒，必然會(huì)出現(xiàn)在以后拼好的某根棍子 k中。 即 : 就算由于以后的拼接失敗，需要重新調(diào)整第 i根棍子的拚法，也不會(huì)考慮替換第 i根棍子中的第一根木棒（換了也沒用）。） 剪枝 1： 每次開始
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1