精华内容
下载资源
问答
  • 剑指Offer——动态规划算法

    万次阅读 多人点赞 2016-08-03 15:24:27
    剑指Offer——动态规划算法什么是动态规划? 和分治法一样,动态规划(dynamicprogramming)是通过组合子问题而解决整个问题的解。 分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解...

    剑指Offer——动态规划算法

    什么是动态规划?

         和分治法一样,动态规划(dynamic programming)是通过组合子问题而解决整个问题的解。

         分治法是将问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解。

         动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。

         此时,分治法会做许多不必要的工作,即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次,将其结果保存起来,从而避免每次遇到各个子问题时重新计算答案。

    适用范围

         最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时,则称该问题具有最优子结构特性。

         最优性原理是动态规划的基础。任何一个问题,如果失去了这个最优性原理的支持,就不可能用动态规划设计求解。

         1.问题中的状态满足最优性原理。

         2.问题中的状态必须满足无后效性。

         所谓无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状态无关,当前状态是对以往决策的总结”。

    动态规划算法的设计

         两种方法:

         自顶向下(又称记忆化搜索、备忘录):基本上对应着递归函数实现,从大范围开始计算,要注意不断保存中间结果,避免重复计算

         自底向上(递推):从小范围递推计算到大范围

    动态规划的重点

        递归方程+边界条件

    爬楼梯问题

         一个人每次只能走一层楼梯或者两层楼梯,问走到第80层楼梯一共有多少种方法。

         设DP[i]为走到第i层一共有多少种方法,那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2(走到第一层只有一种方法:就是走一层楼梯;走到第二层有两种方法:走两次一层楼梯或者走一次两层楼梯)。同理,走到第i层楼梯,可以从i-1层走一层,或者从i-2走两层。很容易得到:

          递推公式:DP[i]=DP[i-1]+DP[i-2]

          边界条件:DP[1]=1   DP[2]=2

          (a)自顶向下的解法:

     

    long long dp[81] = {0};/*用于保存中间结果否则会重复计算很多重复的子问题*/
    long long DP(int n)
    {
        if(dp[n])
            return dp[n];
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        dp[n] = DP(n-1) + DP(n-2);
        return dp[n];
    }  

     

         (b)自底向上的解法:

     

    int i;  
    long long dp[81]; /* 注意当n超过75时,结果值将超过int范围 */  
    dp[1] = 1;  
    dp[2] = 2;  
    for(i=3; i <= 80; i++)  
        dp[i] = dp[i-1] + dp[i-2];

     

    最长上升子序列

         对于序列:4 1 2 24,它的最长上升子序列是1 2 4,长度为3。

         对于序列:4 2 4 25 6,它的最长上升子序列是2 4 5 6,长度为4。

         设a[i]表示原序列,设DP[i]表示以第i个数结尾的最长上升序列的长度,那么很显然想导出DP[i]的值,需要在DP[k](1<=k<i)中找出满足a[k]<a[i]最大的一项。假设第kk项是我们找到的答案,那么第i个数就可以接在第kk个数之后,成为以第i个数结尾的最长升序列。如果没有找到答案,换言之第i个数比前面的数都要小,那么DP[i]=1,也即生成了从自己开始又以自己结尾的最长升序列。综上,我们很容易得出:

         递推公式:DP[i]=max(DP[k]+1,DP[i])  1<=k<i

         边界条件:DP[i]=1                   1<=i<=n

         算法复杂度为O(n^2)

     

    void RiseSequence(int Array[], int num)  
    {  
    #define MAX_LENGTH  30  
        struct  
        {  
            int SequenceValue;  /* max length ending with this num */  
            int PreviousIndex;  /* record the previous number */  
        }ArrayInfo[MAX_LENGTH], temp;  
        int i;  
        for(i = 0; i < num; i++)  
        {  
            int j;  
            ArrayInfo[i].SequenceValue = 1;  
            ArrayInfo[i].PreviousIndex = -1;  
            for(j = 0; j < i; j++)  
            {  
                if(Array[j] < Array[i] && (ArrayInfo[j].SequenceValue + 1 > ArrayInfo[i].SequenceValue))  
                {  
                    ArrayInfo[i].SequenceValue = ArrayInfo[j].SequenceValue + 1;  
                    ArrayInfo[i].PreviousIndex = j;  
                }  
            }  
        }  
        temp.SequenceValue = ArrayInfo[0].SequenceValue;  
        for(i = 1; i < num; i++)  
        {  
            if(temp.SequenceValue < ArrayInfo[i].SequenceValue)  
            {  
                temp.SequenceValue = ArrayInfo[i].SequenceValue;  
                temp.PreviousIndex = i;  
            }  
        }  
        for(i = 0; i < temp.SequenceValue; i++)  
        {  
            printf("%d  ", Array[temp.PreviousIndex]);  /* in reverse order */  
            temp.PreviousIndex = ArrayInfo[temp.PreviousIndex].PreviousIndex;  
        }  
        printf("\nthe max rising sequence length is %d\n", temp.SequenceValue);  
    }  

     

    最长公共子序列

         给定两个序列X和Y,称序列Z是X和Y的公共子序列如果Z既是X的一个子序列,又是Y的一个子序列。例如,如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列,但是它并不是X和Y的最长公共子序列,因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a},长度为4,因为找不到长度为5或更大的公共子序列,所以X和Y的最长公共子序列长度就为4。

         假设两个序列数组分别为a,b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况:

         1.假如a[i]=b[j],那么f(i,j)=f(i-1,j-1)+1

         2.假如a[i]!=b[j],那么f(i,j)=max(f(i-1,j),f(i,j-1))

         边界条件为:f(i,0)=0     1<=i<=len(a)

                f(0,j)=0     1<=j<=len(b)

         算法复杂度:O(n^2),len(a)表示数组a的长度。

    尾声

         动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题,去设计状态转移方程式。

    动态规划还有很多变形,如状态压缩,树形等等。

        虽然通常我们用递归的方式分析动态规划问题,但最终都会基于循环去编码。

    美文美图

     

    展开全文
  • 动态规划算法总结

    千次阅读 2016-07-30 19:49:06
    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示...

    解题方法:

    动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。
    ┌───┐┌───┐┌───┐
    初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
    └───┘└───┘└───┘
    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。
    (2)确定状态和状态变量:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
    (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态之间的关系来确定决策。
    (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或边界条件。
    (5)程序设计实现:动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。
    根据上述动态规划设计的步骤,可得到大体解题框架如下:

         1.初始化(边界条件)

         2.for i:=2 to n (顺推法)  或 for i:=n-1 to 1(逆推法)

             对i阶段的每一个决策点求局部最优

         3.确定和输出结束状态的值.   


    1.射击问题---想好存储的数据结构

     一个人射箭,每次分数在0至10之间,已知射箭10次,得分是50分,编程计算总共有多少种可能?

    package com.ming.test;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class D1 {
    
        public static void main(String[] args) {
    
            D1 a = new D1();
    
            // 总分20分,射箭5次,每次0~10分
            List<List<Integer>> c = a.combine(25, 5, 10);
            System.out.println(c.size());
            // 打印结果
            for (List<Integer> list : c) {
                System.out.println(list);
            }
        }
    
        Integer[] stack;// 存储单次结果
        List<List<Integer>> result;// 存储结果集
    
        /**
         * 
         * @param totalScore
         *            最后得分
         * @param totalTimes
         *            射击次数
         * @param maxScore
         *            每次射箭的最大分数
         * @return
         */
        public List<List<Integer>> combine(int totalScore, int totalTimes,
                int maxScore) {
    
            stack = new Integer[totalTimes];
            result = new ArrayList<List<Integer>>();
    
            dfs(0, 0, totalScore, totalTimes, maxScore);
    
            return result;
        }
                          //目前次数        目前得总分                   //20                5ci        10fen
        public void dfs(int p, int curScore, int totalScore, int totalTimes,
                int maxScore) {
    //划分----确定状态(p---逼近totalTimes,curScore---逼近totalSocre)
            if (p == totalTimes && curScore == totalScore) {
                result.add(new ArrayList<Integer>(Arrays.asList(stack)));
                return;
            }
    //总结结束条件---满足的逻辑
            if (p == totalTimes || curScore > totalScore) {
                return;
            }
    //总结边界条件
            for (int i = 0; i < maxScore; i++) {
                stack[p] = i;
                dfs(p + 1, curScore + i, totalScore, totalTimes, maxScore);//转移方程
            }
        }
    }

    ----------------------------------------------

    动态规划逻辑

    作者:Hawstein
    出处: http://hawstein.com/posts/dp-novice-to-advanced.html
    声明:本文采用以下协议进行授权:  自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

    前言

    本文翻译自TopCoder上的一篇文章: Dynamic Programming: From novice to advanced ,并非严格逐字逐句翻译,其中加入了自己的一些理解。水平有限,还望指摘。

    前言_

    我们遇到的问题中,有很大一部分可以用动态规划(简称DP)来解。 解决这类问题可以很大地提升你的能力与技巧,我会试着帮助你理解如何使用DP来解题。 这篇文章是基于实例展开来讲的,因为干巴巴的理论实在不好理解。

    注意:如果你对于其中某一节已经了解并且不想阅读它,没关系,直接跳过它即可。

    简介(入门)

    什么是动态规划,我们要如何描述它?

    动态规划算法通常基于一个递推公式及一个或多个初始状态 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度, 因此它比回溯法、暴力法等要快许多。

    现在让我们通过一个例子来了解一下DP的基本原理。

    首先,我们要找到某个状态的最优解,然后在它的帮助下,找到下一个状态的最优解。

    “状态”代表什么及如何找到它?

    “状态”用来描述该问题的子问题的解。原文中有两段作者阐述得不太清楚,跳过直接上例子。

    如果我们有面值为1元、3元和5元的硬币若干枚,如何用最少的硬币凑够11元? (表面上这道题可以用贪心算法,但贪心算法无法保证可以求出解,比如1元换成2元的时候)

    首先我们思考一个问题,如何用最少的硬币凑够i元(i<11)?为什么要这么问呢? 两个原因:1.当我们遇到一个大问题时,总是习惯把问题的规模变小,这样便于分析讨论。即大变小!2.这个规模变小后的问题和原来的问题是同质的,除了规模变小,其它的都是一样的, 本质上它还是同一个问题(规模变小后的问题其实是原问题的子问题)。

    好了,让我们从最小的i开始吧。当i=0,即我们需要多少个硬币来凑够0元。 由于1,3,5都大于0,即没有比0小的币值,因此凑够0元我们最少需要0个硬币。 (这个分析很傻是不是?别着急,这个思路有利于我们理清动态规划究竟在做些什么。) 

    这时候我们发现用一个标记来表示这句“凑够0元我们最少需要0个硬币。”会比较方便, 如果一直用纯文字来表述,不出一会儿你就会觉得很绕了。那么, 我们用d(i)=j来表示凑够i元最少需要j个硬币。

    于是我们已经得到了d(0)=0, 表示凑够0元最小需要0个硬币。当i=1时,只有面值为1元的硬币可用, 因此我们拿起一个面值为1的硬币,接下来只需要凑够0元即可,而这个是已经知道答案的, 即d(0)=0。所以,d(1)=d(1-1)+1=d(0)+1=0+1=1。当i=2时, 仍然只有面值为1的硬币可用,于是我拿起一个面值为1的硬币, 接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量),而这个答案也已经知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到这里,你都可能会觉得,好无聊, 感觉像做小学生的题目似的。因为我们一直都只能操作面值为1的硬币!

    耐心点, 让我们看看i=3时的情况。当i=3时,我们能用的硬币就有两种了:1元的和3元的( 5元的仍然没用,因为你需要凑的数目是3元!5元太多了亲)。 既然能用的硬币有两种,我就有两种方案。如果我拿了一个1元的硬币,我的目标就变为了: 凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 这个方案说的是,我拿3个1元的硬币;第二种方案是我拿起一个3元的硬币, 我的目标就变成:凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 这个方案说的是,我拿1个3元的硬币。好了,这两种方案哪种更优呢? 记得我们可是要用最少的硬币数量来凑够3元的。所以, 选择d(3)=1,怎么来的呢?具体是这样得到的:d(3)=min{d(3-1)+1, d(3-3)+1}。

    OK,码了这么多字讲具体的东西,让我们来点抽象的。从以上的文字中, 我们要抽出动态规划里非常重要的两个概念:状态和状态转移方程。

    上文中d(i)表示凑够i元需要的最少硬币数量,我们将它定义为该问题的”状态”, 这个状态是怎么找出来的呢?我在另一篇文章 动态规划之背包问题(一)中写过: 根据子问题定义状态。你找到子问题,状态也就浮出水面了。 最终我们要求解的问题,可以用这个状态来表示:d(11),即凑够11元最少需要多少个硬币。 那状态转移方程是什么呢?既然我们用d(i)表示状态,那么状态转移方程自然包含d(i), 上文中包含状态d(i)的方程是:d(3)=min{d(3-1)+1, d(3-3)+1}。没错, 它就是状态转移方程,描述状态之间是如何转移的。当然,我们要对它抽象一下

    d(i)=min{ d(i-vj)+1 },其中i-vj >=0,vj表示第j个硬币的面值;

    有了状态和状态转移方程,这个问题基本上也就解决了。当然了,Talk is cheap,show me the code!

    伪代码如下:

    下图是当i从0到11时的解:

    从上图可以得出,要凑够11元至少需要3枚硬币。

    此外,通过追踪我们是如何从前一个状态值得到当前状态值的, 可以找到每一次我们用的是什么面值的硬币。比如,从上面的图我们可以看出, 最终结果d(11)=d(10)+1(面值为1),而d(10)=d(5)+1(面值为5),最后d(5)=d(0)+1 (面值为5)。所以我们凑够11元最少需要的3枚硬币是:1元、5元、5元。

    #include <iostream>
    using namespace std;
    
    int main()
    {
    	int cons[3] = {1,3,5};
    	int value;
    	while(cin>>value)
    	{
    		int *arr = new int[value];
    		arr[0]=0;
    		for(int i = 1; i <= value; ++i)
    		{
    			int cons1 = i - 1;
    			int cons3 = i - 3;
    			int cons5 = i - 5;
    			int minConsNum = arr[cons1], lastCons = cons1;
    			if(cons3 >= 0 && arr[cons3] < minConsNum)
    			{
    				minConsNum = arr[cons3];
    				lastCons = cons3;
    			}
    			if(cons5 >= 0 && arr[cons5] < minConsNum)
    			{
    				minConsNum = arr[cons5];
    				lastCons = cons5;
    			}
    			arr[i] = minConsNum + 1;
    
    			cout<<i<<'\t'<<arr[i]<<'\t'<<lastCons<<endl;
    		}
    	}
    	return 0;
    }

    注意:原文中这里本来还有一段的,但我反反复复读了几遍, 大概的意思我已经在上文从i=0到i=3的分析中有所体现了。作者本来想讲的通俗一些, 结果没写好,反而更不好懂,所以这段不翻译了。

    初级

    上面讨论了一个非常简单的例子。现在让我们来看看对于更复杂的问题, 如何找到状态之间的转移方式(即找到状态转移方程)。 为此我们要引入一个新词叫递推关系来将状态联系起来(说的还是状态转移方程)

    OK,上例子,看看它是如何工作的。

    一个序列有N个数:A[1],A[2],…,A[N],求出最长非降子序列的长度。 (讲DP基本都会讲到的一个问题LIS:longest increasing subsequence)

    正如上面我们讲的,面对这样一个问题,我们首先要定义一个“状态”来代表它的子问题, 并且找到它的解。注意,大部分情况下,某个状态只与它前面出现的状态有关, 而独立于后面的状态。

    让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。 假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度,其中i<N, 那么上面的问题变成了原问题的一个子问题(问题规模变小了,你可以让i=1,2,3等来分析) 然后我们定义d(i),表示前i个数中以A[i]结尾的最长非降子序列的长度。OK, 对照“入门”中的简单题,你应该可以估计到这个d(i)就是我们要找的状态。 如果我们把d(1)到d(N)都计算出来,那么最终我们要找的答案就是这里面最大的那个。 状态找到了,下一步找出状态转移方程。

    为了方便理解我们是如何找到状态转移方程的,我先把下面的例子提到前面来讲。 如果我们要求的这N个数的序列是:

    5,3,4,8,6,7
    

    根据上面找到的状态,我们可以得到:(下文的最长非降子序列都用LIS表示)

    • 前1个数的LIS长度d(1)=1(序列:5)
    • 前2个数的LIS长度d(2)=1(序列:3;3前面没有比3小的)
    • 前3个数的LIS长度d(3)=2(序列:3,4;4前面有个比它小的3,所以d(3)=d(2)+1)
    • 前4个数的LIS长度d(4)=3(序列:3,4,8;8前面比它小的有3个数,所以 d(4)=max{d(1),d(2),d(3)}+1=3)

    OK,分析到这,我觉得状态转移方程已经很明显了,如果我们已经求出了d(1)到d(i-1), 那么d(i)可以用下面的状态转移方程得到:

    d(i) = max{1, d(j)+1},其中j<i,A[j]<=A[i]
    

    用大白话解释就是,想要求d(i),就把i前面的各个子序列中, 最后一个数不大于A[i]的序列长度加1,然后取出最大的长度即为d(i)。 当然了,有可能i前面的各个子序列中最后一个数都大于A[i],那么d(i)=1, 即它自身成为一个长度为1的子序列。

    分析完了,上图:(第二列表示前i个数中LIS的长度, 第三列表示,LIS中到达当前这个数的上一个数的下标,根据这个可以求出LIS序列)

    Talk is cheap, show me the code:

    #include <iostream>
    using namespace std;
    
    int lis(int A[], int n){
        int *d = new int[n];
        int len = 1;
        for(int i=0; i<n; ++i){
            d[i] = 1;
            for(int j=0; j<i; ++j)
                if(A[j]<=A[i] && d[j]+1>d[i])
                    d[i] = d[j] + 1;
            if(d[i]>len) len = d[i];
        }
        delete[] d;
        return len;
    }
    int main(){
        int A[] = {
            5, 3, 4, 8, 6, 7
        };
        cout<<lis(A, 6)<<endl;
        return 0;
    }
    

    该算法的时间复杂度是O(n^2 ),并不是最优的解法。 还有一种很巧妙的算法可以将时间复杂度降到O(nlogn),网上已经有各种文章介绍它, 这里就不再赘述。传送门: LIS的O(nlogn)解法。 此题还可以用“排序+LCS”来解,感兴趣的话可自行Google。

    练习题

    无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

    提示:在每一步中,对于那些没有计算过的结点, 及那些已经计算出从结点1到它的最短路径的结点,如果它们间有边, 则计算从结点1到未计算结点的最短路径。

    尝试解决以下来自topcoder竞赛的问题:

    中级

    接下来,让我们来看看如何解决二维的DP问题。

    平面上有N*M个格子,每个格子中放着一定数量的苹果。你从左上角的格子开始, 每一步只能向下走或是向右走,每次走到一个格子上就把格子里的苹果收集起来, 这样下去,你最多能收集到多少个苹果。

    解这个问题与解其它的DP问题几乎没有什么两样。第一步找到问题的“状态”, 第二步找到“状态转移方程”,然后基本上问题就解决了。

    首先,我们要找到这个问题中的“状态”是什么?我们必须注意到的一点是, 到达一个格子的方式最多只有两种:从左边来的(除了第一列)和从上边来的(除了第一行)。 因此为了求出到达当前格子后最多能收集到多少个苹果, 我们就要先去考察那些能到达当前这个格子的格子,到达它们最多能收集到多少个苹果。 (是不是有点绕,但这句话的本质其实是DP的关键:欲求问题的解,先要去求子问题的解)

    经过上面的分析,很容易可以得出问题的状态和状态转移方程。 状态S[i][j]表示我们走到(i, j)这个格子时,最多能收集到多少个苹果。那么, 状态转移方程如下:

    S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)
    

    其中i代表行,j代表列,下标均从0开始;A[i][j]代表格子(i, j)处的苹果数量。

    S[i][j]有两种计算方式:1.对于每一行,从左向右计算,然后从上到下逐行处理;2. 对于每一列,从上到下计算,然后从左向右逐列处理。 这样做的目的是为了在计算S[i][j]时,S[i-1][j]和S[i][j-1]都已经计算出来了。

    伪代码如下:

    以下两道题来自topcoder,练习用的。

    中高级

    这一节要讨论的是带有额外条件的DP问题。

    以下的这个问题是个很好的例子。

    无向图G有N个结点,它的边上带有正的权重值。

    你从结点1开始走,并且一开始的时候你身上带有M元钱。如果你经过结点i, 那么你就要花掉S[i]元(可以把这想象为收过路费)。如果你没有足够的钱, 就不能从那个结点经过。在这样的限制条件下,找到从结点1到结点N的最短路径。 或者输出该路径不存在。如果存在多条最短路径,那么输出花钱数量最少的那条。 限制:1<N<=100 ; 0<=M<=100 ; 对于每个i,0<=S[i]<=100;正如我们所看到的, 如果没有额外的限制条件(在结点处要收费,费用不足还不给过),那么, 这个问题就和经典的迪杰斯特拉问题一样了(找到两结点间的最短路径)。 在经典的迪杰斯特拉问题中, 我们使用一个一维数组来保存从开始结点到每个结点的最短路径的长度, 即M[i]表示从开始结点到结点i的最短路径的长度。然而在这个问题中, 我们还要保存我们身上剩余多少钱这个信息。因此,很自然的, 我们将一维数组扩展为二维数组。M[i][j]表示从开始结点到结点i的最短路径长度, 且剩余j元。通过这种方式,我们将这个问题规约到原始的路径寻找问题。 在每一步中,对于已经找到的最短路径,我们找到它所能到达的下一个未标记状态(i,j), 将它标记为已访问(之后不再访问这个结点),并且在能到达这个结点的各个最短路径中, 找到加上当前边权重值后最小值对应的路径,即为该结点的最短路径。 (写起来真是绕,建议画个图就会明了很多)。不断重复上面的步骤, 直到所有的结点都访问到为止(这里的访问并不是要求我们要经过它, 比如有个结点收费很高,你没有足够的钱去经过它,但你已经访问过它) 最后Min[N-1][j]中的最小值即是问题的答案(如果有多个最小值, 即有多条最短路径,那么选择j最大的那条路径,即,使你剩余钱数最多的最短路径)。

    伪代码:

    下面有几道topcoder上的题以供练习:

    高级

    以下问题需要仔细的揣摩才能将其规约为可用DP解的问题。

    问题:StarAdventure - SRM 208 Div 1:

    给定一个M行N列的矩阵(M*N个格子),每个格子中放着一定数量的苹果。 你从左上角的格子开始,只能向下或向右走,目的地是右下角的格子。 你每走过一个格子,就把格子上的苹果都收集起来。然后你从右下角走回左上角的格子, 每次只能向左或是向上走,同样的,走过一个格子就把里面的苹果都收集起来。 最后,你再一次从左上角走到右下角,每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0,就不用收集)。求你最多能收集到多少苹果。

    注意:当你经过一个格子时,你要一次性把格子里的苹果都拿走。

    限制条件:1 < N, M <= 50;每个格子里的苹果数量是0到1000(包含0和1000)。

    如果我们只需要从左上角的格子走到右下角的格子一次,并且收集最大数量的苹果, 那么问题就退化为“中级”一节里的那个问题。将这里的问题规约为“中级”里的简单题, 这样一来会比较好解。让我们来分析一下这个问题,要如何规约或是修改才能用上DP。 首先,对于第二次从右下角走到左上角得出的这条路径, 我们可以将它视为从左上角走到右下角得出的路径,没有任何的差别。 (即从B走到A的最优路径和从A走到B的最优路径是一样的)通过这种方式, 我们得到了三条从顶走到底的路径。对于这一点的理解可以稍微减小问题的难度。 于是,我们可以将这3条路径记为左,中,右路径。对于两条相交路径(如下图):

    在不影响结果的情况下,我们可以将它们视为两条不相交的路径:

    这样一来,我们将得到左,中,右3条路径。此外,如果我们要得到最优解, 路径之间不能相交(除了左上角和右下角必然会相交的格子)。因此对于每一行y( 除了第一行和最后一行),三条路径对应的x坐标要满足:x1[y] < x2[y] < x3[y]。 经过这一步的分析,问题的DP解法就进一步地清晰了。让我们考虑行y, 对于每一个x1[y-1],x2[y-1]和x3[y-1],我们已经找到了能收集到最多苹果数量的路径。 根据它们,我们能求出行y的最优解。现在我们要做的就是找到从一行移动到下一行的方式。 令Max[i][j][k]表示到第y-1行为止收集到苹果的最大数量, 其中3条路径分别止于第i,j,k列。对于下一行y,对每个Max[i][j][k] 都加上格子(y,i),(y,j)和(y,k)内的苹果数量。因此,每一步我们都向下移动。 我们做了这一步移动之后,还要考虑到,一条路径是有可能向右移动的。 (对于每一个格子,我们有可能是从它上面向下移动到它, 也可能是从它左边向右移动到它)。为了保证3条路径互不相交, 我们首先要考虑左边的路径向右移动的情况,然后是中间,最后是右边的路径。 为了更好的理解,让我们来考虑左边的路径向右移动的情况,对于每一个可能的j,k对(j<k), 对每个i(i<j),考虑从位置(i-1,j,k)移动到位置(i,j,k)。处理完左边的路径, 再处理中间的路径,最后处理右边的路径。方法都差不多。

    用于练习的topcoder题目:

    其它

    当阅读一个题目并且开始尝试解决它时,首先看一下它的限制。 如果要求在多项式时间内解决,那么该问题就很可能要用DP来解。遇到这种情况, 最重要的就是找到问题的“状态”和“状态转移方程”。(状态不是随便定义的, 一般定义完状态,你要找到当前状态是如何从前面的状态得到的, 即找到状态转移方程)如果看起来是个DP问题,但你却无法定义出状态, 那么试着将问题规约到一个已知的DP问题(正如“高级”一节中的例子一样)。

    后记

    看完这教程离DP专家还差得远,好好coding才是王道。

    一个例子:

    两个人从左上角(1,1)到右下角(m,n),或者从左上角走到右下角,再走回去,走过之后格子权值为0.

    两个人走,一个人的坐标为(x1,y1),另一个人的坐标为(x2,y2),有题中规定只能向下或向右走,则可得状态转移方程:
    f(x1,y1,x2,y3)  =  max { f(x1-1,y1,x2-1,y2)  ,f(x1-1,y1,x2,y-1),  f(x1,y1-1,x2-1,y2),  f(x1,y1-1,x2,y2-1)} + map[x1][y1] + map[x2][y2]
    这样写的话时间复杂度会是O(n^4),比较大容易超时,

    改进:

    因为 两个人是同时走的所以 每次都是同时移动一格:因此有   x1+y1==x2+y2 == k
    则状态方程可以改为:
    f(k,x1,x2) = ma{  f(k-1,x1,x2),  f(k-1,x-1,x2) ,f(k-1,x1,x2-1),  f(k-1,x1-1,x2-1)  }  + map[x1][k-x1] + map[x2][k-x2]

    代码:

    int a[201][101][101];  
    int map[101][101];  
      
    int max(int n1,int n2,int n3,int n4)  
    {  
        int s,d;  
        s = n1>n2?n1:n2;  
        d = n3>n4?n3:n4;  
        s = s>d?s:d;  
        return s;  
    }  
      
    int slove(int m,int n)  
    {  
        int x1,y1,x2,y2,k;  
        for (k=2;k<=m+n;++k)  
            for (x1=1;x1<=m;++x1)  
                for (x2=1;x2<=m;++x2)  
                {  
                    y1=k-x1;  
                    y2=k-x2;  
                    if (y1<0 || y2<0 || y1>n || y2>n) continue;  
                    int max = max(a[k-1][x1][x2],a[k-1][x1-1][x2],a[k-1][x1][x2-1],a[k-1][x1-1][x2-1]);  
                    if (y1==y2) a[k][x1][x2] = max + map[x1][y1];  
                    else a[k][x1][x2]= max + map[x1][y1] + map[x2][y2];  
                }  
        return a[m+n][m][m];  
    }  
      
    int main()  
    {  
        int m,n,i,j;  
      
        memset(a,0,sizeof(a));  
        scanf("%d%d",&m,&n);  
        for (i=1;i<=m;++i)  
            for (j=1;j<=n;++j)  
                scanf("%d",&map[i][j]);  
        printf("%d\n",slove(m,n));  
        return 0;  
    }  
    
    
    
    
    

    参考文章:

    http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

    http://hawstein.com/posts/dp-novice-to-advanced.html

    http://hawstein.com/posts/dp-knapsack.html

    http://www.felix021.com/blog/read.php?1587

    http://www.ahathinking.com/archives/117.html

    http://www.ahathinking.com/archives/122.html

    http://www.ahathinking.com/archives/115.html


    展开全文
  • golang实现动态规划算法(背包问题)

    千次阅读 2019-06-30 20:03:08
    本文是学习完算法图解之后的总结以及代码实现,第一部分是问题引入,第二部分是动态规划工作原理简介,第三部分是基于golang的代码实现 问题引入 【以小偷到商店偷东西为例,假设小偷有个4磅容量的背包,商店里有...

    本文是学习完算法图解之后的总结以及代码实现,第一部分是问题引入,第二部分是动态规划工作原理简介,第三部分是基于golang的代码实现

    问题引入

    【以小偷到商店偷东西为例,假设小偷有个4磅容量的背包,商店里有吉他、音响、笔记本电脑三样商品,吉他一磅重,价值1500,音响4磅,价值3000,笔记本3磅价值2000,问怎么才能让此次偷盗价值最大化? 】

    对于这个问题,很容易想到偷吉他和笔记本电脑价值最高为3500,如果再增加几个商品呢? 

    我们先来看看只有三个商品的时候都有那些选择组合,如下图,组合里总容量大于4的不能装到背包里,在剩余的组合中选择最大价值的组合,所以是吉他和笔记本组合, 组合数是2^n,当商品数量增加时组合数呈指数增长,当商品很多时显然这个方法不合适,

    那如何找到最优解呢? 就是我们接下来要介绍的动态规划

    动态规划算法工作原理

    动态规划的思想是先解决小问题,再逐步解决大问题,背包问题来说,就是先解决小背包的问题,再解决大背包的问题

    每个动态规划都是从一个网格开始的,背包问题网格如下。

    商品/

    背包容量

    1234
    吉他    
    音响    
    笔记本    

    网格的每行表示当前可偷的商品,第一行只能偷吉他,第二行能偷吉他和音响,第三行笔记本音响吉他。。。如还有商品以此类推,列表示当前背包的容量,我们把原本4磅的背包拆分成1-4磅的小背包,接下来我们逐行处理来看看。

    吉他行:第一行第一列,吉他重量1,第一列表示背包的容量也是1,刚刚好可以放下,那第一个单元格的最大价值就是1500,

    第二列两磅,也可以放下吉他,故最大价值也是1500,第三列3磅自然可以放下,且慢!笔记本也是3磅啊,记住!第一行只有吉他可以偷,我们要记住动态规划的思路是先从小问题逐步解决大问题,这很重要,所以第三个单元格最大价值只能是1500,第四个单元格也一样

    商品/

    背包容量

    1234
    吉他1500150015001500
    音响    
    笔记本    

    接下来我们看第二行,音响行,这时候你可以偷的商品是吉他和音响了,这时候我们开始考虑,第一列能放下一个四磅重的音响吗? 答案是不能,我们知道这时候还有吉他可选,吉他是1磅的,故而这时最大价值只1500,那么第二、三列情况和第一列是一样的,来到第四列,这是一个四磅背包,那么音响能不能装进背包呢? 刚刚好音响是4磅重的。那应不应该放进背包呢? 当只有吉他的时候四磅重的背包最大价值是1500,音响的价值是3000,显然应该装进背包。

    商品/

    背包容量

    1234
    吉他1500150015001500
    音响1500150015003000
    笔记本    

    来到第三行,我们可选的商品有吉他、音响、笔记本,我们来看第1列,笔记本3磅,无法放入1磅的背包中,观察这个表格,笔记本无法放入,只有音响和吉他可选择的时候,1磅背包的最大价值是多少呢? 我们只需要看上一行的可以了。第2列同第1列一样,第三列有不同了,其实对每个单元格,我们都在考虑几个问题,当前的背包能放的下吗?不能的话,当前能放进背包的最大价值是多少? 能的话,我该不该放进背包呢? 好的,我们就按这个思路来看下,当前3磅的背包能放下吗? 答案是能? 那我们应该放进去吗? 如果我们不放笔记本,那当前的最大价值是1500,而笔记本价值2000,显然应该放进背包,这时更新了背包的最大价值2000, 来看看最后一个单元格,4磅的背包能放的下笔记本,那我们该不该放进背包呢?,如果不放笔记本的话,当前的最大价值是3000,等等,放笔记本的话,不是还有1磅的空间吗? 我们还有可选择的子背包,1磅的背包最大价值是1500啊,这样背包的最大价值是3500了。

    商品/

    背包容量

    1234
    吉他1500150015001500
    音响1500150015003000
    笔记本1500150020003500

    回顾整个填充网格的过程。可提炼公式如下

    cell[n][m]= max  (上一个单元格的值[cell[n][m-1],   当前商品的价值+剩余空间的价值cell[n-1][m-当前商品的重量])

    我们求解每个单元格的目的就是要合并两个子单元格来解决更大的问题。

    代码实现

    接下是用golang实现的动态规划算法。

    package main
    
    import "fmt"
    
    const (
    	// 行
    	RAW int = 4
    	// 列
    	COL int = 5
    )
    
    // 物品的重量 舍弃数组的0位置元素
    var weight = [RAW]int{0, 1, 4, 3}
    
    // 物品的价值 舍弃数组的0位置元素
    var value = [RAW]int{0, 1500, 3000, 2000}
    
    // 动态规划网格
    var cells [RAW][COL]int
    
    // 用于回溯选择的商品 selected[i]=1 表示放进背包,0表示不放进背包
    var selected [RAW]int
    
    // 动态规划计算网格
    func dynamic() {
    
    	for i := 1; i < len(value); i++ {
    		for j := 1; j < 5; j++ {
    			cells[i][j] = maxValue(i, j)
    		}
    	}
    	for i := 0; i < RAW; i++ {
    		fmt.Printf("raw is %v \n", cells[i])
    	}
    	findBack()
    	fmt.Printf("selected goods is %v \n", selected)
    }
    
    // 判断当前单元格最大价值方法
    func maxValue(i, j int) int {
    	// 当前商品无法放入背包,返回当前背包所能容纳的最大价值
    	if j < weight[i] {
    		return cells[i-1][j]
    	}
    	// 可放进背包时候,计算放入当前商品后的最大价值
    	curr := value[i] + cells[i-1][j-weight[i]]
    	// 与当前商品不放进背包的最大价值比较,看是否应该放进背包
    	if curr >= cells[i-1][j] {
    		return curr
    	}
    	return cells[i-1][j]
    }
    
    // 回溯选择的商品方法
    func findBack() {
    	col := COL - 1
    	for i := RAW - 1; i > 0; i-- {
    		if cells[i][col] > cells[i-1][col] {
    			selected[i] = 1
    			col = col - weight[i]
    		} else {
    			selected[i] = 0
    		}
    	}
    }
    
    

    运行结果如下:

    raw is [0 0 0 0 0] 
    raw is [0 1500 1500 1500 1500] 
    raw is [0 1500 1500 1500 3000] 
    raw is [0 1500 1500 2000 3500] 
    selected goods is [0 1 0 1] 

    看到这里,你是否想到,如果我们继续增加商品,比如增加一个重一磅,价值1500的小烤箱会怎么样? 我们来试试

    在表格中新增烤箱列,来到第四行,这时候我们可选择的商品多了一个烤箱,第一个单元是可以放下烤箱的,

    我们发现吉他和烤箱都是一磅,我们要不要放进背包呢? 其实二选一即可,后面的列按之前的规则填满即可,最大价值仍然是3500,这时我们知道了可选择商品可以是吉他和笔记本,也可以是烤箱和笔记本,但是我们的算法只能给出最优解中的一个。

    商品/

    背包容量

    1234
    吉他1500150015001500
    音响1500150015003000
    笔记本1500150020003500
    烤箱150015002000

    3500

    ********************************************************* 正文完 ********************************************************

    本文是看完《算法图解》之后基于书上原理的代码实现,本来只想写代码实现算法,想了想把算法原理也整理了一遍,碍于能力有限,如文中有所欠缺,请阅读《算法图解》第九章。

    展开全文
  • 本文翻译自Coding-Geek文章:《 How does a relational database work》。...本文翻译了如下章节, 介绍数据库查询优化器中寻找最优联表方案动态规划,贪婪算法和启发式算法动态规划、贪婪算法和启...

    本文翻译自Coding-Geek文章:《 How does a relational database work》。原文链接:http://coding-geek.com/how-databases-work/#Buffer-Replacement_strategies

    本文翻译了如下章节, 介绍数据库查询优化器中寻找最优联表方案动态规划,贪婪算法和启发式算法:
    这里写图片描述

    动态规划、贪婪算法和启发式算法-Dynamic programming, greedy algorithm and heuristic

    关系型数据库会尝试之前讲过的所有优化途径。对优化器来说,最重要的工作就是在有限的时间内找出最优的解决方案。

    大部分时间,优化器不是找最优解而是找一个还过得去的解决方案。

    对于小数据的查询,穷举强制找出最优策略是可行的。但是即使最一个中型数据量表的查询,也有避免大量无效的计算而使用穷举方式计算最优解的方法。这就是动态规划算法。

    动态规划-Dynamic Programming

    隐含在这两个单词背后的含义是许多执行策略都是非常类似的。参看下面几种策略:

    它们都具有相同的子树(A JOIN B).因此不用每次都重复计算这个子树的成本,我们能够将计算结果保存起来,每次计算的时候重复利用它的结果。

    更一般的讲,我们将处理一个重复计算的问题。为了避免额外的部分结果重复结算,我们使用缓存技术。

    使用这种缓存计算,我们不需要计算(2*N)!/(N+1)!次,我们仅需要计算3的N次方次即可。在前一个样例中,连接4张表,这意味着计算的次数由336次降到了81次。如果有一个涉及8张表的大查询语句,计算次数由57657600次降到了6561次。

    它的伪代码如下:

    procedure findbestplan(S)
    if (bestplan[S].cost infinite)
       return bestplan[S]
    // else bestplan[S] has not been computed earlier, compute it now
    if (S contains only 1 relation)
             set bestplan[S].plan and bestplan[S].cost based on the best way
             of accessing S  /* Using selections on S and indices on S */
         else for each non-empty subset S1 of S such that S1 != S
       P1= findbestplan(S1)
       P2= findbestplan(S - S1)
       A = best algorithm for joining results of P1 and P2
       cost = P1.cost + P2.cost + cost of A
       if cost < bestplan[S].cost
           bestplan[S].cost = cost
          bestplan[S].plan = “execute P1.plan; execute P2.plan;
                     join results of P1 and P2 using A”
    return bestplan[S]

    对一个大的查询操作,你仍然可以使用动态规划的方式,但可以使用一些额外的规则(或者启发式算法)来移除一些不必要的可选条件:
    1. 如果我们仅仅分析一些确定类型的方案(例如只处理left-deep trees).就可以将计算次数由3的N次方降到n*2的n次方。
    .
    2. 如果我们添加一些逻辑规则来排除某些模式的方案(例如,在给定的连接条件中某张表有索引,那么除非基于索引连接否则不要使用归并连接方法)。这样能建少组合次数又不会将最优解排除掉。
    .
    3. 如果我们能添加一些规则影响执行流程(顺序)(例如:最先执行指定的连接操作),这也能减少很多的组合次数。
    .
    4. …

    贪婪算法-Greedy algorithms

    针对一个非常大的查询(关联的表很多)或者想到快速的得到计算结果,另外一种算法经常被使用,即贪婪算法。

    其基本思想是创建一个用增量的方式构建查询方案。按这个原则,贪婪算法能一次性找出方案的最优解。

    这个算法第一步先加入一个join操作,然后用同样的规则逐步加入其它的join操作。

    我们来看一个简单的例子。我们看一下之前举的4个join基于5张表的查询操作(A,B,C,D and E)。为简化问题,我们仅使用循环嵌套连接。我们使用的规则是“使用连接成本的连接”。
    1. 我们从5张表中任意一张表开始(就选A表吧)。
    2. 我们计算每一个和A表连接的成本(A可以是内连接对象,也可以是外连接对象)。
    3. 我们找到A与B表的连接是成本最低的。
    4. 然后我们可以计算所有与AB表连接结果的连接成本(AB表连接结果可以作为内连接对象或者外连接对象)。.
    5. 我们发现(A JOIN B) JOIN C拥有最低的成本。
    6. 然后我们计算所有与(A JOIN B) JOIN C结果的连接成本。依次类推。
    7. ….
    8. 最终我们找到一个成本最优的连接方案(((A JOIN B) JOIN C) JOIN D) JOIN E)。
    9. 因为我们是随机选择A表作为开始,我们也可以选B,C,D,E开始,最终得到一个成本最优的方案。

    顺便说一下,这个算法有另外一个名称:最近邻居算法。

    我不再输入细节的讲,建立一个好的模型,排好序(N*logN)问题就容易解决了。贪婪算法的时间复杂度是O(N*log(N)) , 相对于动态规划的 O(3N)的来说,这种方案不要太好。如果有一个涉及20张表的连接查询,它意味着26次计算与3486784401次计算的差异。

    贪婪算法的问题是我们假设找两表之间最优成本的连接方案,再通过不断加入新表的方式,最终得到的就是一个最优的方案。但(译者注:局部最优不等于全局最优):
    1. 即使A JOIN B在AB、AC里面是最优的。
    2. (A JOIN C) JOIN B也可能是比(A JOIN B) JOIN C更优的结果。

    为了改进这个算法结果(译者注:注意是改进,无法彻底解决),我们可以使用不同的规则执行多次贪婪算法,保留最好的方法。

    其它算法–Other algorithms
    【如果你已经厌烦算法,你可以跳过这个章节,下面讲的内容不是很关键】。
    寻找最优解在计算机研究领域是个热门话题。他们经常会尝试对一些更具体的问题或者模型找出更好的方案。例如:
    1. 如果查询语句是一个星型连接(多表连接的一种),一些数据库会使用特殊算法。
    2. 如果查询是一个并行查询语句,一些数据库也会采用特殊处理算法。
    3. …

    人们也在研究其它能代替动态规划的算法,在大查询语句中。贪婪算法属于启发式算法家族中的一员。

    贪婪算法遵循一条规则,保留上一步算法找到的结果,并尝试将它追加到当前这一步找到的方案里面。

    一些算法遵循这个原则,但在执行过程中并不保证上一步是使用的最优解决。这些算法被称为探索算法(译者注:如熟知的模拟退火算法,基因遗传算法)。

    例如:基因遗传算法遵循这样一个原则,按不保证上一步总是最优的结果:
    1. 一种方案代表了一种可行的完整查询计划。
    2. 代替(贪婪算法中)保存一种最优解决方案,基因遗传算法在每一步计算的时候保存P种结果方案。
    3. P总查询计划是随机选择的。
    4. 仅拥有最优成本的计划会被保留。
    5. 所有最优的计划合并在一起产生新的P种计划。
    6. P种新计划会被随机修改.
    7. 前面3不重复执行T次。
    8. 保留最后一次迭代(P种计划里面)的最优解。

    迭代的次数越多,你得的方案就越好。
    是不是很神奇?不,它是自然法则:适者生存。

    FYI,基因遗传算法在PostgreSQL中实现了,但是我没有找到该算法是否会默认使用。

    在数据库中还使用了其它一些启发式算法,如模拟退火,迭代改进,两阶段优化等。但是,我不清楚这些算法是否在企业级数据库中使用,或者他们仅在学术研究的数据库中用到。

    更多算法相关的信息,你可以阅读如下文章,它里面介绍了更多可行的算法: Review of Algorithms for the Join Ordering Problem in Database Query Optimization

    展开全文
  • 浅谈路径规划算法

    万次阅读 多人点赞 2017-09-19 16:32:09
    1导言 1.1算法 1.2Dijkstra算法与最佳优先搜索 1.3A*算法 2启发式算法 2.1A*对启发式函数的使用 2.2速度还是精确度? 2.3衡量单位 2.4精确的启发式函数 2.4.1预计算的精确启发式函数 2.4.2线性精
  • 1 回顾 2 你会学到什么 ... 4 动态规划入门 5 解决问题的方法 5-1 问题分析 5-2 暴力枚举 5-3 动态规划 5-4 算法思路 5-5 源码实现 5-6 模拟gif 6 算法评价 7 总结 8 GitChat 9 公众号
  • 常用算法大全-动态规划算法

    千次阅读 2007-03-09 17:44:00
    在介绍动态规划原理之后,本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠 等方面的应用。3.1 算法思想和贪婪算法一样,在动态规划中,可将一个问题的解决方案...
  • 一般实际生活中我们遇到的算法分为四类:  一>判定性问题  二>最优化问题  三>构造性问题  四>计算性问题 ...而今天所要总结的算法就是着重解决 最优化问题 ...《算法之道》对三种算法进行了归纳总结,如下表所
  • 上面的代码是利用了动态规划的思想来实现的最短编辑距离算法,它的实现与原理方程基本上是一致的,都是先对第一行和第一列的数据进行初始化,然后开始逐行逐列进行计算,填充满整个数组,即自底向上的思想,通过这样...
  • 常用算法:分治算法、动态规划算法、贪心算法、回溯法、分支限界法 分治算法 一、基本概念  在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的...
  • 动态规划 编号 题目 1最短行驶路线 问题: 给定一个的矩形网络,设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干个网格点处设置了障碍,表示...
  • 一种基于A* 算法的动态多路径规划算法 本文转自:http://www.chinaaet.com/article/3000017595 2016年微型机与应用第04期 刘斌,陈贤富,程政 (中国科学技术大学 信息科学技术学院,安徽 合肥 230027) 摘要: 车载...
  • 动态规划原理

    千次阅读 2015-12-28 11:34:44
    动态规划原理  虽然我们已经用动态规划方法解决了两个问题,但你可能还是弄不清应该在何时使用动态规划。接下来,我们关注适合应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构和子问题重叠。以及...
  • 算法动态规划

    千次阅读 2016-04-23 09:36:18
    1.首先来看看维基百科怎么定义的动态规划 引自wiki:Dynamic programming In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic...
  • 贪心算法动态规划的比较

    千次阅读 2016-07-24 00:48:34
    贪心算法与动态规划算法。通过 介绍两种算法思想的基本原理, 比较两种算法的联系和区别。 通过背包问题对比了两种算法 的使用特点和使用范围。   【 关键字 】动态规划;贪心算法;   背包问题    ...
  • 贪心算法 AND 动态规划

    千次阅读 2018-01-16 09:42:57
    贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心选择是采用从顶向下、以迭代的方法...
  • 1、动态规划算法:  动态规划:通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。   基本思想:若要解一个给定问题,我们需要解其...
  • D* Lite路径规划算法

    万次阅读 多人点赞 2018-12-19 21:43:39
    D* Lite路径规划算法D* Lite算法简述 D* Lite算法简述 D_star Lite算法是Koenig S和Likhachev M基于LPA_star 算法基础上提出的路径规划算法。 D_star Lite 算法之于 LPA_star 算法犹如 D_star 算法之于 A_star 算法...
  • 算法导论—动态规划

    2015-08-27 10:52:19
    首先区分动态规划和分治策略。 这两者有很相似的地方,都是通过组合子问题的解来求解原问题。不同的是,分治策略将原问题划分为互不相交的子问题,递归的求解子问题,再将它们的解组合起来,求出原问题的解。与之...
  • 路径规划算法

    千次阅读 2019-03-21 18:47:43
    1.1算法 1.2Dijkstra算法与最佳优先搜索 1.3A*算法 2启发式算法 2.1A*对启发式函数的使用 2.2速度还是精确度? 2.3衡量单位 2.4精确的启发式函数 2.4.1预计算的精确启发式函数 2.4.2线性精确启发式...
  • 路径规划算法进阶

    千次阅读 2020-03-28 18:14:49
    路径规划算法进阶 最早是在大学期间学习路径规划算法,严蔚敏_吴伟民的《数据结构》讲的最短路径。当时感到有些晦涩难懂,并没有理解算法思想。回头看,主要是因为应付考试,没有和实际应用场景建立连接,所以体会...
  • 算法导论-----动态规划是什么

    千次阅读 2016-12-14 21:41:20
    算法导论》中并没有把动态规划的来龙去脉介绍清楚,网上很多讲解都是动态规划的数学模型,感觉没必要系统的学习数学的定义,把人搞晕了。本文更像是一篇科普,方便理解什么是动态规划。一、动态规划概述  动态...
  • 贪心算法动态规划的区别与联系

    千次阅读 2019-09-21 09:53:00
    一、动态规划算法简介  动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。  1.基本思想与策略  动态规划算法的基本思想与分治法类似,也是将待求解...
  • 算法导论_第十六章_动态规划

    千次阅读 2016-06-12 21:08:35
    动态规划 个人对动态规划的理解: ...算法导论对动态规划的解释: 动态规划和分治方法相似,都是通过组合子问题的解来求解原问题,分治方法将问题划分为互不相交的子问题,递归的求解子问题,再将他们的解组合起来
  • 动态规划问题(一)——原理

    千次阅读 2016-08-14 01:17:42
    动态规划与分治方法相似,都是通过组合子问题的解来求解原问题。
  • 目录动态规划与字符串的编辑距离动态规划基本思想四个步骤三个例子 动态规划与字符串的编辑距离 动态规划 动态规划(dynamic programming)是解决多阶段决策问题常用的最优化理论,该理论由美国数学家Bellman等人...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,654
精华内容 12,261
关键字:

动态规划算法的工作原理