Algorithm理解用例：动态规划

时间：2022-10-30 11:09:41

“说得高大上，其实是Very Simple”

动态规划算法主要是用于“最优解”的问题。

相较于贪心算法，动态规划的使用范围更广，往往贪心法能够解决的问题动态规划算法都能解决。

动态规划算法可以看成是贪心法的复用（这一句是个人理解）。

算法思想很简单：
　　为了找出从初始态（Initial State）经过n次决策到最终态（Final State）的最优解，首先应确定初始态的状态集合S1。然后就是算法核心部分了，在第i次决策时（i∈[1,n]），需要对当前状态集合Si内所有状态分别进行“贪心”选择，得到新的状态Si+1，并记录决策内容。最后，将经过n次决策后得到的状态集Sfinal内所有状态进行比较得到的最优解，就是整个问题的最优解。

使用条件：
　　无论初始状态如何或者初始决策如何，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 就上述算法来说S1S2…SnSfinal，即为最优决策序列，而且对于任何一次决策i来说，得到的新的状态集合Si+1不会影响到Si。（越说越虚，最终还是要例子）

多段图问题（Multistage Graph）

Algorithm理解用例：动态规划
摘自：《计算机算法基础》第三版，徐祥宣/崔国华/邹海明，华中科技大学出版社，P125

问题描述：如上图，找出从状态“s”出发到状态“t”结束的最短路径？

问题分析：
　　上图已经经过处理，能够明确的看出是一个5段图，即总共有5个阶段V1到V5，每个阶段中的节点都满足这样一个要求“不存在由当前阶段节点到之前阶段的节点的路径”。

向前处理法：
　　先说说向前处理法，因为更容易理解一点。该方法是指从最终态“ｔ”向初始态反向处理找出最优解。
　　阶段V4、V5的节点很好确定他们到“t”的最短路径，因为就是其本身。
　　我们从V3阶段开始分析，逐个分析V3中的节点6、7、8，同一阶段内的节点分析顺序可以随机。
　　以节点6为例，此时我的决策目的是找出节点6到最终态“t”的最短路径，并且节点6下一跳的节点9、10到“t”的最短路径已经在上一次决策中确定了。
　　那么，我仅仅需要比较cost<6,9>+minCost(9)与cost<6,10>+minCost(10)就可以确定节点6到最终态的最短路径minCost(6)，同样的方式可以求出minCost(7)、minCost(8)。
　　以此类推就能够接着求出V2中各节点的最短路径，进而确定V1中节点也就是初始状态到最终态的最短路径。
　　注：minCost(9)表示节点9到“t”的最短路径。

代码如下：

int _MG_FGRAPH( _graph g, int stageNum, int *path )
{
    /* * 向前处理算法 * g: 矩阵图 * stageNum: 多段图的段数 * path: 记录最终结果 */

    int nodeNum = g[0][0].data;
    int *cost = MALLOC(int,nodeNum+1); // 数组cost用于记录每一个状态到最终状态的最小代价
    int *D = MALLOC(int,nodeNum+1); // 数组D用于记录每个状态的下一跳，使其到最终状态付出的代价最小

    int i,j;
    int iToJ_add_costJ; // 方便阅读：cost<i,j>+minCost(j)

    // 初始化
    for( i=0; i<=nodeNum; i++ ) cost[i] = GRAPHDATA_MAXVALUE; // 令所有节点到最终态需花无穷大代价
    cost[nodeNum] = 0; // 最终态到其自身的代价为0
    for( i=0; i<=nodeNum; i++ ) D[i] = 0; // 将所有节点设为未找到下一跳状态

    // 计算cost 和 D
    for( i=nodeNum-1; i>=1; i-- ) { 
        /* * 由最终态向初始状态一次考虑每一个状态。 * * 因为节点已经按照其所处的状态集进行排序，所以无需使用另外算法或空间来控制向前处理顺序。 */
        for( j=i+1; j<=nodeNum; j++ )
        {
            // 遍历所有序号大于i的节点，以确定使其到最终态路径最短的下一跳节点
            // 此处可以继续优化，非相邻状态的节点无需考虑
            // weight<i,j> + cost(j)
            iToJ_add_costJ = addEdgeDataG(g[i][j].data,cost[j]);
            if( cmpEdgeDataG(iToJ_add_costJ,cost[i]) == -1 ) {
                cost[i] = iToJ_add_costJ;
                D[i] = j;
            }
        }
    }

    // 根据D得到Path
    path[1] = 1;
    for( i=2; i<=stageNum; i++ ) {
        path[i] = D[path[i-1]];
    }

    return 0;
}

