最小重量算法设计

1、最小重量机器设计问题 一、实验目的 1、了解回溯法和分支限界法的基本思想。 2、运用回溯法和分支限界法解决最小重量机器设计问题。 二、实验要求 最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应 商处购得。设Wj是从供应商j处购得的部件i的重量，q是相应的价格。试设计一个算法， 给出总价格不超过 c的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。 三、算法思想和实现 1、回溯法 (1 )此问题是一棵排列树，设开始时bestx=-1,-1,-1则相应的排列树由x0:n-1的所有 排列构成。 (2) 找最小重量机器设计的回溯算法 Backtrack 是类 m

2、achine 的公有成员。 私有数据成员整 型数组Savex保存搜索过的路径，到达叶节点后将数据赋值给数组bestxo成员bestw记录 当前最小重量， cc 表示当前花费， cw 表示当前的重量。 (3) 在递归函数 Backtrack 中，在保证总花费不超过 c 的情况下： 当i=n时，当前扩展结点是排列树的叶节点。此时搜索到一个解，判断此时的最小重量是否 小于当前最小重量，若小于则更新bestw，并得到搜索路径 bestxo 当in时，当前扩展结点位于排列树的第i-1层。当x0:i的花费小于给定最小花费时，算 法进入排列树的第i层，否则将减去相应的子树。算法用变量cc记录当前路径x0:i

3、的费用。 #include using namespace std; #define N 3 #define M 3 int wNM=1,2,3,3,2,1,2,2,2; int cNM=1,2,3,3,2,1,2,2,2; class machine public:void InitMachine(int C); void Backtrack(int i); void printsave(); private: int COST;/ 题目中的 C int cw;/ 当前的重量 int cc;/ 当前花费 int bestw;/ 当前最小重量 int bestxN;/ 最优解 int save

4、xN;/savexi 如果为 j ，表示第 i 个零件应该选用第 j 个人供应的 ； void machine:InitMachine(int C) COST=C; cw=cc; bestw=-1;/ 初值为 -1，标记最小重量是否变化 for(int j=0;j=N)/ 达到叶子节点 if(cwbestw|bestw=-1)/ 当前能找到的最小重量 以前最小重量，保留当前的最小重 量 bestw=cw; cout * endl; cout 搜索路径的 bestw:bestwendl 供应商搜索路径： for(int k=0;kN;k+)/ 把当前搜过的路径记下来 coutbestxk; sa

5、vexk=bestxk; coutendl; return； for(int j=0;jM;j+)/ 依次递归尝试这三个供应商 if(cc+cij0) cc+=cij; cw+=wij; bestxi=j; Backtrack(i+1); bestxi=-1; cc-cij; cw-=wij; void machine:printsave() if(bestw=-1) cout 输入的总价格太小！ endl; cout else endl; cout 最优重量( bestw )是： bestwendl; for(int k=0;kN;k+) cout 第 k+1 个部件由第 savek+1 供

6、应商供应 endl; coutendl; int main() mach Mach; int C; coutC;/ 输入最小花费 Mach.InitMachine(C); Mach.Backtrack(0); Mach.printsave(); return 0; 2、分支限界法 解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时， 将排列树的根节点置为当前扩展结点。 在初始扩展结点处还设有选定部件是哪个供应商提供 的，故cv=0 , cw=0 , position=0 , peer=0, 1窃。x1:n记录供应商的选择 while完成对排 列树内部结点的有序扩展。

7、 循环体内依次从活结点优先队列中取出具有最小重量的结点，依 次为当前扩展结点。并且花费不超过 c 并加以扩展，队列为空时则结束循环。当 peer=n 时， 此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer 1) temp=queuesi; queuesi=queuesi/2; queuesi/2=temp; i = i/2; /last 是当前堆的元素个数，执行该函数后 struct nodetype * deletemin(int last,struct nodetype *a) / 返回堆的第一个元素(即最小元素) struct nodetype *temp; temp=

8、a1; a1=alast; last -; int i = 1; int j=0; while(i r r)|(2*i = last) j = 2*i; elsej=2*i+1; if(ai-r aj-r) struct nodetype *temp; temp=ai; ai=aj; aj=temp; i = j; else return(temp); return(temp); void main() / 小根堆 / ifstream fin(input.txt); ofstream fout(output.txt); int n,m,c; finn;finm;finc; double *w

9、=new double*n+1; double *cc=new double*n+1; for(int i=1;i=n;i+) wi=new doublem+1; cci=new doublem+1; for(i=1;i=n;i+) for(int j=1;jccij; for(i=1;i=n;i+) for(int j=1;jwij; double *cmin=new doublen+1; double *wmin=new doublen+1; for(i=1;i=n;i+) cmini=cci1; wmini=wi1; for(int j=2;jccij) cmini=ccij; if(w

10、miniwij) wmini=wij; double *rc=new doublen+1;/ 剩余部件最小价格和 double *rw=new doublen+1;/ 剩余部件最小重量和 rcn=0;rwn=0; for(i=n-1;i=1;i-) rci=rci+1+cmini+1; rwi=rwi+1+wmini+1; struct nodetype *node=new struct nodetype; node-peer=0; node-cv=0; node-cw=0; node-position=0; node-r=rw1+wmin1; insert(node,0); int cpee

11、r=0; int q_len=1; bool isend=false; while(!isend q_len-; if(node-peer=n) isend=true; foutcw=1;k-) xk=node-position; node=node-parent; for(k=1;k=n;k+) foutxk ; foutendl; return; for(int j=1;jcv+ccnode-peer+1j+rcnode-peer+1peer+1; struct nodetype *node_add=new struct nodetype ; node_add-peer=cpeer; node_add-cv=node-cv+cccpeerj; node_add-cw=node-cw+wcpeerj; node_add-r=node_add-cw+rwcpeer; node_add-position=j; node_add-parent=node; insert(node_add,q_len); q_len+; if(q_len=0