DFS + 剪枝策略

1：簡介

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

（2）蠻力搜搜需要優(yōu)化時，就是需要不停的剪枝，提早減少沒必要要的搜索路徑，提早發(fā)現(xiàn)判斷的過濾條件；

（3）剪枝的核心問題就是設(shè)計(jì)剪枝判斷方法，哪些搜索路徑應(yīng)當(dāng)舍棄，哪些搜索路徑不能舍棄（保存）；

（4）高效的剪枝過濾條件需要從局部和全局來斟酌問題，發(fā)現(xiàn)內(nèi)在的規(guī)律。

（5）詳細(xì)的剪枝算法，請見剪枝算法(算法優(yōu)化)

2：示例驗(yàn)證

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

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

（2）解題思路

  1.   首先 Sum1定要能被 L 整除。 
        2.   L 1定 大于等于 題目給出的最長的木棍的長度 Max。由上述兩點(diǎn)，我們想到，可以從 Max 開始遞增地枚舉 L, 直到成功地拼出 Sum/L 支長度為 L 的                  木棍。
        搜索種的剪枝技能： 
        3. 將輸入的輸入從大到小排序，這么做是由于1支長度為 K 的完全木棍，總比幾支短的小木棍拼成的要好。 形象1些： 如果我要拼 2 支長為8的木棍，                第1支木棍我拼成   5 + 3    然后拼第2支木棍但是失敗了，而我手中還有長為 2 和 1  的木棍，我可以用 5 + 2 + 1 拼好第1支，再嘗試拼第2
             支，仔細(xì)想想，就會發(fā)現(xiàn)這樣做沒意義，注定要失敗的。   我們應(yīng)當(dāng)留下 2+1 由于 2+1 比 3 更靈活。 
        4. 相同長度的木棍不要搜索屢次， 比如： 我手中有1些木棍, 其中有 2 根長為 4 的木棍， 當(dāng)前搜索狀態(tài)是 5+4+....(即表示長度為 5,4,2 的3支拼在1起, 
                ...表示深層的行將搜索的部份), 進(jìn)行深搜后不成功，故我 沒必要用另外一個 4 在進(jìn)行 5+4+... （題目中相鄰的前后比較）
         5. 將開始搜索1支長為 L 的木棍時，我們總是以當(dāng)前最長的未被使用的 木棍開始，如果搜索不成功，那末以比它短的開始，那末也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++)
                              {} 
                的區(qū)分，這個不多說了。
        7. 我用過的另外一個剪枝，但是對 poj 的數(shù)據(jù)效果1般， 用1個數(shù)組， Sum[i] 保存 第 i 個木棍以后，即比第 i 枝木棍短或與之相等所有的木棍的長度和。               試想，如果剩余的所有木棍加在1起都不能和我當(dāng)前的狀態(tài)拼 出1根長為 L 的木棍(從長度來看)，還有必要搜下去么？ 

（3）詳細(xì)代碼

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

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

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

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

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

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

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

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

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