动态规划

来自计算思维百科
跳转至: 导航搜索
动态规划1.png

动态规划('Dynamic Programming'),也称多阶段决策,是运筹学的分支,是求解决策过程(Decision Process)最优化的数学方法。

基本描述

动态规划('Dynamic Programming'),也称多阶段决策,是运筹学的分支,是求解决策过程(Decision Process)最优化的数学方法。20世纪50年代初美国数学家Richard Bellman等人在研究多阶段决策过程的优化问题时,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法—动态规划。

动态规划求解问题的基本思想是将待求解的问题划分为若干个阶段,即若干个互相联系的子问题,然后按自底向上的顺序推导出原问题的解。通过存储子问题的解,可以避免在求解过程中重复多次求解同一个子问题,提高算法的求解效率。动态规划算法实质是分治思想和冗余解决方法的结合。

应用范围

动态规划已在经济管理、生产调度、工程技术和最优控制等方面得到广泛应用,库存管理、资源分配、设备更新、排序和装载等问题运用动态规划算法求解比较方便。

使用方法及步骤

1.首先确定大规模问题与小规模问题之间的关系;

2.求解出最小规模问题的解;

3.把已经得到的解记下来;

4.利用大规模问题与小规模问题(解已经记下来了)之间的关系求解大规模问题的解;

5.反复这个过程;

6.2、

应用

动态规划已在经济管理、生产调度、工程技术和最优控制等方面得到广泛应用,库存管理、资源分配、设备更新、排序和装载等问题运用动态规划算法求解比较方便。

GPS寻找最优路径

假设图1中无向图G,顶点表示城市,边上权值表示两个城市之间的距离或时间开销。图中任两个顶点之间有多条路径,最短路径是指在两个顶点的所有路径中求边权值之和最小的路径。

以图中顶点0到顶点6的最短路径为例进行求解。

                RTENOTITLE

                       图1动态规划求解最短路径例子

显然,从0顶点到6顶点的最短路径,若经过k顶点,则最短路径中从0到k的路径也是0到k的最短路径。这一点用反证法可以证明,这里略去。

用动态规划求解最短路径基于上述原理,为计算从顶点0到顶点6的最短路径,只需依次求得从顶点0到各中间顶点的最短路径。按照与0顶点的距离,将整个求解过程划分为5个阶段。

定义cost[i] :从顶点0到顶点i的最短路径,path[i]记录从0到i的最短路径上顶点i的前一顶点。初始,cost[0] = 0。后续各阶段,依次递推计算即可。

第0阶段:cost[0] = 0

第1阶段:cost[1] = cost[0]+4 = 4,path[1] = 0

     cost[2] = cost[0]+5 = 5,path[2] = 0

第2阶段:cost[3] = min{cost[0]+8,cost[1]+4,cost[2]+5} = 8,path[3] = 0

第3阶段:cost[4] = min{cost[3]+8,cost[1]+6} = 10,path[4] = 1

     cost[5] = min{cost[3]+9,cost[2]+7} = 12,path[5] = 2

第4阶段:cost[6] = min{cost[4]+5,cost[3]+9,cost[5]+4} = 15,path[6] = 4

根据计算得,从顶点0到顶点6的最短路径值为15。从path[6]向前回溯,得到最短路径为:0->1->4->6。

Fibonacci数列的动态规划算法

递归一节所讲的Fibonacci数列也可用动态规划自底向上递推计算。用一个数组F记录Fibonacci数列,初始F[1]=1,F[2]=1,然后根据式F[i]=F[i-1]+F[i-2]顺序计算F[3],…,F[n]。

动态规划求Fibonacci数列的伪代码描述如下:

Fibonacci数列的动态规划算法如下:

输入:正整数n

输出:Fibonacci数列的第n项

Fib(n)

1   F[1]ß F[2]ß1

2  FOR i=3 to n

3  DO   F[i] ß F[i-1]+F[i-2]

4  RETURN F[n]

追女生

案例:某个计算机系的男生想追同个专业的漂亮女生,苦于没有经验,聪明的你能用计算思维模式帮他出谋划策吗?如何运用科学的方法,既使该男生做到自信满满又使该女生顿时对男生刮目相看呢?

解决步骤:从计算思维的角度,我们可以用动态规划的思想来解决该问题,把追到女生这个看似天大的难题进行分解。首先,男孩需要进行一番规划,将其分解为对女生朋友和亲戚的问题,把这些问题都解决了,加上锲而不舍的精神,你才更有可能追到女生。而对女生朋友亲戚的问题都是有密切联系的,比如你和她的好朋友成为好朋友,你就可以通过她的好朋友来更深入地了解女生的爱好习惯等等,送礼物的时候也不用愁要送什么好,好朋友通常会帮你打听好,出主意;再比如你得到了她的父母的欢心,她的父母不仅会同意你们交往,还会帮助你在其他亲戚朋友面前说好话,这样你在解决其他亲戚朋友的方面上的问题就简单多了。在这里,动态规划的思想就是:一项复杂的任务常常包括多个子任务,并且这些子任务之间通常具有一定的联系。对其子任务的完成顺序提出一定的要求后,逐步完成子任务直至完成目标任务。(祝你追女生成功!)

评价

动态规划已在经济管理、生产调度、工程技术和最优控制等方面得到广泛应用,库存管理、资源分配、设备更新、排序和装载等问题运用动态规划算法求解比较方便。例如将动态规划方法运用于经济学领域的最优投资与消费选择策略的求解,可以得到连续时间下两类资产的最优投资与消费问题的解决方案。动态规划也适用于人生规划,它是人类智慧的体现。千里之行,始于足下,任何一项伟大事业的完成总是从小事做起的,小目标的达成是实现大目标的基础。

可以体现的计算思维

动态规划算法实质是分治思想和冗余解决方法的结合,体现了计算思维的优化特点。