精华内容
下载资源
问答
  • 优先队列式分支限界法解01背包

    千次阅读 2019-05-18 19:17:42
    对于优先队列式分支限界法解01背包,实际上是广搜遍历生成树的过程。因为01背包。背包只有选和不选。所以该生成树是一个二叉树。假设规定左叉标1(代表选择该物品装入背包),右叉标0(代表不选择该物品装入背包)...

    概念

      分支限界采用的是广搜。

      优先队列采用的是队列里最优的出队。(这里采用最大堆来实现活结点优先队列,最大堆以活结点的界值作为优先级)

    说明:

        对于优先队列式分支限界法解01背包,实际上是广搜遍历生成树的过程。因为01背包。背包只有选和不选。所以该生成树是一个二叉树。假设规定左叉标1(代表选择该物品装入背包),右叉标0(代表不选择该物品装入背包)。给定示例输入:

    背包容量c=10

    物品个数n=5

    物品重量w={2,2,6,5,4}

    物品价格p={6,3,5,4,6}

    步骤:

        左子树的解的上界与父节点相同,不用计算。右子树的解的界值:较好的就算方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直到装不下时,再装入该物品的一部分来装满背包。由此得到的价值是右子树中解的上界(尽管这不是一个可行解,但可以证明其价值是最优值的上界)。

    1.排好序的情况:

    物品重量w={2,2,4,6,5}

    物品价格p={6,3,6,5,4}

    2.一层一层的将活结点加入到活结点优先队列中:

    说明:

        0.程序先是将1,2结点加入到队列中,由于1的界大于2的 界,所以选择1结点继续扩展(继续向下搜索)---进入到3,4结点的选择。由于父节点2没有出队。所以相继的5,6结点就被沉默掉了,故第二层只考虑3,4结点,3选择了2号物品后没有超重,4的界也大于当前背包的价格6+3=9.所以3,4都被加入到活结点,又由于3的界大于4的界,所以选择3作为扩展结点,继续向下进行扩展。。。。。。直到叶子结点。。。。程序结束

        1.该生成树中:只要左儿子结点没超重就把他加入到活结点优先队列中来。只要右儿子结点的界值大于当前背包的价值,就将右儿子结点也加入到活结点优先队列中来。当进入到下一层的搜索时,会从上一层的活结点队列中选择最优的那个结点(界值最大的)作为父节点(扩展结点)进行扩展,向下搜索。而上一层没有机会出队的活结点将暂时被沉默掉,等待出队的机会

       2.下面再附上MaxKanpsack()函数的运行数据变化图。方便更快速的理解代码。

          注解:下图中:i=4,  a'''=add(14>10),add其实是addlivenode()函数,这里的14表示当前结点下(选择1,2,3,4号物品后背包重量为14=2+2+4+6,明显大于了背包的重量10,所以a'''=add()也应该划叉,即该结点被终结了,因为超重了。下文的i=5,a'''=add(13>10)分析同上。)

         各个节点界的计算:1结点:(6+3+6)+(10-2-2-4)*(5/6)=16.6666            

                                         2结点:(3+6)+(10-2-4)*(5/6)=12.3333         ...........................

                                         8结点:  (6+3)+(10-2-2)*(5/6)=14.00000

                                         16结点: (6+3+6)+(10-2-2-4)*(4/5)=16.60000

                                         34结点: (6+3+6)+(10-2-2-4)* 0=15

                                         左儿子结点的界不用算,直接继承父节点的界(左儿子的界=父节点的界)3结点的界=1结点的界=7结点的界=16.66

                        

    过程说明:i=1时:第一层广搜:1和2结点作比较。由于1和2的界(16.6,12.3)都大于当前背包的价值6,故都加入活结点的优先队列中。又1的 界大于2的界,选择1作扩展结点(父节点)进入下一层。............

                    i=3时,背包价格:15=6+3+6;而8号的界为14<15(8号界小于当前背包重量,不加入活结点优先队列中),15号结点对应的背包重量是2+2+4+6=14>10(背包重量),超重了。

    代码如下:

    #include<stdio.h>
    #include <iostream>
    using namespace std;
    typedef int Typew;
    //typedef int Typep;
    //物品类
    class Object{
    	friend float Knapsack(Typew *, float *, Typew, int, int *);
        public:
    	int operator <= (Object a) const{
          return (d >= a.d);
    }
    
    private:
    	int ID; //物品编号
    	float d; //单位重量价值
    };
    //树结点类
    class bbnode{
    	friend class Knap;
    	friend float Knapsack(Typew *, float *, Typew, int, int *);
    private:
    	bbnode *parent; //指向父节点的指针
    	int LChild; //如果是左儿子结点取1,也即说明该物品已装进背包
    };
    //堆结点类
    class HeapNode{
    	friend class Knap;
    	friend class MaxHeap;
    public:
    	operator float()const{return uprofit;};
    private:
    	float uprofit, //结点的价值上界
    		  profit; //结点所相应的价值
    	Typew weight; //结点所相应的重量
    	int level; //活结点在子集树中所处的层序号
    	bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针
    };
    //最大堆类
    class MaxHeap{
    public:
    	MaxHeap(int maxElem)
    	{
    		HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留
    		capacity = maxElem;
    		size = 0;
    	}
    	void InsertMax(HeapNode *newNode);
    	HeapNode DeleteMax(HeapNode* &N);
    private:
    	int capacity;
        int size;
        HeapNode **HeapElem;
    };
    //0-1背包问题的主类
    class Knap{
    	//Knapsack主函数功能:解决初始化、求解最优值和最优解、回收内存
    	friend float Knapsack(Typew *, float *, Typew, int, int *);
    public:
    	float MaxKnapsack();
    private:
    	MaxHeap *H;
    	//Bound辅助Maxknapsack函数:计算结点价值上界
    	float Bound(int i);
    	//AddLiveNode辅助Maxknapsack函数:将活结点插入子集树和优先队列中
    	void AddLiveNode(float up, float cp, Typew cw, int ch, int level);
    	bbnode *E; //指向扩展结点的指针
    	Typew c; //背包容量
    	int n; //物品总数
    	Typew *w; //物品重量数组(以单位重量价值降序)
    	float *p; //物品价值数组(以单位重量价值降序)
    	Typew cw; //当前装包重量
    	float cp; //当前装包价值
    	int *bestx; //最优解
    };
    //这是博客上大牛自己写的,原教材上没有
    void MaxHeap::InsertMax(HeapNode *newNode)
    {
    	//极端情况下暂未考虑,比如堆容量已满等等
    	int i = 1;
    		for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit; i /= 2)
    		{
    			HeapElem[i] = HeapElem[i/2];
    		}
    		HeapElem[i] = newNode;
    }
    //这是博客上大牛自己写的,原教材上没有
    HeapNode MaxHeap::DeleteMax(HeapNode *&N)
    
    {
    	//极端情况下暂未考虑
    		if(size >0 )
    		{
    			N = HeapElem[1];
    			//从堆顶开始调整
    			int i = 1;
    			while(i < size)
    			{
    	if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit > HeapElem[i*2 +1]->uprofit)
    				{
    		HeapElem[i] = HeapElem[i*2];
                	i = i*2;
    				}
                	else
    				{
    					if(i*2 <= size)
    					{
                            	HeapElem[i] = HeapElem[i*2];
    							i = i*2;
    					}
    					else
    						break;
    				}
    			}
    			if(i < size)
    				HeapElem[i] = HeapElem[size];
    		}
    		size--;
    		return *N;
    }
    float Knap::MaxKnapsack()
    {
    	H = new MaxHeap(1000);
    	bestx = new int [n+1];
    	//初始化,为处理子集树中的第一层做准备,物品i处于子集树中的第i层
    	int i = 1; //生成子集树中的第一层的结点
    	E = 0; //将首个扩展点设置为null,也就是物品1的父节点
    	cw = 0;
    	cp = 0;
    	float bestp = 0; //当前最优值
        float up = Bound(1); // 选取物品1之后的价值上界
    	//当选择左儿子结点时,上界约束up不用关心,重量约束wt需要考虑。因为上界约束跟父节点相同。
    	//当选择右儿子结点时,上界约束up需要考虑,重量约束不需要考虑。因为父节点和该结点重量相同。
    	while (i != n+1)
    	{
    		//检查当前扩展结点的左儿子结点
    		int wi=w[i];
    		int pi=p[i];
    		int cp1=cp;
    		int cw1=cw;
    		int test=cw1+cp1;
    		Typew wt = cw + w[i]; //当前选择物品i之后的总重量wt
    		if(wt <= c) //背包能将物品i装下,也即当前扩展结点的左儿子结点可行
    		{
    			if(cp + p[i] > bestp)
    				bestp = cp +pi;
    				//bestp = cp + p[i]
    			AddLiveNode(up, cp + p[i], cw + w[i], 1, i);
    		}
            //检查当前扩展结点的右儿子结点
    		up = Bound(i + 1); //未选择物品i之后的价值上界
    		if(up >= bestp)
    			AddLiveNode(up, cp, cw, 0, i);
    		//从优先队列中选择价值上界最大的结点成为扩展结点
    		HeapNode* N;
    		H->DeleteMax(N);
    		E = N->elemPtr;
    		cw = N->weight;
    		cp = N->profit;
    		up = N->uprofit;
    		i = N->level + 1; //准备生成N.level+1层的子集树结点
    	}
    	//从子集树中的某叶子结点开始构造当前最优解
        for (int i = n; i > 0; i--)
    	{
    	bestx[i] = E->LChild;
    	E = E->parent;
    	}
    	return cp;
    }
    
    float Knap::Bound(int i)
    {
    	Typew cleft = c - cw;
    	float b = cp;
    	while (i<=n && w[i] <= cleft)
    	{
    	cleft -= w[i];
    	b += p[i];
    	i++;
    	}
    	if(i<=n) b += p[i]/w[i] * cleft;
        return b;
    }
    void Knap::AddLiveNode(float up, float cp, Typew cw, int ch, int level)
    {
    	bbnode *b=new bbnode;
        b->parent=E;
        b->LChild=ch;
    	HeapNode *N = new HeapNode;
        N->uprofit=up;
        N->profit=cp;
        N->weight=cw;
        N->level=level;
    	N->elemPtr=b;
    	H->InsertMax(N);
      }
       //Knapsack返回最大价值,最优值保存在bestx
       float Knapsack(Typew *w, float *p, Typew c, int n, int *bestx)
       {//数组w、p和bestx中下标为0的元素保留不用
    	//初始化
    	Typew W = 0;
    	float P = 0;
    	Object *Q = new Object[n];
    	for(int i =1; i<=n; i++)
    	{
    	Q[i-1].ID = i;
    	Q[i-1].d = 1.0*p[i]/w[i];
    	P += p[i];
    		W += w[i];
    	}
    	//所有物品的总重量小于等于背包容量c
    	if (W <= c)
    	{
    		for(int i =1; i<=n; i++)
    	{
    				bestx[i] = p[i];
    		}
    	return P;
    	}
    	//所有物品的总重量大于背包容量c,存在最佳装包方案
        //sort(Q,n);对物品以单位重量价值降序排序
    	//1.对物品以单位重量价值降序排序
    	//采用简单冒泡排序
    	for(int i = 1; i<n; i++)
    		for(int j = 1; j<= n-i; j++)
    		{
    			if(Q[j-1].d < Q[j].d)
    			{
    				Object temp = Q[j-1];
    				Q[j-1] = Q[j];
    				Q[j] = temp;
    			}
    		}
        //Knapsack主函数功能:解决初始化、求解最优值和最优解、回收内存
    	Knap K;
    	K.p = new float [n+1];
    	K.w = new Typew [n+1];
    	for(int i = 1; i<=n; i++)
    	{
    		K.p[i] = p[Q[i-1].ID];//(以单位重量价值降序排序)
    		K.w[i] = w[Q[i-1].ID];//(以单位重量价值降序排序)
    	}
    	K.cp = 0;
    	K.cw = 0;
    	K.c = c;
    	K.n = n;
    	//2.MaxKnapsack()负责分支限界的搜索,并找出最优值------这是一个填二叉树的过程
    	float bestp = K.MaxKnapsack();
    	for(int i = 1; i<=n; i++)
    	{
    		bestx[Q[i-1].ID] = K.bestx[i];
    	}
    	delete [] Q;
    	delete [] K.w;
    	delete [] K.p;
    	delete [] K.bestx;
    	delete [] K.H;
    	return bestp;
    }
    int main(int argc, char* argv[])
    {
    	const int N = 5;
            Typew c=10; //背包容量
    	int bestx[N+1]; //最优解
    	int bestp; //最优值
    	//需要说明的是,这里的数组p[]和w[]的第一个元素是-1,这是因为我在操作过程中
    	//都是从数组元素的1开始的,而我们知道数组中第一个元素是0号元素,所以我这里用-1填上
    	Typew w[]={0,2,2,6,5,4};//物品重量
    	float p[]={0,6,3,5,4,6};//物品价值
    //排好序之后的:
    //p【6,3,6,5,4】
    //w【2,2,4,6,5】
    	bestp = Knapsack(w, p, c, N, bestx);
    	cout<<"物品总数N = "<< N<<",背包容量C = "<< c<<endl;
    	for (int i = 1; i <= N; i++)
    	{
    		if(i ==1 ) cout<<"重量数组:";
    		cout<<w[i];
    		if(i != N) cout<<",";
    		else
    			cout<<endl;
    	}
    	for (int i = 1; i <= N; i++)
    	{
    		if(i ==1 ) cout<<"价值数组:";
    		cout<<p[i];
    		if(i != N) cout<<",";
    		else
    			cout<<endl;
    	}
    	for (int i = 1; i <= N; i++)
    	{
    		if(i ==1 ) cout<<"是否选取:";
    		cout<<bestx[i];
    		if(i != N) cout<<",";
    		else
    			cout<<endl;
    
    	}
    	cout<<"背包最优价值:"<<bestp<<endl;
    	system("pause");
    	return 0;
    }
    
     
    

    上述代码对于w={3,4,5}    p={4,5,6}  c=6  执行的结果有误

    再附上修正后的:

    #ifndef BEIBAO_H
    #define  BEIBAO_H
    #include <math.h>
    #include <iostream>
    using namespace std;
    //子空间中节点类型
    class BBnode{
    public:
    	BBnode*  parent;   //父节点
    	bool leftChild;   //左儿子节点标志
    	BBnode(BBnode* par,bool ch){
    		parent=par;
    		leftChild=ch;
    	}
    	BBnode(){
    
    	}
    };
    
    class HeapNode {
    public:
    	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;
    	}
    	 HeapNode(){
    
    	 }
    	 int compareTo(HeapNode o) {
    		double xup =o.upperProfit;
    		if(upperProfit < xup)
    			return -1;
    		if(upperProfit == xup)
    			return 0;
    		else
    			return 1;
    	}
    };
    
    class Element  {
    public:
    	int id;
    	double d;
    	Element(){
    
    	}
    	Element(int idd,double dd){
    		id=idd;
    		d=dd;
    	}
    	int compareTo(Element x){
    		double xd=x.d;
    		if(d<xd)return -1;
    		if(d==xd)return 0;
    		return 1;
    	}
    	 bool equals(Element x){
    		return d==x.d;
    	}
    };
    
    class MaxHeap{
    public:
    	 HeapNode *nodes;
    	 int nextPlace;
    	 int maxNumber;
    	 MaxHeap(int n){
    		maxNumber = pow((double)2,(double)n);
    		nextPlace = 1;//下一个存放位置
    		nodes = new HeapNode[maxNumber];
    	}
    	 MaxHeap(){
    	 }
        void put(HeapNode node){
    		nodes[nextPlace] = node;
    		nextPlace++;
    		heapSort(nodes);
    	}
    	HeapNode removeMax(){
    		HeapNode tempNode = nodes[1];
    		nextPlace--;
    		nodes[1] = nodes[nextPlace];
    		heapSort(nodes);
    		return tempNode;
    	}
    	 void heapAdjust(HeapNode *  nodes,int s,int m){
    		HeapNode rc = nodes[s];
    		for(int j=2*s;j<=m;j*=2){
    			if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)
    				++j;
    			if(!(rc.upperProfit<nodes[j].upperProfit))
    				break;
    			nodes[s] = nodes[j];
    			s = j;
    		}
    		nodes[s] = rc;
    	}
        void heapSort(HeapNode * nodes){
    		for(int i=(nextPlace-1)/2;i>0;--i){
    			heapAdjust(nodes,i,nextPlace-1);
    		}
    	}
    } ;
    
    #endif
    
    //子空间中节点类型
    
    double c=10;
    const int n=5;
    double *w;
    double *p;
    double cw;
    double cp;
    int    *bestX;
    MaxHeap * heap;
    
    
    //上界函数bound计算结点所相应价值的上界
     double bound(int i){
    	double cleft=c-cw;
    	double b=cp;
    	while(i<=n&&w[i]<=cleft){
    		cleft=cleft-w[i];
    		b=b+p[i];
    		i++;
    	}
    	//装填剩余容量装满背包
    	if(i<=n)
    		b=b+p[i]/w[i]*cleft;
    	return b;
    }
    //addLiveNode将一个新的活结点插入到子集树和优先队列中
     void addLiveNode(double up,double pp,double ww,int lev,BBnode* par,bool ch){
    	//将一个新的活结点插入到子集树和最大堆中
    	BBnode *b=new BBnode(par,ch);
    	HeapNode  node =HeapNode(b,up,pp,ww,lev);
    	heap->put(node);
    }
     double MaxKnapsack(){
    	//优先队列式分支限界法,返回最大价值,bestx返回最优解
    	BBnode * enode=new BBnode();
    	int i=1;
    	double bestp=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->removeMax();
    		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;
    }
    
    
     double knapsack(double *pp,double *ww,double cc,int *xx){
    	//返回最大值,bestX返回最优解
    	c=cc;
    	//n=sizeof(pp)/sizeof(double);
    	//定义以单位重量价值排序的物品数组
    	Element *q=new Element[n];
    	double ws=0.0;
    	double ps=0.0;
    	for(int i=0;i<n;i++){
    		q[i]=Element(i+1,pp[i+1]/ww[i+1]);
    		ps=ps+pp[i+1];
    		ws=ws+ww[i+1];
    	}
    	if(ws<=c){
    		return  ps;
    	}
    	p=new double[n+1];
    	w=new double[n+1];
    	for(int i=0;i<n;i++){
    		p[i+1]=pp[q[i].id];
    		w[i+1]=ww[q[i].id];
    	}
    	cw=0.0;
    	cp=0.0;
    	bestX = new int[n+1];
    	heap = new MaxHeap(n);
    	double bestp = MaxKnapsack();
    	for(int j=0;j<n;j++)
    		xx[q[j].id]=bestX[j+1];
    
    	return  bestp;
    
    }
    
    int main(){
    
    	//w=new double[4];
    	double w[6]={0,2,2,6,5,4};
    	 double p[6]={0,6,3,5,4,6};
    	int *x = new int[4];
    	double m = knapsack(p,w,c,x);
    
    
    	cout<<"*****分支限界法*****"<<endl;
    	cout<<"*****物品个数:n="<<n<<endl;
    	cout<<"*****背包容量:c="<<c<<endl;
    	cout<<"*****物品重量数组:w= {"<<w[3]<<" "<<w[1]<<" "<<w[2]<<"}"<<endl;
    	cout<<"*****物品价值数组:v= {"<<p[3]<<" "<<p[1]<<" "<<p[2]<<"}"<<endl;
    	cout<<"*****最优值:="<<m<<endl;
    	cout<<"*****选中的物品是:";
    	for(int i=1;i<=3;i++)
    		cout<<x[i]<<" ";
    	cout<<endl;
    	return 0;
    }
    

    图片:

    展开全文
  • ; margin-right:0">主要问题:随机生成顶点数为n的图,随机指定顶点出发,利用优先队列式分支限界法完成旅行商问题求解。 ; margin-right:0">怎么实现随即指定顶点出发</p>
  • 采用优先队列式分枝限界法求解0/1背包问题,算法设计第五章,描述的很清晰,里面有完整代码,由于害怕你弄混,所以完整运行的代码参考我的博客文章即可
  • 解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。 活结点m在优先队列中的优先级定义为:活结点m对应的子树费用下界lcost。 lcost=cc+rcost,其中,cc为当前结点费用,rcost为当前顶点最小出边费用...

    问题描述:

     某售货员要到若干城市去推销商品,已知各城市之间的路程,他要选定一条从驻地出发,经过每个城市一遍,最后回到住地的路线,使总的路程最短。
              
    结果为: 1 3 2 4 1


    问题分析

    • 解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表
    • 活结点m在优先队列中的优先级定义为:活结点m对应的子树费用下界lcost
    • lcost=cc+rcost,其中,cc为当前结点费用,rcost为当前顶点最小出边费用加上剩余所有顶点的最小出边费用和
    • 优先队列中优先级最大的活结点成为下一个扩展结点。
    • 排列树中叶结点所相应的载重量与其优先级(下界值)相同,即:叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值
    • 与子集树的讨论相似,实现对排列树搜索的优先队列式分支限界法也可以有两种不同的实现方式:(旅行售货员问题采用第一种实现方式。)
    1. 用优先队列来存储活结点。优先队列中每个活结点都存储从根到该活结点的相应路径
    2. 用优先队列来存储活结点,并同时存储当前已构造出的部分排列树。优先队列中的活结点不必存储从根到该活结点的相应路径,该路径必要时从存储的部分排列树中获得

    在这里插入图片描述在这里插入图片描述
    令Minout[i]代表顶点i的最小出边费用。图中:

       Minout[1]=4                 Minout[2]=5
       Minout[3]=5                 Minout[4]=4


    如,在扩展顶点D处:

    rcost=Minout[3]+Minout[2]+Minout[4]=14
      其中:Minout[3]:当前顶点最小出边
         Minout[2],Minout[4]:剩余所有顶点最小出边



    算法描述

    • 要找最小费用旅行售货员回路,选用最小堆表示活结点优先队列。
    • 算法开始时创建一个最小堆,用于表示活结点优先队列。
    • 堆中每个结点的优先级是子树费用的下界lcost值
    • 计算每个顶点i的最小出边费用并用minout[i]记录
    • 如果所给的有向图某个顶点没有出边,则该图不可能有回路,算法结束。


    基于优先队列式分支限界的旅行售货员问题求解算法,采用限界函数lcost ,作为优先级,不断调整搜索方向,选择最有可能取得最优解的子树优先搜索;同时,根据限界函数lcost进行剪枝,剪掉不包含最优解的分支

    • 算法的while循环完成对排列树内部结点的扩展。对于当前扩展结点,算法分两种情况进行处理。
    1. 令s表示结点在排列树中的层次(节点B为第0层)。考虑排列树层次s=n-2的情形,此时当前扩展结点是排列树中某个叶结点的父结点
       (1).检测图G是否存在一条从顶点x[n-2]到顶点x[n-1]的边和一条从顶点x[n-1]到顶点1的边。
       (2). 如果这两条边都存在,则找到一条旅行员售货回路。
       (3).此时,算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。
       (4). 如果是,则必须更新当前最优值bestc和当前最优解bestx
    if(cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1] < bestc )
    {    // 找到更优的旅行路径
    	 for (int j = 0; j <= n-1; j++) bestx[j] = x[j];
    	 bestc = cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1];    
    }
    

    在这里插入图片描述在这里插入图片描述

    1. 令x记录当前解,s表示结点在排列树中的层次(结点B为第0层)。当扩展结点所处的层次s<n-2时,算法依次产生当前扩展结点的所有儿子结点
       (1). 由于当前扩展结点所相应的路径是x[0: s],该扩展结点可行儿子结点是从剩余顶点x[s+1: n-1]中选取的顶点x[i],且(x[s],x[i])是所给有向图G中的一条边。
       (2).对于当前扩展结点的每一个可行儿子结点,计算出其前缀(x[0:s],x[i])的费用cc和相应的下界lcost。
       (3).当lcost<bestc时,将这个可行儿子结点插入到活结点优先队列中,否则,将剪去以该儿子结点为根的子树。
      在这里插入图片描述在这里插入图片描述
    • while循环的终止条件:排列树的一个叶结点成为当前扩展结点, 算法结束
    • 当s=n-1时,已找到的回路是x[0: n-1],它已包含图G的所有n个顶点。
    • 因此,当s=n-1时,相应的扩展结点表示一个叶结点。该叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值。因为一旦一个叶结点成为当前扩展结点,剩余活结点的下界值(lcost值),都大于等于当前叶子节点处已找到的回路的费用。它们都不可能导致费用更小的回路。
    • 因此,已找到叶结点所相应的回路,是一个最小费用旅行售货员回路,算法结束。
    • 算法结束时,返回找到的最小费用,相应的最优解由数组v给出



    优先队列式分支限界法求解TSP问题

     s代表当前节点在排列树中层次,从排列树的根节点到当前结点的路径为x[0:s],进一步搜索的顶点为x[s+1: n-1]

    class MinHeapNode {
    Friend Traveling <Type>;
    Public:
      	Operator Type () const { return lcost;}
    private:
    	Type lcost,  费用下界
    	Type cc, 当前费用
    	Type rcost, 顶点最小出边费用和(顶点为:x[s:n-1])
    	int s,  当前结点在排列树中的层次;
    	Int *x,  存储解(结点路径)
    }
    

    下界:lcost=cc+rcost
    Minout[i]:顶点i的最小费用出边
    初始化时:cc=0, s=0, x[0]=1, x[1: n-1]=(2,3,…, n)
    在这里插入图片描述
    初始化时:bestc为较大数值



    样例

    在这里插入图片描述



    分析演示

    在这里插入图片描述

    代码

    #include <iostream>
    #define NO_PATH -1         //没有通路
    #define MAX_WEIGHT 4000
    
    using namespace std;
    
    int N;                     //城市数目
    int City_Graph[100][100];  //保存图信息
    int x[100];                //x[i]保存第i步遍历的城市
    int isIn[100];             //保存 城市i是否已经加入路径
    int bestw;                 //最优路径总权值
    int cw;                    //当前路径总权值
    int bestx[100];            //最优路径
    //-----------------------------------------------------------------
    void Travel_Backtrack(int t){        //递归法
        int i,j;
        if(t>N){                         //走完了,输出结果
            for(i=1;i<=N;i++)            //输出当前的路径
                cout<<x[i];
            cout<<endl;
            if(cw < bestw){              //判断当前路径是否是更优解
                for (i=1;i<=N;i++){
                    bestx[i] = x[i];
                }
                bestw = cw+City_Graph[x[N]][1];
            }
            return;
        }
        else{
            for(j=1;j<=N;j++){           //找到第t步能走的城市
                if(City_Graph[x[t-1]][j] != NO_PATH && !isIn[j]){ //能到而且没有加入到路径中
                    isIn[j] = 1;
                    x[t] = j;
                    cw += City_Graph[x[t-1]][j];
                    Travel_Backtrack(t+1);
                    isIn[j] = 0;
                    x[t] = 0;
                    cw -= City_Graph[x[t-1]][j];
                }
            }
        }
    }
    int main(){
        int i;
        cout<<"请输入城市数目:";
        cin>>N;
        for(int i=1;i<=N;i++){
            cout<<"请输入第"<<i<<"座城市的路程信息(不通请输入-1):";
            for(int j=1;j<=N;j++){
                cin>>City_Graph[i][j];
            }
        }
    
        //测试递归法
        for (i=1;i<=N;i++){
            x[i] = 0;               //表示第i步还没有解
            bestx[i] = 0;           //还没有最优解
            isIn[i] = 0;            //表示第i个城市还没有加入到路径中
        }
    
        x[1] = 1;                   //第一步 走城市1
        isIn[1] = 1;                //第一个城市 加入路径
        bestw = MAX_WEIGHT;
        cw = 0;
        Travel_Backtrack(2);        //从第二步开始选择城市
        cout<<"最优值为:"<<bestw;
        cout<<"最优解为:";
        for(i=1;i<=N;i++){
            cout<<bestx[i];
        }
       cout<<endl;
    }
    



    测试样例

    数据与例子中的数据相同。

    输入:
    4
    -1 30 6 4
    30 -1 5 10
    6 5 -1 20
    4 10 20 -1

    输出
    1234
    1243
    1324
    1342
    1423
    1432
    最优值为:25最优解为:1423
    在这里插入图片描述

    展开全文
  • 优先队列式分支限界法 解装载问题

    千次阅读 2018-12-28 15:29:53
    上一篇我们学习了用队列式分支限界法求解,这一次采用优先队列式分支限界法来求解。 有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量为wi,且要求确定是否有一个合理的装载方案可将这n个集...

    继续学习装载问题

    上一篇我们学习了用队列式分支限界法求解,这一次采用优先队列式分支限界法来求解。
    有一批共n个集装箱要装上2艘载重量分别为c1,c2的轮船,其中集装箱i的重量为wi,且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
    可证明,采用如下策略可以得到一个最优装载方案:先尽可能的将第一艘船装满,其次将剩余的集装箱装到第二艘船上。

    其实质是要求第一艘船的最优装载。 其解空间树是一棵子集树。
    《算法设计与分析》-王晓东著 一书P164-165给出的代码同样是存在问题,无法运行的。主要表现是MaxHeap的定义没有给出,循环变量i的初值是1,计算扩展结点相应载重量的for循环以及构造当前最优解的for循环中终止条件都没有考虑j=0的情况;

    对代码的修订如下:

    package ch06.book;
    
    
    import java.util.PriorityQueue;
    
    public class PiorityBBLoading {
    
    	static PriorityQueue<HeapNode> heap = null;
    	static int bestWeight = 0;
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] weight = {10,40,40};
    		int capacity = 50;
    		int [] bestSolution = new int[weight.length];
    
    		bestWeight = maxLoading(weight, capacity, bestSolution);
    		System.out.printf("the best load weight is: %d \r\n", bestWeight);
    		System.out.print("the node path of best solution:");
    		for(int i=0; i<bestSolution.length; i++) {
    			System.out.printf("\t%d", bestSolution[i]);
    		}
    	}
    
    	public static int maxLoading(int []containerWeight , int capacity, int[] bestSolution) {
    		
    		// initialization 
    		heap = new PriorityQueue<HeapNode>();
    		int n = containerWeight.length -1; // n+1 represents the number of boxes, equals with the number of tree levels;
    		BBNode expandNode = null;
    				
    		int i = 0;     // represent the node level of current expand node;
    		int expandWeight = 0;   // the weight of load at the expand node;
    		
    		// declare the remain weight array
    		int [] remains = new int[n +1];
    		remains[n] = 0;
    		// backward calculate the remain weight for each node;
    		for (int j = n-1; j>=0; j--) {
    			remains[j] = remains[j+1] + containerWeight[j+1];
    		}
    		
    		// search the binary solution space tree until reach a leaf node;
    		// reach a leaf node when i = n+1;
    		while (i != n +1) {
    			// check left child node;
    			System.out.printf("checking left child, trying weight:%d + %d \r\n", expandWeight , containerWeight[i]);
    			if (expandWeight + containerWeight[i] <= capacity) {
    				// the overall weight include left child node is less than capacity, so left child is a feasible node;
    				// then put the left child node in queue;
    				
    				int nodePriority = expandWeight + containerWeight[i]+ remains[i];
    				System.out.printf("try put left child in Heap: level %d, priorty: %d \r\n", i, nodePriority);
    				addLiveNode(nodePriority, i+1, expandNode, true);
    			}
    			// right child node is always feasible;
    			System.out.printf("try put right child in Heap: level %d, priorty: %d \r\n", i, expandWeight + remains[i]);
    			
    			addLiveNode(expandWeight + remains[i], i+1, expandNode, false);
    			
    			// retrieve next expand node;	
    			HeapNode node = heap.poll();
    			i = node.level;
    			expandNode = node.liveNode;
    			expandWeight = node.upperLimitWeight - remains[i-1];
    			System.out.printf("get next expand node in Heap and process: level:%d, node weight: %d\r\n", i, expandWeight);
    		}
    		// build the best solution 
    		for(int j = n; j>=0; j--) {
    			bestSolution[j] = expandNode.isLeftChild? 1:0;
    			
    			expandNode = expandNode.parent;
    		}
    		return expandWeight;
    	}
    	
    	public static void addLiveNode(int upLimit, int level, BBNode parent, boolean isLeft) {
    		// put this live node in to MaxHeap of live node;
    		BBNode b = new BBNode(parent, isLeft);
    		HeapNode node = new HeapNode(b, upLimit, level);
    		heap.add(node);
    	}
    
    	/**
    	 * This internal class represent a solution space tree node;
    	 * @author wanyongquan
    	 *
    	 */
     static class BBNode{
    	BBNode parent;
    	boolean isLeftChild; 
    	
    	 BBNode(BBNode parent, boolean isLeft) {
    		this.parent = parent;
    		this.isLeftChild = isLeft;
    	}
    }
     
     /**
      * This internal class represent a node in MaxHeap;
      * @author wanyongquan
      *
      */
     static class HeapNode implements Comparable<HeapNode>{
    	 BBNode liveNode; 
    	 int upperLimitWeight;  // the upper limitation of live node;
    	 int level;             // the node level in solution space tree 
    	 
    	 public HeapNode(BBNode node, int upLimit, int level) {
    		 this.liveNode = node;
    		 this.upperLimitWeight = upLimit;
    		 this.level = level;
    		 
    	 }
    	 public int compareTo(HeapNode otherNode) {
    		 // notice the two params's order ;
    		 // this will works as MaxHeap;
    		 return Integer.compare( otherNode.upperLimitWeight, this.upperLimitWeight ) ;
    			
    	 }
    	 public boolean equals(HeapNode item) {
    		 return this.upperLimitWeight == ((HeapNode)item).upperLimitWeight;
    	 }
     }
     
    }
    

    main方法中测试的结果如下图所示,可以最优装载量和解空间树最优选择路径都是正确的。

    the best load weight is: 50 
    the node path of best solution:	1	1	0

     

    展开全文
  • 随机给定一个3×3的矩阵,其元素为8个不同的数码,起始状态为S0,目标状态为Sg,要求用两种或以上的方法设计优先队列式分支限界法,寻找从初始状态变换到目标状态的最优解,说明不同的优先选择策略变换到最终状态用...
  • 这里实现优先队列式分支限界法。如果你在用优先队列时用less关键字,发现生成的并不是优先队列 参考https://blog.csdn.net/m0_38015368/article/details/80461938#include &lt;bits/stdc++.h&gt; using ...

    装载问题实质: 装载问题是一个子集选取问题,因此其解空间树是一颗子集树。

    这里实现优先队列式分支限界法。

    如果你在用优先队列时用less关键字,发现生成的并不是优先队列 参考https://blog.csdn.net/m0_38015368/article/details/80461938

    #include <bits/stdc++.h>
    using namespace std;
    class MaxHeapQNode
    {
    public:
        MaxHeapQNode *parent;
        int lchild;
        int weight;
        int lev;
    };
    struct cmp
    {
        bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
        {
            return a->weight < b->weight;
        }
    };
    int n;
    int c;
    int bestw;
    int w[100];
    int bestx[100];
    void InPut()
    {
        scanf("%d %d", &n, &c);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &w[i]);
    }
    void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E,  int wt, int i, int ch)
    {
        MaxHeapQNode *p = new MaxHeapQNode;
        p->parent = E;
        p->lchild = ch;
        p->weight = wt;
        p->lev = i + 1;
        q.push(p);
    }
    void MaxLoading()
    {
        priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
        //定义剩余重量数组r
        int r[n + 1];
        r[n] = 0;
        for(int j = n - 1; j > 0; --j)
            r[j] = r[j + 1] + w[j + 1];
        int i = 1;
        MaxHeapQNode *E;
        int Ew = 0;
        while(i != n + 1)
        {
            if(Ew + w[i] <= c)
            {
                AddAliveNode(q, E, Ew + w[i] + r[i], i, 1);
            }
            AddAliveNode(q, E, Ew + r[i], i, 0);
    
            //取下一节点
            E = q.top();
            q.pop();
            i = E->lev;
            Ew = E->weight - r[i - 1];
        }
        bestw = Ew;
        for(int j = n; j > 0; --j)
        {
            bestx[j] = E->lchild;
            E = E->parent;
        }
    }
    void OutPut()
    {
        printf("最优装载量为 %d\n", bestw);
        printf("装载的物品为 \n");
        for(int i = 1; i <= n; ++i)
            if(bestx[i] == 1)
              printf("%d ", i);
    }
    int main()
    {
        InPut();
        MaxLoading();
        OutPut();
    }

    测试样例:

    输入:

    (多解,输出其中一个)

    4 60
    10
    40

    50

    20

    输出

    最优装载量为 60
    装载的物品为
    1 3

    运行截图


    展开全文
  • 优先队列式分支限界法解决旅行售货商问题 问题描述: 某售货员要到若干城市去推销商品,已知各城市之间的路程(或旅费)。 他要选定一条从驻地出发,经过每个城市一次,最后回到驻地的路线,使总的路程(或总旅费)最小。...
  • 现在采用优先队列式分支限界法来求解; 1. 优先队列中节点i的优先级由该节点的上界函数bound计算出的值upperprofit给出。该上界函数与回溯法中计算方法一致。 子集树中以i结点为跟的子树的任一节点的上界不会超过i...
  • 优先队列式分支限界法求解0-1背包问题 #include <iostream> #include <cstdlib> #include <queue> #include <vector> using namespace std; #define n 4 int w[n]= {3,5,2,1},v[n]= {9,10,7...
  • 分支限界法中的优先队列式分支限界法解装载问题
  • 优先队列式分支限界法_0-1背包问题

    千次阅读 2020-05-29 00:02:19
    需要的同学请自取哦~欢迎大家与我交流 问题: 0-1背包问题的问题提出是,有n个物品,其中物品i的重量是 ,价值是 ,有一容量为C的背包,要求选择若干物品装入背包,...设 ,使用优先队列式分支限界法求解此问题。 pack
  • 最近真的好久没有更了,会陆续更一些算法问题,有需要的朋友请...采用优先队列式分支限界算法解决该问题。 import java.util.Scanner; public class BBTSP { //排列树结点描述类 private static class HeapNode imple
  • 0-1背包问题用优先队列式分支限界法实现时, ①问题有2^n种可能解(物品放入/不放入背包); 解空间树为子集树:左子节点(当前物品放入)、右子节点(当前物品不放入) ②约束条件:背包剩余容量 lw ≥ 当前物品...
  • 上一次介绍了集装箱装载问题的队列式分支限界法,本次将分享优先队列式分支限界法解决这个问题的算法。 Problem: 装载问题的问题提出是,有一批共n个集装箱要装上2艘载重量分别为 c1和c2 的轮船,其中集装箱i的重量...
  • 试设计一个优先队列式分支限界法,给出总价格不超过d的最小重量机器设计。 [之所以想记录这个问题,是因为我觉得自己"用各个部件的最小重量作为未来最理想重量"的这个设计还挺特别。其他都是实验报告中的内容] ...
  • 问题描述:给定一个带权有向图G = (V, E), 其中每...解法:用优先队列式分支限界法,代码核心跟贪心的Dijkstra算法差不多相同,要首先学会使用优先队列的使用。贪心的Dijkstra算法实现见Dijkstra算法实现代码:#incl...
  • 代码链接: 链接:pan.baidu.com/s/1GAFnDuj7-3x6BNa0uOL9Vg 码:pbfv 算法分析与设计第 4 次实验 ... 用优先队列式分支限界法求解0-1背包问题 ... 通过上机实验,要求掌握优先队列式分支限界...
  • 本代码运用优先队列式分支限界法解决了最小重量机器设计问题。 算法思路: 对于在某一个供应商是否购买某一零件,可以将这个过程抽象化为子集树模型。该树的第i层则代表第i个零件的购买情况,每个商家j对应一棵子树...
  • c++实现的批处理作业调度问题·优先队列式分支限界法·回溯法包括了FlowShop和make类模板,有测试数据data
  • 6-18 一般解空间的优先队列式分支限界法 问题描述 试设计一个用优先队列式分支限界法搜索一般解空间的函数。该函数的参数包括结点可 行性判定函数和上界函数等必要的函数,并将此函数用于解布线问题。 印刷电路...
  • 优先队列式分支限界法解决0-1背包问题的算法思想: 1.分支限界法常以广度优先或最小耗费优先(最大效益优先)方式搜索问题的解空间树, 对于0-1背包问题的解空间树是一个颗子集树。 2.在分支限界法中有一个活结点...
  • 设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度。 给出输入数据。第1行有2个正整数n和k。第2行的n个正整数是完成n个任务需要的时间。 样例输入 7 3 2 14 4 16 6 5 3 样例输出 17 思路 (仅做参考) ...
  • } 样例测试 数据为上面那个样例 输入 4 12 8 6 2 3 输出 最优装载量为 11 装载的物品为 1 4 优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。 活结点x在优先队列中的优先级定义...
  • 相同点: 在这两种分支限界算法中每一个活结点都只有一次机会成为扩展节点,一旦活结点成为扩展节点,便一次性产生所有儿子节点,在...有限队列式:按照优先队列中的优先级进行选取子节点成为扩展节点。
  • //采用优先队列式分枝限界法求解0/1背包问题 #include <stdio.h> #include <queue> using namespace std; #define MAXN 20 //最多可能物品数 //问题表示 int n=3,W=30; int w[]={0,16,15,15}; /...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 923
精华内容 369
关键字:

优先队列式