动态规划理论(精华)
动态规划理论
一．动态规划的逆向思维法
动态规划是一种思维方法，没有统一的、具体的模式。动态规划可以从多方面去考察，不同的方面对动
态规划有不同的表述。我们不打算强加一种统一的表述，而是从多个角度对动态规划的思维方法进行讨
论，希望大家在思维具体问题时，也能够从多个角度展开，这样收获会更大。
逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成
几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。
你也许会想，这种将大问题分解成小问题的思维不就是分治法吗?动态规划是不是分而治之呢?其实，
虽然我们在运用动态规划的逆向思维法和分治法分析问题时，都使用了这种将问题实例归纳为更小的、
相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解
出来的各个子问题的性质不同。
分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，
便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不
必要的工作，重复地解公共的子问题。
动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)
，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效
的一个原因。
动态规划的逆向思维法的要点可归纳为以下三个步骤：
(1)分析最优值的结构，刻画其结构特征；
(2)递归地定义最优值；0
(3)按自底向上或自顶向下记忆化的方式计算最优值。
【例题1】背包问题描述：
有一个负重能力为m的背包和n种物品，第i种物品的价值为v，重量为w。在不超过背包负重能力的前
提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。
假设每种物品都有足够的数量。
分析：
从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合
方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效
的算法。
但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维法来分析这个问题。
(1)背包问题最优值的结构
动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含
其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动
态规划的显著特征。
对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力
为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来
划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包
问题具有最优子结构。
(2)递归地定义最优值
动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问
题而言，有状态转移方程：
／max{s[k-w]+v}(其中1≤i≤n，且k-w≥0)
s[k]= 若k>0且存在1≤i≤n使k-w≥0，
＼ 0 否则。
有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输
入背包的负重能力k，返回对应的子背包问题的最优值s[k]：
function knapsack(k:integer):integer；
begin
knapsack:=0；
for i:=1 to n do
if k-w>=0 then
begin
t:=knapsack(k-w)+v；
if knapsack < t then knapsack:=t；
end;
end；
上述递归算法在求解过程中反复出现了一个子问题，且对每次重复出现的子问题都要重新解一次，这
需要多花费不少时间。下面先考虑一个具体的背包问题。例如，当 m=3，n=2，v[1]=1，w[1]=1，v[2]=2，w[2]=2，
图1示出了由调用knapsack(3)所产生的递归树，每一个结点上标有参数k的值，请注意某些数出现了
多次。
3
／＼
2 1
／＼＼
1 0 0
／
图1
例如，knapsack(1)被引用了两次：在计算knapsack(3)和knapsack(2)中分别被引用；而knapsack(0)
更是被引用了三次。如果knapsack(1)和knapsack(0)每次都要被重新计算，则增加的运行时间相当可观
。
下面，我们来看看动态规划是如何解决这个问题的。
(3)按自顶向下记忆化或自底向上的方式求最优解
一般地，如果一个解最优化问题的递归算法经常反复地解重复的子问题，而不是总在产生新的子问题
时，我们说该最优化问题包含重迭子问题。这类问题不宜用分治法求解，因为分治法递归的每一步要求
产生相异的子问题。在这种情况下，采用动态规划是很合适的，因为该方法对每一个子问题只解一次，
然后把解存放在一个表中，以便在解同样的子问题时查阅，充分利用了重迭子问题。一般来说，解决重
迭子问题的方式有两种。
①自顶向下的记忆化方式
该方式的程序流程基本按照原问题的递归定义，不同的是，它专门设置了一张表，以记忆在求解过程
中得出的所有子问题的解。一个记忆的递归算法为每个子问题的解在表中记录一个表项。初始时每个表
项都包含一个特殊值，以示该表项的解有待填入。例如背包问题中：
s=-1；(0≤i≤m)
当在递归算法的执行中第一次遇到一个子问题时(即s=-1)，计算其解并填入表中，以后每遇到该子问题
，只要查看表中先前填入的值即可。
下面，我们按照自上而下的记忆化方式，写出求背包问题的递归算法。
函数memorized_knapsack输入背包的负重能力k，返回背包问题的解
s[k]。s表应设为全局变量，使得
函数执行后，传出所有子问题的解s(0≤i≤m)。
function memorized_knapsack(k:integer):integer；
begin
if s[k]=-1 then
begin
s[k]:=0；
for i:=1 to n do
if k-w>=0 then
begin
t:=memorized_knapsack(k-W)+V；
if s[k] < t then s[k]:=t；
end；
end；
memorized_knapsack:=s[k]；
end；
我们在主程序通过调用memorized_knapsack(m)即可获得背包问题的解。
显然这种自顶向下记忆化的算法效率比重复解重迭子问题的knapsack算法要强一些。此外，在程序中
加入判别哪些子问题需要求解的语句，只解那些肯定要解的子问题，从而节省了时间。
②自底向上的方式
假设我们要解决在分析函数knapsack当中提出的那个具体的背包问题。观察一下在调用
memorized_knapsack(4)的过程中，s[k]被计算出来的顺序。我们发现，首先是s[0]被计算出来，然后是
s[1]，s[2]，最后s[3]被计算出来，这与调用的次序正好相反。
动态规划的执行方式是自底向上，所有的子问题计算一次，充分利用重迭子问题。因此，我们很自然
就想到与这种自底向上的执行方式相应的采用自底向上的方式递推所有子问题的最优值。
我们知道，计算负重能力为k的背包问题的解仅依赖于计算负重能力小于k的背包问题的解，因此填s
表的方式与解决负重能力递增的背包问题相对应：
最初设定负重能力为0的背包问题的解s[0]=0。然后依次考虑负重能力为1，2，…，m的背包问题的解
。每填入一个s[k](0≤k≤m)时，充分利用所有重迭子问题的解：s[k-
w](0≤i≤n，k-w≥0)
下面是按照自底向上方式计算背包问题的算法流程。过程
knapsack_order输入背包的负重能力k，s表
设为全局变量。过程执行后所有子问题的解通过s表传给主程序。
procedure knapsack_order(k:integer);
begin
for i:=1 to k do s:=0;
for j:=1 to k do
for i:=1 to n do
if j-w>=0 then
begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t;
end;
end;
我们在主程序调用knapsack_order(m)，过程执行后s[m]即为背包问题的解。
最后，我们分析一下背包问题的动态规划解法的复杂度。所需的存储开销主要在s表上，其空间复杂
度是O(m)。而整个s表用两重循环求出，循环内语句的执行只需常数时间，因此，时间复杂度是O(m,n)。
自顶向下的记忆化是动态规划的一种变形。动态规划的执行方式是自底向上，因此自底向上的计算方
式是与动态规划的执行方式相一致的。它无需递归代价，且维护记忆表的开销也要小些，因此其效率通
常好于自顶向下的记忆法。
但是，在动态规划的执行过程中，并不是所有的子问题都要用到它。对某个具体问题而言，可能有大
部分子问题的最优值是不必计算的。自底向上的计算方式无法判断那些子问题是需要求解的，所以它将
一视同仁地处理所有的子问题，这就可能会把大量的时间都花在计算不必解决的子问题上；而自顶向下
的记忆法可以判断那些子问题是需要求解的，只解那些肯定要解的子问题，在这个意义上，自顶向下的
算法效率又好于自底向上。所以到底那种方式效率更高，我们要具体问题具体分析。
最后，给出求解背包问题的程序如下：
{//背包问题程序}
program knapsack;
const
maxn=100;
maxm=1000;
var
m,n:integer;
S:array[0..maxm] of integer;
v,w:array[1..maxn] of integer;
{//输入数据}
procedure read_data;
var i:integer;
begin
read(m,n);
for i:=1 to n do read(v,w);
end;
{//采用自底向上的方式求解背包问题}
procedure knapsack_order;
var i,j,t:integer;
begin
for i:=1 to m do s:=0;
for j:=1 to m do
for i:=1 to n do
if j-w>=0 then
begin
t:=s[j-w]+v;
if s[j] < t then s[j]:=t;
end;
end;
{//主程序}
begin
read_data;
knapsack_order;
writeln(s[m]);
end.
二．动态规划的正向思维法
正向思维法是指从初始状态或边界状态出发，利用某种规则不断到达新的状态，直到问题目标状态的方
法。动态规划的正向思维法，正是从已知最优值的初始状态或边界状态开始，按照一定的次序遍历整个
状态空间，递推出每个状态所对应问题的最优值。
提出动态规划的正向思维法的根本原因，是为了摆脱逆向思维法当中那种将大问题转化为子问题的思
维框框，提供一种新的思维方式。在正向思维法中，我们不再区分原问题和子问题，将动态规划的过程
看成是从状态到状态的转移。我们将所有的状态构造出一个状态空间，并在状态空间中设想一个状态网
络，若对两个状态i,j，存在决策变量di使t(i，di)=j，则向状态网络添加有向边。给定己知最优值的初
始状态或边界状态，我们可以沿着有向边推广到未知最优值的新状态，利用状态转移方程得到新状态的
状态变量的最优值。我们可以用这种方式遍历整个状态空间，得到每个状态的状态变量的最优值。
因为正向思维法中不再区分原问题、子问题、子子问题，所以我们不再按照问题被递归调用求解的相
反次序的方法确定状态最优值的计算次序。从上面我们知道可以按照状态的拓扑序列来计算每个状态的
最优值，于是我们用一个新的名词"阶段"来描述在状态空间遍历的过程中，各个状态最优值的计算次序
。我们将每个状态和一个阶段挂钩，前一个阶段的状态先计算，后一个阶段的状态后计算。有的时候我
们甚至将一组状态和一个阶段挂钩，前一个阶段的那组状态先计算，后一个阶段的那组状态后计算，而
在同一个阶段内，那些状态的计算次序可以是任意的。
动态规划的正向思维法的要点可归纳为以下三个步骤：
(1)构造状态网络；
(2)根据状态转移关系和状态转移方程建立最优值的递推计算式：
(3)按阶段的先后次序计算每个状态的最优值。
在下一节"最短路问题"当中，我们将结合最短路问题来示范动态规划的正向思维法。
动态规划的正向思维法带给我们什么启示呢?动态规划需要按阶段遍历整个状态空间，因此动态规划
的效率取决于状态空间的大小和计算每个状态最优值的开销：如果状态空间的大小是多项式的，那么应
用动态规划的算法就是多项式时间的；如果状态空间的大小是指数的，那么应用动态规划的算法也是指
数时间的。因此，找一个好的状态划分对动态规划的效率是至关重要的。
将这个结论应用到逆向思维上，我们得出如下结果：一个问题的最优子结构常常暗示了动态规划的状
态空间。典型的情况是，某一个特定问题可有几类"自然"的子问题，不同的子问题往往意味着不同的最
优子结构，从而我们得到不同的状态划分方案。但是由这些不同的状态得到的算法的效率可能差异极大
。例如，某个问题的输入是一个有序序列，有两类"自然"的子问题，一类子问题的输入是原问题输入序
列的所有子序列，另一类子问题的输入是原问题输入序列的任意元素构成的新序列。显然若我们采用后
者的最优子结构来建立状态，它的状态空间必然远远大于基于前者的状态空间。那末基于后者的状态空
间的动态规划则要解许多不必要的问题，使得算法的效率骤然下降。
从动态规划的正向思维法的分析可以看出，我们从已知最优值的初始状态和边界状态出发，利用最优
化原理，一步一步向未知的目标状态推进，直到目标状态的最优值解决。这种"从己知推广到未知"的思
维，正是动态规划正向思维法的精髓。大家在运用动态规划的正向思维法时如果能掌握这一点，那么就
能达到应用自如的境界。
在应用动态规划求解的问题的过程中，希望读者能够注意从题目的分析中领会：应用动态规划解题是
富于技巧和创造性的，没有固定的模式可套；题目出现的形式多种多样，而且大部分表面上与动态规划
看不出直接的联系。只有在充分把握其思想精髓的前提下大胆联想，才能达到得心应手，灵活运用的境
界。
三．动态规划设计方法的一般模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达
到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的
活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
┌───┐ ┌───┐ ┌───┐
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
└───┘ └───┘ └───┘
图1 动态规划决策过程示意图
(1)划分阶段：，按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后
的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶
段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常
是反过来做，根据相邻两段各状态之间的关系来确定决策。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
(5)程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单
。
根据上述动态规划设计的步骤，可得到大体解题框架如图2所示。
图2 动态规划设计的一般模式
上述提供了动态规划方法的一般模式，对于简单的动态规划问题，可以按部就班地进行动态规划的设
计。
下面，给出一个利用动态规划方法求解的典型例子。
【例题6】数字三角形问题。图3示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整
数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。
任务一：假设三角形行数≤10，键盘输入一个确定的整数值M，编程确定是否存在一条路径，使得沿着
该路径所经过的数字的总和恰为M，若存在则给出所有路径，若不存在，则输出"NO Answer!"字样。
任务二：假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过
的数字的总和最大，输出最大值。
输人数据：由文件输入数据，任务一中文件第一行是三角形的行数N和整数值 M。以后的N行分别是从
最顶层到最底层的每一层中的数字。任务二中文件数据格式同任务一，只是第一行中没有整数值M。在例
子中任务二的文件数据表示如下：
输入：5
7 输出：
3 8 7 输出路径和最大值
8 1 0 3 8 或"No Answer!"字样。
2 7 7 4 8 1 0
4 5 2 6 5 2 7 4 4
图3 数字三角形 4 5 2 6 5
【分析】对于这一问题，很容易想到用枚举的方法去解决，即列举出所有路径并记录每一条路径所经过
的数字总和。然后判断数字总和是否等于给定的整数值M或寻找出最大的数字总和，这一想法很直观，而
且对于任务一，由于数字三角形的行数不大(<＝10)，因此其枚举量不是很大，应该能够实现。但对于任
务二，如果用枚举的方法，当三角形的行数等于100时，其枚举量之大是可想而知的，显然，枚举法对于
任务二的求解并不适用。其实，只要对对任务二稍加分析，就可以得出一个结论：
如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中
间点的路径所经过的数字和也为最大。因此该问题是一个典型的多阶段决策最优化的问题。算法设计与
分析如下：
对于任务一，合理地确认枚举的方法，可以优化问题的解法。由于从塔顶到底层每次都只有两种走法
，即左或右。设"0"表示左， "1"表示右，对于层数为N的数字塔，从顶到底的一种走法可用一个N-1位
的二进制数表示。如例中二进制数字串1011，其对应的路径应该是：8-1-4-
6。这样就可以用一个N-l位
的二进制数来模拟走法和确定解的范围。穷举出从0到2n-1个十进制数所对应的N-1位二进制串对应的路
径中的数字总和，判定其是否等于M而求得问题的解。
对于任务二，采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为 n，则可把问题看做一
个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段……
第n-1阶段中各决策点至始
点的最佳路径，最终求出始点到终点的最佳路径。
设：fk(Uk)为从第k阶段中的点Uk至三角形顶点有一条最佳路径，该路
径所经过的数字的总和最大，
fk(Uk)表示为这个数字和；
由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：
Uk1为k-1阶段中某点Uk沿左斜线向下的点；
Uk2为k-1阶段中某点Uk沿右斜线向下的点；
dk(Uk1)为k阶段中Uk1的数字；dk(Uk2)为k阶段中Uk2的数字。
因而可写出顺推关系式(状态转移方程)为：
fk(Uk)=max{fk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)}(k=1，2，3，…，n) f0(U0)＝0
经过一次顺推，便可分别求出由顶至底N个数的N条路径，在这N条路径所经过的N个数字和中，最大值
即为正确答案。
四．动态规划方法实现的灵活性与技巧性
上述例子给出了一般情况下的动态规划思维过程。一些较为简单的问题可以"按部就班"来操作，但大多
数的"动态规划"问题，特别是作为信息学竞赛中的"动态规划"问题，考察的知
识是多方面的，应用的技
巧是灵活多变的。下面给出上述例5变形的例子。
【例题7】花店橱窗布置问题('99IOI试题)。假设以最美观的方式布置花店的橱窗，有F束花，每束花
的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到
右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V 的花瓶在最右边，花束可以移
动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I < J，则
花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标
识数为3，所有的花束在放人花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中
，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每
个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放人不同的花束时会产生不同的美学效果，
并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的
美学值，可以用如下表格表示：
┌───┬───┬───┬───┬───┬───┐
││花瓶1 │花瓶2 │花瓶3 │花瓶4 │花瓶5 │
├───┼───┼───┼───┼───┼───┤
│杜鹃花│7 │ 23 │ -5 │ -24 │ 16 │
├───┼───┼───┼───┼───┼───┤
│秋海棠│ 5 │ 21 │ -4 │ 10 │ 23 │
├───┼───┼───┼───┼───┼───┤
│康乃馨│ -21 │ 5 │ -4 │ -20 │ 20 │
└───┴───┴───┴───┴───┴───┘
根据表格，杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。
为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大
美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1≤F≤100，F≤V≤
100，－50≤AIJ≤50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V和矩阵(AIJ)，输出最大
美学值和每束花摆放在各个花瓶中的花瓶编号。
[分析]问题实际就是给定F束花和V个花瓶，以及各束花放到不同花瓶中的美学值，要求你找出一种摆
放的方案，使得在满足编号小的花放进编号小的花瓶中的条件下，美学值达到最大。
(1)将问题进行转化，找出问题的原型。首先，看一下上述题目的样例数据表格。
将摆放方案的要求用表格表现出来，则摆放方案需要满足：每行选且只选一个数(花瓶)；摆放方案的
相邻两行中，下面一行的花瓶编号要大于上面一行的花瓶编号两个条件。这时可将问题转化为：给定一
个数字表格，要求编程计算从顶行至底行的一条路径，使得这条路径所经过的数字总和最大(要求每行选
且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数大于上一行数字的惺 ?
br> 看到经过转化后的问题，发现问题与例题6的数学三角形问题十分相似，数字三角形问题的题意
是：
给定一个数字三角形，要求编程计算从顶至底的一条路径，使得路径所经过的数字总和最大(要求每
行选且仅选一个数字)。同时，路径中相邻两行的数字，必须保证下一行数字的列数与上一行数字的列数
相等或者等于上一行数字的列数加1。
上例中已经知道：数字三角形中的经过数字之和最大的最佳路径，路径的每个中间点到最底层的路径
必然也是最优的，可以用动态规划方法求解，对于"花店橱窗布置"问题经过转化后，也可采取同样的方
法得出本题同样符合最优性原理。因此，可以对此题采用动态规划的方法。
(2)对问题原型动态规划方法的修改。"数字三角形"问题的动态规划方法为：已知它是用行数来划分
阶段。假设用a[i，j]表示三角形第i行的第j个数字，用p [i，j]表示从最底层到a[i,j]这个数字的最佳
路径(路径经过的数字总和最大)的数字和，易得问题的动态转移方程为： p[n+1,j]=0 (1≤i≤n+1)
p[i,j]=max{p[i+1,j],p[i+1,j+1]}+a[i,j]
(1≤i≤i≤n，其中n为总行数)
分析两题的不同之处，就在于对路径的要求上。如果用path表示路径中第 i行的数字编号，那么两题
对路径的要求就是："数字三角形"要求path≤path[i+1]≤path+1，而本题则要求path[i+1)>path。
在明确两题的不同之后，就可以对动态规划方程进行修改了。假设用
b[i，j]表示美学值表格中第i行
的第j个数字，用q[i，j]表示从表格最底层到b[i，j]这个数字的最佳路径(路径经过的数字总和最大)的
数字和，修改后的动态规划转移方程为：
q[i,V+1]=-∞(1≤i≤F+1)
q[F，j]=b[F，j](1≤j≤V)
q[i，j]=max{q[i+1，k](j 这样，得出的max{q[1，k]} (1≤j≤V)就是最大的美学值，算法的时间复杂度为O(FV2)。 (3)对算法时间效率的改进。先来看一下这样两个状态的求解方法： q[i,j]=max{q[i+1，k] (j < k≤V+1)}+b[i，j] (1≤i≤F，1≤j≤V) q[i,j+1)=max{q[i+1，k] (j+1 < k≤V+1)}+a[i，j+1) (1≤i≤F， 1≤j+1≤V) 上面两个状态中求max{q[i+1，k]}的过程进行了大量重复的比较。此时 对状态的表示稍作修改，用数 组t[i，j]=max{q[i,k](j≤k≤V+1)}(1≤i≤F，1≤j≤V)表示新的状态。经 过修改后，因为q[i，j]=t [i+1，j+1]+a[i，j]，而t[i，j]=max{t[i，j+1]，q[i,j}(1≤i≤F， 1≤j≤V)，所以得出新的状态转移 方程： t[i,V+1]=-∞ (1≤i≤F十1) t[F，j]=max{t[F，j+1]，b[F，j]} (1≤j≤V) t[i,j]=max{t[i，j+1]，t[i+1，j+1]+a[i，j]} (1≤i≤F，1≤j≤V) 这样，得出的最大美学值为t[1,1]，新算法的时间复杂度为O(F*V)，而 空间复杂度也为O(F*V)，完全 可以满足1≤F≤V≤100的要求。下面给出这一问题的源程序。 {$A+，B-，D+，E+，F-，G-，I+，L+，N-，O-，P-，Q-，R-，S+，T-， V+，X+} {$M16384，0，655360} program ex；{花店橱窗布置问题} const st1='flower.inp'; {输入文件名} st2='flower.out'; {输出文件名} var f，v：integer； {f为花束的数量；v为花瓶的数量} b：array[1．．100，1．．100] of shortint； {b[i,j]为第i束花放进第j个花瓶的美学值} t：array[1．．101，1．．101] of integer； {t[i，¨为将第i到第f束花放进第j到第v个花瓶所可能得到的最大美学值} procedure readp； {从文件中读入不同花束对应不同花瓶的美学值} var f1：text； i，j：integer； begin assign(f1,st1)；reset(f1)； readln (f1, f, v); for i:=1 to f do for j:=1 to v do read (f1, b [i, j]); close (f1); end; procedure main; {用动态规划对问题求解} var i, j: integer; begin for i:=1 to f+1 do t[i, v+1]:=-9999; for j:=v downto 1 do if t[f, j+l] > b[f, j] then t[f,j]:=t[f, j+1] else t[f,j]:=b[f,j]; {设定动态规划的初始条件，其中-9999表示负无穷} for i:=f-1 downto 1 do for j:= v downto 1 do begin t[i, j]:=t[i, j+1]; if t[i+1, j+1] + b[i, j] > t[i, j] then t[i, j]:=t[i+1, j+1] +b[i, j]; end; end; procedure print; {将最佳美学效果和对应方案输出到文件} var f1: text; i,j,p: integer; {为当前需确定位置的花束编号，p为第i束花应插入的花瓶编号的最小值} begin assign (f1, st2); rewrite (f1); writeln (f1, t [1, 1]); p:=1; for i:=1 to f do begin {用循环依次确定各束花应插入的花瓶} j:=p; while t[i, j] =t[i, p] do inc (j); write (f1, j-1,' '); p:=j; end; writeln (f1); close (f1); end; begin readp; main; print; end. 由此可看出，对于看似复杂的问题，通过转化就可变成简单的经典的动态规划问题。在问题原型的基 础上，通过分析新问题与原问题的不同之处，修改状态转移方程，改变问题状态的描述和表示方式，就 会降低问题规划和实现的难度，提高算法的效率。由此可见，动态规划问题中具体的规划方法将直接决 定解决问题的难易程度和算法的时间与空间效率，而注意在具体的规划过程中的灵活性和技巧性将是动 态规划方法提出的更高要求。 五．应用举例. 【例题1】最短路径问题 现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试 找出从结点A到结点E的最短距离。 图 1 我们可以用深度优先搜索法来解决此问题，该问题的递归式为 其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。 具体算法如下： function MinDistance(v):integer; begin if v=E then return 0 else begin min:=maxint; for 所有没有访问过的节点i do if v和i相邻 then begin 标记i访问过了; t:=v到i的距离+MinDistance(i); 标记i未访问过; if t end; end; end; 开始时标记所有的顶点未访问过，MinDistance(A)就是从A到E的最短距离。这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间 复杂度为O(n!)，这是一个"指数级"的算法，那么，还有没有更好的算法呢？首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求 从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两 遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整 个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离"记录在案"， 随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v 到E的最短距离记录下来， 在算法中递归地求MinDistance(v)时先检查以前是否已经求过了 MinDistance(v)，如果求过了则不用重 新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该 算法的数量级为O(n)。 更进一步，可以将这种递归改为递推，这样可以减少递归调用的开销。 请看图1，可以发现，A只和Bi相邻，Bi只和Ci相邻,...，依此类推。这样，我们可以将原问题的解决过 程划分为4个阶段，设 S1={A},S2={B1,B2},S3={C1,C2,C3,C4},S4={D1,D2,D3}，Fk(u)表示从Sk中的点u到 E的最短距离，则 并且有边界条件 显然可以递推地求出F1(A)，也就是从A到E的最短距离。这种算法的复杂度为O(n)，因为所有的状态总数 动态规划基本原理 动态规划基本原理 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目 需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经 不再停留于简单的递推和建模上了。 要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采 取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了 一个过程的活动路线，则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供 选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可 以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策 略中间，选取一个最优策略，使在预定的标准下达到最好的效果. 让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最 短 图4-1 带权有向多段图 路径的长度(下面简称最短距离)。 我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可 能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达D点 必然要经过B1和B2中的一个，所以A到D的最短距离必然等于B1到D的最短距离加上5，或是B2到D的最短距离加上2。同样的，B1到D的最短距离必然等于C1到D的最短距离 加上3或是C2到D的最短距离加上2，……。 我们设G[i]为点i到点D的距离，显然G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析， 有： G[B1]=min{G[C1]+3，G[C2]+2}=5， G[B2]=min{G[C2]+7，G[C3]+4}=9， 再就有G[A]=min{G[B1]+5，G[B2]+2}=10， 动态规划算法原理及其应用研究 系别：x x x 姓名：x x x 指导教员： x x x 2012年5月20日 摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数 2015年天津商业大学数学建模竞赛 承诺书 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、 电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨 论与赛题有关的问题。 我们明白，抄袭不人的成果是违反竞赛规则的, 假如引用不人的成 果或其他公开的资料（包括网上查到的资料），必须按照规定的参考 文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。 如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B中选择一项填写）： B 参赛队员 (打印并签名) ：1. 叶恒扬 2. 施艺敏 3. 张一鸣 日期： 2015 年 4 月 27 日 基于动态规划的面试时刻优化模型 摘要 现代信息社会中，求职面试差不多成为就业的一个重要环节。科学有效的组织和安排不管对面试者依旧对组织单位、用人单位差不多上省时省力、节略成本的。因此如何紧凑、高效、省时地安排面试者按顺序完成面试具有重要研究意义。 本文综合运用运筹学、统计学、经济学、平面设计、计算机软件等知识，通过建立数学模型来求解面试的最短时刻，进一步规划最优的面试流程。 针对问题一，通过分析给定的面试时期顺序和不同意插队等特性，为满足面试时刻最短，建立了求解最短时刻的0-1非线性规划模型（见公式（1）），然后利用Lingo11.0程序（见附录1），求解出最短面试时刻为100分钟，最佳安排顺序为：3 → →，同学最早9:40 → 4→ 1 5 2 一起离开。接着利用AutoCAD2007分不绘制出同学和面试官的面试过程时刻图（见图1～2）。在此基础上，利用Excel2007制作出同学的 运用动态规划模型解决物流配送中的最短路径问题 王嘉俊 （盐城师范学院数学科学学院09（1）班） 摘要：随着现代社会的高速发展，物流配送成为了连接各个生产基地的枢纽，运输的成本问题也成为了企业发展的关键。运费不但与运量有关，而且与运输行走的线路相关。传统的运输问题没有考虑交通网络，在已知运价的条件下仅求出最优调运方案，没有求出最优行走路径。文中提出“网络上的物流配送问题“，在未知运价，运量确定的情况下，将运输过程在每阶段中选取最优策略，最后找到整个过程的总体最优目标，节省企业开支。 关键词：动态规划，数学模型，物流配送,最优路径 1 引言 物流配送是现代化物流系统的一个重要环节。它是指按用户的订货要求, 在配送中心进行分货、配货, 并将配好的货物及时送交收货人的活动。在物流配送业务中, 合理选择配送径路, 对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。物流配送最短径路是指物品由供给地向需求地的移动过程中, 所经过的距离最短(或运输的时间最少, 或运输费用最低) , 因此, 选定最短径路是提高物品时空价值的重要环节。[1] 经典的Dijkstra 算法和Floyd 算法思路清楚,方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性。我国学者用模糊偏好解试图改善经典方法[]5,取得了较好的效果。遗憾的是,模糊偏好解本身就不完全是客观的。文献[]6详细分析了经典方法的利弊之后,提出将邻接矩阵上三角和下三角复制从而使每条边成为双通路径,既适用于有向图也适用于无向图, 但复杂性增加了。为了避免上述方法存在的不足,本文以动态规划为理论,选择合理的最优值函数,用于解决物流配送最短路径问题。 动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。 动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决 城市理论是对城市应该是什么样的描述。这个问题十分复杂,存在很多学派,看法很不一致,但有一点是一致的,即城市要“以人为本”和“宜人为本”。不同的行业如城市规划、城市建筑设计、城市管理、城市环境的学者,从自己专业的角度可以提出对城市的不同理论。但是,联合国于1996年在土耳其伊斯坦布尔召开的《人居国际会议》上，通过了《关于新千年中的城市和其他人类居住区的宣言》,简称《21世纪人居议程》，其中反复强调了城市要以人为本的基本观点。主要的传统理论有: (1)城市规划理论 《雅典宪章》(1933)指出,城市规划的目的是解决居住、工作、休闲及交通四大活动问题。原则有:①城市建筑景观美化的原则;②城市生态环境原则;③城市功能布局与城市结构相协调的原则;④城市交通现代化的原则;⑤城市土地利用合理布局的原则。还有如:城市要与所处的自然背景或周围环境相融为一体的原则,建筑艺术、园林艺术与文化历史相协调的原则,要与国土规划、区域规划相协调的原则等。 重庆鲁能·星城的规划设计说明，就是以《雅典宪章》为线索进行论述： ·住宅区应该计划成安全舒适方便宁静的邻里单位。——1933年《雅典宪章》 ·城市依赖地理的，经济等区域单位而发展。——1933年《雅典宪章》 ·工作地点与居住地点之间的距离，应该在最少时间内可以到达。——1933年《雅典宪章》 ·公园适当的地点应留作公共设施之用，设立音乐台、小图书馆、小博物馆及公共会堂等，以提倡正当的集体文娱活动。——1933年《雅典宪章》 (2)城市建筑理论 城市是以建筑为主题的,而建筑之道以人为本,建筑之美宜人为本。建筑的一切要素应以人的舒适、安全、愉悦为出发点。在有限的物质空间里,营造并延伸精神的自由空间(张开济,2000)。 (3)人居环境科学理论 吴良镛(2001.9)提出城市的五大纲领(生态、经济、技术、社会、人文艺术),五大系统(自然、人、社会、居住、支撑网络),五大层次(全球、区域、城市、社区、建筑)和一个原则(“以人为中心的生态环境”)。俞孔坚(2000.6)提出理想人居原则——天、地、人和谐的原则,即城市建筑要与自然环境相协调,要宜人为本。 (4)人类生态系统理论 城市是城市范围的,甚至是一个地区的社会、经济的自然生态系统的复合体,是人类对自然改造的人工生态系统。人类是该系统的主体，城市是人工环境(各类建筑物)和自然环境相结合的产物。城市生态系统的功能是生产(主要指商品生产和精神文明生产)和消费(原料、食物等),物质和能量的输入和输出是守恒的,但它们的价值是不守恒的,增值的主要原因与信息有关,这一过程还是非线性的。 (5)城市生态理论或生态城市理论 在殖民时期，欧洲移民兴建的沿海城市，都是以大教堂、主广场为中心，采用棋盘式布局。第二次世界大战后，拉丁美洲各国首都和港口城市的人口迅速增加，圣保罗、里约热内卢、布宜诺斯艾利斯、圣地亚哥、墨西哥城、波哥大等很快发展为几百万人口的大都市，高楼大厦次第出现。但城市只是按原有布局延伸扩大，出现了住宅短缺、交通阻塞、环境质量下降等情况。从上世纪50年代起，一些国家的城市规划有所发展。巴西为发展内地经济， 动态规划理论在城市规划中实践与应用 发表时间：2019-05-23T16:15:30.983Z 来源：《基层建设》2019年第4期作者：谢洁惠 [导读] 摘要：城市发展是一个涉及面广、影响因素多的复杂过程，过分强调终极蓝图的传统规划已无法为城市发展提供可行的指引与路径，故而动态规划思想在规划实践中得到应用，因此本文对动态规划理论在城市规划中的实践与应用进行了探讨。 云浮市城市规划设计院 527399 摘要：城市发展是一个涉及面广、影响因素多的复杂过程，过分强调终极蓝图的传统规划已无法为城市发展提供可行的指引与路径，故而动态规划思想在规划实践中得到应用，因此本文对动态规划理论在城市规划中的实践与应用进行了探讨。 关键词：动态规划理论；实践；应用；城市规划 传统城市规划是以土地利用控制为核心、以发展目标和理想愿景为导向的“静态规划”，强调终极蓝图的实现，却无法提供切实可行的城市发展指引与行动路径[1]。传统规划在实施过程中疲于应对，甚至被当作经济发展的绊脚石，城市规划编制方法和管理机制面临变革与创新需求，更加关注规划的过程性与灵活性成为规划工作现实的选择，进而导致从理想蓝图到动态规划的演进[2]。随着我国经济发展从“求量”到“求质”的转变，新的发展环境愈加迫切呼唤规划创新，因此本文对动态规划理论在城市规划中的实践与应用进行了探讨。 1 动态规划背景及理论概述 1.1 动态规划的起源 在城市规划领域，至少20世纪60年代西方规划理论界就提出了系统规划、结构规划、行动规划、程序规划、程序性规划、连续性规划、渐进性规划、适应性规划、恢复性规划等具有动态规划思想的理论。其中提出连续性规划的布兰奇认为城市规划过于重视规划的终极状态而忽视了规划过程，这种观点很好地诠释了传统规划对终极蓝图过分强调的本质。国内从20世纪90年代开始有学者关注动态规划，但直到2012年“城市规划——从终极蓝图到动态规划”论坛召开，才引起广泛的关注。 1.2 动态规划的内涵 目前，学术界对动态规划概念并未形成统一的认识，一般认为城市规划编制应重视规划目标与规划路径的结合，以增强规划对外部变化的适应能力。动态规划并不否认规划的静态性，实际上“静态”才是规划的本质特征，“动态”则是相对的，“动”和“静”是辩证统一的关系。动态规划重在过程引导，通过动静结合引导和控制城市发展[3]。需强调的是，动态规划并不是一种新的规划类型，而是一种有别传统规划的思维方法和程序。传统规划思维方法是静态线性的，规划目标是一次性的终极目标，规划程序是单向直线，规划目标与实施路径没有直接关联；而动态规划思维方法是动态网络化的，规划目标是分阶段的过程目标，规划程序是反复循环的，规划目标与实施路径是结合在一起的。 1.3 动态规划的特征 动态规划的典型特征有4个，即过程性、渐进性、循环性和灵活性。过程性即动态规划把规划看作过程而非成果，规划是形成方案到落实建设的过程。渐进性强调城市发展的渐进性过程，故而城市规划目标与任务需细化分解，通过确定阶段性任务和目标，逐步完成总体目标。循环性强调规划过程的曲折性，即规划遵循设计-评价-再设计-再评价的过程，通过不断修正完善逐步完成目标。灵活性体现了规划方法和内容的弹性，根据预测结果设计有弹性的方案，并在实施过程中分阶段修正建设偏差，确保实际建设按规划目标进行。 1.4 动态规划的方法 由于动态规划理论多元化，遵循不同理论的规划方法也必然有差别，现以行动规划方法为例说明。某地以控规作为规划审批的平台和管理的依据，以行动规划作为协调工具，用于控规编制和项目审批的参考依据。控规实施过程中发现不适应发展的内容，通过行动规划进行调节修正，并通过动态维护保障控规的动态化。当出现影响控规布局的建设项目或相关部门提出新要求时，及时启动控规修改程序。由于控规处于不断动态调整状态，所以它是一个循环往复过程。规划内容随城市生长不断更新和完善，体现了有机生长的动态设计过程和全周期的评价更新过程。 2 动态规划理论在城市规划中的应用与实践 2.1 基于分期布局的动态规划 城镇发展是一个复杂连续的过程，其发展目标、发展道路、产业结构调整均具有不确定性，传统规划模式常与城镇发展过程脱节，用地布局也难以反映市场需求，所以规划方式需更新。 相比大城市，城镇经济规模较小，经济发展更具灵活性，尤其适合各种动态规划方法。分期布局是指按照城镇发展规律将总体规划分为若干期，通过分析合理规模确定发展空间，而时间与空间无严格对应关系，根据空间发展需要确定大致时间。在规划过程中，应用门槛理论、集聚扩散理论、外部形态演化过程理论对分期布局进行合理分段，第一阶段为集聚阶段，第二阶段为扩散阶段。发展规模受制于城镇自然环境、资源条件及与周围地区的关系，以城镇化率70%作为合理规模。用地布局是在城镇总体规划基本架构基础上所做出的分阶段结构性布局。为适应城镇动态发展需要，实施过程中有较大弹性。例如某城镇现时人口为10万，预计达到70%城镇化率时的人口规模不超过35万，发展年限大约在40年后。根据合理规模划分6个分期，再按时序进行排队，使每个分期布局相对完整，相邻分期之间布局相互衔接。确定每个分期的发展重点及与已建成区的关系，明晰产业区、居住区、生态绿化区的结构布局关系，明确城镇中心区的新建、扩建、改造内容等。分期布局规划的意义在于，追求动态完整，确保每个分期布局合理，兼顾远、中、近各阶段发展；每个分期发展重点不一样，例如有的分期以新区发展为主，另一个分期可能以旧城改造为主；重视发展时序的同时，注重特殊因素的灵活处理。 2.2 基于滚动性规划的动态规划 滚动性规划是指按照城镇总体规划要求，并根据城镇经济社会发展特点，确定近期建设的滚动性规划。通常，近期建设规划编制周期为一年，每年编制后3年的建设规划。由于滚动性规划中有部分内容是重复的，上一年未完成的项目、用地和基础设施等自动滚动到下一年，而规划始终处于修订和完善之中，不像常规做法那样，完成了1个建设周期才编制下一周期的规划，滚动性规划能保持规划的动态性与连续性。制定滚动性规划时，合理确定近期目标是重点，一般可通过寻找城镇近期经济发展的突破口来确定，只要认真分析城镇发展阶段和机遇条件，不难确定城镇近期经济发展目标。相关理论包括历史积累效应触发机制、小区域联动效应发展机制、大型建设项目随动效应等。以某城镇滚动性规划编制为例，分析经济与用地统计数据的相关性，再据此确定城镇年度用地规模，即根据土地利用效益来确定建设用地使用量。如果效益好，可以适当增加土地投放量；反之，则需要控制土地市场投放量。接着确定城镇建设项目，为此可根据城镇过去 动态规划基本原理 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。 要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果. 让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最短 图4-1 带权有向多段图 路径的长度(下面简称最短距离)。 我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达D点必然要经过B1和B2中的一个，所以A到D的最短距离必然等于B1到D的最短距离加上5，或是B2到D的最短距离加上2。同样的，B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2，……。 我们设G[i]为点i到点D的距离，显然G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析， 有： G[B1]=min{G[C1]+3，G[C2]+2}=5， G[B2]=min{G[C2]+7，G[C3]+4}=9， 再就有G[A]=min{G[B1]+5，G[B2]+2}=10， 所以A到D的最短距离是10，最短路径是A→B1→C2→D。 二、动态规划的术语 1．阶段 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。 在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。 2．状态 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。 在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。 过程的状态通常可以用一个或”一组数”来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。 当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。 3．无后效性 我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发 动态规划的原理及应用 班级：计科1302班 小组成员：王海涛蔡佳韦舒 蒋宪豪尹卓 完成时间：2015年5月26日 动态规划的原理及应用 学生：算法设计第5组，计算机系 指导教师：甘靖，计算机系 摘要：动态规划是解决多阶段决策过程最优化问题的一种方法。特点是把多阶段决策问题变换为一系列相互联系的单阶段问题，然后逐个加以解决。其基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优，适用于在解决问题过程中需要多次重复解决子问题的问题。其应用领域广泛，涉及到管理学、经济学、交通、军事和计算机等多个领域，将动态规划思想正确地应用于实践，将对我们的生活带来便利，甚至带给我们的社会和国家以保障。 关键词：动态规划；最优决策；应用；领域 The Principle and Application of Dynamic Programing The dynamic programing is a way to solve optimization problem in the process of multi-stage decision,whose feature is alter the multi-stage decision problems to single phase problems which are connected with each other,and then solve them one by one.The basic idea is to change the overall problem into partcial problem.And the partcial one must keep the best in order to promise the quality of overall one,which splies to repeatedly solving subproblem throughout the whole process.It is spreading to many fields,like management,economics,traffic,military and computer. Put the idea of dynamic programing correctly into practice will bring a lot of convenience to our daily life,our society as well as our country. 城市规划师必须了解的十大城市理论 城市理论是对城市应该是什么样的描述。这个问题十分复杂,存在很多学派,看法很不一致,但有一点是一致的,即城市要“以人为本”和“宜人为本”。不同的行业如城市规划、城市建筑设计、城市管理、城市环境的学者,从自己专业的角度可以提出对城市的不同理论。但是,联合国于1996年在土耳其伊斯坦布尔召开的《人居国际会议》上，通过了《关于新千年中的城市和其他人类居住区的宣言》,简称《21世纪人居议程》，其中反复强调了城市要以人为本的基本观点。主要的传统理论有: (1)城市规划理论 《雅典宪章》(1933)指出,城市规划的目的是解决居住、工作、休闲及交通四大活动问题。原则有:①城市建筑景观美化的原则;②城市生态环境原则;③城市功能布局与城市结构相协调的原则;④城市交通现代化的原则;⑤城市土地利用合理布局的原则。还有如:城市要与所处的自然背景或周围环境相融为一体的原则,建筑艺术、园林艺术与文化历史相协调的原则,要与国土规划、区域规划相协调的原则等。 重庆鲁能·星城的规划设计说明，就是以《雅典宪章》为线索进行论述： 1住宅区应该计划成安全舒适方便宁静的邻里单位。——1933年《雅典宪章》 2城市依赖地理的，经济等区域单位而发展。——1933年《雅典宪章》 3工作地点与居住地点之间的距离，应该在最少时间内可以到达。——1933年《雅典宪章》 4公园适当的地点应留作公共设施之用，设立音乐台、小图书馆、小博物馆及公共会堂等，以提倡正当的集体文娱活动。——1933年《雅典宪章》 (2)城市建筑理论 城市是以建筑为主题的,而建筑之道以人为本,建筑之美宜人为本。建筑的一切要素应以人的舒适、安全、愉悦为出发点。在有限的物质空间里,营造并延伸精神的自由空间(张开济,2000)。 (3)人居环境科学理论 吴良镛(2001.9)提出城市的五大纲领(生态、经济、技术、社会、人文艺术),五大系统(自然、人、社会、居住、支撑网络),五大层次(全球、区域、城市、社区、建筑)和一个原则(“以人为中心的生态环境”)。俞孔坚(2000.6)提出理想人居原则——天、地、人和谐的原则,即城市建筑要与自然环境相协调,要宜人为本。 (4)人类生态系统理论 城市是城市范围的,甚至是一个地区的社会、经济的自然生态系统的复合体,是人类对自然改造的人工生态系统。人类是该系统的主体，城市是人工环境(各类建筑物)和自然环境相结合的产物。城市生态系统的功能是生产(主要指商品生产和精神文明生产)和消费(原料、食物等),物质和能量的输入和输出是守恒的,但它们的价值是不守恒的,增值的主要原因与信息有关,这一过程还是非线性的。 §6 动态规划模型举例 以上讨论的优化问题属于静态的，即不必考虑时间的变化，建立的模型——线性规划、非线性规划、整数规划等，都属于静态规划。多阶段决策属于动态优化问题，即在每个阶段（通常以时间或空间为标志）根据过程的演变情况确定一个决策，使全过程的某个指标达到最优。例如： （1）化工生产过程中包含一系列的过程设备，如反应器、蒸馏塔、吸收器等，前一设备的输出为后一设备的输入。因此，应该如何控制生产过程中各个设备的输入和输出，使总产量最大。 （2）发射一枚导弹去击中运动的目标，由于目标的行动是不断改变的，因此应当如何根据目标运动的情况，不断地决定导弹飞行的方向和速度，使之最快地命中目标。 （3）汽车刚买来时故障少、耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变得故障多，油耗高，维修费用增加，经济效益差。使用时间俞长，处理价值也俞低。另外，每次更新都要付出更新费用。因此，应当如何决定它每年的使用时间，使总的效益最佳。 动态规划模型是解决这类问题的有力工具，下面介绍相关的基本概念及其数学描述。 （1）阶段 整个问题的解决可分为若干个相互联系的阶段依次进行。通常按时间或空间划分阶段，描述阶段的变量称为阶段变量，记为k 。 （2）状态 状态表示每个阶段开始时所处的自然状况或客观条件，它描述了研究过程的状况。各阶段的状态通常用状态变量描述。常用k x 表示第k 阶段的状态变量。n 个阶段的决策过程有1+n 个状态。用动态规划方法解决多阶段决策问题时，要求整个过程具有无后效性。即：如果某阶段的状态给定，则此阶段以后过程的发展不受以前状态的影响，未来状态只依赖于当前状态。 （3）决策 某一阶段的状态确定后，可以作出各种选择从而演变到下一阶段某一状态，这种选择手段称为决策。描述决策的变量称为决策变量。决策变量限制的取值范围称为允许决策集合。用)(k k x u 表示第k 阶段处于状态k x 时的决策变量，它是k x 的函数，用)(k k x D 表示k x 的允许决策集合。 （4）策略 一个由每个阶段的决策按顺序排列组成的集合称为策略。由第k 阶段的状态k x 开始到终止状态的后部子过程的策略记为)}(,),(),({)(11n n k k k k k k x u x u x u x p Λ++=。在实际问题中，可供选择的策略有一定范围，称为允许策略集合。其中达到最优效果的策略称为最优策略。 （5）状态转移方程 如果第k 个阶段状态变量为k x ，作出的决策为k u ，那么第1+k 阶段的状态变量1+k x 也被完全确定。用状态转移方程表示这种演变规律，写作(1k k T x =+k x ，)k u （6）最优值函数 指标函数是系统执行某一策略所产生结果的数量表示，是用来衡量策略优劣的数量指标，它定义在全过程和所有后部子过程上。指标函数的最优值称为最优值函数。 下面的方程在动态规划逆序求解中起着本质的作用。 动态规划的特点及其应用 摘要:本文的主要内容就是分析它的特点。第一部分首先探究了动态规划的本质，因为动态规划的特点是由它的本质所决定的。第二部分从动态规划的设计和实现这两个角度分析了动态规划的多样性、模式性、技巧性这三个特点。第三部分将动态规划和递推、搜索、网络流这三个相关算法作了比较，从中探寻动态规划的一些更深层次的特点。文章在分析动态规划的特点的同时，还根据这些特点分析了我们在解题中应该怎样利用这些特点，怎样运用动态规划。这对我们的解题实践有一定的指导意义。本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。 关键词: 动态规划，阶段 1 引言 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2 动态规划的基本思想 一般来说，只要问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解 1D/1D 动态规划优化初步 所谓1D/1D 动态规划，指的是状态数为O(n)，每一个状态决策量为O(n)的动态规划方程。直接求解的时间复杂度为O(n 2)，但是，绝大多数这样的方程通过合理的组织与优化都是可以优化到O(nlogn)乃至O(n)的时间复杂度的。这里就想讲一讲我对一些比较初步的经典的优化方法的认识。 本文中不想进行过多的证明与推导，主要想说明经典模型的建立、转化与求解方法。 由于本人认识与水平相当有限，如果出现什么错误与疏漏，还请大牛多多指正。另外，也希望大牛们更多地向我们介绍一下有关动态规划优化的更深入的东西。 本文中使用两种方式表示一个函数：f(x)与f[x]，用方括号表示的函数值可以在规划之前全部算出（常量），而用圆括号表示的函数值必须在规划过程中计算得到（变量）。无论是什么函数值一经确定，在以后的计算中就不会更改。 经典模型一：11 ()min{()[,]}x i f x f i w i x -==+ 相信这个方程大家一定是不陌生的。另外，肯定也知道一个关于决策单调性的性质： 假如用k(x)表示状态x 取到最优值时的决策，则决策单调性表述为： ,()()i j k i k j ?≤≤，当且仅当： ,[,][1,1][1,][,i j w i j w i j w i j w i j ?≤+++≤+++，对于这个性质的证明读者可以在任意一篇讲述四边形不等式的文章中找到，所以这里不再重复。而且，从实战的角度来看，我们甚至都不需要验证w 函数的这个性质，最经济也是最可靠的方法是写一个朴素算法打出决策表来观察（反正你总还是要对拍）。当然，有的时候题目要求你做一点准备工作，去掉一些明显不可能的决策，然后在应用决策单调性。这是上述性质也许会有点用处。 正如前文中所述，我们关注的重点是怎样实现决策单调性。有了决策单调性，怎样高效地实现它呢？很容易想到在枚举决策的时候，不需要从1开始，只要从k(x-1)开始就可以了，但这只能降低常数，不可能起到实质性的优化。 另一种想法是从k(x-1)开始枚举决策更新f(x)，一旦发现决策u 不如决策u+1来得好，就停止决策过程，选取决策u 作为f(x)的最终决策。这样时间是很大提高了，但可惜是不正确的。决策单调性并没有保证f(j)+w[j,x]有什么好的性质，所以这样做肯定是不对的。 刚才我们总是沿着“f(x)的最优决策是什么”这个思路进行思考，下面我们换一个角度，思考对于一个已经计算出来的状态f(j)，“f(j)能够更新的状态有哪些”。这样，每一步过程中某些状态的决策可能不是最优的，但是当算法结束的时候所有状态对应的决策一定是最优的。 一开始，只有f(1)的函数值被计算出来，于是所有状态的当前最优决策都是1。 111111111111111111111111111111111111111111111111111111111111111 现在，显然f(2)的值已经确定了：它的最有决策只能是1。我们用决策2来更新这个决策表。由于决策单调性，我们知道新的决策表只能有这样的形式： 城市规划原理考试总结 一.名词解释 1.城市：从文字字义来看，城是以武器守卫土地的意思，是一种防御性的构筑物。市是一 种交易的场所，城市是有着商业交换职能的居民点;城市与农村的主要区别,在于它们的产业结构、居民的人口规模和集聚密度的不同。 2.城乡规划：城乡规划是各级政府统筹安排城乡发展建设空间布局，保护生态和自然环境， 合理利用自然资源，维护社会公正与公平的的重要依据，具有重要公共政策的属性。3.城市规划区：城市市区、近郊区以及城市行政区域内其他因城市建设和发展需要实行规 划控制的区域。 4.城市建成区：城市行政区内实际已成片开发建设、市政公用设施和公共设施基本具备的 地区。 5.新城市主义：是城市规划中新的一个城市设计运动，始于1990年初。是基于市郊不断 蔓延、社区日趋瓦解的背景而发展起来的。新城市主义主张借鉴二战前美国小城镇和城镇规划优秀传统，塑造具有城镇生活氛围、紧凑的社区，取代郊区蔓延的发展模式。6.日照间距：前后两列房屋之间为保证后排房屋在规定的时日，获得所需日照量而保持一 定间距为日照间距。一般以冬至日中午正南太阳能照射到住宅底层窗台高度为依据，寒冷地区可以考虑太阳能照射到住宅的墙脚。 7.一化二系三结构： 一化——城市化水平； 二系——交通、通讯、供水、供电以及社会、公共服务设施系统；区域生态环境系统； 三结构——规模等级结构；职能结构；布局空间结构（空间发展轴；发展构成中的增长极；生长点的研究） 8.田园城市：是为健康、生活以及产业而设计的城市，它的规模能足以提供丰富的社会生 活，但不应超过这一程度；四周要有永久性农业地带围绕，城市的土地归公众所有，由一委员会受托管理。 9.新城：是一定区域范围内的中心城市，为其本身周围的地区服务，并且与中心城市发生 相互作用，成为城镇体系中的一个组成部分，对涌人大城市的人口起到一定的截流作用。 10.区位：指为某种活动所占据的场所在城市中所处的空间位置。各种区位理论的目的就是 为各项城市活动寻找到最佳区位，即能够获得最大利益的区位。 11.可持续发展：既满足当代人的需要，又不对后代人满足其需要的能力构成危害的发展。 12.城市性质：是指城市在国家经济和社会发展中所处的地位和所起的作用，是各城市在城 市网络以至更大范围内分工的主要职能。国标《城市规划基本术语标准》：城市性质是指“城市在一定地区、国家以至更大范围内的政治、经济与社会发展中所处的地位和所担负的主要职能。” 13.城镇化：最简单的解释是农业人口和农用土地向非农业人口和正式用地转化的现象和过 程，具体包括以下几个方面：（1）人口职业的转变（2）产业结构的转变（3）土地及地域空间的变化 14.城市形态： 15.城市用地：是城市规划区范围内赋以一定用途与功能的土地的统称，是用于城市建设和 满足城市技能运转所需要的空间。通常所说的城市用地，既是指已经建设用地利用的土地，也包括已列入城市规划区域范围内尚待开发建设的土地。 16.城市对外交通：是城市与外部保持密切联系，维持城市正常运转的重要手段和通道。通 常由铁路、公路、航运以及航空运输组成。 17.城市基础设施：最初由西方经济学家在20世纪40年代提出的概念，泛指由国家或各种 动态规划的基本概念 基本概念 设我们研究某一个过程,这个过程可以分解为若干个互相联系的阶段。每一阶段都有其初始状态和结束状态,其结束状态即为下一阶段的初始.状态。第一阶段的初始状态就是整个过程的初始状态,最后一阶段的结束状态就是整个过程的结束状态。在过程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖于其初始状态和该阶段的决策。动态规划问题就是要找出某种决策方法, 使过程达到某种最优效果。 这种把问题看作前后关联的多阶段过程称为多阶段决策过程, 可用图9.1表示。下面介绍动态规划的术语和基本概念。 (l)阶段 把所研究的过程恰当地分为若干个互相联系的相对独立过程。 (2)状态变量 用来描述系统所处状态的变量称为状态变量。通常用s k 表示第k 阶段的初始状态，则s k +1表示第k 阶段结束时(也就是第k+l 阶段开始时)过程的状态。 通常要求状态变量具有无后效性, 即过程在第k 阶段以后的变化只与该阶段结束时的状态有关, 而与系统如何到达此状态的过程无关。 (3)决策变量的状态转移方程。系统在第k 阶段中的变化过程, 通常我们并不关心，但我们希望知道该阶段的初始状态与结束状态之间的关系。我们用以影响该系统的手段，也用一个变量x k 表示，称为决策变量， 则第k 阶段结束时的状态s k +1是决策变量x k 和初始状态s k 的函数, 即 s k +1=T (s k ,x k ) (9-1) (9-1)称为状态转移方程。 (4)权函数 反映第k 阶段决策变量x k 的效益函数W k (s k ,x k ) 称为权函数。 (5)指标函数 判断整个过程优劣的数量指标称为指标函数。当第k 阶段初始状态为s k 时,设我们在此阶段及以后各阶段均采取最优策略时,所获得的效益为f k (s k ), 那么有 ))}(),,(({)(11++∈=k k k k k k D x k k s f x s W F opt s f k k (9-2) 其中opt 表示最优,按具体问题可取为max 或min , D k 是决策变量x k 的定义域;F k 是某一个函数; s k +1=T (s k ,x k ). 图9.1 现代城市规划理论 主要内容 ?一城市规划编制实践相关理论 ?二国外近现代城市规划理论的发展 ?三中外城市规划体系比较 ?四城市规划主要理论介绍 第一讲城市规划编制实践相关理论 一相关概念 二规划编制的依据 三规划的目标 四规划的实施 1. 规划的概念 （1）规划的主体——政府 ——公众利益的代表者 ——有权威对城市内各个体和组织的利益进行分配 ——有能力保证规划的实施 （2）规划的客体 ——城市的物质环境和非物质环境 为“满足市民的物质及精神需求，实现经济和社会发展目标”而开展的对城市物质或非物质设施和环境的“设计、安排”。 （3）规划的核心 ——城市和区域发展 发展是实现经济和社会目标的基础，目前我国经济社会所处的阶段更要求一发展为先。 发展是全方位和可持续的，但经济发展是基础的基础，城市规划必须充分领会和体现这个道理。 （4）规划的目标 ——经济、社会和生态环境目标 目标是规划设计的依据 城市规划的目标是通过建设布局、规划管理来实现的 目标具有多维性、层次性 （5）规划的合理性 ——专业上的科学性与管理上的可行性 符合技术标准规范，经济合理 符合法律政策规定，具有操作性 （6）规划的实施 ——政策、法律和组织的保障 法律手段 经济手段 行政手段 组织机构 2. 规划编制的依据 ◆法律依据 ◆技术依据 ◆理论依据 ◆现实依据 ◆——发展条件和机遇 （1）自然条件与自然资源 1）产业发展方向的决定 ——区域分工理论、成本比较理论 2）城市发展容量的限制 ?水、地、能源等资源的支撑能力——资源容量 ?城市及其区域对污染的自净能力——生态环境容量 ?城市合理规模——各种条件综合决定的，而非仅由经济效益决定的。（2）社会背景 ——历史与文化背景 1）历史基础 ?规律与借鉴，文化的传承 ?历史的纵横剖面分析 2）文化背景 ?城市和区域文化既包括反映地方特色的文化典籍、文学艺术、建筑风格、风俗习惯，也包括在长期历史积淀中形成的地方性社会意识、思维方式和行为 方式。前者是显性的，后者是隐性的。后者是人们心理结构的主要成分，它 存在于人们的“集体无意识”之中，制约着人们的思想、行为和社会组织的 整合功能。 ?任何一个城市或区域的协调发展，经济的健康持续增长，其基础是区域文化背景的力量。从宏观层面看,文化发展不仅以物质文化、科技文化形式直接 推动生产发展,还以政治制度形式、思想意识形态为推动区域发展提供保障。 从微观层面看,各经济主体的文化建设,对弘扬其精神,塑造形象,提高其文化 含量,从而提升竞争力具有重要意义。 （2）社会背景 ——人口与劳动力及就业问题 1）人口与劳动力的数量及其增长变化 ?城市规模的人口因素决定（经济因素？人均GDP与城市化——城市 化的低质推进） 2）人口与劳动力的素质 ?自然素质；文化素质；道德素质 3）就业与失业 ?民工潮与民工荒；伪装失业（非公开失业）与公开失业4）脑流失问题 ?教育的成本与效益，创新型城市建设 伪装失业这—概念原来并不是针对不发达经济而提出来的，最初提出这—概念的是琼.罗宾逊。她指出：由于有效需求不足而解雇工人，其结果就会使得许多工人不得不从事更加劣等的职业。她认为这些工人的边际生产率为零或为负，井把在这样低的边际生产率下的就业叫做伪装失业。 罗宾逊在给伪装失业下定义时不仅考虑到了经济发达的城市工人具有伪装失业现象，同时也指出不发达的农业部门存在伪装失业。 伪装失业动态规划基本原理
动态规划算法原理与的应用
基于动态规划的面试时间优化模型概述
运用动态规划模型解决最短路径问题
必须了解的十大城市规划理论
动态规划理论在城市规划中实践与应用
动态规划基本原理
动态规划的原理及应用
(完整版)城市规划师必须了解的十大城市理论
数学建模案例分析--最优化方法建模6动态规划模型举例
动态规划
1D1D动态规划优化初步
城市规划原理考试总结
动态规划的基本概念
现代城市规划理论