动态规划法

篁篓：　苎　∞　２０Ｍ０　７￣姗５　ｆｌ　

基于动态规划法的图像压缩算法　

马寻罄　

（宁夏大学数学计算机学院，宁夏银川７５００２１）　

摘要：介绍了动态规划法在图像压缩问题中的应用，给出了图像压缩算法的实现步骤和算法描述，　分析了算法的效率和压缩率．　关键词：图像压缩；动态规划；最优解　中围分类号：ＴＰ＇３９１　文献标识码：Ａ　文章编号：１００１—０４９１ｌ２００７）０３—００５７—０３　收稿日期：２ｏ０６一ｌ１—２４　作者简介：马子睿（１９７７一），男，宁夏银川人，讲师．　

１动态规划法　

动态规划算法的基本思想ｎ　是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问　

题的解得到原问题的解．动态规划法适用于解最优化问题．通常可以按以下步骤设计动态规划算法：　

（１）找出最优解的性质，并刻画其结构特征；　（２）递归地定义最优值；　

（３）以自底向上的方式计算出最优值；　

（４）根据计算最优值时得到的信息，构造最优解．　动态规划法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性　

质．这也是是否选择动态规划法的标准．　

２图像压缩问题　

２．１图像的表示　像素点灰度值序列｛Ｐ　，Ｐ　，Ｐ，，…，Ｐ　｝，其中Ｐ　表示像素点ｉ的灰度值，１　ｉ曼ｎ，Ｏ　ｐ　＿＜２５５，一个　

像素用８位表示．　２．２图像的变位压缩存储格式　将像素点序列｛Ｐ　，Ｐ　，Ｐ，，…，Ｐ　｝分割成ｍ个连续段ｓ　，ｓ　，ｓ３，…，ｓ　，设　

ｌ［ｉ］表示第ｉ个像素段中的像素个数，１－－＜ｌ［ｉ］＿＜２５５　ｂ［ｉ］表示第ｉ个像素段中每个像素的位数　ｉ＝１　ｔ［ｉ］＝．　Ｉ［ｋ］　ｔ：１　Ｓ［ｉ］：｛Ｐｔ…＋ｌ，ｐ　［ｉ】＋２，…，Ｐｔ［ｉ】＋ｌ［ｉ】｝，１ｓｉ　ｍ　ｈｉ：［　（　［ｉ】＋１　ｍ　ａｘ［ｉ】＋　［ｉ］Ｐｋ＋１）ｌ，１　ｉ　ｍ，ｈｊ≤ｂ［ｉ］≤８，且用３位表示ｂ［ｉ］・

　维普资讯 ５８　宁夏师范学院学报（自然科学）　２００７年５月　

例：动态规划法解静态规划问题

222

123

123

12342

329

0max

..

,,Zxxx

xxx

st

xxx12=−++

⎧++≤⎪

⎨≥⎪⎩

解：令，将问题改写为下列形式：

1122332,,yxyxyx===3

222

123

123

1234121

94

9

0max

..

,,Zyyy

yyy

st

yyy2=−++

⎧++≤⎪

⎨≥⎪⎩

(1) 按变量划分阶段，即k=1,2,3;

(2) 为决策变量；

123,,yyy

(3) 状态变量：

3322311239,,sysyysyyy==+=++≤

(4) 状态转移方程：

1123,,,

kkkssyk

+=−=

(5) 阶段效应函数：()()()22

111122223333412

94,,,,,rsyyrsyyrsyy==−2=

(6) 动态规划方程：()

()()(){}

()11

44321

12max,,,,

kkkkkkkkkkyDsfsrsyfsk

fs++∈⎧=+⎪

⎨

=⎪⎩=

用逆序法求解：

k = 3:

(){}

3322

333333212212max,

ysfsysys∗

==+=+=

k = 2:

()()

22222222

22232220011212212

44maxmax

ysysfsysysy

≤≤≤≤⎧⎫⎧

=−++=−+−+⎨⎬⎨

⎩⎭⎩⎫

⎬

⎭ 由：()

222

222221

22120

47

yysyyss′⎡⎤

−+−+=⇒=>

⎣⎦20,s8

⎢⎥可知在

2y⎡⎤⎣⎦的端点处

取极大值，从而 ()2

22

22222

2212

212112

4max,s

fssy

s∗⎧⎫+⎪⎪==+⎨⎬

−+⎪⎪⎩⎭0=

k = 1:

()()

11112222

22121110044212212

99maxmax

ysysfsysysy

≤≤≤≤⎧⎫⎧

=++=+−⎨⎬⎨

⎩⎭⎩⎫

+⎬

⎭ 由()()

112222

1111111144442124212

999,

yyysyysysy′′⎡⎤⎡⎤

+−+=−+−+=>⎢⎥⎢⎥

⎣⎦⎣⎦440

9′

知： 当

119

实验三 动态规划法

【实验目的】

应用动态规划算法思想求解矩阵连乘的顺序问题。

【实验性质】

验证性实验。

【实验要求】

应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]，A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义：

0 （ i=j ）

m[i][j]=

min{m[i][k]＋ m[k+1][j]+ni-1nknj （ i

要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【实验内容】

对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2，…，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di (1≤i≤n)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成测试。

【调试分析和心得体会】

运行依算法写出的程序并分析算法实现的时间复杂度情况。

0—1背包问题

一、实验目的

学习掌握动态规划法思想。

二、实验内容

用动态规划法求解0—1背包问题，并输出问题的最优解。0—1背包问题描述如下：

给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

三、实验条件

Jdk1.5以上

四、需求分析

对于给定n种物品和一背包。在容量最大值固定的情况下，要求装入的物品价值最大化。

五、基本思想：

动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

六、详细设计

/*

* Dynamic_Programming.java

*

* Created on 2007年6月3日, 下午4:13

*

* To change this template, choose Tools | Template Manager

* and open the template in the editor.

*/

package sunfa;

/**

*

* @author Administrator

*/

public class Dynamic_Programming {

public static void knapsack(int[] v, int[] w, int c, int[][] m)

{

/** v[] w[] c 分别是价值、重量、和背包容量数组