动态规划算法-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

动态规划算法

简介:
斐波纳契数列F(n)

n

0

1

2

3

4

5

6

7

8

9

10

F(n)

1

1

2

3

5

8

13

21

34

55

89

递归 vs 动态规划

递归版本(太慢):

int f(int n)
{
    if(n <= 1) return 1;
    else return f(n-1)+f(n-2);
}

动态规划版本(有效率!算法复杂度是 O(n)):

int a[1000];
int f(int n)
{
    a[0]=a[1]=1;
    for(int i=2; i<=n; i++)
        a[i]=a[i-1]+a[i-2];
    return a[n];
}

方法概要

构造一个公式,它表示一个问题的解是与它的子问题的 解相关的公式.   E.g.  F(n) = F(n-1) + F(n-2).

为这些子问题做索引 ,以便它们能够在表中更好的存储与检索 (i.e., 数组array[])

以自底向上的方法来填写这表格; 首先填写最小子问题的解.

这就保证了当我们解决一个特殊的子问题时, 可以利用比它更小的所有可利用的 子问题的解.

动态规划算法原理

算法思想:

将待求解的问题分解成若干个子问题,并存储子问题的解而避免计算重复的子问题,并由子问题的解得到原问题的解。

动态规划算法通常用于求解具有某种最优性质的问题。

动态规划算法的基本要素:最优子结构性质和重叠子问题。

原理:

最优子结构性质:问题的最优解包含着它的子问题的最优解。即不管前面的策略如何,此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。

重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些问题被反复计算多次。对每个子问题只解一次,然后将其解保存起来,以后再遇到同样的问题时就可以直接引用,不必重新求解。

解决问题的基本特征:

1. 动态规划一般解决最值(最优,最大,最小,最长……)问题;

2. 动态规划解决的问题一般是离散的,可以分解(划分阶段)的;

3. 动态规划解决的问题必须包含最优子结构,即可以由(n-1)的最优推导出n的最优

解决问题的基本步骤:

动态规划算法的4个步骤:

1. 刻画最优解的结构特性. (一维,二维,三维数组)

2. 递归的定义最优解. (状态转移方程)

3. 以自底向上的方法来计算最优解.

4. 从计算得到的解来构造一个最优解.

举例实战

例题一.   斐波纳契数列F(n)

步骤1:用F(n)表示在斐波纳契数列中第n个数的值;

步骤2:状态转移方程:

 

步骤3:以自底向上的方法来计算最优解

n

0

1

2

3

4

5

6

7

8

9

10

F(n)

1

1

2

3

5

8

13

21

34

55

89

步骤4:在数组中分析构造出问题的解;

例题二.   输入n,求出n!

步骤1:用F(n)表示n!的值;

步骤2:状态转移方程:

步骤3:以自底向上的方法来计算最优解

n

0

1

2

3

4

5

6

7

8

9

10

F(n)

1

1

2

6

24

120

720

       

例题三:排队买票问题

一场演唱会即将举行。现有n个歌迷排队买票,一个人买一张,而售票处规定,一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间 Ti(1≤i≤n),队伍中相邻的两位歌迷(第j个人和第j+1个人)也可以由其中一个人买两张票,而另一位就可以不用排队了,则这两位歌迷买两张票的时 间变为Rj,假如Rj<Tj+Tj+1,这样做就可以缩短后面歌迷等待的时间,加快整个售票的进程。现给出n, Tj和Rj,求使每个人都买到票的最短时间和方法。

分析:

如果前i个人买票的最优买票方式一确定,比如第i-1个人买一张票,则前i-1个人的买票方式也一定是最优的。即问题的最优解包含子问题的最优解。

步骤1:用F(i)表示前i个人买票的最优方式,即所需最短时间;现在要决定F(i)需要考虑两种情况:

(1)第i个人的票自己买

(2)第i个人的票由第i-1个人买

步骤2:状态转移方程:

步骤3:以自底向上的方法来计算最优解

程序的实现(伪代码):

BuyTicks(T, R)
1    n ← length[T] 
2    f[0] ← 0
3    f[1] ← T[1]
4    for i ← 2 to n do 
5                 f[i] ← f[i-2]+R[i-1]
6                 if  f[i] > f[i-1]+T[i] then 
7                     f[i] ← f[i-1]+T[i]
8    return f

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章