《算法导论》— Chapter 15 动态规划

序

算法导论一书的第四部分—高级设计和分析技术从本章开始讨论，主要分析高效算法的三种重要技术：动态规划、贪心算法以及平摊分析三种。

首先，本章讨论动态规划，它是通过组合子问题的解而解决整个问题的，通常应用于最优化问题。

动态规划算法的设计可以分为如下4个步骤：

• 描述最优解的结构
• 递归定义最优解的值
• 按照自底向上的方式计算最优解的值
• 由计算出的结果构造一个最优解

15.1 装配线调度

问题描述

第一个动态规划的例子是求解一个制造问题，Colonel汽车公司在有两条装配线的工厂生产汽车，具体如下图所示：



针对装配线调度问题，下面给出一个实例，要求利用动态规划方法分析设计程序实现。

程序实现

/*
* 《算法导论》第十五章 动态规划
*  15.1 装配线调度问题
*/

#include <iostream>
#include <cstdlib>

using namespace std;

//初始化装配线以及站点个数
const int L = 2;
const int S = 6;

//程序输入：装配点耗费时间、底盘进入耗费时间、装配点移动耗费时间、底盘离开耗费时间
int a[L + 1][S + 1] , e[L + 1], t[L + 1][S], x[L + 1] , n = S;

//程序输出：
int f[L + 1][S + 1], l[L + 1][S + 1] , rf , rl;

//求解f[][] 用到的参数int **a, int *e, int **t, int *x, int n
void FastestWay()
{
    f[1][1] = e[1] + a[1][1];
    f[2][1] = e[2] + a[2][1];
    //由公式15.4 - 15.7 推导计算

    for (int j = 2; j <= n; j++)
    {
        if (f[1][j-1] + a[1][j] <= f[2][j - 1] + t[2][j - 1] + a[1][j])
        {
            f[1][j] = f[1][j - 1] + a[1][j];
            l[1][j] = 1;
        }
        else{
            f[1][j] = f[2][j - 1] + t[2][j - 1] + a[1][j];
            l[1][j] = 2;
        }

        if (f[2][j - 1] + a[2][j] <= f[1][j - 1] + t[1][j - 1] + a[2][j])
        {
            f[2][j] = f[2][j - 1] + a[2][j];
            l[2][j] = 2;
        }
        else{
            f[2][j] = f[1][j - 1] + t[1][j - 1] + a[2][j];
            l[2][j] = 1;
        }
    }

    if (f[1][n] + x[1] <= f[2][n] + x[2])
    {
        rf = f[1][n] + x[1];
        rl = 1;
    }
    else{
        rf = f[2][n] + x[2];
        rl = 2;
    }

}

//打印调度结果
void PrintStations()
{
    //最后一个站点的装配线号
    int i = rl;

    cout << "倒序结果输出：" << endl;

    cout << "line : " << i << " , station : " << n << endl;

    for (int j = n; j >= 2; j--)
    {
        i = l[i][j];
        cout << "line : " << i << " , station : " << j - 1 << endl;
    }
}

//打印调度结果 —— 以站号递增的顺序输出装配站
void PrintStations2()
{
    int r[S] , tem = rl;

    for (int j = S; j > 1 ; j--)
    {
        tem= l[tem][j];
        r[j - 1] = tem;
    }

    cout << "正序结果输出：" << endl;

    for (int j = 1; j < S; j++)
    {
        cout << "line : " << r[j] << " , station : " << j << endl;
    }
    //输出最后一个装配站
    cout << "line : " << rl << " , station : " << n << endl;
}

void Input()
{
    cout << "请输入装配点耗费时间：" << endl;
    for (int i = 1; i <= L; i++)
        for (int j = 1; j <= S; j++)
        {
            cin >> a[i][j];
        }

    cout << "请输入进入装配点耗费时间：" << endl;
    for (int i = 1; i <= L; i++)
    {
        cin >> e[i];
    }

    cout << "请输入站点移动耗费时间：" << endl;
    for (int i = 1; i <= L; i++)
        for (int j = 1; j < S; j++)
        {
            cin >> t[i][j];
        }
    cout << "请输入离开装配点耗费时间：" << endl;
    for (int i = 1; i <= L; i++)
    {
        cin >> x[i];
    }
}

void Output()
{
    int i, j;
    cout << "输出f[i][j]" << endl;
    //f[i][j]表示第j个站是在装配线i上完成的，完成1到j的装配最少需要的时间
    for (i = 1; i <= L; i++)
    {
        for (j = 1; j <= S; j++)
            cout << f[i][j] << ' ';
        cout << endl;
    }

    cout << "rf = " << rf << endl;

    cout << "输出l[i][j]" << endl;
    //l[i][j]表示使得f[i][j]最小时在哪个装配线上装配j-1
    for (i = 1; i <= L; i++)
    {
        for (j = 2; j <= S; j++)
            cout << l[i][j] << ' ';
        cout << endl;
    }

    cout << "rl = " << rl << endl;
}

//主程序
int main()
{
    //数据输入
    Input();

    FastestWay();

    //数据输出
    Output();

    //结果打印
    PrintStations();

    PrintStations2();

    system("pause");
    return 0;
}

运行结果

15.1练习

15.1-1

//递归输出结果，参数为：（站点，装配线编号）
void PrintStations3(int s, int ll)
{
    cout << "正序结果输出：" << endl;

    if (s < n)
        ll = l[ll][s + 1];

    if (s > 1)
        PrintStations3(s - 1, ll);

    cout << "line : " << ll << " , station : " << s << endl;
}

