算法分析与设计分枝限界算法Word文档格式.docx
《算法分析与设计分枝限界算法Word文档格式.docx》由会员分享，可在线阅读，更多相关《算法分析与设计分枝限界算法Word文档格式.docx（14页珍藏版）》请在冰点文库上搜索。
但两者求解方法有两点不同：
第一，回溯法只通过约束条件剪去非可行解，而分枝—限界法不仅通过约束条件，而且通过目标函数的限界来减少无效搜索，也就是剪掉了某些不包含最优解的可行解；
第二，在解空间树上，回溯法以深度优先搜索，而分枝—限界法则以广度优先或最小耗费优先的方式搜索。
分枝—限界的搜索策略是，在扩展节点处，首先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。
为了有效地选择下一扩展结点，以加速搜索进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值从当前活结点表中选择一个最有利的结点做为扩展，使搜索朝着解空间树上最优解的分支推进，以便尽快找出一个最优解。
分枝—限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树（问题的解空间树是表示问题皆空间的一颗有序树，常见的有子集树和排序树）。
在搜索问题的解空间树时，分枝—限界法的每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，那些导致不可行解或非最优解的儿子结点将被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表取出下一结点成为当前扩展结点，并重复上述扩展过程，直到找到最优解或活结点表为空时停止。
实现0-1背包问题的分枝—限界算法
算法实现：
packagecn.lgh;
importjava.io.BufferedReader;
importjava.io.InputStreamReader;
importjava.util.Arrays;
publicclassBBKnapsack{
doublec;
//背包重量
intn;
//物品总数
double[]w;
//物品重量数组
double[]p;
//物品价值数组
doublecw;
//当前重量
doublecp;
//当前价值
int[]bestx;
//最优解
MaxHeapmaxHeap=newMaxHeap（）;
//活节点优先队列
//计算节点所对应的节点的上界
privatedoublebound（inti）{
doublecleft=c-cw;
doubleb=cp;
//以物品单位重量价值递减装填剩余容量
while（i<
=n&
&
w[i]<
=cleft）{
cleft-=w[i];
b+=p[i];
i++;
}
//装填剩余容量装满背包
if（i<
=n）{
b+=p[i]/w[i]*cleft;
returnb;
}
//添加新的活节点到子集树和优先队列中
privatevoidaddLiveNode（doubleupperProfit,doublepp,doubleww,
intlevel,BBnodeparent,booleanleftChild）{
BBnodeb=newBBnode（parent,leftChild）;
HeapNodenode=newHeapNode（b,upperProfit,pp,ww,level）;
maxHeap.put（node）;
//优先队列式分支界限法
privatedoublebbKnapsack（）{
BBnodeenode=null;
inti=1;
doublebestp=0.0;
doubleup=bound
（1）;
while（i!
=n+1）{
doublewt=cw+w[i];
//检查当前扩展节点的左儿子节点
if（wt<
=c）{
if（cp+p[i]>
bestp）{
bestp=cp+p[i];
}
addLiveNode（up,cp+p[i],cw+w[i],i+1,enode,true）;
}
up=bound（i+1）;
//检查当前扩展节点的右儿子节点
if（up>
=bestp）{
addLiveNode（up,cp,cw,i+1,enode,false）;
HeapNodenode=maxHeap.removeMax（）;
enode=node.liveNode;
cw=node.weight;
cp=node.profit;
up=node.upperProfit;
i=node.level;
//构造当前最优解
for（intj=n;
j>
0;
j--）{
bestx[j]=（enode.leftChild）?
1:
enode=enode.parent;
returncp;
/**
*将个物体依其单位重量价值从大到小排列，然后调用bbKnapsack完成对子集树优先队列式分支界
*限搜索。
*
*@return最优解
*/
publicdoubleknapsack（double[]pp,double[]ww,doublecc,int[]xx）{
c=cc;
n=pp.length;
Element[]q=newElement[n];
doublews=0.0;
doubleps=0.0;
for（inti=0;
i<
n;
i++）{
q[i]=newElement（i+1,pp[i]/ww[i]）;
ps+=pp[i];
ws+=ww[i];
if（ws<
for（inti=1;
=n;
xx[i]=1;
returnps;
//依单位重量价值排序
Arrays.sort（q,newElemComparator（））;
p=newdouble[n+1];
w=newdouble[n+1];
for（inti=1;
p[i]=pp[q[i-1].id-1];
w[i]=ww[q[i-1].id-1];
cw=0.0;
cp=0.0;
bestx=newint[n+1];
maxHeap=newMaxHeap（）;
//调用bbKnapsack求问题的最优解
doublemaxp=bbKnapsack（）;
xx[q[i-1].id-1]=bestx[i];
returnmaxp;
publicstaticvoidmain（Stringarg[]）{
Stringinput;
Stringflag;
doublecapacity=0;
double[]pp;
double[]ww;
int[]xx;
doublebestP=0.0;
BBKnapsackbbKnapsack=newBBKnapsack（）;
BufferedReaderin=newBufferedReader（newInputStreamReader（System.in））;
do{
try{
do{
System.out.println（"
请选择数字功能键：
1--输入数据，2--退出系统"
）;
flag=in.readLine（）.trim（）;
}while（!
（flag.equals（"
1"
）||flag.equals（"
2"
）））;
if（flag.equals（"
））{
break;
请输入各物品重量，数据之间必须以顿号间隔分开！
"
input=in.readLine（）.trim（）;
input=in.readLine（）.replaceAll（"
"
"
}while（input.equals（"
））;
if（input.equals（"
））{
Stringdatas[]=input.split（"
[、]"
intn1=datas.length;
pp=newdouble[n1];
ww=newdouble[n1];
for（inti=0;
n1;
ww[i]=Double.parseDouble（datas[i]）;
请输入各物品价值，数据之间必须以顿号间隔分开！
datas=input.split（"
intn2=datas.length;
if（n1!
=n2）{
输入数据个数不一致，重新输入"
continue;
pp[i]=Double.parseDouble（datas[i]）;
请输入背包的容量：
xx=newint[n1];
capacity=Double.parseDouble（input）;
bestP=bbKnapsack.knapsack（pp,ww,capacity,xx）;
System.out.println（"
分支界限法法解得最优价值：
+bestP）;
各个被装入物品情况（1表示被装入，0表示未被装入）：
System.out.print（xx[i]+"
\n"
}catch（Exceptione）{
e.printStackTrace（）;
}while（true）;
}
/**
*分支界限节点
*/
publicclassBBnode{
BBnodeparent;
//父节点
booleanleftChild;
//左孩子标识
publicBBnode（BBnodeparent,booleanleftChild）{
this.parent=parent;
this.leftChild=leftChild;
importjava.util.Comparator;
*Element对象比较器
publicclassElemComparatorimplementsComparator<
Object>
{
publicintcompare（Objectobject1,Objectobject2）{
Elementelement1=（Element）object1;
Elementelement2=（Element）object2;
if（element1.d<
element2.d）{
return1;
}else{
return0;
*物品编号和单位重量价值载体。
publicclassElement{
intid;
//物品编号
doubled;
//单位重量价值
publicElement（intid,doubled）{
this.id=id;
this.d=d;
*堆节点比较器。
publicclassHeapComparatorimplementsComparator<
HeapNodeheapNode1=（HeapNode）object1;
HeapNodeheapNode2=（HeapNode）object2;
if（heapNode1.upperProfit<
heapNode2.upperProfit）{
*堆节点
publicclassHeapNode{
BBnodeliveNode;
//活节点
doubleupperProfit;
//节点价值上限
doubleprofit;
//节点所对应的价值
doubleweight;
//节点所对应的重量
intlevel;
//活节点在子集树中所处的层次序号
//构造方法
publicHeapNode（BBnodeliveNode,doubleupperProfit,doubleprofit,
doubleweight,intlevel）{
this.liveNode=liveNode;
this.upperProfit=upperProfit;
this.profit=profit;
this.weight=weight;
this.level=level;
importjava.util.List;
*装载和管理HeapNode对象。
publicclassMaxHeap{
//堆节点容器
privateList<
HeapNode>
heap=newArrayList<
（）;
publicvoidput（HeapNodeheapNode）{
heap.add（heapNode）;
publicHeapNoderemoveMax（）{
Collections.sort（heap,newHeapComparator（））;
HeapNodemaxNode=null;
if（!
heap.isEmpty（））{
maxNode=heap.get（0）;
heap.remove（maxNode）;
returnmaxNode;
三、测试数据和执行结果（在给定数据下，执行操作、算法和程序的结果，可使用数据、图表、截图等给出）
四、实验结果分析及总结（对实验的结果是否达到预期进行分析，总结实验的收获和存在的问题等）
在做本次实验之前，自己对分支限界法的原理不是非常的理解，所以就花了半天时间看了课本上的相关内容。
同时结合曾做过的利用分支限界法解0-1背包问题的几道作业题进行分析，加深自己对分支限界法解0-1背包问题的理解。
至于课本所提供的相关代码，自己很容易看懂。
不过那是C++代码，有些封装好的方法在Java里好像没能找到对应的方法，所以只能自己编写同功能的对应方法。
同时课本所提供的代码也是不能直接翻译过来用，当你懂得算法的基本原理后，你会发现数组下标会出错，课本所提供的代码数组下标一般都是从1开始，而我们输入的数据数组下标默认都是从0开始，所以在参考课本所提供的代码的同时，必须结合算法的实际情况对代码中的相关变量进行修改，这样才能充分利用课本所提供的代码完成本次实验。
通过本次试验，自己基本上掌握分支限界法解0-1背包问题的原理，达到实验的目的。
教
师
评
阅
实验内容和设计（A-E）：
操作过程、算法或代码（A-E）：
实验结果（A-E）：
实验分析和总结（A-E）：
实验成绩（A-E）：
反馈评语：
升级会员 