4

我只知道通过分支定界，可以减少获得解决方案的过程，但这仅有助于具有解决方案空间树的问题。

4

2 回答 2

9

动态规划

动态规划（通常称为 DP ）是解决特定类别问题的一种非常强大的技术。它需要非常优雅的方法表述和简单的思维，并且编码部分非常容易。
这个想法很简单，如果你用给定的输入解决了一个问题，那么保存结果以备将来参考，以避免再次解决同样的问题。很快“记住你的过去”。

如果给定的问题可以分解成更小的子问题，这些更小的子问题又被分成更小的子问题，并且在这个过程中，如果你观察到一些重叠的子问题，那么它对 DP 来说是一个很大的提示. 此外，子问题的最优解有助于给定问题的最优解（称为最优子结构属性）。

有两种方法可以做到这一点。

1.) 自上而下：通过分解问题开始解决给定的问题。如果您发现问题已经解决，则只需返回保存的答案。如果还没有解决，请解决并保存答案。这通常很容易想到并且非常直观。这称为记忆。

2.) 自下而上：分析问题并查看解决子问题的顺序，并从琐碎的子问题开始解决，直至给定问题。在这个过程中，保证在解决问题之前先解决子问题。这被称为动态规划。

分支和绑定

  • 分支定界算法包括通过状态空间搜索对候选解进行系统枚举：候选解的集合被认为是形成一棵有根树，整个集合在根处。
  • 该算法探索这棵树的分支，这些分支代表解决方案集的子集。在枚举分支的候选解之前，会根据最优解的估计上限和下限检查分支，如果它不能产生比算法迄今为止找到的最佳解更好的解，则将其丢弃。

有关 Branch and Bound 的更多信息，请参阅此链接：

http://www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf

于 2017-04-04T20:15:04.613 回答
0

动态编程需要递归结构（也就是 CRLS 中的最优子结构）。也就是说，在给定状态下，可以基于部分解来表征最优决策。

分支定界是一种更通用的方法，用于通过解空间的隐式枚举来解决更困难的问题。

于 2013-09-26T18:42:19.153 回答