向后处理方法：

当问题与上图所示一样，初始态和最终态都只有一种状态，那么不论向前还是向后处理都可以。

向后处理方法就是由初始状态开始向最终态，依次做贪心决策。同样的以类似向前处理的方式来解释。

每次决策，我需要进行的判断就是，找出初始态节点1到当前节点i的最短路径。

上图中阶段V1、V2可以直接看出，我们还是以状态节点6进行说明。

对于节点6，我们已知在之前状态中，只有节点2、3与其直接相连。另外，在上一次决策时，初始态到V2中所有节点的最小代价已经确定。因此我们仅仅需要比较minCost(2)+cost<2,6>与minCost(3)+cost<3,6>就可以得到从节点1到节点6的最短路径。以此类推，我们就可以确定状态V3上的所有节点对应的minCost()。

同样依据这种简单的算法，我们最终就可以得到问题的解。

实现代码如下：

int _MG_BGRAPH( _graph g, int stageNum, int *path )
{
    /* * 向后处理算法 */

    int nodeNum = g[0][0].data;
    int *cost = MALLOC(int,nodeNum+1); // 数组cost用于记录每一个状态到最终状态的最小代价
    int *D = MALLOC(int,nodeNum+1); // 数组D用于记录每个状态的下一跳，使其到最终状态付出的代价最小

    int i,j,costI_add_iToJ;

    // 初始化
    for( i=0; i<=nodeNum; i++ ) cost[i] = GRAPHDATA_MAXVALUE; // 令所有节点到最终态需花无穷大代价
    cost[1] = 0; // 初始态到其自身的代价为0
    for( i=0; i<=nodeNum; i++ ) D[i] = 0; // 将所有节点设为未找到下一跳状态

    // 计算cost 和 D
    for( i=2; i<=nodeNum; i++ ) { 
        /* * 由初始态向最终状态一次考虑每一个状态。 * * 因为节点已经按照其所处的状态集进行排序，所以无需使用另外算法或空间来控制向后处理顺序。 */
        for( j=i-1; j>=1; j-- )
        {
            // minCost(j) + cost<j,i>
            costI_add_iToJ = addEdgeDataG(cost[j],g[j][i].data);
            if( cmpEdgeDataG(costI_add_iToJ,cost[i]) == -1 ) {
                cost[i] = costI_add_iToJ;
                D[i] = j;
            }
        }
    }

    // 根据D得到Path
    path[stageNum] = nodeNum;
    for( i=stageNum-1; i>=1; i-- ) {
        path[i] = D[path[i+1]];
    }


    return 0;
}

每对节点之间的最短路径问题（All pairs shortest path problem）

其实就是Floyd算法。

求此问题可以使用动态规划方法依据就是很简单的一句话（为了表述更加清晰，我用“Vi”表示节点i，用“MinPath(Vi,Vj)”表示由Vi到Vj的最短路径。）：
　　
　　假设Vk是MinPath(Vi,Vj)上的一个中间结点，那么必有 Path(Vi,Vk) = MinPath(Vi,Vk) 和Path(Vk,Vj) = MinPath(Vk,Vj)。否则，假设不成立。

根据这个思想，我们就可以很快的理解Floyd算法。

首先，用矩阵存储有向图的边集可以再时间复杂度为O(1)的情况加定位需要修改的边。

然后就可以开始根据例子理解这个算法了，依旧使用《计算机算法的基础》的例子，如图：Algorithm理解用例：动态规划
摘自：《计算机算法基础》第三版，徐祥宣/崔国华/邹海明，华中科技大学出版社，P131

