2022年最小重量算法设计文 .pdf
最小重量机器设计问题一、实验目的1、了解回溯法和分支限界法的基本思想。2、运用回溯法和分支限界法解决最小重量机器设计问题。二、实验要求最小重量机器设计问题：设某一机器由n 个部件组成，每一种部件可以从m 个不同的供应商处购得。设wij是从供应商j 处购得的部件i 的重量， cij是相应的价格。试设计一个算法，给出总价格不超过c 的最小重量机器设计。分别用回溯法和分支限界法实现问题的算法。三、算法思想和实现1、回溯法（1）此问题是一棵排列树，设开始时 bestx=-1,-1, ,-1则相应的排列树由x0:n-1 的所有排列构成。（2）找最小重量机器设计的回溯算法Backtrack 是类 machine 的公有成员。 私有数据成员整型数组 Savex 保存搜索过的路径，到达叶节点后将数据赋值给数组bestx。成员 bestw 记录当前最小重量，cc 表示当前花费，cw 表示当前的重量。（3）在递归函数Backtrack 中，在保证总花费不超过c 的情况下：当 i=n 时，当前扩展结点是排列树的叶节点。此时搜索到一个解，判断此时的最小重量是否小于当前最小重量，若小于则更新bestw，并得到搜索路径bestx。当 in 时，当前扩展结点位于排列树的第i-1 层。当 x0:i 的花费小于给定最小花费时，算法进入排列树的第i 层，否则将减去相应的子树。算法用变量cc 记录当前路径x0:i 的费用。#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: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - void InitMachine(int C); void Backtrack(int i); void printsave(); private: int COST;/ 题目中的C int cw;/ 当前的重量int cc;/ 当前花费int bestw;/ 当前最小重量int bestxN;/ 最优解int savexN;/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; savexk=bestxk; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - 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; else cout*endl; cout最优重量（ bestw ）是： bestwendl; for(int k=0;kN;k+) cout第k+1 个部件由第 savek+1 供应商供应 endl; coutendl; int main() mach Mach; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - int C; coutC;/ 输入最小花费Mach.InitMachine(C); Mach.Backtrack(0); Mach.printsave(); return 0; 2、分支限界法解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故 cv=0，cw=0，position=0 ，peer=0， 1 i n。x1:n 记录供应商的选择while 完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c 并加以扩展，队列为空时则结束循环。当peer=n 时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若 peer 1)&(queuesi-r r) struct nodetype *temp; temp=queuesi; queuesi=queuesi/2; queuesi/2=temp; i = i/2; /last 是当前堆的元素个数，执行该函数后struct nodetype * deletemin(int last,struct nodetype *a) /返回堆的第一个元素（即最小元素）struct nodetype *temp; temp=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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - else return(temp); return(temp); void main() /小根堆 / ifstream fin(input.txt); ofstream fout(output.txt); int n,m,c; finn;finm;finc; double *w=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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - if(wminiwij) 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 cpeer=0; int q_len=1; bool isend=false; while(!isend&q_len0) node=deletemin(q_len,queues); q_len-; if(node-peer=n) isend=true; foutcw=1;k-) xk=node-position; node=node-parent; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - 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) foutNo Solution!endl; return; 四、结果input.txt 3 3 4 1 2 3 3 2 1 2 2 2 1 2 3 3 2 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - 2 2 2 output.txt 4 1 3 1 五、总结分支限界法与回溯法对当前扩展结点所采用的扩展方式不同。在分支限界法中， 每一个结点只有一次机会成为扩展结点。而在回溯法中，每一个活结点有多次机会成为扩展结点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -
