欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

0-1背包问题和TSP问题的分支限界法算

程序员文章站 2022-05-23 12:02:17
分支限界算法运用练习（1）0-1背包问题；（2）TSP问题一、实验目的本次实验是针对分支限界算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。三、实验项目1．请用分支限界法对下列问题进行求解。题目：（1）0-1背包问题；（2）TSP问题；具体题目容请参照教材四、实验过程（一）题目一：0-1背包问题题目分析每个物品不可再分割，选择装入背包的物品，使得装入背包中的物品的总价值最大。算法构造在此论证算法设计中的一些必要的设计依据。放...

分支限界算法运用练习
（1）0-1背包问题；（2）TSP问题
一、实验目的

本次实验是针对分支限界算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。

三、 实验项目
1．请用分支限界法对下列问题进行求解。
题目：（1）0-1背包问题；（2）TSP问题；具体题目容请参照教材

四、 实验过程

（一）题目一：0-1背包问题

  1. 题目分析
    每个物品不可再分割，选择装入背包的物品，使得装入背包中的物品的总价值最大。

  2. 算法构造
    在此论证算法设计中的一些必要的设计依据。
    放入背包中的物品的重量应该小于背包的容量：
    if(ew+w[i]<=c)
    inQueue(ev+v[i],ew+w[i],i);

  3. 算法实现
    程序源代码（请写入必要的注释）。
    package com.cn;
    import java.util.Collections;
    import java.util.LinkedList;
    class BBnode{
    BBnode parent;//父节点
    boolean leftChild;//左儿子结点标志

    public BBnode(BBnode par,boolean left){
    parent=par;
    leftChild=left;
    }
    }

class HeapNode implements Comparable{
BBnode liveNode;//活结点
double upperProfit;//结点的价值上界
double profit;//结点所相应的价值
double weight;//结点所相应的重量
int level;//活结点在子集树种所处的层序号

//构造方法
HeapNode(BBnode node,double up,double pp,double ww,int lev){
	liveNode=node;
	upperProfit=up;
	profit=pp;
	weight=ww;
	level=lev;
}

@Override
public int compareTo(Object x) {//降序排列
	double xs=((HeapNode) x).upperProfit;
	if(upperProfit>xs) return -1;
	if(upperProfit==xs) return 0;
	return 1;
}

}
class Element implements Comparable{
int id;//背包编号
double d;//单位重量价值

public Element(int id,double d){
	this.id=id;
	this.d=d;
}

@Override
public int compareTo(Object o) {//降序排列
	double xs=((Element) o).d;
	if(d>xs) return -1;
	if(d==xs) return 0;
	return 1;
}
public boolean equals(Object o){
	return d==((Element) o).d;
}

}

public class BBKnapsack {
public double c;//背包容量
public int n;//物品总数
public double[] w;//物品重量数组
public double[] p;//物品价值数组
public double cw;//当前重量
public double cp;//当前价值
public int[] bestx;//最优解
public LinkedList heap;//活结点优先队列

//上界函数bound计算结点所相应价值的上界
public double bound(int i){
	double cleft=c-cw;//剩余容量
	double b=cp;
	//以物品单位重量价值递减顺序装填剩余容量
	while(i<=n&&w[i]<=cleft){
		cleft-=w[i];
		b+=p[i];
		i++;
	}
	if(i<=n)
		b+=p[i]*cleft/w[i];
	return b;
}

public void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch){
	BBnode b=new BBnode(par,ch);
	HeapNode node=new HeapNode(b,up,pp,ww,lev);
	heap.add(node);
	Collections.sort(heap);
}
/**
 * 优先队列式分支限界法，返回最大价值，bestx返回最优解
 * @return
 */