初始状态如图（b），之后我们需要依节点序号 k 由小到大（也可以按随机顺序）做3次（同节点数相同）决策。

每次决策的目的是确定节点 i 到 j 在不经过序号比 k 大的节点这一条件下的最短路径，即
　　min{ cost< i，j >，cost< i，k >+cost< k，j > }
　　
依此例，经过第一次决策后得到如下图所示矩阵：
Algorithm理解用例：动态规划

“A1”中的“1”的语义为“经过编号不大于1的节点”。

对比该矩阵和前文的矩阵（B）我们可以发现只有A[3][2]这一条边的值由∞变成了7，这就表示“经过不大于1的节点，节点 3 到 2 的最短路径为 7，且中间节点集合必然包括节点 1”。

再对“A1”进行决策，得到“A2”如下图：
Algorithm理解用例：动态规划

对比矩阵“A1”,A[1][3]由11变为6，其意义是“在不经过序号大于2的节点的条件下，由节点 1 到 3 的最短路径的中间节点集合必然包括节点 2 ”。

值没有改变的情况，比如在前一次迭代中改变的A[3][2]，此时的语义就是“在不经过序号大于 2 的节点的条件下，由节点 3 到 2 的最短路径的中间节点集合不包括节点 2”。

因为总共只有 3 个节点，所以只用再做最后一次决策就可以得到问题的最终解了。如图：Algorithm理解用例：动态规划

路径的存储方式，我同样采用一个二维矩阵 fg，“ fg[i][j].data = k ”对应的语义为“有节点 i 到节点 j 的最短路径必然经过节点 k，k为这条最短路径的中间结点集合中序号最大的节点”。之所以采用这样的存储方式的可行性，完全可以由前文所述的“可以使用动态规划方法的依据”进行解释。

附上代码：

_graph _FLOYD( _graph g )
{
    /* * fg: Floyd最小成本路径矩阵，fg[i][j].data = k的语义为 * 节点i到节点j的最短路劲必须经过节点k，即min<i,j> = min<i,k> + min<k,j> * fgCost: Floyd最小成本矩阵，fgCost[i][j].data = v的语义为 * 节点i到节点j的最短路劲代价为v，即minCost<i,j> = minCost<i,k> + minCost<k,j> = v */
    _graph fg,fgCost; 
    int i,j,k,nodeNum = g[0][0].data;
    int ikAddKj; // cost<i,k>+cost<k,j>

    // 初始化
    fgCost = duplicateG(g);
    fg = createG(nodeNum);

    // 计算fg和fgCost
    // 决策nodeNum次，k表示“第k次决策”
    for(k=1; k<=nodeNum; k++ ) { 
        // 遍历所有边
        for(i=1; i<=nodeNum; i++ ) {
            for(j=1; j<=nodeNum; j++ ) {
                ikAddKj = addEdgeDataG(fgCost[i][k].data,fgCost[k][j].data); // cost<i,k>+cost<k,j>
                if( cmpEdgeDataG(ikAddKj,fgCost[i][j].data) == -1 ) {
                    fgCost[i][j].data = ikAddKj;
                    fg[i][j].data = k;
                }
            }
        }
    }

    return fg;
}

最优二分检索树

二分检索树（Binary Search Tree）的概念很简单，树中任何一个节点Ni都应满足如下条件：
①、假设LChild、RChild分别表示Ni的左、右孩子；
②、LChild = null 或者 LChild.weight < Ni.weight；
③、RChild = null 或者 Ni.weight < RChild.weight；

构造一个检索树的最简单算法伪代码如下：

