剪枝算法(算法優化)
來源：程序員人生 發布時間：2015-03-23 08:11:42 閱讀次數：10777次
1：剪枝策略的尋覓的方法
1）微觀方法：從問題本身動身，發現剪枝條件
2）宏觀方法：從整體動身，發現剪枝條件。
3）注意提高效力，這是關鍵，最重要的。
總之，剪枝策略，屬于算法優化范疇；通常利用在DFS 和 BFS 搜索算法中；剪枝策略就是尋覓過濾條件，提早減少沒必要要的搜索路徑。
2：剪枝算法(算法優化)
1、簡介
在搜索算法中優化中，剪枝，就是通過某種判斷，避免1些沒必要要的遍歷進程，形象的說，就是剪去了搜索樹中的某些“枝條”，故稱剪枝。利用剪枝優化的核心問題是設計剪枝判斷方法，即肯定哪些枝條應當舍棄，哪些枝條應當保存的方法。
2、剪枝優化3原則: 正確、準確、高效.原則
搜索算法,絕大部份需要用到剪枝.但是,不是所有的枝條都可以剪掉,這就需要通過設計出公道的判斷方法,以決定某1分支的取舍. 在設計判斷方法的時候,需要遵守1定的原則.
剪枝的原則
1） 正確性
正如上文所述,枝條不是愛剪就可以剪的. 如果隨意剪枝,把帶有最優解的那1分支也剪掉了的話,剪枝也就失去了意義. 所以,剪枝的條件是1定要保證不丟失正確的結果.
2）準確性
在保證了正確性的基礎上,我們應當根據具體問題具體分析,采取適合的判斷手段,使不包括最優解的枝條盡量多的被剪去,以到達程序“最優化”的目的. 可以說,剪枝的準確性,是衡量1個優化算法好壞的標準.
3）高效性
設計優化程序的根本目的,是要減少搜索的次數,使程序運行的時間減少. 但為了使搜索次數盡量的減少,我們又必須花工夫設計出1個準確性較高的優化算法,而當算法的準確性升高,其判斷的次數一定增多,從而又致使耗時的增多,這便引出了矛盾. 因此,如何在優化與效力之間尋覓1個平衡點,使得程序的時間復雜度盡量下降,一樣是非常重要的. 倘若1個剪枝的判斷效果非常好,但是它卻需要耗費大量的時間來判斷、比較,結果全部程序運行起來也跟沒有優化過的沒甚么區分,這樣就太得不償失了.
3、分類
剪枝算法依照其判斷思路可大致分成兩類:可行性剪枝及最優性剪枝.
3.1 可行性剪枝 ―― 該方法判斷繼續搜索能否得出答案，如果不能直接回溯。
3.2 最優性剪枝
最優性剪枝，又稱為上下界剪枝，是1種重要的搜索剪枝策略。它記錄當前得到的最優值，如果當前結點已沒法產生比當前最優解更優的解時，可以提早回溯。
3：示例分析
題目來源于poj 3900 The Robbery (類似于背包問題，但是不能夠用背包求解)
1 分析：W，C值很大，數組開不下（所以，不能用背包處理），但是發現N值很小，(1+15)*15/2=120，所以可以斟酌dfs+剪枝。
首先利用貪心的思想我們對箱子進行排序，關鍵字為性價比（參考了poj里的discuss）。也就是單位重量的價值最高的排第1，搜索的時候枚舉順序注意1定要從滿到空，這樣才能最快的找到1個可行解然后利用它進行接下來的剪枝。
剪枝1. 以后所有的鉆石價值+目前已得到的價值<=ans 則剪枝。
剪枝2. 剩下的重量全部裝目前最高性價比的鉆石+目前已得到的價值<=ans 則剪枝（非常重要的剪枝）。
2 程序代碼
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MY_MAX(a,b) (a)>(b)?(a):(b)
const int maxN = 20;
struct NOTE
{
long long weight;
long long value;
int num;
}box[maxN];
int n;// 個數小于20
long long m,ans;// m 總重量,ans最優解
long long sum[maxN]; //保存1個后綴和
bool cmp(const struct NOTE &a, const struct NOTE &b)
{//按性價比排序,從大到小排列（注意若有取地址符號，則需有const）
return a.value*1.0/a.weight > b.value*1.0/b.weight;
}
inline bool cut (int pos,long long now_value,long long last_weight)
{
if(pos == n+1) return true;//邊界返回條件
if(now_value+sum[pos] < ans) return true;////如果后面所有的鉆石加起來都<=ans，剪掉
double best = (box[pos].value*1.0/box[pos].weight);//當前最大的性價比
if(now_value+(long long)ceil(best*last_weight) < ans) return true;//以這個性價比取剩下的所有重量，如果<=ans,剪掉
return false;
}
void dfs(int pos,long long now_value,long long last_weight) //pos 當前數組的下標位置，now_value 目前的重量和，last_weight當前背包剩余容量
{
ans = MY_MAX(ans,now_value);
if(cut(pos,now_value,last_weight)) return;//剪枝函數
for(int i=box[pos].num;i>=0;--i)//(暴力搜索)枚舉順序從滿到空枚舉，這樣才能最快找到ans，然后利用ans剪枝
{
if(last_weight<box[pos].weight*i) continue;
dfs(pos+1,now_value+box[pos].value*i,last_weight-box[pos].weight*i);
}
}
int main()
{
int cas;
long long sumv,sumw;// 價值和重量的和；僅僅用到了1次（特殊情況才用到，能夠1次全帶走）
scanf("%d",&cas);
while(cas--)
{
ans=0;
sumv=sumw=0;
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&box[i].weight);
sumw+=box[i].weight*i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&box[i].value);
box[i].num=i;
sumv+=box[i].value*i;
}
// 以上是數據的輸入，下面才是剛剛開始的
// 如果sumv開始就比m總重量還小，直接輸出
if(sumw<=m)
{
printf("%lld
",sumv);
continue;
}
sort(box+1,box+1+n,cmp);// 從1開始計數的
sum[n+1]=0; // 倒著開始的
for(int i=n;i>=1;i--)
{
//計算后綴和
sum[i]=sum[i+1]+box[i].value*box[i].num;
}
dfs(1,0,m);
printf("%lld
",ans);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
