随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177858
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

第十四章我想放在后面再看,先搁下。希望大家总结的一些文章也能向我推荐下,大家互相学习。

首先,还是建议看看前言:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

其次,阿门,感谢老天送给了我们这么一本圣经,看了这一章,再次感受到了《算法导论》分析问题的精辟,强悍的魅力。Orz, Orz,各种Orz。

这一章讲的是动态规划,学算法的朋友,尤其是搞ACM的,对这个策略一定非常熟悉,所以这个算法网上的分析讲解教程也是铺天盖地,大家可以多搜几篇学习学习。

动态规划(Dynamic Programming,简称DP)是通过组合子问题的解来解决问题的。

注意这里的programming不是指编程,而是指一种规划

因为DP用的太广泛了,并且书上也花了很大的篇幅来讲这一章,所以我也准备把这一章分几篇来总结,并且我不按照书上的顺序来总结,也不会全部用书上的例子。

这一章首先给出一些基础的概念,然后给出一个最基础入门的DP问题,三角形求值问题。

DP适用于子问题不是独立的情况,这样如果用分治法,也会作许多重复的工作,而DP只对子问题求解一次,将其结果保存在一张表中,从而避免了每次遇到各个子问题时重新计算的情况。

比较分治法于动态规划的区别:

分治法:将问题划分为一些独立的子问题,递归的求解各子问题,然后合并子问题的解而得到原问题的解。

eg.

MERGE-SORT(A, p, r)
1 if p < r
2   then q ← |(p + r)/2|
3        MERGE-SORT(A, p, q)
4        MERGE-SORT(A, q + 1, r)
5        MERGE(A, p, q, r)
动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题,鉴于会重复的求解各子问题,DP对每个问
只求解一遍,将其保存在一张表中,从而避免重复计算。

DP算法的设计可以分为四个步骤

①.描述最优解的结构。

②.递归定义最优解的值。

③.按自底而上的方式计算最优解的值。

④.由计算出的结果创造一个最优解。

下面来看看三角形求值这个问题:

将一个由N行数字组成的三角形,如图所以,设计一个算法,计算出三角形的由顶至底的一条路径,使该路径经过的数字总和最大。

sanjiaoxing

这是在我见过的DP题目中,算是最简单的了,我相信就算没有学过DP的也会。

将上图转化一下:

sanjiaoxing2

假设上图用map[][]数组保存。

令f[i][j]表示从顶点(1, 1)到顶点(i, j)的最大值。

则可以得到状态转移方程:

f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]

此题既适合自顶而下的方法做,也适合自底而上的方法,

当用自顶而下的方法做时,最后要在在最后一列数中找出最大值,

而用自底而上的方法做时,f[1][1]即为最大值。

所以我们将图2根据状态转移方程可以得到图3:

sanjiaoxing3

最大值是30.

很简单的DP题,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
Description: 动态规划之三角形求值问题
*/
#include <iostream>
using namespace std;
 
int map[6][6] = 
{
	{0, 0, 0, 0, 0, 0},
	{0, 7, 0, 0, 0, 0},
	{0, 3, 8, 0, 0, 0},
	{0, 8, 1, 0, 0, 0},
	{0, 2, 7, 4, 4, 0},
	{0, 4, 5, 2, 6, 5}
};
 
int f[6][6];
 
int _max(int a, int b)
{
	if(a >= b)
		return a;
	return b;
}
 
int main()
{
	memset(f, 0, sizeof(f));
	for(int i=0; i<6; ++i)
		f[5][i] = map[5][i];
	for(int i=4; i>=1; --i)
		for(int j=1; j<=i; ++j)
			f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
	for(int i=1; i<=5; ++i)
	{
		for(int j=1; j<=5; ++j)
		{
			cout.width(2);
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	cout << f[1][1] << endl;
}

结果如图:

sanjiaoxing4

下一篇会将装配线的调度。

在我独立博客上的原文:http://www.wutianqi.com/?p=2484

欢迎大家互相学习,互相进步!

posted on 2011-05-20 07:27 Tanky Woo 阅读(1709) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理