public double bbKnapsack(){
	//初始化
	BBnode enode=null;
	int i=1;
	double bestp=0.0;//当前最优解
	double up=bound(1);//价值上界
	
	//搜索子集空间树
	while(i!=n+1){
		//非叶节点
		//检查当前扩展结点的左儿子结点
		double wt=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);
		}
		
		HeapNode node=heap.poll();
		enode=node.liveNode;
		cw=node.weight;
		cp=node.profit;
		up=node.upperProfit;
		i=node.level;
	}
	
	//构造当前最优解
	for(int j=n;j>0;j--){
		bestx[j]=(enode.leftChild)?1:0;
		enode=enode.parent;
	}
	return cp;
}
public double knapsack(double[] pp,double[] ww,double cc,int[] xx){
	c=cc;
	n=pp.length-1;
	double ps=0;//统计所有背包的价值总量
	double ws=0;//统计所有的背包重量之和
	Element[] q=new Element[n];
	for(int i=1;i<=n;i++){
		q[i-1]=new Element(i,pp[i]/ww[i]);
		ps+=pp[i];
		ws+=ww[i];
	}
	if(ws<=c){//所有物品之和<=最大容量C,即可全部物品装包
		for(int i=1;i<=n;i++){
			xx[i]=1;
		}
		return ps;
	}
	
	//依物品单位重量价值排序
	java.util.Arrays.sort(q);
	
	//初始化数据成员
	p=new double[n+1];
	w=new double[n+1];
	
	for(int i=1;i<=n;i++){
		p[i]=pp[q[i-1].id];
		w[i]=ww[q[i-1].id];
	}
	
	cw=0;
	cp=0;
	bestx=new int[n+1];
	
	heap=new LinkedList<HeapNode>(); 
	
	//调用bbKnapsack求问题的最优解
	double maxp=bbKnapsack();
	for(int i=1;i<=n;i++){
		xx[q[i-1].id]=bestx[i];
	}
	return maxp;
}

