第3章 动态规划算法实验指导_第1页
第3章 动态规划算法实验指导_第2页
第3章 动态规划算法实验指导_第3页
第3章 动态规划算法实验指导_第4页
第3章 动态规划算法实验指导_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第3章动态规划算法实验3.1动态规划算法的实现与时间复杂度测试实验目的编程实现经典的动态规划算法,理解动态规划算法设计的基本思想、程序实现的相关技巧,加深对动态规划算法设计与分析思想的理解。通过程序的执行时间测试结果,与理论上的时间复杂度结论进行对比、分析和验证。原理解析■动态规划算法的基本思想动态规划是一种在数学和计算机科学中使用的、用于求解包含重叠子问题的最优化问题的有效方法。其基本思想是:将原问题分解为相似的子问题,在求解的过程中通过子问题的解描述并求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域,在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题,为了避免多次解决这些子问题,它们的结果都逐渐被计算并保存,从小规模的子问题直到整个问题都被解决。因此,动态规划对每一子问题只做一次计算,具有较高的效率。■测试算法0-1背包问题是使用动态规划算法求解的代表问题,算法如下:KnapsackDP({w1,w2,…,wn),(v1,v2,…,vn}, C)fori=0tondom[i,0]=0endforforj=0toCdom[0,j]=0endforfori=1tondoforj=1toCdom[i,j]=m[i-1,j]ifwijthenm[i,j]=max{m[i,j],m[i-1,j-wi]+vi}endifendforendforreturnm[n,C]算法的时间复杂度为0(^Qo实验内容编程实现以上求解0-1背包问题的动态规划算法,并通过手动设置、生成随机数获得实验数据。记录随着输入规模增加算法的执行时间,分析并以图形方式展现增长率;测试、验证、对比算法的时间复杂度。实验步骤和要求编程实现以上算法,并进行测试,保证程序正确无误。其中,分别在程序开始和结束处设置记录系统当前时间的变量、用于计算程序执行的时间(以毫秒(ms)作为程序执行时间的计数单位)。测试C值不变的情形下随着n增加、程序执行时间增加的趋势。对于C=200、400、800、2000这四种情形,分别使用实验1中的随机数生成算法生成n个随机整数作为n个物品的重量,再生成n个随机整数作为n个物品的价值(n=10,20,40,100,200,400,800,2000)。对于每个C值,记录随着n增加程序的执行时间,并使用MSExcel图表绘制工具生成各不同C值情形下程序执行时间的对比曲线图(4条折线)。与理论上的时间复杂度结论进行对比分析,完成实验报告。

实验3.2动态规划算法的适应性测试1.实验目的对于同一问题,编程实现其分治算法和动态规划算法,通过对比分析,理解动态规划算法的适用情形。通过程序的执行时间测试结果,与理论结论进行对比、分析和验证。2.原理解析■分治算法与动态规划算法的对比:针对子问题是否重叠虽然很多问题均可分解为子问题、动态规划和分治算法都是通过子问题的解决来获得原问题的解。然而,分治算法适用于子问题不重叠(即相互独立)的情形,对于子问题重叠的情形分治法具有较高的时间复杂度,动态规划是针对这类情形的有效算法。■测试算法斐波纳契数列在现代物理、准晶体结构、化学等领域都有直接的应用。斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、……,这个数列从第三项开始,每一项都等于前两项之和,即:'('(n)=〃(n-1),f(n-2)n=1,2

n>3直观地,斐波纳契数列可递归地得到,算法如下:DAC_f(n)if(n==1)or(n==2)thenreturn1elsereturnf(n-1)+f(n-2)endif通过理论分析已经得出结论:以上递归算法随着n增大有指数计算时间。对于n的多项式个数的子问题,显然指数计算时间是不现实的。基于动态规划算法可高效地求解Fibonacci数问题,算法如下:DP_f(n)Initializef[1..n]fori=1tondoif(i==1)or(i==2)thenf[i]=1elsef[i]=f[i-1]+f[i-2]endifendforreturnf[n]算法的时间复杂度为。3)。实验内容编程实现以上求斐波纳契数的分治算法和动态规划算法。对于每个算法,记录随着斐波纳契数数列大小增加基本操作的执行次数,分析并以图形方式展现增长率;对比这两个算法,随着数列大小增加算法增长率的变化趋势;测试、验证、对比理论结论。实验步骤和要求“加法”是以上两个斐波纳契数算法的基本操作。编程实现以上DAC_f和DP_f算法,并进行测试,在其中设置加法执行次数的计数器变量。分别测试不同n值(n=5,10,15,20,25,30)情形下DAC_f和DP_f算法的加法次数,记录加法次数,并使用MSExcel图表绘制工具生成各不同n值情形下以上两个算法加法次数的对比曲线图(2条折线)。与两个算法时间复杂度的理论结论进行对比分析,总结分治与动态规划算法的适用条件和特点,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论