当前位置:首页 >> IT/计算机 >>

回溯法实验(最优装载)


算法分析与设计实验报告 第 二 次附加实验
姓名 时间 实验名称 12.12 上午 回溯法实验(最优装载) 学号 地点 班级 工训楼 309

实验目的

1. 掌握回溯法求解问题的思想 2. 学会利用其原理求解相关问题

实验原理

基本思想: 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 在任何 时刻, 算法只保存从根结点到当前扩展结点的路径。 如果解空间树中从根结点 到叶结点的最长路径的长度为 h(n),则回溯法所需的计算空间通常为 O(h(n))。 而显式地存储整个解空间则需要 O(2h(n))或 O(h(n)!)内存空间。 基本解题步骤: (1) 针对所给问题,定义问题的解空间; (2) 确定易于搜索的解空间结构; (3) 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

(1)首先将第一艘轮船尽可能装满; (2)将剩余的集装箱装上第二艘轮船; 实验步骤 (3)用可行性约束函数可剪去不满足约束条件 的子树; (4)定义上界函数为 cw+r。在以 z 为根的子树中任一叶结点所相应的载重量 均不超过 cw+r。因此,当 cw+r<=bestw 时,可将 z 的右子树剪去。

关键代码

template<class Type> void Loading<Type>::Backtrack(int i) //搜索第i层结点 { if(i>n) { //到达叶结点 if(cw>bestw){ for(int j=1;j<=n;j++){ bestx[j]=x[j]; //更新最优解 bestw=cw; }}

return; } r-=w[i]; if(cw+w[i]<=c) { x[i]=1; cw+=w[i]; Backtrack(i+1); cw-=w[i]; } if(cw+r>bestw) { x[i]=0; Backtrack(i+1); } r+=w[i]; }

//根据判断条件,看是否要搜索左子树

//回溯标志 //根据上界函数,判断是否要搜索右子树

当输入的数据有解时:

测试结果

当输入的数据无解时:

实验分析

在实验中并没有生成多组数据,进行比较,也没有利用随机生成函数,因 为在这种有实际有关联的问题中, 利用随机生成函数生成的数据是十分的不合 适的, 在此我们只需要验证该程序是否正确即可。 在这个实验中其实际上是一 种特殊的 0-1 背包问题, 我们在第一艘栓船上就是利用 0-1 背包的思想, 第二 艘船只需要将剩余货物的重量和第二艘船的载重量相比较就可以了, 如果可以 装下就说明有解,否则就是无解。由于数据较小,所以时间上并不能反映出什 么东西。

实验心得 在这一章的回溯算法中, 我们用的比较多的就是; 利用子集树来进行问题 的探索,就例如上图是典型的一种子集树,在最优装载、0-1 背包都是利用了 这种满二叉树的子集树进行求解, 然后通过深度优先的策略, 利用约束函数和 上界函数, 将一些不符合条件或者不包含最优解的分支减掉, 从而提高程序的 效率,通过实现编程实现该问题,是我对于这一问题;理解的更加明白,果然 动手去实现才是一种好的学习的习惯,怪不得确实在动手的同学学的比较好 呢,以后我也要多努力啊。 实验得分 助教签名

附录: 完整代码(贪心法)

//回溯法 递归求最优装载问题 #include<iostream> #include<time.h> #include<iomanip> using namespace std; template<class Type> class Loading { public: void Backtrack(int i);

int n, *x, *bestx; Type *w, c, cw, bestw, r; };

//集装箱数 //当前解 //当前最优解 //集装箱重量数组 //第一艘轮船的载重量 //当前载重量 //当前最优载重量 //剩余集装箱重量

template<class Type> void Loading<Type>::Backtrack(int i); template<class Type> //参数为:w[]各物品重量数组,c为第一艘轮船的载重量,n为物品数量,bestx[] 数组为最优解 Type MaxLoading(Type w[],Type c,int n,int bestx[]); int main() { int n=3,m; int c=50,c2=50; int w[4]={0,10,40,40}; int bestx[4]; clock_t start,end,over; start=clock(); end=clock(); over=end-start; start=clock(); //计算程序运行时间的算法

m=MaxLoading(w,c,n,bestx);

//调用MaxLoading函数

cout<<"轮船的载重量分别是:"<<endl; cout<<"c(1)="<<c<<",c(2)="<<c2<<endl; cout<<"待装集装箱重量分别为:"<<endl; cout<<"w(i)="; for(int i=1;i<=n;i++) {cout<<w[i]<<" ";} cout<<endl; cout<<"回溯选择结果:"<<endl; cout<<"m(1)="<<m<<endl;

//输出两个船的装载量 //输出待装货物的重量

//输出第一艘船的实际装载量

cout<<"x(i)="; for(int i=1;i<=n;i++) {cout<<bestx[i]<<" ";} cout<<endl; int m2=0; for(int j=1;j<=n;j++) m2=m2+w[j]*(1-bestx[j]); cout<<"m(2)="<<m2<<endl; //输出是那种货物装到第一艘船上

//计算剩余的货物重量

if(m2>c2) {cout<<"因为m(2)大于c(2),所以原问题无解!"<<endl;} //如果剩余重量大于第二艘船的载重量,则无解 end=clock(); printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间 cout<<endl; system("pause"); return 0; } template<class Type> void Loading<Type>::Backtrack(int i) //搜索第i层结点 { if(i>n) //到达叶结点 { if(cw>bestw) { for(int j=1;j<=n;j++) { bestx[j]=x[j]; //更新最优解 bestw=cw; } } return; } r-=w[i]; if(cw+w[i]<=c) //根据判断条件,看是否要搜索左子树 { x[i]=1; cw+=w[i]; Backtrack(i+1); cw-=w[i]; //回溯标志 }

