算法合集之《参数搜索的应用》.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《算法合集之《参数搜索的应用》.pdf》由会员分享,可在线阅读,更多相关《算法合集之《参数搜索的应用》.pdf(27页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、参数搜索的应用 芜湖市第一中学 汪汀 引言 参数搜索是解决最优解问题的一种常见的方法。其本质就是对问题加入参数,先解决有参数的问题,再不断调整参数,最终求得最优解。下面通过几个例子来说明这一点。问题一 分石子问题 有N个石子,每个石子重量Qi;按顺序将它们装进K个筐中;求一种方案,使最重的筐尽量轻。问题一 分石子问题 N=9,K=3 9 7 5 6 8 4 3 2 7 16 19 16 最大为19 9 7 5 6 8 4 3 2 7 21 18 12 最大为21|问题一 分石子问题分析 本题可采用动态规划 时间复杂度O(N2)能否找到实现更简单,更优秀的算法呢?太高了 问题一 分石子问题分析?
2、问题一 分石子问题分析 引入参数P,求一个判定可行解问题:判断是否存在最大重量不超过P的方案 问题一 分石子问题分析 可以用贪心法解决,具体方法如下:按顺序把石子放入筐,若一个筐中石 子总重量不足P,我们就继续 对这个 筐加入新的石子;如果超过P,则我们 将石子放入新的筐中。问题一 分石子问题分析 3 N=5,K=3,P=12 问题一 分石子问题分析 回到最初的问题:从小到大枚举P,找到第一个可行解,该解即为问题所求 令T=Qi,则这个算法的时间复杂度为O(TN)需要进一步优化!问题一 分石子问题分析 若我们能找到一个最大重量不超过P的方案,则我们可以找出一个最大重量不超过P+1的方案 二分法
3、!问题一 分石子问题分析 不断重复以上步骤即可找到问题的最优解。时间复杂度O(NlogT)特别地,由于答案必定为某一段连续石子的重量和 所以可以得到一个时间复杂度为O(Nlog3N)的算法 1 T M 尝试区间1,M-1 尝试区间M+1,T 小结 首先引入参数P,解决带参数的问题;用贪心法可以判断是否存在最大重量和不超过p的方案;枚举P求出问题的最优解;二分法降低了算法的时间复杂度,最终解决了问题。小结 首先引入参数P,解决带参数的问题;判断是否存在结果优于P的方案 调整P得到最优解。通过二分法或迭代法减少调整次数,降低算法时间复杂度。问题二 最大比率问题 有N道题目,每道题目有不同的分值和难
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 参数搜索的应用 算法 参数 搜索 应用
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内