/* * 输入二叉树bt，以及查找目标target * target存在时，返回对应标识 * target不存在时，建立target节点 */ 
_biTreeNode* searchBiTree( _biTree *bt, int target) 
{
    if( isEmpty(bt) ) {
        // bt为空树，以target建立根节点
        createRoot(bt,target);
        return null_ptr;
    }

    // 二分查找目标
    _biTreeNode* scanPointer = bt->root;
    while(1) {
        if( scanPointer->weight == target ) {
            return scanPointer; // 找到目标，则返回节点地址
        } 
        else if( target < scanPointer->weight ) {
            // lChild为空时，以target建立左孩子节点，并返回空
            // 否则，继续考虑左子树
            if( scanPointer->lChild == null_ptr ) {
                addChild(scanPointer,target,LEFT);
                return null_ptr;
            }
            else scanPointer= scanPointer->lChild;
        }
        else {
            if( scanPointer->rChild == null_ptr ) {
                addChild(scanPointer,target,RIGHT);
                return null_ptr;
            }
            else scanPointer = scanPointer->rChild;
        }
    }
}

这个算法虽然简单，往往会生成一个查询代价高昂的二分检索树。举个简单的例子，整数集合S={1，2，3}。根据搜索的顺序不同，得到的检索树的代价会不同：

Algorithm理解用例：动态规划

树(a)，虽然P(E1)处在“Level 2”，但实际上在“Level 1”的时候就能得出“检索不正确”的结论，因此检索不成功的情况的代价就应该是

Cost(i)=(Level(i)−1)×P(i)

假设上例中，各种情况出现的概率相等，即

P(1)=P(2)=P(3)=P(E1)=P(E2)=P(E3)=P(E4)=17

能够算出树(a)的平均检索代价：

CostA=∑i=13Level(i)×P(i)+∑i=14(Level(Ei)−1)×P(Ei)=157

树(b)的平均检索代价：

CostB=∑i=13Level(i)×P(i)+∑i=14(Level(Ei)−1)×P(Ei)=137

可以看到，用这种方法生成的二分检索树实际上是和输入的关键字顺序有很大关系的。为了得到最优的二分检索树，就可以使用接下来的动态规划方法。核心的思想其实是一如既往的简单。

算法思想：
　　假设有 n 个节点，Tree(i,j) 表示由第i个节点到第j个节点生成的最优二分检索树，Root(i,j)表示这棵树的根。
　　那么，令 k = Root(i,j)，必有 R(i,k-1) 和 R(k,j) 分别为 Tree(i,j) 的左最优二分检索子树T(i,k-1)的根和右最优二分检索子树T(k,j)的根。

算法简述：
　　①、将所有节点都看成一棵只有一个根节点的最优二分检索树的根。
　　②、找出所有相邻两个节点组成的最优二分检索树的根。
　　③、找出所有相邻3个节点组成的最优二分检索树的根。
　　④、逐个增加相邻节点的数目，直到找出所有节点组成的最优二分检索树的根为止。

下面是我觉得是这个算法中最难理解的一个部分了。我采用的方法是“嗯，先拿来用，至于为什么，说不定用着用着就知道了”。

首先，在迭代过程中，我们不能真正的先把一个个二叉树建立起来，再选出其中最优解的根。那么，就必须找一个方法，或者数学模型来代替这个过程。

于是，这个模型我就直接从教材（《计算机算法基础》第三版，徐祥宣/崔国华/邹海明，华中科技大学出版社，P134~P135）抄过来了，略微简化了一下：

级数的测定是把各个子树的根看成是第 1 级来进行的，其中“Q(i)”表示“检索不成功情况 i 的概率”，“P(i)”表示“检索成功情况 i 的概率”。

Weight(i,j)=Q(i)+∑l=i+1j(Q(l)+P(l))

于是可以得到作为检索树 T (下图) 的预期成本 :

Algorithm理解用例：动态规划

Cost(T) = P(k)×1 + Cost(L) + Cost(R) + Weight(0,k-1) + Weight(k,n)　　①
Cost(L) = Cost(0,k-1)　　②
Cost(R) = Cost(k,n)　　③
k 使 Cost(0,k-1) + Cost(k,n) 的值最小　④

综合①、②、③、④，得到
Cost(T) = Cost(0,n) = Weight(0,k-1) + P(k) + Weight(k,n) + Cost(0,k-1) + Cost(k,n)
又有 Weight(0,k-1) + P(k) + Weight(k,n) = Weight(0,n)

