脚本宝典收集整理的这篇文章主要介绍了算法第五章上机实践报告,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量,cij是相应的价格。 试设计一个算法,给出总价格不超过d的最小重量机器设计。
第一行有3 个正整数n ,m和d, 0<n<30, 0<m<30, 接下来的2n 行,每行n个数。前n行是c,后n行是w。
输出计算出的最小重量,以及每个部件的供应商
3 3 4 1 2 3 3 2 1 2 2 2 1 2 3 3 2 1 2 2 2
在这里给出相应的输出。例如:
4 1 3 1
每个零件有m个供应商可以选择,这样有m^n种可选方案,其中就有问题想要的最优解。然后把解空间组织成一棵m叉树,然后以深度优先搜索的方式纵深向下搜索,当不满足约束函数(即约束条件d)或者是限界函数(即搜索过的可行方案中最小的质量总和)时回溯,寻求尝试另一种方案,然后继续纵深向下搜索。当向下搜索到叶子节点时,不再向下搜索,转去更新最优值。
解空间是穷举所有可能解的空间,{(1,3,1),(1,3,2),(1,3,3)}
解空间树是一棵m叉树,从根节点出发后,每一层分别表示一个部件的不同供应商,往下延伸共n层。
每个结点有两个状态值,分别是当前的总价格、当前的总重量。
#include<iostream> using namespace std; int n,m,d;//n个组件 m个供应商 总价格不超过d int c[999][999],w[999][999];//c[i][j],w[i][j] 各表示从供应商j处购得部件i的价格/重量 int cw=0,cp=0;//记录当前最小的重量和价值 int bestw=999,bestp=999;//最小重量 int x[999],bestx[999];//保存当前重量下每个部件供应商的号码 void backtrack(int i) { if(i>n) { if(cp<=d&&cw<bestw) { //条件更优时,更新数据 bestw=cw; bestp=cp; for(int j=1; j<=n; j++) { bestx[j]=x[j]; } } } else { for(int j=1; j<=m; j++) { x[i]=j;//记录下当前部件是哪一个供应商 cw=cw+w[i][j]; cp=cp+c[i][j]; if(cp<=d&&cw<bestw) {//剪枝,如果当前供应商的部件可以满足条件 直接进入下一个部件的判断 backtrack(i+1); } //回溯过程 cw=cw-w[i][j]; cp=cp-c[i][j]; } } } int main() { cin>>n>>m>>d; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>c[i][j]; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { cin>>w[i][j]; } } backtrack(1); cout<<bestw<<endl; for(int i=1; i<=n; i++) { cout<<bestx[i]<<" "; } return 0; }
1.回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。
2.回溯法的基本步骤: (1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
3.常用剪枝函数: (1)用约束函数在扩展结点处剪去不满足约束的子树; (2) 用限界函数剪去得不到最优解的子树。
4.通解模板如下:
void backtrack (int t) //回溯法对解空间作深度优先搜索,因此,在一般情况下用递归方法实现回溯法 { if (t>n) output(x); //算法已搜索到一个叶结点,输出该结果 else for (int i=f(n,t);i<=g(n,t);i++) //f(n,t),g(n,t)分别表示扩展结点的子树的起始编号和终止编号。尝试这些选择 { x[t]=h(i); //H(i)表示第i个可选值 if (constraint(t)&&bound(t)) //分别表示约束函数和限界函数 backtrack(t+1); } }
5. 在用回溯法求解问题时,常常遇到两种典型的解空间树: ①子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树成为子集树。例:0-1背包问题。
遍历子集树函数:
void Backtrack(int t) {//以深度优先的方式遍历第t层中的某棵子树 if(t>n) { Output(x); return; } if (……) { x[t]=1; Backtrack(t+1); } if (……) { x[t]=0; Backtrack(t+1); } }
②排列树:当所给问题是确定n个元素的满足某种性质的排列时,相应的解空间树称为排列树。例:旅行售货员问题。
遍历排列树函数:
void Swap(int *p,int *q) { int temp; temp=*p;*p=*q;*q=temp; } void Backtrack(int t) { //遍历第t层结点为根的某棵子树 int i; if(t>n) { Output(x); return; } for(i=t;i<=n;i++) //x[1]~x[t-1]确定,获得x[t]~x[n]的不同组合 if(……) { Swap(&x[t],&x[i]); Backtrack(t+1); Swap(&x[t],&x[i]); } }
以上是脚本宝典为你收集整理的算法第五章上机实践报告全部内容,希望文章能够帮你解决算法第五章上机实践报告所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。