算法笔记——分支限界法最优装载问题

1、 问题描述      有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。      容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。      (1)首先将第一艘轮船尽可能装满；     (2)将剩余的集装箱装上第二艘轮船。      

2、1、队列式分支限界法求解      在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。     活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。   

3、 节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r<bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。     为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。     找到最优值后

4、，可以根据parent回溯到根节点，找到最优解。     算法具体代码实现如下：     1、Queue.hcpp view plain copy1. #include<iostream>  2. using namespace std;  3.   4. template <class T>  5. class Queue  6.  

5、; 7.     public:  8.         Queue(int MaxQueueSize=50);  9.         Queue()delete  queue;  10.         bool&#

6、160;IsEmpty()constreturn front=rear;  11.         bool IsFull()return ( (  (rear+1)  %MaxSize=front )?1:0);  12.         T Top() const; 

7、0;13.         T Last() const;  14.         Queue<T>& Add(const T& x);  15.         Queue<T>& AddLeft(const

8、 T& x);  16.         Queue<T>& Delete(T &x);  17.         void Output(ostream& out)const;  18.        &

9、#160;int Length()return (rear-front);  19.     private:  20.         int front;  21.         int rear;  22.      &#

10、160;  int MaxSize;  23.         T *queue;  24. ;  25.   26. template<class T>  27. Queue<T>:Queue(int MaxQueueSize)  28.   29.    

11、60;MaxSize=MaxQueueSize+1;  30.     queue=new TMaxSize;  31.     front=rear=0;  32.   33.   34. template<class T >  35. T Queue<T>:Top()const  36.   

