您當前位置：首頁 > php開源 > 綜合技術 > DFS + 剪枝策略

DFS + 剪枝策略

來源：程序員人生發布時間：2015-03-11 08:06:33 閱讀次數：6333次

1：簡介

（1）相信做過ACM的人，都很熟習圖和樹的深度優先搜索；算法里面有蠻力法 ―― 就是暴力搜索（不加任何剪枝的搜索）；

（2）蠻力搜搜需要優化時，就是需要不停的剪枝，提早減少沒必要要的搜索路徑，提早發現判斷的過濾條件；

（3）剪枝的核心問題就是設計剪枝判斷方法，哪些搜索路徑應當舍棄，哪些搜索路徑不能舍棄（保存）；

（4）高效的剪枝過濾條件需要從局部和全局來斟酌問題，發現內在的規律。

（5）詳細的剪枝算法，請見剪枝算法(算法優化)

2：示例驗證

（1）題目來源于 poj 1011 Sticks DFS + 剪枝

題目大意：給出1些長度不大于 50 的木棍，要求你把這些小木棍拼成,長度相同木棍，固然長度越小越好。

（2）解題思路

1. 首先 Sum1定要能被 L 整除。
2. L 1定大于等于題目給出的最長的木棍的長度 Max。由上述兩點，我們想到，可以從 Max 開始遞增地枚舉 L, 直到成功地拼出 Sum/L 支長度為 L 的木棍。
搜索種的剪枝技能：
3. 將輸入的輸入從大到小排序，這么做是由于1支長度為 K 的完全木棍，總比幾支短的小木棍拼成的要好。形象1些：如果我要拼 2 支長為8的木棍，第1支木棍我拼成 5 + 3 然后拼第2支木棍但是失敗了，而我手中還有長為 2 和 1 的木棍，我可以用 5 + 2 + 1 拼好第1支，再嘗試拼第2
支，仔細想想，就會發現這樣做沒意義，注定要失敗的。我們應當留下 2+1 由于 2+1 比 3 更靈活。
4. 相同長度的木棍不要搜索屢次，比如：我手中有1些木棍, 其中有 2 根長為 4 的木棍，當前搜索狀態是 5+4+....(即表示長度為 5,4,2 的3支拼在1起,
...表示深層的行將搜索的部份), 進行深搜后不成功，故我沒必要用另外一個 4 在進行 5+4+... （題目中相鄰的前后比較）
5. 將開始搜索1支長為 L 的木棍時，我們總是以當前最長的未被使用的木棍開始，如果搜索不成功，那末以比它短的開始，那末也1定不能獲得全局的成功。由于每支題目給出的木棍都要被用到。如果，有
4
5 4 4 3 2 想拼成長為 6 的木棍，那末從 5 開始，但是明顯沒有能與 5 1起拼成 6 的，那末我就沒必要去嘗試從 4 開始的，由于終究 5 1定會被拋棄。在拼第 2 3 ... 支木棍時，1樣。（小的更加靈活）

6. 最后的最簡單的1個就是，
for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)
{}
與
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
{}
的區分，這個不多說了。
7. 我用過的另外一個剪枝，但是對 poj 的數據效果1般，用1個數組， Sum[i] 保存第 i 個木棍以后，即比第 i 枝木棍短或與之相等所有的木棍的長度和。試想，如果剩余的所有木棍加在1起都不能和我當前的狀態拼出1根長為 L 的木棍(從長度來看)，還有必要搜下去么？

（3）詳細代碼

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int Max = 65; int n, len, stick[Max]; bool flag, vis[Max]; bool cmp(int a, int b) { return a > b; } void dfs(int dep, int now_len, int u) { // dep為當前已被用過的小棒數，u為當前要處理的小棒。 if(flag) return;//完成的遞歸返回條件 if(now_len == 0){ // 當前長度為0，尋覓下1個當前最長小棒。 int k = 0; while(vis[k]) k ++; // 尋覓第1個當前最長小棒。 vis[k] = true; dfs(dep + 1, stick[k], k + 1); vis[k] = false; return; } if(now_len == len) { // 當前長度為len，即又拼湊成了1根原棒。 if(dep == n) flag = true; // 完成的標志：所有的n根小棒都有拼到了。 else dfs(dep, 0, 0); return;//未完成的遞歸返回條件 } for(int i = u; i < n; i ++) if(!vis[i] && now_len + stick[i] <= len)// 過濾條件 { if(!vis[i⑴] && stick[i] == stick[i⑴]) continue; // 不重復搜索：最重要的剪枝。 vis[i] = true; dfs(dep + 1, now_len + stick[i], i + 1); vis[i] = false; } } int main() { while(scanf("%d", &n) && n != 0) { int sum = 0; flag = false; for(int i = 0; i < n; i ++) { scanf("%d", &stick[i]); sum += stick[i]; } sort(stick, stick + n, cmp); // 從大到小排序。 for(len = stick[0]; len < sum; len ++) if(sum % len == 0)// 這里也相當因而剪枝（過濾條件） { // 枚舉能被sum整除的長度。 memset(vis, 0, sizeof(vis)); dfs(0, 0, 0); if(flag) break; } printf("%d ", len); } return 0; }

（4）對照比較 poj 1011(本博客) 和 poj 3900 (剪枝算法(算法優化))

對前者 ―― 是依照性價比排序；性價比高的未必最后會要（有選擇的要）；構成兩條剪枝條件：

剪枝1. 以后所有的鉆石價值+目前已得到的價值<=ans 則剪枝。

剪枝2. 剩下的重量全部裝目前最高性價比的鉆石+目前已得到的價值<=ans 則剪枝（非常重要的剪枝）。

對后者 ―― 依照長度排序（都是提早從大到小的排序）；必須把全部小木棒用上，因此需要有visit數組在dfs前后的true 和 false 的變化；

剪枝1、由于所有原始棒子等長，那末必有sumlen%Initlen==0；

剪枝2、若能在[maxlen,sumlen-InitLen]找到最短的InitLen，該InitLen必也是[maxlen,sumlen]的最短；若不能在[maxlen,sumlen-InitLen]找到最短的InitLen，則必有InitLen=sumlen；

剪枝3、由于所有棒子已降序排序，在DFS時，若某根棒子不適合，則跳過其后面所有與它等長的棒子；

剪枝4、最重要的剪枝：對某個目標InitLen，在每次構建新的長度為InitLen的原始棒時，檢查新棒的第1根stick[i]，若在搜索完所有stick[]后都沒法組合，則說明stick[i]沒法在當前組合方式下組合，不用往下搜索(往下搜索會令stick[i]被舍棄)，直接返回上1層

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生