最小重量算法设计.doc

最小重量机器设计问题一、实验目的1、了解回溯法和分支限界法的基本思想。2、运用回溯法和分支限界法解决最小重量机器设计问题。二、实验要求最小重量机器设计问题:设某一机器由n个部件组成,每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。试设计一个算法,给出总价格不超过c的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。三、算法思想和实现1、回溯法(1)此问题是一棵排列树,设开始时bestx=[-1,-1,……,-1]则相应的排列树由x[0:n-1]的所有排列构成。(2)找最小重量机器设计的回溯算法Backtrack是类machine的公有成员。私有数据成员整型数组Savex保存搜索过的路径,到达叶节点后将数据赋值给数组bestx。表示当前花费,cw表示当前的重量。(3)在递归函数Backtrack中,在保证总花费不超过c的情况下:当i=n时,当前扩展结点是排列树的叶节点。此时搜索到一个解,判断此时的最小重量是否小于当前最小重量,若小于则更新bestw,并得到搜索路径bestx。当i<n时,当前扩展结点位于排列树的第i-1层。当x[0:i]的花费小于给定最小花费时,算法进入排列树的第i层,否则将减去相应的子树。记录当前路径x[0:i]的费用。#include<iostream>usingnamespacestd;#defineN3#defineM3intw[N][M]={{1,2,3},{3,2,1},{2,2,2}};intc[N][M]={{1,2,3},{3,2,1},{2,2,2}};classmachine{public:voidInitMachine(intC);voidBacktrack(inti);voidprintsave();private:intCOST;//题目中的Cintcw;//;//当前花费intbestw;//当前最小重量intbestx[N];//最优解intsavex[N];//savex[i]如果为j,表示第i个零件应该选用第j个人供应的};voidmachine::InitMachine(intC){COST=C;;bestw=-1;//初值为-1,标记最小重量是否变化for(intj=0;j<N;j++)bestx[j]=-1;}voidmachine::Backtrack(inti){if(i>=N)//达到叶子节点{if(cw<bestw||bestw==-1)//当前能找到的最小重量<以前最小重量,保留当前的最小重量{bestw=cw;cout<<"************************************"<<endl;cout<<"搜索路径的bestw:"<<bestw<<endl<<"供应商搜索路径:";for(intk=0;k<N;k++)//把当前搜过的路径记下来{cout<<bestx[k]<<"";savex[k]=bestx[k];cout<<endl;}return;}for(intj=0;j<M;j++)//依次递归尝试这三个供应商{if((cc+c[i][j]<COST)&&(w[i][j]>0)){cc+=c[i][j];cw+=w[i][j];bestx[i]=j;Backtrack(i+1);bestx[i]=--c[i][j];cw-=w[i][j];}}voidmachine::printsave(){if(bestw==-1){cout<<"输入的总价格太小!"<<endl;}else{cout<<"************************"<<endl;cout<<"最优重量(bestw)是:"<<bestw<<endl;for(intk=0;k<N;k++)cout<<"第"<<k+1<<"个部件由第"<<save[k]+1<<"供应商供应"<<endl;cout<<endl;}}intmain(){machMach;cout<<"输入总价格不超过的C:";cin>>C;//(C);(0);();return0;}2、分支限界法解空间为一棵排列树,采用优先队列式分支限界法找出所给的最小重量机器设计,开始时,将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的,故cv=0,cw=0,position=0,peer=0,1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点,依次为当前扩展结点。并且花费不超过c并加以扩展,队列为空时则结束循环。当peer=n时,此