12、;37.     if(IsEmpty()  38.       39.         cout<<"queue:no element,no!"<<endl;  40.         return 0;  41.

13、       42.     else return queue(front+1) % MaxSize;  43.   44.   45. template<class T>  46. T Queue<T> :Last()const  47.   48.   

14、60; if(IsEmpty()  49.       50.         cout<<"queue:no element"<<endl;  51.         return 0;  52.     

15、;  53.     else return queuerear;  54.   55.   56. template<class T>  57. Queue<T>&  Queue<T>:Add(const T& x)  58.   59.     if(I

16、sFull()cout<<"queue:no memory"<<endl;  60.     else  61.       62.         rear=(rear+1)% MaxSize;  63.        &#

17、160;queuerear=x;  64.       65.     return *this;  66.   67.   68. template<class T>  69. Queue<T>&  Queue<T>:AddLeft(const T& x)  70.

18、   71.     if(IsFull()cout<<"queue:no memory"<<endl;  72.     else  73.       74.         front=(front+MaxSize-1)% MaxSize; 

19、; 75.         queue(front+1)% MaxSize=x;  76.       77.     return *this;  78.   79.   80. template<class T>  81. Queue<T>&&

20、#160; Queue<T> :Delete(T & x)  82.   83.     if(IsEmpty()cout<<"queue:no element(delete)"<<endl;  84.     else   85.       86. &

21、#160;       front=(front+1) % MaxSize;  87.         x=queuefront;  88.       89.     return *this;  90.   91.  

22、0;92.   93. template<class T>  94. void Queue <T>:Output(ostream& out)const  95.   96.     for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i-)  97.        

23、out<<queuei;  98.   99.   100. template<class T>  101. ostream& operator << (ostream& out,const Queue<T>& x)  102. x.Output(out);return out;        2

24、、6d3-1.cppcpp view plain copy1. /装载问题 队列式分支限界法求解   2. #include "stdafx.h"  3. #include "Queue.h"  4. #include <iostream>  5. using namespace std;  6.   7. const int

25、 N = 4;  8.   9. template<class Type>  10. class QNode  11.   12.     template<class Type>  13.     friend void EnQueue(Queue<QNode<Type>*&

26、gt;&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch);  14.   15.     template<class Type>  16.     friend Type MaxLoa

27、ding(Type w,Type c,int n,int bestx);  17.   18.     private:  19.         QNode *parent;  /指向父节点的指针  20.         bool LC

28、hild;    /左儿子标识  21.         Type weight;    /节点所相应的载重量  22. ;  23.   24. template<class Type>  25. void EnQueue(Queue<QNode<Type>*>&

29、Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch);  26.   27. template<class Type>  28. Type MaxLoading(Type w,Type c,int n,int bestx);  

30、29.   30. int main()  31.   32.     float c = 70;    33.     float w = 0,20,10,26,15;/下标从1开始    34.     int xN+1;   

31、; 35.     float bestw;  36.     37.     cout<<"轮船载重为："<<c<<endl;    38.     cout<<"待装物品的重量分别为："<<endl;    39.

32、    for(int i=1; i<=N; i+)    40.         41.         cout<<wi<<" "    42.       

33、0; 43.     cout<<endl;    44.     bestw = MaxLoading(w,c,N,x);    45.     46.     cout<<"分支限界选择结果为:"<<endl;    47. &#

34、160;   for(int i=1; i<=4; i+)    48.         49.         cout<<xi<<" "    50.        

35、 51.     cout<<endl;    52.     cout<<"最优装载重量为："<<bestw<<endl;  53.     54.     return 0;    55.   56.   5

36、7. /将活节点加入到活节点队列Q中  58. template<class Type>  59. void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch)  60.   6

37、1.     if(i = n)/可行叶节点  62.       63.         if(wt = bestw)  64.           65.       

38、0;     /当前最优装载重量  66.             bestE = E;  67.             bestxn = ch;       

39、;     68.           69.         return;  70.       71.     /非叶节点  72.     QNode<Type>

40、0;*b;  73.     b = new QNode<Type>  74.     b->weight = wt;  75.     b->parent = E;  76.     b->LChild = ch;  

41、77.     Q.Add(b);  78.   79.   80. template<class Type>  81. Type MaxLoading(Type w,Type c,int n,int bestx)  82. /队列式分支限界法，返回最优装载重量，bestx返回最优解  83.  /初始化  84.  

42、0;  Queue<QNode<Type>*> Q;      /活节点队列  85.     Q.Add(0);                   /同层节点尾部标识  86.    

43、; int i = 1;                  /当前扩展节点所处的层  87.     Type Ew = 0,             

44、0;  /扩展节点所相应的载重量  88.          bestw = 0,             /当前最优装载重量  89.          r = 0;  

45、;               /剩余集装箱重量  90.   91.     for(int j=2; j<=n; j+)  92.       93.         r

46、 += wj;  94.       95.       96.     QNode<Type> *E = 0,           /当前扩展节点  97.      

47、0;          *bestE;         /当前最优扩展节点  98.   99.     /搜索子集空间树  100.     while(true)  101.       

48、;102.         /检查左儿子节点  103.         Type wt = Ew + wi;  104.         if(wt <= c)/可行节点  105.    &

49、#160;      106.             if(wt>bestw)  107.               108.           &

50、#160;     bestw = wt;  109.               110.             EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);  111.  

51、         112.   113.         /检查右儿子节点  114.         if(Ew+r>bestw)  115.           116. 

52、0;           EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);  117.           118.         Q.Delete(E);/取下一扩展节点  119.   120. 

53、0;       if(!E)/同层节点尾部  121.           122.             if(Q.IsEmpty()  123.          

54、0;    124.                 break;  125.               126.           &

55、#160; Q.Add(0);       /同层节点尾部标识  127.             Q.Delete(E);    /取下一扩展节点  128.             i+;

56、0;           /进入下一层  129.             r-=wi;        /剩余集装箱重量  130.          

57、0;131.         Ew  =E->weight;      /新扩展节点所对应的载重量  132.       133.   134.     /构造当前最优解  135.     for(int j=n-1;&

58、#160;j>0; j-)  136.       137.         bestxj = bestE->LChild;  138.         bestE = bestE->parent;  139.    &#

59、160;  140.     return bestw;  141.        程序运行结果如图：     2、优先队列式分支限界法求解      解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。     优先队列中优先级最大的活结点成为下一个扩

60、展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。     在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。     算法具体代码实现如下：     1、MaxHeap.hcpp view plain copy1. template<class T>  2. class MaxHeap 

61、60;3.   4.     public:  5.         MaxHeap(int MaxHeapSize = 10);  6.         MaxHeap() delete  heap;  7.     

62、    int Size() const return CurrentSize;  8.   9.         T Max()   10.                   

63、/查  11.            if (CurrentSize = 0)  12.              13.               

64、;  throw OutOfBounds();  14.              15.            return heap1;  16.           17.

65、  18.         MaxHeap<T>& Insert(const T& x); /增  19.         MaxHeap<T>& DeleteMax(T& x);   /删  20.   21.

66、        void Initialize(T a, int size, int ArraySize);  22.   23.     private:  24.         int CurrentSize, MaxSize;  2

67、5.         T *heap;  / element array  26. ;  27.   28. template<class T>  29. MaxHeap<T>:MaxHeap(int MaxHeapSize)  30. / Max heap constructor. 

68、 31.     MaxSize = MaxHeapSize;  32.     heap = new TMaxSize+1;  33.     CurrentSize = 0;  34.   35.   36. template<class T>  37.

69、 MaxHeap<T>& MaxHeap<T>:Insert(const T& x)  38. / Insert x into the max heap.  39.     if (CurrentSize = MaxSize)  40.       41.   

70、;      cout<<"no space!"<<endl;   42.         return *this;   43.       44.   45.     / 寻找新元素x的位置 

71、 46.     / i初始为新叶节点的位置，逐层向上，寻找最终位置  47.     int i = +CurrentSize;  48.     while (i != 1 && x > heapi/2)  49.      

72、; 50.         / i不是根节点，且其值大于父节点的值，需要继续调整  51.         heapi = heapi/2; / 父节点下降  52.         i /= 2;   

73、60;          / 继续向上，搜寻正确位置  53.       54.   55.    heapi = x;  56.    return *this;  57.   58.   59. template&

74、lt;class T>  60. MaxHeap<T>& MaxHeap<T>:DeleteMax(T& x)  61. / Set x to max element and delete max element from heap.  62.     / check if heap

75、 is empty  63.     if (CurrentSize = 0)  64.       65.         cout<<"Empty heap!"<<endl;   66.     

76、60;   return *this;   67.       68.   69.     x = heap1; / 删除最大元素  70.     / 重整堆  71.     T y = heapCurre

77、ntSize-; / 取最后一个节点，从根开始重整  72.   73.     / find place for y starting at root  74.     int i = 1,  / current node of heap  75. 

78、0;      ci = 2; / child of i  76.   77.     while (ci <= CurrentSize)   78.       79.         /&#

79、160;使ci指向i的两个孩子中较大者  80.         if (ci < CurrentSize && heapci < heapci+1)  81.           82.        

80、0;    ci+;  83.           84.         / y的值大于等于孩子节点吗？  85.         if (y >= heapci)  86.  &#

81、160;        87.             break;   / 是，i就是y的正确位置，退出  88.           89.   90.      &

82、#160;  / 否，需要继续向下，重整堆  91.         heapi = heapci; / 大于父节点的孩子节点上升  92.         i = ci;           

83、60; / 向下一层，继续搜索正确位置  93.         ci *= 2;  94.       95.   96.     heapi = y;  97.     return *this;  98.

84、   99.   100. template<class T>  101. void MaxHeap<T>:Initialize(T a, int size,int ArraySize)  102. / Initialize max heap to array a.  103.     delete &#

85、160;heap;  104.     heap = a;  105.     CurrentSize = size;  106.     MaxSize = ArraySize;  107.   108.     / 从最后一个内部节点开始，一直到根，对每个子树进行堆

86、重整  109.    for (int i = CurrentSize/2; i >= 1; i-)  110.      111.         T y = heapi; / 子树根节点元素  112.    

87、;     / find place to put y  113.         int c = 2*i; / parent of c is target  114.           

88、         / location for y  115.         while (c <= CurrentSize)   116.           117.    &#

89、160;        / heapc should be larger sibling  118.             if (c < CurrentSize && heapc < heapc+1)  11

90、9.               120.                 c+;  121.               122.

91、60;           / can we put y in heapc/2?  123.             if (y >= heapc)  124.       

92、        125.                 break;  / yes  126.               127.   128.

93、            / no  129.             heapc/2 = heapc; / move child up  130.         

94、60;   c *= 2; / move down a level  131.           132.         heapc/2 = y;  133.       134.  &

95、#160;     2、6d3-2.cppcpp view plain copy1. /装载问题 优先队列式分支限界法求解   2. #include "stdafx.h"  3. #include "MaxHeap.h"  4. #include <iostream>  5. using namespace std;  6.

96、   7. const int N = 4;  8.   9. class bbnode;  10.   11. template<class Type>  12. class HeapNode  13.   14.     template<class Type>  15.

97、     friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);  16.     template<class Type>  17.     friend Type MaxLo

98、ading(Type w,Type c,int n,int bestx);  18.     public:  19.         operator Type() constreturn uweight;  20.     private:  21.    

99、;     bbnode *ptr;        /指向活节点在子集树中相应节点的指针  22.         Type uweight;       /活节点优先级(上界)  23.       

100、;  int level;          /活节点在子集树中所处的层序号  24. ;  25.   26. class bbnode  27.   28.     template<class Type>  29.     frie

101、nd void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);  30.     template<class Type>  31.     friend Type MaxLoading(Type w,Type c

102、,int n,int bestx);  32.     friend class AdjacencyGraph;  33.   34.     private:  35.         bbnode *parent;     /指向父节点的指针 &

103、#160;36.         bool LChild;        /左儿子节点标识  37. ;  38.   39. template<class Type>  40. void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbno

104、de *E,Type wt,bool ch,int lev);  41.   42. template<class Type>  43. Type MaxLoading(Type w,Type c,int n,int bestx);  44.   45.   46. int main()  47.   48.

105、60;   float c = 70;    49.     float w = 0,20,10,26,15;/下标从1开始    50.     int xN+1;    51.     float bestw;  52. &#

106、160;   53.     cout<<"轮船载重为："<<c<<endl;    54.     cout<<"待装物品的重量分别为："<<endl;    55.     for(int i=1; i<=N; i+) 

107、   56.         57.         cout<<wi<<" "    58.         59.     cout<<endl;   

108、; 60.     bestw = MaxLoading(w,c,N,x);    61.     62.     cout<<"分支限界选择结果为:"<<endl;    63.     for(int i=1; i<=4; i+) &#

109、160;  64.         65.         cout<<xi<<" "    66.         67.     cout<<endl;   &

110、#160;68.     cout<<"最优装载重量为："<<bestw<<endl;  69.     70.     return 0;   71.   72.   73. /将活节点加入到表示活节点优先队列的最大堆H中  74. template<class Type>  75. void AddLiveNode(MaxHeap<HeapNode<Type&