当前位置：文档之家 › 动态规划中的提纯

动态规划中的提纯

  • 格式：doc
  • 大小：187.00 KB
  • 文档页数：5

动态规划中的“提纯”
广东中山纪念中学 陈启峰
【概述】
动态规划中优化的方法有很多种，总的来说可以分为两种方法，即减少重复计算和减少冗余。

这两种“提纯”方法都体现了动态规划的本质特征。

减少重复计算一般从策略上着手，先找出重复计算的值，然后增添新的状态来存储该状态值；而减少冗余一般可以从状态和策略去优化，删除无用的状态和策略。

通过下面这题的分析，希望能对大家起到抛砖引玉的作用。

【关键字】
减少重复计算、减少冗余
【正文】
问题简述——求两个序列的最长公共上升子序列（LCIS ）：
给出两个长度分别为n,m 的序列A 和B 。

求出一个长度最长序列C ，满足：
① 1C < 2C < 3C …… <l C ；
② C 既是A 的子序列又是B 的子序列；
题目分析：
当看到这题的三个关键字——最长、公共、上升时，我便不禁有似曾相识的感觉。

如果抛开公共或者上升的要求，就是我们都熟悉的最长公共子序列（LCS ）问题，和最长上升子序列（LIS ）问题了！
动态规划的首要任务是确定好状态。

回顾LCS 和LIS 的状态表示方法，综合这两种状态表示方法的特性，便可以得到这题的一种状态表示：
设j i X ,表示1A 到i A 和1B 到j B 的LCIS 的长度，其中要求A i =B j 、必须选取A i 和B j 作为一个匹配。

