AI 中文社
Copyright © 2022-2024 aizws.net · 网站版本: v1.2.6·内部版本: v1.23.3·
页面加载耗时 0.00 毫秒·物理内存 61.9MB ·虚拟内存 1301.8MB
欢迎来到 AI 中文社区（简称 AI 中文社），这里是学习交流 AI 人工智能技术的中文社区。 为了更好的体验，本站推荐使用 Chrome 浏览器。
算法：动态规划
动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。但不同的是，分而治之，这些子问题并没有独立解决。相反，记住这些较小子问题的结果并用于类似或重叠的子问题。
动态编程用于我们遇到问题的地方，可以将其划分为类似的子问题，以便可以重复使用它们的结果。大多数情况下，这些算法用于优化。在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。结合子问题的解决方案以实现最佳解决方案。
所以我们可以说 -
- 该问题应该能够分成较小的重叠子问题。
- 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
- 动态算法使用Memoization。
对照
与解决局部优化的贪婪算法相反，动态算法被激励用于问题的整体优化。
与分而治之的算法相比，其中解决方案被组合以实现整体解决方案，动态算法使用较小子问题的输出，然后尝试优化更大的子问题。动态算法使用Memoization来记住已经解决的子问题的输出。
例
使用动态编程方法可以解决以下计算机问题 -
- 斐波纳契数系列
- 背包问题
- 河内塔
- 由Floyd-Warshall完成的所有最短路径
- Dijkstra的最短路径
- 项目安排
动态编程可以自上而下和自下而上的方式使用。当然，大多数情况下，参考之前的解决方案输出比CPU周期重新计算更便宜。
下一章：算法：基本概念
算法：基本概念算法：本章介绍与数据结构相关的基本术语。 数据定义数据定义定义具有以下特征的特定数据。原子 - 定义应该定义一个单一的概念。可追踪 - 定义应该能够映射到某些数据元素。准确 - 定义应该是明确的。清晰简洁 - 定义应 ...