知识卡片

普通读书笔记卡 · 5654.c.3.b.3.a

无后效性来自状态信息充分

理解等级:中级

状态应保存决定未来合法选择和答案所需的信息,使同状态的不同历史可以共用后续计算。它并不意味着真实过程没有历史,只是历史影响已被状态充分概括。

若楼梯禁止连续两次走1阶,仅保存当前阶数不够,需要再保存上一步走1还是2。扩充状态能恢复正确转移,但状态数与成本也会增加;不能因一个简单状态失败就断言整个问题不能用DP。

后文障碍生成与旅行商的难点在于历史信息可能使状态很大,并非原则上绝不能DP;例如旅行商可把已访问集合和当前位置纳入状态,但代价可能指数增长。应区分能否形成充分状态与这种状态是否经济。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      我们需要扩展状态定义:状态 表示处在第 阶并且上一轮跳了 阶,其中 。此状态 定义有效地区分了上一轮跳了 阶还是 [ ,1] − 1,2] 阶,我们可以据此判断当前状态是从何而来的。 ‧ 当上一轮跳了 阶时,上上一轮只能

    • · 查看原书依据

      下次跳跃依赖过去所有的状态,因为每一次跳跃都会在更高的阶梯上设置障碍,并影响未来 的跳跃。对于这类问题,动态规划往往难以解决。 实际上,许多复杂的组合优化问题(例如旅行商问题)不满足无后效性。对于这类问题,我们通常会选择

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[13736,13846)) - 结论依据:实际带约束楼梯按阶数+上一步类型二维状态,保留充分性而非遗忘历史的误解。 - 原始内容:我们需要扩展状态定义:状态 表示处在第 阶并且上一轮跳了 阶,其中 。此状态 定义有效地区分了上一轮跳了 阶还是 [ ,1] − 1,2] 阶,我们可以据此判断当前状态是从何而来的。 ‧ 当上一轮跳了 阶时,上上一轮只能 补充原书证据:spine 6 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;归一字符[14713,14823)。 - 结论依据:实际障碍/TSP段限制简单状态,保留状态扩充的成本边界,不将未展开具体算法虚称原书内容。 - 原始内容:下次跳跃依赖过去所有的状态,因为每一次跳跃都会在更高的阶梯上设置障碍,并影响未来 的跳跃。对于这类问题,动态规划往往难以解决。 实际上,许多复杂的组合优化问题(例如旅行商问题)不满足无后效性。对于这类问题,我们通常会选择