动态规划是个啥?

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),从前往后算出每个阶段每个状态的最短路径
动态规划:最优路径上每一个节点到终点的路径都是最优的,可以从后向前开始逐段求最优子路线
我已经晕了,先占个坑,后面谈一谈Dijkstra算法和Floyd算法吧,应该会帮助区分递推、搜索和动态规划
 

© Dino 2021 - 2022