从数学的视角来看,动态规划是一种运筹学方法,是在多轮决策过程中的最优方法。
动态规划与分治法的区别是:从分治法的视角来看,每个子问题必须相互独立;但在多轮决策中,这个假设显然不成立,而多轮决策就用到了动态规划方法。
多轮决策和动态规划:
动态规划的解题方法没有那么标准化,它因题而异,需要仔细分析问题并寻找解决方案。
动态规划有宏观层面通用的方法论:
具有如下几个特征的问题,可以采用动态规划求解:
一个非常典型的例子,最短路径问题。每个结点是一个位置,每条边是两个位置之间的距离。如下图所示,寻找结点 A 到结点 G 的最短距离。
可以看到,需要求解的路线是由 A 到 G,这就意味着 A 要先到 B,再到 C,再到 D,再到 E,再到 F。每一轮都需要做不同的决策,而每次的决策又依赖上一轮决策的结果。
例如,做 D2 -> E
的决策时,D2 -> E2
的距离为 1,最短。但这轮的决策,基于的假设是从 D2 出发,这就意味着前面一轮的决策结果是 D2。由此可见,相邻两轮的决策结果并不是独立的。
动态规划还有一个重要概念叫作状态。在这个例子中,状态是个变量,而且受决策动作的影响。例如,第一轮决策的状态是 S1,可选的值是 A,第二轮决策的状态是 S2,可选的值就是 B1 和 B2。以此类推。
A -> B
、B -> C
、C -> D
、D -> E
、E -> F
、F -> G
,6 个阶段。dk(sk,uk)
是在 sk
时,选择 uk
动作的距离,如 d5(E1,F1) = 3。本题为 n = 7,则有如下为最终要优化的目标:接下来把所有的已知条件凝练为上面的符号之后,只需要借助最优子结构,就可以把问题解决了。最优子结构的含义是,原问题的最优解所包括的子问题的解也是最优的。
如果 A -> ... -> F1 -> G
是全局 A 到 G 最优的路径,那么此处 A -> ... -> F1
也是 A 到 F1 的最优路径。此时,优化目标的含义为,从 A 到 G 的最短路径,是 A 到 F1 到 G 的路径和 A 到 F2 到 G 的路径中更短的那个。
最终输出路径为 A -> B1 -> C2 -> D1 -> E2 -> F2 -> G
,最短距离为 18。
对于输入的图,可以采用一个 m x m 的二维数组来保存。在这个二维数组里,m 等于全部的结点数,也就是结点与结点的关系图。而数组每个元素的数值,定义为结点到结点需要的距离。
public class testpath {
public static int minPath(int[][] matrix) {
return process(matrix, matrix[0].length-1);
}
// 递归
public static int process(int[][] matrix, int i) {
// 到达A退出递归
if (i == 0) {
return 0;
}
// 状态转移
else{
int distance = 999;
for(int j=0; j<i; j++){
if(matrix[j][i]!=0){
int d_tmp = matrix[j][i] + process(matrix, j);
if (d_tmp < distance){
distance = d_tmp;
}
}
}
return distance;
}
}
public static void main(String[] args) {
int[][] m = {
{0,5,3,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,3,6,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,8,7,6,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,6,8,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,3,5,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,8,4,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,2,2,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,3,5,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,5,2,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,6,6,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3}
};
System.out.println(minPath(m));
}
}
在代码中定义了二维数组 m,对应于输入的距离图。m 是 15 x 16 维的,忽略了最后一行的全 0(即使输入也不会影响结果)。
然后调用函数 minPath
。它的内部又调用了 process(matrix, matrix[0].length-1)
。在这里,matrix[0].length-1
的值是 15,表示的含义是 matrix 数组的第 16 列(G)是目的地。
接着进入 process
函数中。在动态规划的过程中,是从后往前不断地推进结果,这就是状态转移的过程。
经过运行,这段代码的输出结果是 18,这与手动的推导结果一致。
动态规划并不简单,动态规划的适用范围也没有那么广。如果不是专门从事运筹优化领域的工作,对它不了解也正常。如果求职的岗位与运筹优化关系不大,一般而言被面试到动态规划的可能性也是极低的。