分支界定是一種在問題的解空間樹上搜索問題的解的方法，其實就是剪枝廣搜，它始終維護一個上下界用來剪枝，一個限界函數計算對解的最有期望。主要用于解決離散問題的優化。

分支界定的關鍵問題：

（1）如何確定合適的限界函數

（2）如何組織待處理節點表

（3）如何記錄最優解路徑

限界函數應該是經過該節點所有搜索路徑的最佳期望

最大問題：本質還是廣搜，復雜度肯定不低，2^n的節點空間也受不了，試著解決01背包超時又超存，肯定不如DP，也可以解決TSP，排線問題等，

下邊自己寫的一個01背包，問題一堆，哎，菜鳥一個....

http://acm.hdu.edu.cn/showproblem.php?pid=2602

?

1 #include<stdio.h> 2 #include<queue> 3 #include<algorithm> 4 5 using namespace std; 6 7 #define MAXN 1005 8 9 struct ITEM 10 { 11 int w,v; 12 }b[MAXN]; 13 14 struct NODE 15 { 16 int w,v,ve,pos; 17 18 bool operator < (const NODE & other)const 19 { 20 return ve < other.ve; 21 } 22 }; 23 24 int search(ITEM * b,int num,int vol); 25 int cmp(const void * a,const void * b); 26 int expect(NODE a,ITEM * b,int num); 27 28 int main() 29 { 30 //freopen("Sample Input.txt","r",stdin); 31 int caseNum; 32 scanf("%d",&caseNum); 33 34 while(caseNum--) 35 { 36 int vol,num; 37 scanf("%d%d",&num,&vol); 38 39 for(int i = 0;i < num;i++) 40 { 41 scanf("%d",&b[i].v); 42 } 43 for(int i = 0;i < num;i++) 44 { 45 scanf("%d",&b[i].w); 46 } 47 48 printf("%d\n",search(b,num,vol)); 49 } 50 } 51 52 int search(ITEM * b,int num,int vol) 53 { 54 qsort(b,num,sizeof(b[0]),cmp); 55 56 /*for(int i = 0;i < num;i++) 57 { 58 printf("%d %d\n",b[i].w,b[i].v); 59 }*/ 60 61 int min = 0; //貪心的一個最小界 62 int t = vol; 63 for(int i = 0;i < num;i++) 64 { 65 if(t >= b[i].w) 66 { 67 min += b[i].v; 68 t -= b[i].w; 69 } 70 } 71 /*printf("%d %d\n",vol,min);*/ 72 priority_queue<NODE> que; 73 74 NODE fir; 75 fir.v = 0; 76 fir.w = vol; 77 fir.pos = 0; 78 fir.ve = expect(fir,b,num); 79 que.push(fir); 80 81 while(!que.empty()) 82 { 83 NODE cur = que.top(); 84 que.pop(); 85 86 if(cur.pos == num) 87 { 88 return cur.v; 89 } 90 91 for(int i = 0;i <= 1;i++) 92 { 93 NODE next = cur; 94 if(i == 1 && next.w < b[cur.pos].w) 95 { 96 continue; 97 } 98 next.w -= (i * b[cur.pos].w); 99 next.v += (i * b[cur.pos].v); 100 next.pos++; 101 next.ve = expect(next,b,num); 102 103 if(next.pos == num && next.v > min) 104 { 105 min = next.v; 106 } 107 if(next.ve >= min) 108 { 109 que.push(next); 110 } 111 } 112 } 113 } 114 115 int cmp(const void * a,const void * b) 116 { 117 double rate_a = double(((ITEM *) a) -> v) / ((ITEM *) a) -> w; 118 double rate_b = double(((ITEM *) b) -> v) / ((ITEM *) b) -> w; 119 return rate_b - rate_a; 120 } 121 122 int expect(NODE a,ITEM * b,int num) //限界函數 123 { 124 if(a.pos == num) 125 { 126 return a.v; 127 } 128 else 129 { 130 return a.v + a.w * b[a.pos].v / b[a.pos].w; 131 } 132 }

?

轉載于:https://www.cnblogs.com/codingMozart/p/6439743.html

總結

以上是生活随笔為你收集整理的分支限界的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。