15.1-5

若Canty教授猜测正确，存在满足l1[j]=2且l2[j]=1的站点，则公式15.6与公式15.7中的公式必须同时成立，得到：

f1[j−1]+a1,j>f2[j−1]+t2,j−1+a1,j

f2[j−1]+a2,j>f1[j−1]+t1,j−1+a2,j

明显的，为两个矛盾式。所以Canty教授的猜测是不正确的。

15.2 矩阵链乘法

问题描述

解决矩阵链乘问题是动态规划的一个典型实例。

程序实现

/*
* 《算法导论》第十五章 动态规划
*  矩阵链乘法
*/

#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 6; //进行链乘的矩阵数目

//链乘矩阵维数序列
int A[N + 1] = { 30, 35, 15, 5, 10, 20, 25 };
//int A[N + 1] = { 5, 10, 3, 12, 5, 50, 6 };
//动态优化结果存储
int m[N + 1][N + 1] , s[N+1][N+1];

void MatrixChainOrder()
{
    int i, j, k , l, q;
    for (i = 1; i <= N; i++)
            m[i][i] = 0;

    for (l = 2; l <= N; l++)
    {
        for (i = 1; i <= N - l + 1; i++)
        {
            j = i + l - 1;
            m[i][j] = 0x7fffffff;
            for (k = i; k <= j - 1; k++)
            {
                q = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }//for
    }
}

void PrintOptimalParens(int i , int j)
{
    if (i == j)
        cout << "A" << i << " ";
    else{
        cout << "(";
        PrintOptimalParens( i, s[i][j]);
        PrintOptimalParens( s[i][j] + 1, j);
        cout << ")";
    }
}

int main()
{
    MatrixChainOrder();
    PrintOptimalParens(1, N);
    cout << endl;
    system("pause");
    return 0;
}

运行结果

15.2练习

15.2-1

最优加括号结果为：

15.2-2

15.3 动态规划基础

采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

1. 最优子结构
   
   用动态规划求解优化问题的第一步是描述最优解的结构，如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。

2.重叠子问题

适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要“很小”，也就是用来解原问题的递归算法可以反复的解同样的子问题，而不是总在产生新的子问题。

重叠子问题实现矩阵链乘

/*
* 《算法导论》第十五章 动态规划
*  15.3 动态规划基础
*  重叠子问题实现
*/

#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 6; //进行链乘的矩阵数目

//动态优化结果存储
int m[N + 1][N + 1], s[N + 1][N + 1];

int RecusiveMatrixChain(int *A, int i, int j)
{
    if (i == j)
        return 0;
    m[i][j] = 0x7fffffff;

    for (int k = i; k <= j - 1; k++)
    {
        int q = RecusiveMatrixChain(A, i, k) + RecusiveMatrixChain(A, k + 1, j) + A[i - 1] * A[k] * A[j];

        if (q < m[i][j])
        {
            m[i][j] = q;
            s[i][j] = k;
        }

    }//for
    return m[i][j];
}

void PrintOptimalParens(int i, int j)
{
    if (i == j)
        cout << "A" << i << " ";
    else{
        cout << "(";
        PrintOptimalParens(i, s[i][j]);
        PrintOptimalParens(s[i][j] + 1, j);
        cout << ")";
    }
}

int main()
{
    //链乘矩阵维数序列
    int A[N + 1] = { 30, 35, 15, 5, 10, 20, 25 };
    //int A[N + 1] = { 5, 10, 3, 12, 5, 50, 6 };

    RecusiveMatrixChain(A, 1, N);
    PrintOptimalParens(1, N);

    cout << endl;
    system("pause");
    return 0;
}

做备忘录实现矩阵链乘

动态规划有一种变形，它既具有通常的动态规划方法的效率，又采用了一种自顶向下的策略。其思想就是备忘原问题的自然但低效的递归算法。

/*
* 《算法导论》第十五章 动态规划
*  15.3 动态规划基础
*  做备忘录
*/

#include <iostream>
#include <cstdlib>

using namespace std;

const int N = 6; //进行链乘的矩阵数目

//动态优化结果存储
int m[N + 1][N + 1], s[N + 1][N + 1];

int LookUpChain(int *A, int i, int j)
{

    if (m[i][j] < 0x7fffffff)
        return m[i][j];

    if (i == j)
        m[i][j] = 0;
    else
    {
        for (int k = i; k <= j - 1; k++)
        {
            int q = LookUpChain(A, i, k) + LookUpChain(A, k + 1, j) + A[i - 1] * A[k] * A[j];

            if (q < m[i][j])
            {
                m[i][j] = q;
                s[i][j] = k;
            }

        }//for
    }

    return m[i][j];
}

int MemorizedMatrixChain(int *A)
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            m[i][j] = 0x7fffffff;
        }

    return LookUpChain(A, 1, N);
}

void PrintOptimalParens(int i, int j)
{
    if (i == j)
        cout << "A" << i << " ";
    else{
        cout << "(";
        PrintOptimalParens(i, s[i][j]);
        PrintOptimalParens(s[i][j] + 1, j);
        cout << ")";
    }
}

int main()
{
    //链乘矩阵维数序列
    int A[N + 1] = { 30, 35, 15, 5, 10, 20, 25 };
    //int A[N + 1] = { 5, 10, 3, 12, 5, 50, 6 };

    MemorizedMatrixChain(A);
    PrintOptimalParens(1, N);

    cout << endl;
    system("pause");
    return 0;
}

15.3练习