public static void main(String[] args) {
	double pp[]={0,2,1,4,3};
	double ww[]={0,1,4,2,3};
	double cc=8;
	int n=pp.length-1;
	int[] xx=new int[n+1];
	BBKnapsack b=new BBKnapsack();
	double maxp=b.knapsack(pp, ww, cc, xx);
	System.out.println("装入背包中物品总价值最大为："+maxp);		
	System.out.println("装入的物品的序号为：");
	for(int i=1;i<=n;i++){
		System.out.println(i+":"+xx[i]);
	}
}

}
4. 运行结果

  1. 经验归纳
    此问题是以广度优先的方式进行搜索，采用一个限界函数，计算限界函数值，选择一个最有利的子结点作为扩展结点，使搜索朝着解空间树上有最优解的分枝推进，以便尽快地找出一个最优解。
    （二）题目二：TSP问题
  2. 题目分析
    一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，要求路径的总和最小。
  3. 算法构造
    在此论证算法设计中的一些必要的设计依据。
    判断所走路径花费最少的最优解：
    if (temp_cc + temp_rcost < Best_Cost) {
    for (j = 0; j < City_Size; j++) {
    temp_x[j] = Best_Cost_Path[j];
    }
  4. 算法实现
    程序源代码（请写入必要的注释）。
    package com.cn;

import java.util.Collections;
import java.util.LinkedList;

public class Tsp {
float[][] a;//图G的邻接矩阵
public Tsp(float[][] a){

	this.a=a;
}

public static class HeapNode implements Comparable{

	float lcost;//子树费用的下界
	float cc;//当前费用
	float rcost;//x[s:n-1]中顶点最小出边费用和
	int s;//根节点到当前节点的路径为x[0:s]
	int[] x;//需要进一步搜索的顶点是x[s+1:n-1]
	
	//构造方法
	public HeapNode(float lc,float ccc,float rc,int ss,int[] xx){
		lcost=lc;
		cc=ccc;
		s=ss;
		x=xx;
	}
	public int compareTo(Object x){
		float xlc=((HeapNode) x).lcost;
		if(lcost<xlc) return -1;
		if(lcost==xlc) return 0;
		return 1;
	}
}

public float bbTsp(int[] v){

	
	int n=v.length-1;//节点数
	LinkedList<HeapNode> heap=new LinkedList<HeapNode>();
	//minOut[i]=i的最小出边费用
	float[] minOut=new float[n+1];
	float minSum=0;//最小出边费用和
	for(int i=1;i<=n;i++){//针对每个节点，找到最小出边
		//计算minOut[i]和minSum
		float min=Float.MAX_VALUE;
		for(int j=1;j<=n;j++){
			if(a[i][j]<Float.MAX_VALUE&&a[i][j]<min)
				min=a[i][j];
		}
		if(min==Float.MAX_VALUE)
			return Float.MAX_VALUE;
		minOut[i]=min;
		minSum+=min;
	}
	
	//初始化
	int[] x=new int[n];
	for(int i=0;i<n;i++)
		x[i]=i+1;
	HeapNode enode=new HeapNode(0,0,minSum,0,x);
	float bestc=Float.MAX_VALUE;
	
	//搜索排列空间树
	while(enode!=null&&enode.s<n-1){
		//非叶节点
		x=enode.x;
		if(enode.s==n-2){
			//当前扩展结点是叶节点的父节点
			//再加两条边构成回路
			//所构成回路是否优于当前最优解
			if(a[x[n-2]][x[n-1]]!=-1&&a[x[n-1]][1]!=-1&&enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1]<bestc){
				//找到费用更小的回路
				bestc=enode.cc+a[x[n-2]][x[n-1]]+a[x[n-1]][1];
				enode.cc=bestc;
				enode.lcost=bestc;
				enode.s++;
				heap.add(enode);
				Collections.sort(heap);
			}
		}else{//内部结点
			//产生当前扩展结点的儿子结点
			for(int i=enode.s+1;i<n;i++){
				if(a[x[enode.s]][x[i]]!=-1){
					//可行儿子结点
					float cc=enode.cc+a[x[enode.s]][x[i]];
					float rcost=enode.rcost=minOut[x[enode.s]];
					float b=cc+rcost;//下界
					if(b<bestc){
						//子树可能含有最优解，结点插入最小堆
						int[] xx=new int[n];
						for(int j=0;j<n;j++)
							xx[j]=x[j];
						xx[enode.s+1]=x[i];
						xx[i]=x[enode.s+1];
						HeapNode node=new HeapNode(b,cc,rcost,enode.s+1,xx);
						heap.add(node);
						Collections.sort(heap);
					}
				}
			}
			
		}
		
		//取下一个扩展结点
		enode=heap.poll();
	}
	//将最优解复制到v[1...n]
	for(int i=0;i<n;i++)
		v[i+1]=x[i];
	return bestc;
}
public static void main(String[] args) {
	int n=5;
	float[][] a={{0,0,0,0,0,0},{0,-1,5,-1,7,9},{0,5,-1,10,3,6},{0,-1,10,-1,8,-1},{0,7,3,8,-1,4},{0,9,6,-1,4,-1}};//a下标从1开始，0用来凑数；-1表示不同，1表示连通
	Tsp b=new Tsp(a);
	int []v=new int[n+1];
	System.out.println("最短回路长为："+b.bbTsp(v));
	System.out.print("最短回路为：");
	for(int i=1;i<=n;i++){
		System.out.print(v[i]+" ");
	}

}
}

  1. 运行结果

  2. 经验归纳
    此问题需要建立小根堆比较困难，把访问的节点先存放到小根堆中，利用广度优先搜索依次访问其它节点，把花费较少的保留下来，花费大的节点从小根堆中删除。
    五、实验总结
    0-1背包问题和TSP问题都用到了分支限界法，都要用到广度优先搜索访问节点。0-1背包问题中的物品要么放入要么不放，根据广度优先搜索的方法先访问节点存放起来，接着访问后面的节点，找到使得所放物品价值最大为止；TSP问题是建立小根堆，判断加入一个节点是否使得花费最少，以广度优先搜索的方式以此类推直至访问完所有节点为止

本文地址：https://blog.csdn.net/qq_45152962/article/details/109647254

相关标签： 算法 java

上一篇： 机器人走入日本人日常生活 能搞定所有家务

下一篇： 宋真宗赵恒早年经历了哪些事件？史书对他有着怎样的记载？

推荐阅读