动态规划及贪心选择实验.doc_第1页
动态规划及贪心选择实验.doc_第2页
动态规划及贪心选择实验.doc_第3页
动态规划及贪心选择实验.doc_第4页
全文预览已结束

下载本文档

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

文档简介

实 验 报 告实验内容： 姓 名： 魏成林 学 号： 201101020126 班 级： 计算机科学与技术 完成日期： 2013-11-7 实验要求一、实验目的1. 了解动态规划和贪心选择算法2. 区分两个算法二、实验内容1. 实现矩阵连乘、0-1背包问题、最优搜索树三个问题的动态规划算法。2实现活动安排的贪心算法。3. 对动态规划和贪心算法进行比较。实验报告一 、实验问题回答1. 概述动态规划算法思想。答：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。保存已解决的子问题的答案，在需要的时候再找出来避免重复计算，从而得到算法。2. 满足什么条件的问题可以用动态规划算法求解。答：具有最优子结构和子问题重叠性质。3. 写出动态规划算法求解的步骤。答：(1)找出最优解的性质，并刻画其结构特征；(2)递归的定义最优值；(3)以自底向上的方式计算出最优值；(4)根据计算最优值时得到的信息，构造最优解。4. 什么是最优子结构，如何证明一个问题有最优子结构性质。答：问题的最优解包含着其子问题的最优解；利用反证法来证明一个问题有最优子结构性质，假设一个问题不具有最优子结构性质，然后逐步的证明该问题存在最优子结构性质，与假设的产生矛盾，假设不成立，所以该问题就有最优子结构。5. 写出贪心算法思想。答：贪心算法并不从整体最优考虑，而是作出在某种局部意义上的最优选择。6. 贪心算法的基本要素是什么？答：具有最优子结构性质和贪心选择性质。7. 0-1背包问题可否用贪心算法求解？不可以是为什么？如果可以请用贪心算法实现，并与动态规划算法实现的0-1背包问题求解结果对比，是否正确。答：0-1背包问题不能用贪心算法求解。因为在某种情况下，不能保证背包被装满，也就是说背包有剩余的空间没有利用起来，导致无法达到最大价值。8. 分治策略和动态规划的异同。答：分治策略得到的子问题往往是独立的，而动态规划得到的子问题不是独立的。分治法得到的子问题太多导致耗费时间，而且存在许多的重复计算。动态规划则可以避免重复计算。9. 动态规划和贪心选择的异同。答：共同点是两种算法都需要问题具有最优子结构。不同的是有些问题可以用贪心算法求解，而有些问题不能用贪心算法求解。二、实验总结与收获用几句简短的话对
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论