if(cw+r>bestw) { x[i]=0; Backtrack(i+1); } r+=w[i]; }

//根据上界函数,判断是否要搜索右子树

template<class Type> Type MaxLoading(Type w[],Type c,int n,int bestx[]) { Loading<Type>X; //初始化Loading类X X.x=new int[n+1]; //动态分配 X.w=w; X.c=c; X.n=n; X.bestx=bestx; X.bestw=0; X.cw=0; //初始化r X.r=0; for(int i=1;i<=n;i++) X.r+=w[i]; X.Backtrack(1); delete []X.x; return X.bestw; } //调用回溯函数 //返回最优解

//返回最优载重量


相关文章:
回溯法实验(最优装载).doc
回溯法实验(最优装载) - 算法分析与设计实验报告 第二 次附加实验 姓名 时间 实验名称 12.12 上午 回溯法实验(最优装载) 学号 地点 班级 工训楼 309 实验...
回溯法求装载问题_物联1301班_刘悦_201308080112.doc
回溯法装载问题_物联1301班_刘悦_201308080112_工学_高等教育_教育专区。算法...//当前最优载重量 float r; //剩余集装箱的重量 } ; 实验原理 实验步骤 ...
贪心算法求最优装载_物联1301班_刘悦_201308080112.doc
就在最优装载问题来说, 算 法的时间复杂度为 O(nlogn)。虽然不是多项式时间,但是我个人认为较回溯 法来说,O(nlogn)的时间已经非常好了。 通过这个实验代码的...
回溯法实验(0-1背包问题).doc
回溯法实验(0-1背包问题)_IT/计算机_专业资料。算法分析与设计实验报告 第五 ...0-1 背包问题和之前的最优 装载其实质上一样的,都是利用解空间树,通过深度...
算法实验三回溯法(2017).pdf
实验三 回溯法实验目的学习编程实现深度优先搜索状态空间树求解实际问题的方法, ...装载问题 1、如果给定的装载问题有解,则采用下面的策略可以得到一个最优装载...
最优装载问题实验报告.doc
最优装载问题实验报告 - 最优装载问题的贪心算法实现 姓名: (学号: ) 一、作业及实验目的 通过本实验使学生掌握贪心算法基本要素、步骤及其应用 二、作业及实验...
算法分析设计回溯法求解装载问题实验报告.pdf
算法分析设计回溯法求解装载问题实验报告_IT/计算机_专业资料。算法分析设计回溯法...如果比前面得到的最优解 bestw 好,则替换原最优 解。 if(i>n) { if(cw...
最优装载问题的回溯算法(JAVA).txt
最优装载问题的回溯算法(JAVA)_IT/计算机_专业资料。最优装载问题的回溯算法...公交网络最优路径求解算... 4页 免费 N皇后问题Java回溯法实现... 2页...
《算法设计与分析》实验指导书--xin.doc
(1)掌握设计贪心算法的基本思想; 贪心算法 (2)通过最优装载、单源最短路径...实验实验四 1、 实验目的 (1)掌握设计回溯法的基本思想; 回溯法 (2)...
最优装载问题的算法实现与比较研究.doc
本项目要求能对解决最优装载问题的贪婪法、分支限界法、回溯法、遗传算法、模 ...2011 年 12 月到 2012 年 1 月进行实验环境的配置和准备工作。 2012 年 2...
算法设计与分析课程标准.pdf
活动安排问题, 最优装载, 哈夫曼编码, 单源最短路径,最小生成树,多机调度。...3.实验技能要求 理解、 掌握回溯法的思想并能熟练使用分治算法解决问题,掌握分析...
算法设计与分析课程教学大纲.doc
实验课时:16 理论课时: ,实验课时: 分】 3 【课程性质、目标和要求】《算法...最优装载 2. 单源最短路径 第五章 回溯法 一、学习目的要求 1.理解回溯法...
贪心算法解决最优装载问题.doc
贪心算法解决最优装载问题 - 算法设计与分析实验报告 //author : Ke
算法装载问题.doc
算法装载问题 - 回溯法最优装载方案 java 包括流程图,源代码... 回溯法最优装载方案 java 包括流程图,源代码...算法设计与分析 算法设计与分析实验报告 - 1....
回溯算法装载问题.doc
回溯算法装载问题_计算机软件及应用_IT/计算机_专业资料。实验回溯算法(2 学...[])//迭代回溯法,返回最优载重量及其相应解, 初始化根结点 { int i=1;/...
实验五 箱子装载问题.doc
=-1)cout<<"最优装载量:"<<k<<endl; return 1; } 五、结果运行与分析: 贪心算法: 回溯法: 六、心得与体会:通过本次实验,重新复习了贪心算法和回溯法的...
箱子装载问题.doc
策略; 二、实验内容及要求 1、使用贪心算法、回溯法、分支限界法解决箱子装载...继续搜索下一节点 五、结果运行与分析 (1)贪心算法 贪心算法并没有求得最优...
分支限界法求解装载问题实验报告.pdf
分支限界法求解装载问题实验报告_IT/计算机_专业资料。算法分析与设计,分支限界法...分支限界法实验(最优装载... 暂无评价 6页 2下载券 回溯法、分支限界法...
回溯法的应用之装载问题.doc
回溯法的应用之装载问题 - 1、实验题目: 回溯法的应用 2、实验内容: (1)装载问题; 3、实验基本思路: (1)将第一艘轮船尽可能装满,等价于选取全体集装箱的...
算法设计与分析-贪心算法-最优装载.doc
算法设计与分析-贪心算法-最优装载_机械/仪表_工程科技_专业资料。计算机算法与设计 实验内容:贪心算法-最优装载 问题描述:有一批集装箱要装上一艘载重量为 c ...
更多相关标签: