中国讲座网总首页 > 音频讲座 > 管理经营
无插件

【动态规划】怎样从小问题出发,逐级解决大问题?

  • 软件大小:37.0 MB 更新时间:2021-11-07 09:31:29
  • Tags: 授权方式:破解版
  • 音频类别:培训 / 管理经营 音频语言:简体中文
  • 插件:推荐星级:
  • 售价:¥ 0 元 销量:0 套

【动态规划】怎样从小问题出发,逐级解决大问题?——更多资源,课程更新在

资源,名师讲座课程简介:

【动态规划】怎样从小问题出发,逐级解决大问题?

要确保问题可以分解成和原问题类似的子问题,并且这些子问题之间还相互独立,这时分治策略才能奏效。

算法分治策略的目的,不是要把一个不能解决的问题解决掉,而是要解决得更快。

咱举个例子,在计算机图形学中有个问题叫碰撞检测”。 解决这个问题可不容易,尤其是模拟的空间中物体很多的时候。 100个球总共的计算次数是4950次。如果物体的个数更大些,计算次数会以平方的形式上升。 平方的形式,复杂度就挺高了。如果用这种算法,游戏在进行得枪林弹雨时,你的画面肯定会卡。 分解”的时候计算成本的问题。 合并的时候,也有类似的问题。比如说你在分割空间的时候,可能会正好把某些球从中间割断。 合并的时候,你发现这些球不属于任何一个子空间,要判断它们有没有发生碰撞,还得额外计算。这是合并结果的成本。 分治中的两个重要操作,分解和合并,不是免费的。 如果它们自身就要耗费很多次计算,那很可能分治策略提升不了效率,也不算是奏效了。

分治算法,还可以通过巧妙地利用硬件”,让效率进一步提升。这就是并行计算”。 并行计算能让多个计算机的CPU同时为解决一个问题出力,但并不能减少总的操作数量。 并不是所有算法都可以用并行计算的。 迭代算法要求每一步以前一步的结果作为出发点,按步骤、按顺序进行计算。 顺序计算和并行计算有本质上的差异。 分治算法因为能把问题分解成独立的部分,所以和并行计算是天然的好朋友。 数据量越大,处理起来的所花的步骤也就多。那为了能快速地对数据进行分析处理,就必须用分治算法。 1 分治算法是通过回溯,不断分解同样的问题,直到问题小得可以直接解决,再把小问题的解合并成原来问题解的算法策略。 2 确保要解决的问题能分解成与原问题类似的子问题,并且这些子问题之间相互独立,这时分治策略才能奏效。 3 如果分解问题和合并结果计算不复杂,分治策略能减小算法的复杂度。 4 分治策略开启了并行计算的大门,利用多CPU硬件上的优势,可以减少算法的运行时间。 分治算法与生活中通常理解的分治不同,不是简单的将复杂大的问题分解成小的问题各个击破。 分治算法包括了分解和合并两步,将问题分解成用同样方法可以解决的独立小问题,再把这些小问题的解合并成原来问题的解,分解出来的小问题可以通过并行计算提高效率;所以,分解和合并本身的计算复杂度也决定了分治算法应用的可行性。 动态规划:怎样从小问题出发,逐级解决大问题? 动态规划”是什么意思呢?动态”指的是多个步骤,而规划”指的就是决策。动态规划”这个词既指多步骤的决策优化问题,也代表解决这类问题的算法方法。 问题的解决思路:以终为始,以小建大 要弄清楚动态规划,我们得从两方面入手,一个是它的内涵,它的解决思路;一个是它的外在,这个算法的结构。我们先来说它的解决思路,叫以终为始,以小建大”。 这就是以终为始,以小建大”的解决思路。也就是说,我们要先得到小问题的解,再构建出大问题的解。 火箭垂直软着陆的问题虽然更复杂,但解决的思路是类似的。 火箭科学家需要的,就是以终为始,从后往前解决问题。 每一步都施加正确的推进力,才能确保最后成功的软着陆。 动态规划算法的结构:最优子结构 以终为始”的思想要能实现,还得通过特定的算法结构才能实现。这个结构,叫最优子结构。 如果将来的你总是遵守最优策略,那现在拿2颗糖就一定是现阶段最优的选择。 这也就是说,我们在面对一个多步骤的决策问题时,某一步决策的最优,包含且依赖于对更小规模问题的最优策略。 这就是最优子结构。 这个结构很重要。

