浅析静态规划和动态规划
例子:最短路径问题。
下图中,连接两个节点的线段上标注着节点间的距离,请问A到D点的最短距离是多少?
静态规划
有一个很简单的思路,穷举所有可能的途径,从中选择最短的一条。这个方法的缺点是速度慢,因为问题规模较大时,穷举全部路径要面临一个天文数字的计算量。
当然这种方法也有优点,在穷举过程中,我们始终保存着一个可行解。如果不愿意继续计算,停止计算后,总能得到一个不算太差的可行解,运气好的话可能就是最优解。如果以后有时间了,想接着进行穷举,理论上也是可以的。这种方法,从一个或多个可行解开始,通过不断迭代对现有可行解优化,最后得到最优解。这种方法称为静态规划。
线性规划的单纯性解法,是一种静态规划方法。首先生成线性规划的一个可行解,然后不断迭代优化可行解,最后得到最优解。在迭代计算过程中,始终保持一个可行解或近优解,这是静态优化的一个显著特征。
忽然想起了机器学习里面有一种所谓的在线式学习方法,大概也是按照这个模式去寻找模型最优解的。比如各种神经网络模型求解过程应该都属于这类静态划问题。
当然,上面这个问题如果用静态规划的路子求解,可以穷举所有可能的途径,从中选择最短的一条。如果问题规模比较大,采用穷举的方法性能就太差了,所以才会考虑其他更好的方法。动态规划就是出于这样一种考虑被发明出来了。
动态规划
前面的问题求解可以分成 A->B,B->C,C->D 三个阶段完成。采用拆分的方法,把问题分解成多个相互联系的单阶段问题,通过求解每个单阶段问题,完成问题求解。这种方法称为动态规划。
前面的问题比较简单,我们很容易用手工标出从A点出发到各个节点的最短距离,参见下图。
如果我们用F(X)表示节点X到A点的最短距离,很明显
F(D) = min( F(C1)+2, F(C2)+1, F(C3)+3 )
在动态规划问题中,F(X)称为状态,上述状态关系式称为状态转移方程。在上式中,F(D)的求解问题归结为了F(C1)、F(C2)、FC3)三个子问题。同样,可以得到:
F(C2) = min( F(B1)+3, F(B2)+1 )
状态转移
动态规划的关键就是确定状态转移方程,所谓状态实质上就是动态规划的子问题。动态规划的解决方法,是利用状态转移方程把问题归结的子问题求解。换句话讲,把最终状态的求解归结为其他状态的求解,这大概是状态转移的要表达的含义。
穷举状态 vs 穷举路径
动态规划真正的威力在于它的高效率。状态转移模型中,状态的数量远远少于状态转移路径的数量。采用传统的搜索算法暴力穷举每条路径,算法复杂度远远高于遍历状态节点。
相关文章
- 华为数字化转型规划“三阶十二步法”
- 自动驾驶路径规划——基于MATLAB的栅格地图
- 图算法(十):关联路径算法(n-Paths)【适用场景:用于关系分析、路径设计、网络规划等场景】【用于寻找图中两节点之间在层关系内的n条路径】
- 动态规划经典问题Java实现
- 企业服务器规划
- 机械设备维修技术(第2版)(普通高等教育“十一五”国家级规划教材)
- [C++]动态规划系列之币值最大化
- 【动态规划】用动态规划算法求解下面的组合优化问题:max g1(x1) + g2(x2) + g3(x3) || x1^2 + x2^2 + x3^2 <=10,x1,x2,x3为非负整数...
- BI规划落地的正确姿势,五步教你搭建企业级BI项目
- LeetCode_位运算_动态规划_简单_338.比特位计数
- 动态规划概述
- 田园综合体规划指南