动态规划是个啥?
date
Jun 4, 2021
slug
dp
status
Published
tags
学习
summary
递推?搜索?动态规划?傻傻的分不清楚
type
Post
1.动态规划与分治
分治:为了解决一个大问题,把它分成两个或多个小问题,分别解决。如:汉诺塔、快速排序
动态规划:用一个数组记录所有已解决的子问题的答案,无论子问题以后是否被用到,只要它被计算过,就将其结果存入数组
动态规划减少子问题的重复计算
动态规划在实现时可以用递推的手段实现
2.动态规划与递推
递推:模4最优路径问题,最优策略的子策略不一定最优
递推法借用了动态规划的思想解决了动态规划不能解决的问题
3.动态规划与搜索
动态规划能解决的问题,搜索也能解决
动态规划是自底向上的递推求解
搜索是自顶向下的递归求解(这里指深度优先搜索,宽度优先搜索类似)
动态规划算法在时间效率上优于搜索算法
搜索可以排除一些无效状态,还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多
记忆化算法保存求解状态的解,综合了搜索和动态规划的优点
动态规划的优点:
当每个阶段的状态变量个数不多于三个,而每一个允许决策聚合不太大时,每个问题可穷举,再动态规划
动态规划的设计步骤
1.划分阶段
2.选择状态
3.确定决策并写出状态转移方程
4.写出规划方程(包括边界条件)
我对最短行军路线的理解(可能不对...
宽度优先搜索:f(G) = min(f(F1) + F1, f(F2) +F2),从前往后算出每个阶段每个状态的最短路径
动态规划:最优路径上每一个节点到终点的路径都是最优的,可以从后向前开始逐段求最优子路线