1 / 67
文档名称:

启发式规则分治法递归汉诺塔排序算法.ppt

格式:ppt   大小:287KB   页数:67页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

启发式规则分治法递归汉诺塔排序算法.ppt

上传人:fanglangjizv 2021/7/12 文件大小:287 KB

下载得到文件列表

启发式规则分治法递归汉诺塔排序算法.ppt

相关文档

文档介绍

文档介绍:第4章 分治法
概 述
递 归
排序问题中的分治法
组合问题中的分治法
几何问题中的分治法
1
概 述
分治法的设计思想
分治法的求解过程
2
将一个难以直接解决的大问题,划分成一些规模较小的子问题,以便各个击破,分而治之。更一般地说,将要求解的原问题划分成k个较小规模的子问题,对这k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足够小,很容易求出其解为止,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。
分治法的设计思想
3
2. 独立子问题:各子问题之间相互独立,这涉及到分治法的效率,如果各子问题不是独立的,则分治法需要重复地解公共的子问题。
1. 平衡子问题:最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题(通常k=2),这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。
启发式规则:
4
子问题1
的规模是n/2
子问题1的解
子问题2的解
子问题2
的规模是n/2
原问题的解
原问题
的规模是n
分治法的典型情况
5
分治法的求解过程
一般来说,分治法的求解过程由以下三个阶段组成:
(1)划分:既然是分治,当然需要把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。
(2)求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题,有时递归处理也可以用循环来实现。
(3)合并:把各个子问题的解合并起来,合并的代价因情况不同有很大差异,分治算法的有效性很大程度上依赖于合并的实现。
6
例:计算an,应用分治技术得到如下计算方法:
34
32
32
81
31
31
9
31
31
9
3
3
3
3
分解问题
求解每个子问题
合并子问题的解
不是所有的分治法都比简单的蛮力法更有效。
分析时
间性能
ë
û
é
ù
î
í
ì
>
´
=
=
1
1
2
2
n
a
a
n
a
a
n
n
n
如果
如果
7
通用分治递推式
问题规模为n的实例被划分为 b个规模为n/b的实例,其中a个实例需要求解,假设n是b的幂
T(n)=aT(n/b)+f(n)
8
主定理
如果在递推式中f(n)∈(nd),其中d≥0
当a<bd时
当a=bd时
当a>bd时
9
递 归
递归的定义
递归函数的运行轨迹
递归函数的内部执行过程
10

最近更新

国际贸易中的风险防范法律戴庆康 27页

革兰氏阴性需氧杆菌 20页

万丽品牌活动策划方案相关7篇 14页

2023年最新质量月企业员工全面质量管理知识典.. 15页

仓库的管理人员职责 12页

有机化学与药学的关系 7页

新的一年即将到来句子范文六篇 15页

创意元旦活动策划方案【九篇】 19页

写说明的格式模板 14页

住所使用证明三篇 4页

1《迷娘(之一)》同步练习 (含答案)统编版高中.. 7页

2021水工监测工-水工监测工(技师)(精选试题) 10页

2022-2023学年辽宁省沈阳市市级重点高中联合体.. 11页

2023-2024学年度五年级科学上册 第二单元 水循.. 14页

2023年专升本(大学语文)考试题库含答案及详细.. 16页

2023年广东专插本《民法》真题 6页

2023年流感等种突发传染病防治知识继续教育答.. 22页

2024届贵州省平塘县化学九年级第一学期期中复.. 5页

25道德邦物流物流师岗位常见面试问题含HR常问.. 16页

TPU检验规范 5页

《平行四边形的面积》教学反思 20页

护理本科开题报告答辩ppt 27页

上海市青少年科技创新大赛高中 获奖课题 6页

中国社区团购行业发展现状、竞争格局及行业发.. 9页

九年级下册 第四单元 第15课 第二次世界大战.. 11页

上海市建设工程白玉兰奖(市优质工程)评选办法.. 23页

初中化学试卷双向细目表 3页

xx乡2022年民生实事票决项目工作总结正文 2页

南京安魂曲 1页

2021年民用建筑隔声设计规范 16页