算法设计与分析课件 21 分治算法_第1页
算法设计与分析课件 21 分治算法_第2页
算法设计与分析课件 21 分治算法_第3页
算法设计与分析课件 21 分治算法_第4页
算法设计与分析课件 21 分治算法_第5页
已阅读5页，还剩1页未读， 继续免费阅读

下载本文档

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

文档简介

算法设计与分析本节要点CONTENTS分治算法分治算法“凡治众如治寡，分数是也。”

—《孙子兵法》“分数”的“分”是指分各层次的部分，“数”是每部分的人数编制，意为通过把部队分为各级组织，将帅就只需通过管理少数几个人来实现管理全军众多组织。这样，管理和指挥人数众多的大军，也如同管理和指挥人数少的部队一样容易。分治算法在算法设计中，引入分而治之的策略，称为分治算法，其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之。在现实生活中，什么样的问题才能使用分治法解决呢？分治算法使用分治算法需要满足以下3个条件：（1）原问题可分解为若干个规模较小的相同子问题。（2）子问题相互独立。（3）子问题的解可以合并为原问题的解。分治算法分治法解题步骤：（1）分解：将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。（2）治理：求解各个子问题。各个子问题与原问题形式相同，只是规模较小。当子问题足够小时，就可以用较简单的方法解决。（3）合并：按原问题的要求，将子问题的解合并为原问题的解。分治算法分治法就是将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破，分而治之。在分治算法中，各个子问题形式相同，解决的方法也一样，

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论