动态规划基础-最优子结构_动态规划最优子结构是什么?

作者：知新_RL | 2024-04-28 04:29:18

踩

动态规划最优子结构是什么?

最优子结构

定义：如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构。

举个简单的例子。下面是一个地图，我们要找一条从左下角（起点）到右上角（终点）、只向右和向上走的路径。

如果要让路径经过的数字总和最大，那么最优路径是下面这条：

可以验证，对于最优路径上的任意一点，最优路径从起点到该点的部分，也正是从起点到该点的所有路径中数字总和最大的那一条。这就叫「满足最优子结构」。

现在换一个「最优」的标准，要求路径经过的数字总和的绝对值最小。那么最优路径是下面这条：

但是，对于最优路径上 -4 这个点，最优路径从起点到该点的部分，却不是从起点到该点的所有路径中，数字总和的绝对值最小的那一条，因为下面这条路径上数字总和的绝对值更小：

这就叫「不满足最优子结构」。

常见的最优化问题，问法一般都是「最大」「最小」，不太会出现「绝对值最小」这种奇葩的最优化标准。
而问「最大」「最小」的问题，一般都是满足最优子结构的。

感谢王赟 Maigo

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/500442