如果一个问题满足了这个结构,那就说明我们可以从解决小问题开始,慢慢构建对大问题的解。 如果这个性质不满足,以终为始,以小建大的解决方案就不奏效。 这就出现了最优子结构不满足的情况。

你从北京,经东京到纽约的联程机票,虽然是两步问题中的最优解,但它并不包含从东京到纽约单步问题的最优解,因为联程机票不能分开使用。 即使你算出了北京到东京,和东京到纽约单步机票的价格,也不能构建出从北京到纽约的联程机票,大问题并不依赖于小问题的解。

所以这时候,最优子结构的条件就不满足,以终为始”的思想就实现不了了。 动态规划算法,就是在多步骤的决策优化问题满足最优子结构的时候,用以终为始、以小建大的思想解决问题的算法策略。

动态规划在实际中出现的频率非常高。比如库存管理问题,每个周期是不是应该补货。工厂生产控制问题,每天应该生产哪拨订单。飞行器降落,每个时刻应该施加多少的加速度。股票交易,每天是应该买进还是卖出。这些问题的解决,都可以依赖动态规划的算法策略。 动态规划策略有效的条件 维度爆炸”。 这个维度的大小,决定着我们要求解子问题的个数。

当问题的维度很大的时候,子问题的数量会呈指数形式上升。 即使最优子结构没有变化,但以终为始、以小建大的解决方向就会遇到计算瓶颈了。 选择算法策略最重要的考量就是在质量和效率之间寻求平衡。 算法工程师不一定会精确求解所有的子问题,很可能只求解其中的一部分,而且是非精确求解,对另外的子问题的解,只进行一个估计。 虽然不能得到完美的最优决策,得到的结果也是足够好的。

1 动态规划指的既是多步骤的决策优化问题,也是解决这类问题的算法方法。

2 动态规划算法是在多步骤的决策优化问题满足最优子结构的时候,用以终为始、以小建大的方向解决问题的算法策略。

3 动态规划的效率会受维度爆炸”的影响。 动态规划指解决多步骤决策优化问题的算法,限制条件是要满足最优子结构,然后以终为始、以小建大来解决整体问题 严格以来最优最结构,否则不成立 还会面对维度爆炸的问题。 分支定界:怎样决定谁是被淘汰者”?


马上创业  诚商数据云销售系统  一键更新授权

音频用户点评

       评论摘要(共 0 条,得分 0 分,平均 0 分)

发表评论


用户名:

分 值:100分 85分 70分 55分 40分 25分 10分 1分

内 容:

         通知管理员 验证码:

下载说明

* 为了达到最快的下载速度,推荐使用网际快车或迅雷下载本站软件。
* 请一定升级到最新版WinRAR3.80才能正常解压本站提供的软件!
* 如果您发现下载链接错误,请点击报告错误谢谢!
* 站内提供的所有软件包含破解及注册码均是由网上搜集,若侵犯了你的版权利益,敬请来信通知我们!
网站公告 本站简介 网站帮助 广告合作 下载声明 友情连接 升级记录  ©Copyright © 2009-2015 . All Rights Reserved. 版权所有.页面执行时间:117.18750 毫秒
本站仅提供学习的平台,所有资料均是会员上传私下交流学习之用;将不对任何资源负法律责任,只作为购买原版的参考,并无法代替原版,所有资源请在下载后24小时内删除;
资源版权归作者所有,如果您觉得满意,请购买正版。您若发现本站侵犯了你的版权利益,请来信本站将立即予以删除!