算法设计与分析：穷举法、贪心法、分枝限界法讲稿.doc
版权申诉
138 浏览量
2022-05-06
13:40:56
上传
评论
收藏 149KB DOC 举报
算法设计与分析
——— 穷举法、贪心法、分枝限界法讲稿
一、穷举法（枚举法）
（一）算法思路
就是从可能的解的集合中一一枚举各元素，用题目给定的检验条件，判定哪些是无用
的，哪些是有用的。能使命题成立，即为其解。
（二）例子（第二章介绍过的货郎担问题）
假定以编号为 1 的城市为始发城市，那么就会有 4！=24 个不同的路线，我们只要列
举出每一条路线并分别计算出相应的费用即可。从中就可以找出最小费用及对应的路线。
（三）算法复杂度：O(n!)
（四）算法评价
优点：可得到精确值。当 n 较小时，是可行的；
缺点：较笨拙，由于须列举所有情况，且记录下每次的情况，需要大量的机时和内存
空间。当 n 较大时，该算法是不可行性的。
二、贪心法
贪心法是一种对某些求最优解问题的更简单、更迅速的设计方法。
（一）引言
在给出贪心法的具体定义和算法步骤之前，我们先来看两个例子。
例 1 假设有 4 种硬币，它们的面值分别为 1 角、5 分、2 分和 1 分。现要找给某顾客 3
角 7 分钱，这时，我们几乎不假思索地拿出 3 个 l 角、1 个 5 分和 1 个 2 分的硬币交给顾客。
我们不仅能很快决定要拿哪些硬币，而且与其它找法相比．我们拿出的硬币的个数肯定是
最少的。
在这里，我们实际使用了这样的算法：首先选出一个面值不超过 3 角 7 分的最大硬币(1
角)，然后从 3 角 7 分中减去 1 角，剩下 2 角 7 分再选出一个不超过 2 角 7 分的最大硬币(另
一个 1 角)，如此做下去，直到找足 3 角 7 分。
例 2 如图 1—1，其中，顶点可解释为城市，边上的代价可解释为两城市问的里程。在
图中找一条经过所有结点一次的回路，并使里程的总和为最小。这同样还是货郎担问题。
在解此题时，我们可以按这样一个想法去做：
首先在图中选一条代价最小的边。为了选择下一条边，先要检查一下候选边与已选入的
边之间是否满足以下两点：
1)不会有三条边(候选边及已入选边)与同一顶点相关联。
2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数。
在满足以上两点的候选边中，挑选最短的边作为入选边。如此做下去，直到得到一个
经过所有顶点的回路。
1
剩余10页未读，继续阅读
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
最新资源
- 基于flask和echarts融合交易策略的bitfinex可视化微服务.zip
- 包含了wvp-assist.tar wvp-talk.tar zlmediakit.tar .
- 3r4efgh53wgrf43tw
- 2024新版Java基础从入门到精通全套视频+资料下载
- Spring AI大模型视频教程+ChatGPT视频教程+OpenAI大模型视频教程（资料+视频教程）
- ABB工业机器人教程PDF版本
- 123321123323211
- yolov8实战第八天-pyqt5-yolov8实现车牌识别系统（论文（约7000字）+数据集+完整部署代码+代码使用说明）
- 三相桥式全桥整流电路MATALB Simulink仿真文件
- ABB机器人操作培训文档
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