于是 Cost(0,n) = Weight(0,n) + Cost(0,k-1) + Cost(k,n)，这就是我们需要的核心公式模型。

然后就是代码了：

/* DP type OBST */
typedef struct obstWcrMapNode {
    int weight; // 参考权值，参考，参考，参考！！！
    int cost; // 预期代价
    int root; // 局部最优二分检索树根节点
}_wcrMap;

int assignWcrMapNode( struct obstWcrMapNode *wmNode, int w, int r, int c )
{
    wmNode->weight = w;
    wmNode->root = r;
    wmNode->cost = c;

    return 0;
}

_biTreeNode* createBiTreeByWcrMap( _wcrMap **wcrMap, int i, int j)
{
    // 根据wcrMap，即计算的结果生成最优二分检索树
    int r = wcrMap[i][j].root;

    _biTreeNode *tmpNode = createBiTreeNode(r);

    if( r-i >= 2 ) tmpNode->lChild = createBiTreeByWcrMap(wcrMap,i,r-1);
    if( j > r ) tmpNode->rChild = createBiTreeByWcrMap(wcrMap,r,j);

    return tmpNode;
}

_biTree* _OBST( int *P, int *Q, int n )
{
    /* * 已知查找成功与失败概率，创建最小成本二分查找树 */
    _biTree *bt = createBiTree();
    int i,j,m,k,l,minCost;

    _wcrMap **wcrMap = MALLOC(_wcrMap*,n+1);
    for( i=0; i<=n; i++ ) wcrMap[i] = MALLOC(_wcrMap,n+1);

    /* Initialization */
    for( i=0; i<=n; i++ ) {
        for( j=0; j<=n; j++ ) {
            if( i == j ) assignWcrMapNode(&wcrMap[i][j],Q[i],0,0); // 置初值 ( weight(i,i) , root(i,i) , cost(i,i) ) ← ( Q(i) , 0 , 0 ) 
            else assignWcrMapNode(&wcrMap[i][j],NULL,NULL,NULL);
        }
    }

    /* * 第一次迭代，即 m = 1，每一个节点即为一棵树 */
    for( i=0; i<=n-1; i++ ) {
        // ( weight(i,i+1) , root(i,i+1) , cost(i,i+1) ) ← ( Q(i)+P(i+1)+Q(i+1) , i+1 , Q(i)+P(i+1)+Q(i+1) )
        assignWcrMapNode(&wcrMap[i][i+1],Q[i]+P[i+1]+Q[i+1],i+1,Q[i]+P[i+1]+Q[i+1]);
    }

    /* * 每一次迭代确定有m个节点的树T<i,j>(j-i=m)的根节点。 */
    for( m=2; m<=n; m++ ) { // 第m次迭代
        for( i=0; i<=n-m; i++ ) {
            j = i+m; // 确定组成树T<i,j>的节点集合的边界。

            wcrMap[i][j].weight = wcrMap[i][j-1].weight + P[j] + Q[j]; //weight(i,j) ← weight(i,j-1) + P(j) + Q(j)

            //k ← 使{ cost(i,l-1 ) + cost(l,j) }取最小值的 l 值
            minCost = INT_MAX;
            for( l=i+1; l<=j-1; l++ ) {
                if( wcrMap[i][l-1].cost+wcrMap[l][j].cost <= minCost ) {
                    minCost = wcrMap[i][l-1].cost+wcrMap[l][j].cost;
                    k = l;
                }
            }

            //cost(i,j) ← weight(i,j) + C(i,k-1) + C(k,j)
            wcrMap[i][j].cost = wcrMap[i][j].weight + wcrMap[i][k-1].cost + wcrMap[k][j].cost;

            //R(i,j)←k
            wcrMap[i][j].root = k;
        }
    }

    // Create Binary Search Tree by wcrMap
    bt->root = createBiTreeByWcrMap(wcrMap,0,n);
    bt->elemNum = n;

    return bt;
}
标签：

相关文章