动态规划
- 格式:pdf
- 大小:346.81 KB
- 文档页数:37
动态规划的基本思想动态规划是一种常见的解决问题的算法思想,它通过将复杂的问题分解成一个个子问题,逐步求解并记录下每个子问题的解,最终得到原问题的解。
这种思想在很多领域都有广泛的应用,例如计算机科学、经济学、物理学等。
一、动态规划的定义与特点动态规划是一种分治法的改进方法,它主要用于解决具有重叠子问题和最优子结构性质的问题。
它的基本思想可以概括为“记住中间结果,以便在需要的时候直接使用”。
动态规划算法的特点包括:1. 问题可以分解为若干个重叠的子问题;2. 子问题的解可以通过已知的子问题解来求解,且子问题的解可以重复使用;3. 需要使用一个数据结构(通常是一个矩阵)来存储子问题的解,以便在需要时直接取出。
二、动态规划的基本步骤动态规划算法通常可以分为以下几个基本步骤:1. 确定问题的状态:将原问题转化为一个或多个子问题,并定义清楚每个子问题的状态是什么。
2. 定义问题的状态转移方程:找出子问题之间的关系,即如何通过已知的子问题解来解决当前问题。
3. 设置边界条件:确定最简单的子问题的解,即边界条件。
4. 计算子问题的解并记录:按顺序计算子问题的解,并将每个子问题的解记录下来,以便在需要时直接使用。
5. 由子问题的解得到原问题的解:根据子问题的解和状态转移方程,计算得到原问题的解。
三、动态规划的实例分析为了更好地理解动态规划的基本思想,我们以求解斐波那契数列为例进行分析。
问题描述:斐波那契数列是一个经典的数学问题,它由以下递推关系定义:F(n) = F(n-1) + F(n-2),其中F(0) = 0,F(1) = 1。
解决思路:根据递推关系,可以将问题分解为求解F(n-1)和F(n-2)两个子问题,并将子问题的解累加得到原问题的解。
根据以上思路,可以得到以下的动态规划算法实现:1. 确定问题的状态:将第n个斐波那契数定义为一个状态,记为F(n)。
2. 定义问题的状态转移方程:由递推关系F(n) = F(n-1) + F(n-2)可得,F(n)的值等于前两个斐波那契数之和。
动态规划的基本原理和基本应用动态规划(Dynamic Programming)是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。
动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题,以减少不必要的重复计算。
它在计算机科学和数学中具有广泛的应用,尤其是在优化、组合数学和操作研究等领域。
1.确定最优子结构:将原问题分解为较小的子问题,并且子问题的最优解能够推导出原问题的最优解。
2.定义状态:确定存储子问题解的状态变量和状态方程。
3.确定边界条件:确定初始子问题的解,也称为边界状态。
4.递推计算:利用状态方程将子问题的解计算出来,并存储在状态变量中。
5.求解最优解:通过遍历状态变量找到最优解。
1.背包问题:背包问题是动态规划的经典应用之一、它有多种变体,其中最基本的是0/1背包问题,即在限定容量的背包中选择物品,使得所选物品的总价值最大。
可以使用动态规划的思想来解决背包问题,确定状态为背包容量和可选物品,递推计算每个状态下的最优解。
2. 最长递增子序列:最长递增子序列(Longest Increasing Subsequence)是一种常见的子序列问题。
给定一个序列,找到其中最长的递增子序列。
可以使用动态规划来解决这个问题,状态可以定义为以第i个元素为结尾的最长递增子序列的长度,并递推计算每个状态的解。
3.矩阵链乘法:矩阵链乘法是一种优化矩阵连乘计算的方法。
给定一系列矩阵,求解它们相乘的最小计算次数。
可以使用动态规划解决矩阵链乘法问题,状态可以定义为矩阵链的起始和结束位置,递推计算每个状态下最小计算次数。
4.最短路径问题:最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。
可以使用动态规划解决最短路径问题,状态可以定义为起始节点到一些节点的最短距离,递推计算每个状态的最优解。
动态规划原理动态规划(Dynamic Programming)是一种在数学、计算机科学和经济学等领域中使用的优化方法。
它是一种将复杂问题分解成更小的子问题来解决的方法,通过将问题分解成相互重叠的子问题,动态规划可以大大简化问题的解决过程,提高算法的效率。
在本文中,我们将介绍动态规划的原理及其应用。
动态规划的基本原理是将原问题分解成相互重叠的子问题,通过解决子问题来解决原问题。
在动态规划中,我们通常使用一个表格来存储子问题的解,以便在解决更大的问题时能够重复利用已经计算过的结果。
动态规划通常用于解决具有重叠子问题和最优子结构性质的问题,这些问题可以被分解成相互重叠的子问题,并且最优解可以通过子问题的最优解来计算得到。
动态规划的关键步骤包括定义子问题、构建状态转移方程、初始化边界条件和计算最优解。
首先,我们需要定义子问题,即将原问题分解成更小的子问题。
然后,我们需要构建状态转移方程,即找到子问题之间的递推关系,以便能够通过子问题的解来计算更大的问题的解。
接下来,我们需要初始化边界条件,即确定最小的子问题的解。
最后,我们可以通过自底向上或自顶向下的方式计算最优解。
动态规划的应用非常广泛,包括但不限于最短路径问题、背包问题、编辑距离、最长公共子序列、最大子数组和斐波那契数列等。
这些问题都具有重叠子问题和最优子结构性质,因此可以通过动态规划来解决。
动态规划在实际应用中往往能够大大提高算法的效率,因此受到了广泛的关注和应用。
总之,动态规划是一种将复杂问题分解成更小的子问题来解决的优化方法。
通过定义子问题、构建状态转移方程、初始化边界条件和计算最优解,动态规划可以大大简化问题的解决过程,提高算法的效率。
它在各个领域都有着广泛的应用,是一种非常重要的算法设计思想。
希望本文能够帮助读者更好地理解动态规划的原理及其应用。
以上就是关于动态规划原理的介绍,希望对您有所帮助。
动态规划算法的详细原理及使用案例一、引言动态规划是一种求解最优化问题的算法,它具有广泛的应用领域,如机器学习、图像处理、自然语言处理等。
本文将详细介绍动态规划算法的原理,并提供一些使用案例,以帮助读者理解和应用这一算法的具体过程。
二、动态规划的基本原理动态规划算法通过将问题分解为多个子问题,并利用已解决子问题的解来求解更大规模的问题。
其核心思想是利用存储技术来避免重复计算,从而大大提高计算效率。
具体来说,动态规划算法通常包含以下步骤:1. 定义子问题:将原问题分解为若干个子问题,这些子问题具有相同的结构,但规模更小。
这种分解可以通过递归的方式进行。
2. 定义状态:确定每个子问题的独立变量,即问题的状态。
状态具有明确的定义和可计算的表达式。
3. 确定状态转移方程:根据子问题之间的关系,建立状态之间的转移方程。
这个方程可以是简单的递推关系式、递归方程或其他形式的方程。
4. 解决问题:使用递推或其他方法,根据状态转移方程求解每个子问题,直到获得最终解。
三、动态规划的使用案例1. 背包问题背包问题是动态规划算法的经典案例之一。
假设有一个背包,它能容纳一定重量的物品,每个物品有对应的价值。
目的是在不超过背包总重量的前提下,选取最有价值的物品装入背包。
这个问题可以通过动态规划算法来求解。
具体步骤如下:(1)定义问题:在不超过背包容量的限制下,选取物品使得总价值最大化。
(2)定义状态:令dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值。
(3)状态转移方程:dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]),其中w[i]为第i个物品的重量,v[i]为第i个物品的价值。
(4)解决问题:根据状态转移方程依次计算每个子问题的解,并记录最优解,直到获得最终答案。
2. 最长公共子序列最长公共子序列(Longest Common Subsequence,简称LCS)是一种经典的动态规划问题,它用于确定两个字符串中最长的共同子序列。
动态规划的基本概念与方法动态规划(Dynamic Programming,简称DP)是解决一类最优化问题的一种方法,也是算法设计中的重要思想。
动态规划常用于具有重叠子问题和最优子结构性质的问题。
它将问题分解为子问题,并通过求解子问题的最优解来得到原问题的最优解。
动态规划的基本概念是“最优子结构”。
也就是说,一个问题的最优解可以由其子问题的最优解推导出来。
通过分解问题为若干个子问题,可以形成一个递归的求解过程。
为了避免重复计算,动态规划使用一个表格来保存已经计算过的子问题的解,以便后续直接利用。
这个表格也被称为“记忆化表”或“DP表”。
动态规划的基本方法是“状态转移”。
状态转移指的是,通过已求解的子问题的解推导出更大规模子问题的解。
常用的状态转移方程可以通过问题的递推关系定义。
通过定义好状态转移方程,可以通过迭代的方式一步步求解问题的最优解。
在动态规划中,通常需要三个步骤来解决问题。
第一步,定义子问题。
将原问题划分为若干个子问题。
这些子问题通常与原问题具有相同的结构,只是规模更小。
例如,对于计算斐波那契数列的问题,可以定义子问题为计算第n个斐波那契数。
第二步,确定状态。
状态是求解问题所需要的所有变量的集合。
子问题的解需要用到的变量就是状态。
也就是说,状态是问题(解决方案)所需要的信息。
第三步,确定状态转移方程。
状态转移方程通过已求解的子问题的解推导出更大规模子问题的解。
通常情况下,状态转移方程可以通过问题的递推关系确定。
在实际应用中,动态规划常用于求解最优化问题。
最优化问题可以归纳为两类:一类是最大化问题,另一类是最小化问题。
例如,最长递增子序列问题是一个典型的最大化问题,而背包问题是一个典型的最小化问题。
动态规划的优势在于可以解决许多复杂问题,并且具有可行的计算复杂度。
但是,动态规划也有一些限制。
首先,动态规划要求问题具有重叠子问题和最优子结构性质,不是所有问题都能够满足这两个条件。
其次,动态规划需要存储计算过的子问题的解,对于一些问题来说,存储空间可能会非常大。
动态规划复杂度分析动态规划(Dynamic Programming)是一种常用的解决优化问题的方法,通过将问题分解为若干子问题,并将子问题的答案保存起来,避免重复计算,从而提高算法效率。
在实际应用中,我们需要对动态规划算法的时间复杂度和空间复杂度进行准确的分析,以便评估算法的性能和可行性。
一、动态规划的时间复杂度分析动态规划算法的时间复杂度取决于以下两个因素:1. 子问题数量:动态规划算法将原问题分解为若干子问题,并通过求解子问题的答案来解决原问题。
因此,子问题的数量直接关系到算法的时间复杂度。
如果每个子问题的求解时间相同且规模相等,那么子问题数量的增加会导致时间复杂度的线性增长。
2. 单个子问题的求解时间:每个子问题的求解时间是动态规划算法时间复杂度的另一个重要因素。
在实际应用中,子问题的求解时间可能不同,这取决于子问题之间的关系和具体的求解方法。
一般来说,如果每个子问题的求解时间相同,则总体的时间复杂度为子问题数量乘以单个子问题的求解时间。
基于以上分析,可以得出结论:动态规划算法的时间复杂度与子问题数量和单个子问题的求解时间相关,可以用O(N*M)表示,其中N 为子问题的数量,M为单个子问题的求解时间。
二、动态规划的空间复杂度分析动态规划算法的空间复杂度取决于以下两个因素:1. 子问题数量:与时间复杂度类似,子问题的数量也会影响算法的空间复杂度。
每个子问题需要保存其对应的答案,因此子问题的数量直接关系到算法的空间需求。
2. 单个子问题的空间需求:每个子问题需要保存其对应的答案,因此单个子问题的空间需求是算法空间复杂度的重要因素。
不同的子问题可能需要不同的空间来保存求解结果。
根据以上讨论,可以得出结论:动态规划算法的空间复杂度与子问题数量和单个子问题的空间需求相关,可以用O(N*M)表示,其中N为子问题的数量,M为单个子问题的空间需求。
三、动态规划算法的优化和改进在实际应用中,为了降低动态规划算法的时间复杂度和空间复杂度,可以采取以下优化和改进措施:1. 优化状态转移方程:动态规划算法的核心是状态转移方程,通过优化方程的表达和求解方式,可以减少算法的时间复杂度。
什么是动态规划?⼀、基本思想态规划算法的基本思想与分治法类似,都是将问题⼤问题拆分为⼩问题,通过⼩问题的求解来得到最后的解。
与分治法不同的是,分治法是分⽽治之,分治法将⼤问题拆分为相同性质的⼦问题,最后合并⼦问题的解来构成最终解。
⽽动态规划是,将⼦问题拆解后,按顺序求解⼦问题,前⾯阶段的求解为后⼀阶段提供有⽤信息,通过动态的选择来到达最终解。
⽤图来表⽰就是如下所⽰:⼆、适⽤情况(1)最优化原理:如果问题的最优解所包含的⼦问题的解也是最优的,就称该问题具有最优⼦结构,即满⾜最优化原理。
(2)⽆后效性:即某阶段状态⼀旦确定,就不受这个状态以后决策的影响。
也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3)有重叠⼦问题:即⼦问题之间是不独⽴的,⼀个⼦问题在下⼀阶段决策中可能被多次使⽤到。
(该性质并不是动态规划适⽤的必要条件,但是如果没有这条性质,动态规划算法同其他算法相⽐就不具备优势)----摘⾃百度百科三、求解步骤动态规划中有三个⾮常重要的概念:最优⼦结构、边界、状态转移公式。
最优⼦结构:最优⼦结构指的是,问题的最优解包含⼦问题的最优解。
反过来说就是,我们可以通过⼦问题的最优解,推导出问题的最优解。
边界:就是问题的出⼝。
状态转移公式:动态规划问题的这⼀阶段的最优解是可以通过前⾯阶段的解和上⼀阶段的决策推导出来的。
这个推导过程就是⼀个状态转移公式我们通常按照如下4个步骤设计⼀个动态规划算法:1.刻画⼀个最优解的结构特征2.递归地定义最优解的值3.计算最优解的值,通常采⽤⾃底向上的⽅法(采⽤⼀张表格记录之前的状态)4.利⽤计算出的信息构造⼀个最优解我们之前的和也是⼀样的求解步骤。
以硬币找零问题为例:⾸先,⾯对⼀枚新的硬币,我们有两个选择:使⽤和不使⽤。
构成当前阶段的最优解 = min{使⽤这枚硬币的解,不使⽤这枚硬币的解} ----(1.刻画⼀个最优解的结构特征)然后,我们就得到转移⽅程 Value(i) = min {Value(i-1), Value(s-c[i])) + 1} ---- (2.递归地定义最优解的值)之后我们从找零1⾓开始算起,⼀直到达我们想要找零的数⽬。
什么是动态规划动态规划( D ynamic P rogramming ,所以我们简称动态规划为 DP )是的⼀个分⽀,是求解决策过程(decision process) 最优化的数学⽅法。
20 世纪 50 年代初数学家R.E.Bellman 等⼈在研究多阶段决策过程 (multistep decision process) 的优化问题时,提出了著名的最优化原理 (principle of optimality),把多阶段过程转化为⼀系列单阶段问题,利⽤各阶段之间的关系,逐个求解,创⽴了解决这类过程优化问题的新⽅法 —— 动态规划。
1957 年出版了他的名著《 Dynamic Programming 》,这是该领域的第⼀本著作。
动态规划算法通常基于⼀个递推公式及⼀个或多个初始状态。
当前⼦问题的解将由上⼀次⼦问题的解推出。
使⽤动态规划来解题只需要多项式时间复杂度,因此它⽐回溯法、暴⼒法等要快许多。
说了这么多术语,想必⼤家都很头疼,现在让我们通过⼀个例⼦来了解⼀下DP 的基本原理。
⾸先,我们要找到某个状态的最优解,然后在它的帮助下,找到下⼀个状态的最优解。
这句话暂时理解不了没关系,请看下⾯的例⼦ :如果我们有⾯值为1 元、 3 元和 5 元的硬币若⼲枚,如何⽤最少的硬币凑够 11 元?我们凭直观感觉告诉⾃⼰,先选⾯值最⼤,因此最多选 2枚 5 元的硬币,现在是 10 元了,还差⼀元,接下来我们挑选第⼆⼤的 3 元硬币,发现不⾏( 10+3=13 超了),因此我们继续选第三⼤的硬币也就是 1元硬币,选⼀个就可以( 10+1=11 ),所以总共⽤了 3 枚硬币凑够了 11 元。
这就是贪⼼法,每次选最⼤的。
但是我们将⾯值改为 2 元, 3 元和 5 元的硬币,再⽤贪⼼法就不⾏了。
为什么呢?按照贪⼼思路,我们同样先取 2 枚最⼤ 5 元硬币,现在 10 元了,还差⼀元,接下来选第⼆⼤的,发现不⾏,再选第三⼤的,还是不⾏,这时⽤贪⼼⽅法永远凑不出 11 元,但是你仔细看看,其实我们可以凑出 11 元的, 2 枚 3元硬币和 1 枚五元硬币就⾏了,这是⼈经过思考判断出来了的,但是怎么让计算机算出来呢?这就要⽤动态规划的思想:⾸先我们思考⼀个问题,如何⽤最少的硬币凑够i 元 (i<11) ?为什么要这么问呢?两个原因: 1. 当我们遇到⼀个⼤问题时,总是习惯把问题的规模变⼩,这样便于分析讨论。
运筹学中的动态规划原理-教案一、引言1.1动态规划的基本概念1.1.1动态规划的定义:动态规划是一种数学方法,用于求解多阶段决策过程的最优化问题。
1.1.2动态规划的特点:将复杂问题分解为简单的子问题,通过求解子问题来得到原问题的最优解。
1.1.3动态规划的应用:广泛应用于资源分配、生产计划、库存控制等领域。
1.2动态规划的基本原理1.2.1最优性原理:一个最优策略的子策略也是最优的。
1.2.2无后效性:某阶段的状态一旦确定,就不受这个状态以后决策的影响。
1.2.3子问题的重叠性:动态规划将问题分解为子问题,子问题之间往往存在重叠。
1.3动态规划与静态规划的关系1.3.1静态规划:研究在某一特定时刻的最优决策。
1.3.2动态规划:研究在一系列时刻的最优决策。
1.3.3动态规划与静态规划的区别:动态规划考虑时间因素,将问题分解为多个阶段进行求解。
二、知识点讲解2.1动态规划的基本模型2.1.1阶段:将问题的求解过程划分为若干个相互联系的阶段。
2.1.2状态:描述某个阶段的问题情景。
2.1.3决策:在每个阶段,根据当前状态选择一个行动。
2.1.4状态转移方程:描述一个阶段的状态如何转移到下一个阶段的状态。
2.2动态规划的基本算法2.2.1递归算法:通过递归调用求解子问题。
2.2.2记忆化搜索:在递归算法的基础上,保存已经求解的子问题的结果,避免重复计算。
2.2.3动态规划算法:自底向上求解子问题,将子问题的解存储在表格中。
2.2.4动态规划算法的优化:通过状态压缩、滚动数组等技术,减少动态规划算法的空间复杂度。
2.3动态规划的经典问题2.3.1背包问题:给定一组物品,每种物品都有自己的重量和价值,求解在给定背包容量下,如何选择物品使得背包中物品的总价值最大。
2.3.2最长递增子序列问题:给定一个整数序列,求解序列的最长递增子序列的长度。
2.3.3最短路径问题:给定一个加权有向图,求解从源点到目标点的最短路径。
动态规划的基本原理和基本应用
一、动态规划的基本原理
动态规划(Dynamic Programming)是一种运用在运筹学中的一种数
学规划方法。
它的基本思路是:将一个复杂的求解问题分解成若干个更简
单的子问题,再从这些子问题出发,求出各子问题的解,回溯到原问题求
出原问题的解,通常情况下,动态规划的核心是对于每一个子问题只求解
一次,存储子问题的解,避免了重复求解子问题。
1.最优子结构性质:具有最优子结构性质的问题可以用动态规划求解,即如果一些问题的求解最优解由其子问题的最优解组合而成,那么该问题
也是最优的;
2.重复子问题性质:具有重复子问题性质的问题可以用动态规划求解,即一些问题的解可以由重复的子问题的解组合而成;
3.边界条件:求解动态规划的问题要求有边界条件,即知道求解问题
的初始和终止条件;
4.最优化原理:即求解问题的全局最优解可以由求子问题的最优解组
合而成,求解问题从最优解的最终状态开始,逐渐迭代至初始状态;
5.无后效性:即状态仅取决于其之前的几个状态,不受其之后状态的
影响。
二、动态规划的基本应用
1.适用于短路径问题:在交通运输、通信网络中。
动态规划动态规划模型的分类:以“时间”角度可分成:离散型和连续型。
从信息确定与否可分成:确定型和随机型。
从目标函数的个数可分成:单目标型和多目标型。
动态规划的基本模型1.多阶段决策过程的最优化问题2.动态规划的基本概念3.最优化原理与无后效性多阶段决策过程的最优化问题在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。
当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,如下图所示:最短路径问题。
下图给出了一个地图,地图中的每个顶点代表一个城市,两个城市间的一条连线代表道路,连线上的数值代表道路的长度。
现在想从城市A到达城市E,怎样走路程最短?最短路程的长度是多少?把A到E的全过程分成四个阶段,用K表示阶段变量,第1阶段有一个初始状态A,有两条可供选择的支路A-B1、A-B2;第2阶段有两个初始状态B1、B2,B1有三条可供选择的支路,B2有两条可供选择的支路……。
用DK(X,X+1)表示在第K 阶段由初始状态X到下阶段的初始状态X+1的路径距离,FK(X)表示从第K阶段的X到终点E的最短距离。
在上例的多阶段决策问题中,各个阶段采取的决策,一般来说是与阶段有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。
动态规划的基本概念阶段和阶段变量:用动态规划求解一个问题时,需要将问题的全过程恰当地分成若干个相互联系的阶段,以便按一定的次序去求解。
描述阶段的变量称为阶段变量,通常用K表示,阶段的划分一般是根据时间和空间的自然特征来划分,同时阶段的划分要便于把问题转化成多阶段决策过程,如上题中,可将其划分成4个阶段,即K = 1,2,3,4。
动态规划的基本概念状态和状态变量:某一阶段的出发位置称为状态,通常一个阶段包含若干状态。
一般地,状态可由变量来描述,用来描述状态的变量称为状态变量。
如上题中,C3是一个状态变量。
动态规划的基本概念决策、决策变量和决策允许集合:在对问题的处理中作出的每种选择性的行动就是决策。
即从该阶段的每一个状态出发,通过一次选择性的行动转移至下一阶段的相应状态。
一个实际问题可能要有多次决策和多个决策点,在每一个阶段的每一个状态中都需要有一次决策,决策也可以用变量来描述,称这种变量为决策变量。
在实际问题中,决策变量的取值往往限制在某一个范围之内,此范围称为允许决策集合。
如上题中,F3(C3)就是一个决策变量。
动态规划的基本概念策略和最优策略:所有阶段依次排列构成问题的全过程。
全过程中各阶段决策变量所组成的有序总体称为策略。
在实际问题中,从决策允许集合中找出最优效果的策略成为最优策略。
动态规划的基本概念状态转移方程前一阶段的终点就是后一阶段的起点,对前一阶段的状态作出某种决策,产生后一阶段的状态,这种关系描述了由k阶段到k+1阶段状态的演变规律,称为状态转移方程。
最优化原理与无后效性动态规划的最优化原理。
作为整个过程的最优策略具有:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略的性质。
也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结构的性质,也就是说一个问题的最优解只取决于其子问题的最优解,而非最优解对问题的求解没有影响。
最优化原理与无后效性所谓无后效性原则,指的是这样一种性质:某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。
也就是说,“未来与过去无关”,当前的状态是此前历史的一个完整的总结,此前的历史只能通过当前的状态去影响过程未来的演变。
对于不能划分阶段的问题,不能运用动态规划来解;对于能划分阶段,但不符合最优化原理的,也不能用动态规划来解;既能划分阶段,又符合最优化原理的,但不具备无后效性原则,还是不能用动态规划来解;误用动态规划程序设计方法求解会导致错误的结果。
动态规划的设计划分阶段:按照问题的时间或空间特征,把问题划分为若干个阶段。
确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。
当然,状态的选择要满足无后效性。
确定决策并写出状态转移方程。
寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
问题分析怀特先生需要作出一系列决策:对于每个舞步i,选择他移动的脚foot[i],并移动到目(输入数据,已知)。
一个决策序标位置Ai列对应一个可行解,而他只需要从中选出体力耗费最少的一种。
对于每个舞步i,怀特应根据什么来进行决策呢?根据他以前作出的决策吗?显然不是。
根据他已经耗费的体力吗?也不是。
稍微分析一下就可以看出:只需要根据他现在双脚的位置。
只有这个决定了他今后的决策。
根据这个性质,又可以用递归的思路解题:枚举第i次所作出的决策,计算出达到的状态s,递归的从s出发进行动态决策。
状态转移方程用E(a,b)表示从位置a移动到位置b需要花费的体力,a[k]表示舞曲中第k个箭头的编号。
d[x,y,k]=min{ d[a[k],y,k+1]+E(x,a[k]) ,d[x,a[k],k+1]+E(y,a[k]) }状态变量x k -第k 阶段初分配者手中拥有的设备台数.由题意可知x 0 = M ,x N+1 = 0资源分配问题阶段k 的准则函数为共有N 个工厂,可以把问题分解为N 个阶段:当阶段k =N 时,把手中设备分配给工厂N ;当阶段k =N -1时,把手中设备分配给工厂N -1;依次类推;在任意阶段k 时,把手中设备分配给工厂k ;当阶段k =1时,把手中设备分配给工厂1.决策变量u k -第k 阶段分配给工厂k 的设备台数()k k x u ≤≤0kk k u x x −=+1)(),(k k k k k u g u x v =状态转移方程资源分配问题用f k (x k )表示将手中资源x k 分配给工厂k ,k +1,…, N 时的最大利润,原问题即为计算f 1(M )M=4,N=3,边界条件f 4(x 4) = f 4(0) =0⎩⎨⎧=−=+=++++≤≤.0)(,1,,1,)],()([max )(11110N N k k k k x u k k x f N N k x f u g x f kk L k =3时:(增函数))()]0()([max )(3343303333x g f u g x f x u =+=≤≤;0)0()0(33==g f ;3)1()1(33==g f ;5)2()2(33==g f ;7)3()3(33==g f 8)4()4(33==g f 具体计算(例)资源分配问题k =2时:)]()([max )]()([max )(22322033220222222u x f u g x f u g x f x u xu −+=+=≤≤≤≤;000)0()0()]0()([max )0(3223220022=+=+=−+=≤≤f g u f u g f u ;3}02,30max{)}0()1(),1()0(max{)]1()([max )1(323223221022=++=++=−+=≤≤f g f g u f u g f u ;5}05,32,50max{)}0()2(),1()1(),2()0(max{)]2()([max )2(32323223222022=+++=+++=−+=≤≤f g f g f g u f u g f u ;8}06,35,52,70max{)}0()3(),1()2(),2()1(),3()0(max{)]3()([max )3(3232323223223022=++++=++++=−+=≤≤f g f g f g f g u f u g f u ;10}08,36,55,72,80max{)}0()4(),1()3(),2()2(),3()1(),4()0(max{)]4()([max )4(323232323223224022=+++++=+++++=−+=≤≤f g f g f g f g f g u f u g f u资源分配问题k =1时:)]()([max )]()([max )(11211022110111111u x f u g x f u g x f x u xu −+=+=≤≤≤≤.12}07,37,56,84,100max{)}0()4(),1()3(),2()2(),3()1(),4()0(max{)]4()([max )4(212121212112114011=+++++=+++++=−+=≤≤f g f g f g f g f g u f u g f u 最优解,最大利润为.1,2,1*3*2*1===u u u 12)4(1*==f z 推广1:二维(或多维)资源分配问题推广2:非线性整数规划问题,如:+∈=++−−−++=Zx x x x x x t s x x x x x x z 321321321232221,,4..5342min M=4, N=312111)(u u u g −=2222232)(u u u g −=3233354)(u u u g −=例(Single-level Uncapacitated Lotsizing)某工厂生产某种产品用以满足市场需求,且已知在时段t 中的市场需求为d t . 在某时段t , 如果开工生产, 则生产开工所需的生产准备费为s t , 单件产品的生产费为c t . 在某时段t 期末, 如果有产品库存, 单件产品的库存费为h t . 假设初始库存为0, 不考虑能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且使总费用最小? (Wagner –Whitin,1958)单产品、无能力限制的批量问题假设在时段t , 产品的生产量为x t , 期末产品的库存为I t (I 0 =0); 用二进制变量y t 表示在时段t 工厂是否进行生产准备. .,,2,1,0,,0,,,2,1,0,0,0,1,,,2,1,..)(min 011T t I x I T t x x y T t d I x I t s I h x c y s z t t t t t t t t t t t t t t Tt t L L L =≥==⎩⎨⎧=>===−+++=−=∑可以只考虑当c t 为常数,目标函数变为单产品、无能力限制的批量问题可以证明:一定存在满足条件的最优解.假设费用均非负,则在最优解中,即用f t 表示当t 时段初始库存为0时,从t 时段到T 时段的子问题的最优费用值最优值(费用)为f 1 . 计算复杂性为00==T I I ∑∑===Tt tT t t dx 11)(1t t t Tt t I h y s z +=∑=)1(01T t x I t t ≤≤=−{}T t t t t t t d d d d d d x ++++∈++L L 11,,,,0⎪⎪⎩⎪⎪⎨⎧≤≤⎪⎩⎪⎨⎧>++===∑∑−+=−=+≤≤+++.1,0,][min .0,,01111111T t d f h d s d f f f t t i i t j j i t T t t t t T τττ)(2T O例题三:排队买票问题程序的实现BuyTicks(T, R)1 n ←length[T]2f[0] ←03 f[1] ←T[1]4 for i ←2 to n do5f[i] ←f[i-2]+R[i-1]6if f[i]> f[i-1]+T[i] then7 f[i] ←f[i-1]+T[i]8 return f例题四:传球游戏上体育课的时候,小蛮的老师经常带着同学们一起做游戏。