《分支限界法求解装载问题实验报告》由会员分享，可在线阅读，更多相关《分支限界法求解装载问题实验报告（8页珍藏版）》请在金锄头文库上搜索。
1、分支限界法求解装载问题 一、一、方法一般原理方法一般原理 分支限界法常以广度优先或以最小耗费 （最大效益） 优先的方式搜索问题的解空间树。 在分支限界法中， 每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点， 就一次性产生其所有儿子结点。 在这些儿子结点中， 导致不可行解或导致非最优解的儿子结 点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一 直持续到找到所需的解或活结点表为空时为止。 两种分支限界法 （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先
2、队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 二、二、描述问题描述问题 有一批共 n 个集装箱要装上 2 艘载重量分别为 c1和 c2的轮船，其中集装箱 i 的重量为 wi ，且 21 1 ccw n i i ，要求确定是否有一个合理的装载方案可将这 n 个集装箱装上这 2 艘轮船。如果有，请给出该方案。 三、三、由原理得到的由原理得到的算法、算法的复杂度算法、算法的复杂度、改进、改进 1、 可得算法 算法 enquence 将活结点加入队列。若 i=n，则表示当前为叶节点，此时只要检查对应 的可行解是否为最优解。ibestw) bestw = wt; /
3、加入活结点队列 if(ibestw friend Type MaxLoading_three(Type *,Type,int,int *); private: QNode* parent;/ 指向父结点的指针 bool LChild; /左儿子标志 Type weight; /结点所相应的载重量 ; 四、四、算法实现算法实现 void EnQueue(int wt,int bestxn = ch; return; Add(wt, E, ch); / 不是叶子 int MaxLoading(int w, int c, int n) / 返回最优装载值 / 为层次 1 初始化 int err; /
4、返回值 int i = 1; / 当前扩展结点的层 int Ew = 0; / 当前扩展结点的权值 int r = 0 ; /剩余集装箱重量 Queue *E=0 ; /当前扩展结点 /*bestE 当前最优扩展结点 for(int j =2; jnext = NULL; Q-weight = -1; err = Add(-1, NULL, 0); /标记本层的尾部 if(err) return 0; while (true) int wt = Ew + wi; / 检查左孩子结点 if (wt bestw) bestw = wt; EnQueue(Ew + wi, bestw,i,n,E,b
5、estE,1); / 右孩子总是可行的 EnQueue(Ew, bestw, i, n, E, bestE, 0); Delete(E); / 取下一个扩展结点 if (E!=NULL if(iweight; /构造当前最优解 for(j = n -1; j0; j-) bestxj = bestE-LChild; bestE = bestE -parent; return 0; 五、五、总结总结 由此，我们可以总结出分支限界法的设计思路： 设求解最大化问题，解向量为 X=(x1,xn)，xi 的取值范围为 Si，|Si|=ri。在使用 分支限界搜索问题的解空间树时，先根据限界函数估算目标函数
6、的界down, up，然 后从根结点出发，扩展根结点的 r1 个孩子结点，从而构成分量 x1 的 r1 种可能的取 值方式。 对这 r1 个孩子结点分别估算可能的目标函数 bound(x1)，其含义：以该结点为根的子 树所有可能的取值不大于 bound(x1)，即： bound(x1)bound(x1,x2) bound(x1,xn) 若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该 孩子结点保存在待处理结点表 PT 中。 再取 PT 表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点 时的可行解 X=(x1,xn)，及目标函数值 bound(x1,
7、xn)。 分支限界法与回溯法的不同： （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分 支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找 出在某种意义下的最优解。 （2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以 广度优先或以最小耗费优先的方式搜索解空间树。 六、附录（源码）六、附录（源码） #include using namespace std; class Queue public: Queue* parent; / 指向父结点的指针 bool LChild; / 左儿子标志 int weight; / 结点所
8、相应的载重量 Queue* next; ; int *bestx; int bestw=0; / 目前的最优值 Queue* Q; / 活结点队列 Queue* bestE; /当前最优扩展结点 Queue* lq = NULL; Queue* fq = NULL; int Add(int w, Queue* E, bool l) Queue* q; q = new Queue; q-next = NULL; q-weight = w; q-parent = E; q-LChild = l; if(Q-next = NULL) Q-next = q; fq = lq = Q-next; /一定
9、要使元素放到链中 else lq-next = q; lq = q; return 0; int IsEmpty() if(Q-next=NULL) return 1; return 0; int Delete(Queue* tmp = fq; E = fq; Q-next = fq-next; /*一定不能丢了链表头*/ fq = fq-next; return 0; void EnQueue(int wt,int bestxn = ch; return; Add(wt, E, ch); / 不是叶子 int MaxLoading(int w, int c, int n) / 返回最优装载值
10、 / 为层次 1 初始化 int err; /返回值 int i = 1; / 当前扩展结点的层 int Ew = 0; / 当前扩展结点的权值 int r = 0 ; /剩余集装箱重量 Queue *E=0 ; /当前扩展结点 /*bestE 当前最优扩展结点 for(int j =2; jnext = NULL; Q-weight = -1; err = Add(-1, NULL, 0); /标记本层的尾部 if(err) return 0; while (true) int wt = Ew + wi; / 检查左孩子结点 if (wt bestw) bestw = wt; EnQueue
11、(Ew + wi, bestw,i,n,E,bestE,1); / 右孩子总是可行的 EnQueue(Ew, bestw, i, n, E, bestE, 0); Delete(E); / 取下一个扩展结点 if (E!=NULL if(iweight; /构造当前最优解 for(j = n -1; j0; j-) bestxj = bestE-LChild; bestE = bestE -parent; return 0; void main() int n =0; int c = 0; int i = 0; int* w; coutn; coutc; w = new intn+1; bestx = new intn+1; coutwi; MaxLoading(w, c, n); cout“最优载重量为:“bestwendl; cout“最优装载方案为(1 表示装入,0 表示不装入):“; for(i=1; i=n; i+) coutbestxi“ “;