于是得到一个状态转移方程A
⎪⎩
⎪⎨⎧+=<<<<<}1{max 1,,,,0,0,l k l k j B l B j l i k j i x X 有意义并且X 这个动态规划的时间复杂度为O (n 4)，显然是不尽人意的，需要进行“提纯”。

“提纯”方法1——减少重复计算
仔细分析不同状态的策略，易知意义相同的值会被计算了多遍。

比如：对于任意的两个状态
1,j i X 和2,j i X ，如果存在某个l 使得21j j l 、B B B <并且21、j j l <,那么在两个状态的策略选取时，}|{,i k X l k <里状态都被
计算一次。

计算某个状态集合，其实质是计算这个集合中状态值最大的状态，因此我们只需知道这个集合中的最大状态值就足够了。

而形如}|{,i k X l
k <的集合被计算多次，也就是这些集合的最大状态值被重复计算了，所以可以添增一种状态表示——}|max{,,i k X F j k j i ≤=。

于是得出双状态的状态转移方程B ：
⎪⎩⎪⎨⎧+=-<<<}1{max 1max ,1,0,k i B B j k j i F X j
k },max{,,1,j i j i j i X F F -=
这样总的时间复杂度是O (n 3),如果使用二叉查找树还可以使时间复杂度降到O (n 2logn)。

显然这样的“提纯”已经除去很多杂质了，但可别忘记还有另一把锋利的刀哦~~。

^_^
“提纯”方法2——减少冗余
冗余常常隐藏得很隐蔽，就像豪宅里的白蚁，不易被发现，所以要花多点时间和心思去发挖掘。

在状态转移方程序B 中，不难发现对于任意的一个状态
j i X ,，如果其最优策略k 小于一个j La st (表示满足j B =l B 并且j l <的最大的l ),那么
j
l a st i j i X X ,,=。

于是便产生一个猜想——对于所有状态x j i ,，若其最优策略小于last j ，都有x j i ,= x j last i ,？下面通过证明来证实这个猜想。

证明： j last i X ,是j i X ,的一个可行解：这可由j last i X ,的最优方案构造出来，只要将匹配),(j last i 换成),(j i 就可以了，如下图：
所以j last i j i X X ,,≥。

当策略j last k <,总有j last i k i X F ,
,11≤+-：因为在k i F ,1-的方案里
加上匹配边),(j last i 便可得到j last i X ,的方案。

如下图：
综上所述，如果计算了j last i X ,，就不需要计算)(1
,1j k i last k F <+-。

有了证明以后，再对状态转移方程B 进行改进，就得到了更优的状态转移方程C
⎪⎪⎩
⎪⎪⎨⎧+=-<<<}1{max 1max ,1,,,k i B B j k last last i j i F X X j k j j },max{,,1,j i j i j i X F F -=
}&|,0max{j k j B B j k k Last =<=
这个动态规划的总时间复杂度是O (n 2)，应该说是不错的。

总结
动态规划的“提纯”没有固定的形式，我们就应用它时常常需要灵感。

这种灵感不是空中楼阁，而是基于平时的思考和积累的经验。

我们如果能常总结、常思考、常创新并持之以恒，就能掌握好这种方法。

【感谢】
感谢宋新波老师、郭华阳向我提很多宝贵的意见。

【参考论文】
《充分利用问题性质——例析动态规划的“个性化”优化》——项荣璟2003论文
《减少冗余与算法优化》——胡伟栋2004论文。

合集下载

第6章动态规划

第6章动态规划

第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。

它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。

在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。

动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。

因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。

动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。

在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。

许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。

特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。

动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。

本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。

6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。

任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。

动态规划的基本原理和基本应用

动态规划的基本原理和基本应用

动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。

动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。

它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。

1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。

2.定义状态：确定存储子问题解的状态变量和状态方程。

3.确定边界条件：确定初始子问题的解，也称为边界状态。

4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。

5.求解最优解：通过遍历状态变量找到最优解。

1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。

可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。

2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。

给定一个序列，找到其中最长的递增子序列。

可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。

3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。

给定一系列矩阵，求解它们相乘的最小计算次数。

可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。

4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。

可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。

动态规划算法原理和实现

动态规划算法原理和实现

动态规划算法原理和实现动态规划是解决某些优化问题的一种算法思想，它主要针对的是那些可以分解成子问题的大问题，因此也被称作分治法。

动态规划算法的核心思想是将大问题分解成一个个小问题，然后逐步求解这些小问题并将它们组合成原问题的解。

本文将简单介绍动态规划算法的原理和实现。

一、动态规划算法的原理为了更好地理解动态规划算法的原理，我们可以以一个实例为例：假设有一个背包，它最多能装W重量的物品，现在有n种不同的物品，每种物品都有自己的重量w和价值v。

我们需要选择哪些物品放入背包中，以使得背包中物品的总价值最大。

这是一个典型的动态规划问题。

首先，我们可以把问题分解成子问题：设f(i,j)表示前i种物品放入一个容量为j的背包可以获得的最大价值。

因此，我们可以得到以下状态方程式：f(i,j) = max{f(i-1,j), f(i-1,j-w[i])+v[i]} （1≤i≤n,1≤j≤W）其中，f(i-1,j)表示不放第i种物品的最大价值，f(i-1,j-w[i])+v[i]表示放入第i种物品的最大价值。

因此，当我们计算出f(i,j)时，我们就得到了「前i种物品放入容量为j的背包的最大价值」，这也就是原问题的解。

这样，我们就可以使用动态规划算法来计算出最优解。

具体来说，我们从0开始，逐个计算出f(i,j)的值，直到计算出f(n,W)为止。

此外，我们还需要注意以下几点：1. 在计算f(i,j)的时候，我们需要使用到f(i-1,j)和f(i-1,j-w[i])这两个状态，因此我们需要先计算出f(1,j)，在此基础上计算f(2,j)，以此类推。

2. 对于一些特殊的情况，我们需要单独处理。

比如当背包容量小于某种物品重量时，我们就无法放入该物品。

3. 我们在计算f(i,j)时，有许多状态是可以复用的。

比如，当我们计算出f(i-1,j)后，我们就可以直接使用这个值来计算f(i,j)，而无需重新计算。

二、动态规划算法的实现上面我们已经介绍了动态规划算法的核心思想和实现原理，下面我们来看看具体的实现过程。

动态规划算法的原理与优化

动态规划算法的原理与优化

动态规划算法的原理与优化动态规划算法是一种优化问题求解的算法，它的基本思想是将问题分解为更小的子问题，通过求解子问题得到原问题的最优解。

1. 原理动态规划算法的基本原理是“最优子结构”。

也就是说，一个问题的最优解可由其子问题的最优解推导出。

因此，动态规划算法可以通过求解子问题来推导出整个问题的最优解。

另一个基本原理是“子问题重叠性”。

也就是说，与分治算法不同，同样的子问题可能会被多次求解。

因此，为了避免重复计算，动态规划算法可以用一个表格来存储已解决的子问题的结果。

动态规划算法的基本流程为：(1) 定义状态：定义比较小的子问题，以便于求解原问题。

(2) 描述状态转移：将原问题分解为若干个子问题，并制定状态转移方程。

(3) 边界条件：指定最小的问题的解。

(4) 递推计算：按照状态转移方程，通过已求解的子问题求解出当前问题的解。

2. 优化虽然动态规划算法可以解决很多优化问题，但在实际应用中，它也面临着一些问题。

其中最主要的问题就是时间复杂度。

由于动态规划算法需要存储已解决的子问题的结果，所以空间复杂度也可能很高。

为了避免这些问题，动态规划算法可以进行一些优化。

以下是一些常见的优化方法：(1) 状态压缩状态压缩是一种常见的空间优化方法。

当一个状态只与前一步的状态相关时，可以将状态的存储空间从二维降为一维。

这样可以大大减少存储空间，提高空间效率。

(2) 记忆化搜索动态规划算法中的状态转移方程可能会重复计算同一个子问题。

为了避免重复计算，我们可以使用记忆化搜索，将子问题的结果保存在一个数组中，每次需要计算子问题时先判断结果是否已经被计算过，如果已经计算过，直接取结果，否则进行计算，并将结果保存在数组中。

(3) 剪枝动态规划算法中可能存在一些无用的计算，通过一些剪枝技巧，可以在计算中跳过这些无用的步骤，从而减少计算量，提高效率。

以上是动态规划算法的原理与优化。

在实际应用中，通过不同的优化方法，可以进一步提高算法的效率。