精华内容
下载资源
问答
  • golang实现动态规划算法(背包问题)

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

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

    问题引入

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

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

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

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

    动态规划算法工作原理

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

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

    商品/

    背包容量

    1 2 3 4
    吉他        
    音响        
    笔记本        

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

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

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

    商品/

    背包容量

    1 2 3 4
    吉他 1500 1500 1500 1500
    音响        
    笔记本        

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

    商品/

    背包容量

    1 2 3 4
    吉他 1500 1500 1500 1500
    音响 1500 1500 1500 3000
    笔记本        

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

    商品/

    背包容量

    1 2 3 4
    吉他 1500 1500 1500 1500
    音响 1500 1500 1500 3000
    笔记本 1500 1500 2000 3500

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

    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,这时我们知道了可选择商品可以是吉他和笔记本,也可以是烤箱和笔记本,但是我们的算法只能给出最优解中的一个。

    商品/

    背包容量

    1 2 3 4
    吉他 1500 1500 1500 1500
    音响 1500 1500 1500 3000
    笔记本 1500 1500 2000 3500
    烤箱 1500 1500 2000

    3500

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

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

    展开全文
  • 第15章 动态规划定义及原理钢条切割问题最长公共子序列最优二叉搜索树 定义及原理 动态规划和分治法类似,都是通过组合子问题解来求解原问题。动态规划应用于子问题重叠情况,及不同子...前三步是动态规划算法

    定义及原理

    动态规划和分治法类似,都是通过组合子问题的解来求解原问题。动态规划应用于子问题重叠的情况,及不同的子问题具有公共的子子问题。在这种情况下,分治法会做许多不必要的工作,重复计算求解那些公共子子问题。而动态规划只求解一次,避免了不必要的工作。
    我们通常按照下面四个步骤来设置动态规划算法:

    1. 刻画一个最优解的结构特征
    2. 递归地定义最优解的值
    3. 计算最优解的值,通常采用自底向上的方法
    4. 利用计算出的信息构造一个最优解

    前三步是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值,可以忽略步骤4,如果需要解本身,就需要做步骤4,同时在步骤3维护一些额外的信息。
    适用于动态规划方法求解的最优化问题应该具备两个要素:最优子结构和子问题重叠
    最优子结构
    如果问题的最优解包含的其子问题的解也是最优解,我们就称该问题具有最优子结构性质(即满足最优化原理)
    在尝试使用动态规划方法时一定要小心,要注意问题是否具有最优子结构性质。
    子问题重叠
    如果使用递归算法会反复求解相同的子问题,我们就称该最优化问题具有重叠子问题性质。对每个子问题求解一次,将解存入表中,当再次需要这个子问题时,直接查表,查表的代价为常量时间。与之相反,适用于分治法的问题,通常在递归的每一步都生成全新的子问题,无法通过存储提高时间效率。

    钢条切割问题

    问题描述及分析

    Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…,单位为美元)。钢条的长度均为整英寸。下图给出了一个价格表的样例。
    在这里插入图片描述
    钢条切割问题是这样的:给定一段长度为n英寸的钢条和一个价格表pn(i=1,2,…n),求切割钢条方案,使得销售收益rn最大。注意,如果长度为n英寸的钢条的价格pn足够大,最优解可能就是完全不需要切割。
    我们可以用一个通用的公式来描述最优切割收益:
    在这里插入图片描述
    第一个参数pn代表不切割的收益。其他n-1个参数对应另外n-1中方案。由于无法预知那种方案会获得最大收益,所以我们必须考虑所有的可能。
    除了上面的公式,我们还可以找到一种更简单的递归方法:
    在这里插入图片描述
    钢条切割问题满足最优子结构性质:问题的最优解由相关子问题的最优解组合而成,这些子问题可以独立求解。

    递归实现(自顶向下)

    代码实现:

        /**
         * 递归算法
         * rn = max(pi + r(n-i))
         *
         * @param p 价格表,下标从1开始
         * @param n 钢条长度
         */
        private static int recursiveCutRod(int[] p, int n)
        {
            if (n == 0)
                return 0;
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= n; i++)
            {
                q = Math.max(q, p[i] + recursiveCutRod(p, n - i));
            }
            return q;
        }
    

    自顶向下递归实现的效率很差,因为反复用相同的参数对自己进行递归调用,即它反复求解相同的问题。下图为n = 4时的调用过程。该方法考察了全部2n-1种可能的切割方案,所以时间复杂度为O(2n)。
    在这里插入图片描述

    动态规划实现

    带备忘的自顶向下法

    递归算法效率低是因为反复求解相同的子问题。所以我们可以将每个求解过的子问题的解保存下来,随后再次用到此问题的解,直接找保存的结果即可。这种方式付出额外的空间来节省时间,不过这种空间的付出会带来执行效率的显著提升。
    代码实现:

    	/**
         * 带备忘的自顶向下法
         *
         * @param p 价格表,下标从1开始
         * @param n 钢条长度
         * @param r 辅助数组,用来存储已经计算过的子问题收益,初始化为最小的整数
         */
        private static int memoizedCutRod(int[] p, int n, int[] r)
        {
            if (r[n] > Integer.MIN_VALUE)
                return r[n];
            if (n == 0)
                return 0;
            int q = Integer.MIN_VALUE;
            for (int i = 1; i <= n; i++)
            {
                q = Math.max(q, p[i] + memoizedCutRod(p, n - i, r));
            }
            r[n] = q;
            return q;
        }
    

    自底向上法

    使用这种方式的前提条件是任何子问题的求解都只依赖更小的子问题的求解。因此我们可以将子问题按规模排序,由小到大求解。
    代码实现:

    	/**
         * 自底向上法
         *
         * @param p 价格表,下标从1开始
         * @param n 钢条长度
         */
        private static int BottomUpCutRod(int[] p, int n)
        {
            int[] r = new int[n + 1];
            r[0] = 0;
            // 用来记录解本身,从而输出最优解,而不仅仅是一个值
            int[] s = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                int q = Integer.MIN_VALUE;
                for (int j = 1; j <= i; j++)
                {
                    if (q < p[j] + r[i - j])
                    {
                        q = p[j] + r[i - j];
                        s[i] = j;
                    }
                }
                r[i] = q;
            }
            return r[n];
        }
    

    如果只需要最终子问题的值,而不需要解本身,可以不需要数据s,反之则需要数据s来记录解本身。
    这两种算法的时间复杂度接近,都是O(n2)。由于没有频繁递归调用的开销,所以自底向上的方法的时间复杂度通常具有更小的系数。

    最长公共子序列

    问题描述及分析

    子序列: 不改变串的顺序,从串中去掉任意的元素而获得的新串。
    子串:子串是串的一个连续分部分。
    最大公共子序列问题: 给定两个序列X和Y,求X和Y长度最大的公共子序列。
    该问题的最优子结构如下:
    在这里插入图片描述
    根据最优子结构,可以得到如下公式:
    在这里插入图片描述
    根据公式,我们可以很容易地使用递归算法来计算结果。但为了更高的效率,我们可以用动态规划方法,自底向上求解。

    代码实现

    	/**
         * 求最大公共子序列
         */
        public static int LCSLength(String text1, String text2)
        {
            // 如果长度为0,则公共子序列为0,直接返回
            if (text1.length() == 0 || text2.length() == 0)
                return 0;
    
            // 创建[m+1][n+1]的数组,[0][n]或[n][0]用来让算法更通用,减少特殊判断
            int[][] step = new int[text1.length() + 1][text2.length() + 1];
    
            // 从1开始,可以直接取[m-1]或[n-1]
            for (int i = 1; i <= text1.length(); i++)
            {
                for (int j = 1; j <= text2.length(); j++)
                {
                    if (text1.charAt(i - 1) == text2.charAt(j - 1))
                    {
                        step[i][j] = step[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        step[i][j] = Math.max(step[i - 1][j], step[i][j - 1]);
                    }
                }
            }
            return step[text1.length()][text2.length()];
        }
    

    如果想要构造最优解,可以添加一个二维数组,记录每次跳转路径,也可以对数组result,从[m][n]开始,像左上角查找,每次只需验证三个位置即可。
    在这里插入图片描述

    最优二叉搜索树

    问题描述及分析

    代码实现

    // TODO

    展开全文
  • 最近找工作需要些计算机算法,所以把最常见的动态规划方法整理一下,从浅到深进行一下分析。 一、动态规划的原理 1、动态规划的基本思路 许多问题在实现过程中都是把原问题分解为子问题进行处理,再把子问题...

    最近找工作需要些计算机算法,所以把最常见的动态规划方法整理一下,从浅到深的进行一下分析。

    一、动态规划的原理

    1、动态规划的基本思路

    许多问题在实现的过程中都是把原问题分解为子问题进行处理,再把子问题相互结合形成原问题的解,首先最常用的分治算法就是把原问题分解为不相交的子问题,与之相反动态规划是用于把原问题分解为具有重叠子问题的一种方法。所谓的重叠子问题是指如果原问题的子问题分别为s11和s12(表示第一层子问题的问题1和问题2),在求解s11和s12的时候可能其子问题s111和s121是同一个问题,这也就是重叠子问题。在这时如果用分治算法处理,会把s11和s12当成独立的问题处理,求解了s111和s121,但实际上只要求一次就可以在另一个子问题上也应用这个结果。

    2、动态规划的使用场景

    动态规划通常用来求解最优化问题,希望在许多结果中找最优的那一个(在做题的时候,通常对应关键字:最优、最大、最小、最长和计数问题),而且都是处理离散状态时使用。除了这些,动态规划问题最主要的两个要素就是:最优子结构和重叠子问题。

    最优子结构指的是,子问题的最优决策可以导出原问题的最优决策,原问题的最优决策必定包含子问题的最优决策。这一点是可以证明的:假设子问题的解不是其最优解,那么我们就可以在原问题中将这个解替换为最优解,从而得到原问题的一个更优解,这与假设初始解为原问题的最优解相矛盾。

    对于重叠子问题,就像在基本思路中说的一样,动态规划对于每个子问题之求解一次。

    更多关于最优子结构和重叠子问题在看了后面的例子就会清晰了。

    二、例子

    在看例子之前,一般的动态规划算法都遵循一种思路:

    (1)首先观察如果用暴力的方法那么冗余部分是什么地方。

    (2)定义一个最优解的子结构,也就是原问题是如何由子问题实现的(也就是状态转移方程)

    (3)自底向上的求解最优解,并存储每一个状态(一般用一维数组,二维数组等)

    (4)对于一些问题可能会记录一些额外信息

    ——————————————————————————————————————————————————————————————————————-————

    例1:最简单的例子就是求解斐波那契数列,对于递归的方法我们都很熟悉:F(n) = F(n-1)+F(n-2),首先我们先观察冗余的地方在哪,是我们在求解F(n-1)的时候F(n-2)其实已经求解过了这就是冗余所在,接着定义最优子结构(实际上递归方程就是状态转移方程),接着自底向上求解(从n =2 开始用数组记录每一个F(n),在需要的时候直接在数组中调用就可以)。

    伪代码如下:

    vector F[n]
    F[1] = 1;
    F[2] = 1;
    for i = 3->n
        F[i] = F[i -1] + F[i - 2];
    return F [n]

    例2、假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警

    给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,你最多可以得到多少钱 在不触动报警装置的情况下。(lintcode.392

    这个问题是一个计数问题。首先分析一下这个问题看看如果用暴力的方法处理冗余在哪,如果遍历所有的可能情况对于每一个房屋都计算了很多次初始情况下的问题。接着定义最优子结构,对于每一个房屋都有两种方案,偷或是不偷,如果要偷就必定从房子的前两个房子偷过来,如果不偷就跳过这个房子。不偷的情况是在如果偷前一个房子所得的总金钱大于偷这个房子的总金钱时,就改变路径跳过当前的房子。状态转移方程为max(stl[i-2]+a[i], stl[i-1]),stl[i]为路过第i个房屋时可以得到的最大金钱,a[i]为第个房子的金钱。接着自底向上求解,保存路径上的最大金钱。

    代码为:

    class Solution {
    public:
        /**
         * @param A: An array of non-negative integers.
         * return: The maximum amount of money you can rob tonight
         */
        long long houseRobber(vector<int> A) {
            // write your code here
            vector<long> s;
            int len = A.size();
            s.push_back(0);
            s.push_back(A[0]);
            for(int i = 1; i <len; i++){
                long max = ((A[i] + s[i-1]) > s [i])? (A[i] + s[i-1]):s[i];
                s.push_back(max);
            }
            return s[len];
        }
    };


    注意:这里的s比A的长度多1,记录最初的金钱为0;在看代码的时候S[i]实际上为路过第i-1个房子的情况。

    例3、最经典的01背包问题

    给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

    对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话,最大能够装入的价值为9。

    lintcode.125

    分析:这个问题本质上也是一个计数问题,首先我们也按照前面的流程进行分析,对于每一个背包i都只有装和不装两种状态,如果装就要在剩余的背包体积中装尽量多价值的东西,如果不装同样要在这些体积中装尽量多价值的东西,只不过不包含当前这件物品,在这两种结果中找价值最高的那个。这本质上就是最优子问题的形式,其状态转移方程为f(i,y) = max(f(i-1,y),f(i-1,y-ai)+vi) //y > ai,否则后面一项为0因为剩余空间不足以加入a1//, 也就是如果现有的空间足够加入体积ai的情况下就加入比较,如果不足以加入就令这时的价值等于f(i-1,y)。我们要保存前面子问题的结果这样直接查表就可以了,我们就定义一个二维矩阵f,求解 f(n,m)就可以了。这里再解释一下f(i,y)的含义,i为物品序号(也就是前i个物品的数量),y为可用空间,此时背包可以装的最大价值。可以通过这个blog继续理解一下,可能叙述的顺序不一样,但是本质是相同的。

    在分析的时候,我们发现,每一个状态i都只利用了i-1的状态,可不可以利用这个来降低空间复杂度呢?其实可以用一个滚动数组实现(在当前状态i只由i-1状态决定时可用滚动数组进行优化)。也就是定义两个指向数组的指针v1和v2,在利用前一状态所在的v1计算完成当前状态存入v2后,另v1指向v2,v2指向v1,继续处理。

    class Solution {
    public:
        /**
         * @param m: An integer m denotes the size of a backpack
         * @param A & V: Given n items with size A[i] and value V[i]
         * @return: The maximum value
         */
        void swap(int*& p1, int*& p2){
            int *temp = p1;
            p1 = p2;
            p2 = temp;
        }
    //    int max(int a, int b){
     //       return a > b ? a : b;
    //    }
        int backPackII(int m, vector<int> A, vector<int> V) {
            // write your code here
            int len = A.size();
            if(len == 0 || m == 0) return 0;
            int *v1 = new int[ m + 1] ;//v1保存上一状态
            int *v2 = new int[ m + 1];//v2指示当前状态
            for(int i = 0; i < m+1; i++){
                if(A[0] > i)
                    v1[i] = 0;
                else
                    v1[i] = V[0];
            }
            for(int i = 1; i <len; i++){//i代表物体的序号
                for(int j = 0; j < m + 1; j++){//j代表背包的面积
                    if( j - A[i] < 0){
                        v2[j] = v1[j];
                    }
                    else{
                        v2[j] = max(v1[j - A[i]] + V[i], v1[j]);//选i或者不选i中,取价值最大的 
                    }
    
                }
                swap(v1,v2);
            }
            return v1[m];
        }
    };

    进一步,其实,还可以用一个数组实现。我们看一下这个状态转移方程,f(i,y) = max(f(i-1,y),f(i-1,y-ai)+vi) ,是以j从小到大的顺序求解的,如果我们把j从大到小排列就可以用一个数组来实现了,因为每一个y都是由前面的数据决定的,只要前面的数据不变,就可以得到正确的值。


    再进一步,假设物品的重量为1000 和2000,背包可装3000,其实没有必要用一个3000的向量,这也有优化的潜力。

    ————————————————————————————————————————————————————————————————————————————

    下面两个都是子问题和原问题之间的状态转移方程稍微有点麻烦的问题



    例4、矩阵连乘问题(这个的分析思路很重要)

    给定一个n个矩阵的序列(矩阵链),由于矩阵乘法满足结合律,所以可以在任意地方加括号都可以,但是虽然结果一样但是计算复杂度不一样,不同的计算顺序所需的元素乘法次数不同,求一个完全括号化的矩阵连乘,使得计算的乘法次数最小。

    分析如下,考虑矩阵链{A1,A2,...,An}最优化的括号方案必定在某个位置k(1<= k<=n)划分这个链也就是在Ak和Ak+1之间吧矩阵链分成两个链的乘法,{A1,....Ak}和{Ak+1,....An}。前一个矩阵链的形式与原矩阵链类似,但是后一个形式却不一样,所以我们必须允许子问题可以在两端都可以变化,即{Ai,....,Aj}的形式。这个分析在很多情境下都适用。

    原问题的状态转移方程就可以写为m[i,j] = min{m[i, k]+ m[k+1,j]}+Pi-1*Pk*Pj ;(i<=k<j) 其中(i < j),Pi为矩阵i对应的列数。得到了状态方程就可以自底向上求解了。问题的复杂度为O(n3)。

    伪代码如下:

    MATRIX-CHAIN-ORDER(p){
    n = p.length()-1;
    m[1...n,1....n] and s[1,n-1,2...n]//m记录最小乘法数,s记录分割点
    for i = 1->n
    	m[i,i] = 0;//同一个矩阵不需要乘法;
    }
    for i = 2 ->n  //i为右边界
    	for j = 1 - > i - 1 //j为左边界
    		l = i - j + 1
    		for k = i - >j - 1
    			q = m[i, k]+ m[k+1,j]}+Pi-1*Pk*Pj ;
    			if(q < m[i,j])
    				m[i, j] = q;//不断更新得到最小值
    				s[i, j ] = k;
    return m and s

    注意:结果中的矩阵只有i>j的一半是有意义的。


    例5、最长公共子序列

    这个问题是动态规划最常见的问题,首先要知道什么是子序列:是在该序列中删去若干元素后得到的序列,也就是可以不是连续的。可以参考lintcode77.

    与前面问题的区别是,这个问题根据原问题的条件排除了一部分子问题。

    首先分析一下问题,如果暴力搜索所有公共子序列明显复杂度太高了。现在我们看一下原问题是怎么由子结构所构成的。假设两个序列X{x1,...xn},Y{y1,..ym}。 对于任意一个状态xi和yj总共有两种可能性:xi = yj和xi!=yj,对于前一种情况:原问题与子问题的关系就是LSC( i , j) = LSC(i+1) + 1也就是公共子序列长度在前面的基础上加1;对于第二种情况有两种,一种是LSC(i, j) = LSC(i, j-1) 一种是LSC(i, j) = LSC(i-1, j) 取两者中的大的就是当前的最长公共子序列长度。

    代码如下:

    class Solution {
    public:
        /**
         * @param A, B: Two strings.
         * @return: The length of longest common subsequence of A and B.
         */
        int longestCommonSubsequence(string A, string B) {
            // write your code here
            int lenA = A.length();
            int lenB = B.length();
            if(lenA == 0 || lenB ==0) return 0;
            int LSC[lenA + 1][lenB + 1];
            for(int i = 0; i < lenA + 1; i++){
                LSC[i][0] = 0;
            }
            for(int i = 0; i < lenB + 1; i++){
                LSC[0][i] = 0;
            }
            for(int i = 1; i < lenA + 1; i++){
                for(int j = 1; j < lenB + 1; j++){
                    if(A[i-1] == B[j-1]){
                        LSC[i][j] = LSC[i-1][j-1]+ 1;
                    }
                    else
                        LSC[i][j] = max(LSC[i -1][j], LSC[i][j-1]);
                }
            }
            return LSC[lenA][lenB];
        }
    };


    最后举一个例子作为动态规划的完结。证明能用贪心的时候就不用动态规划了。

    例6、Wiggle Subsequence

    问题在leetcode376,这里有两种方法一种使用动态规划求解,一种是用贪心算法求解。但是总感觉用动态规划过于麻烦,但是可以不断优化到和贪心算法一样的时间和空间复杂度。

    问题可以叙述为,找到一种最长的摆动的子序列长度。例子在题介绍上面有。

    分析:这个问题类似于找极点的感觉,但是有时候不变的起始点也可能是摆动子序列的一部分。对于一个原问题m[i],有两种情况一种是m为极点,一种是非极点。对于前一种情况首先判断是极小值还是极大值m[i] = m[i-1]+1;对于第二种情况,首先如果前后是递增或递减 m[i] = m[i-1],如果是后面的值与当前值相等m[i] = m[i-1],就跳过后面的值,直到可以确定是递增或递减。这是贪心的思想。

    我的贪心代码如下:

    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            int len = nums.size();
            if(len <= 1) return len;
            int ret = 0;
            int diff = nums[1] - nums[0];//用于记录上一个极值点的状态
            ret = diff !=0 ? 2: 1;
            for(int i = 2; i < len ; i++){
                if( (diff <= 0 && nums[i-1] < nums[i] )|| (diff >= 0 && nums[i-1] > nums[i] )){
                    ret++;
                    diff = nums[i] - nums[i-1];
                }
                   
            }
            return ret;
        }
    };



    展开全文
  • 上一章已经详细地分析过动态规划,接下来还是结合具体问题,感受一下这些算法是怎么工作的,是如何解决问题的,再问体体会这些算法的本质。我觉得比单纯记忆原理和定义更有价值。 贪心算法 1. 如何理解贪心算法? ...

    贪心、回溯、分治、动态规划,确切地讲,应该是算法思想,并不是具体的算法,常用来知道我们设计具体的算法和编码等。上一章已经详细地分析过动态规划,接下来还是结合具体问题,感受一下这些算法是怎么工作的,是如何解决问题的,再问体体会这些算法的本质。我觉得比单纯记忆原理和定义更有价值。

    • 贪心算法

    1. 如何理解贪心算法?

    假设我们有一个可以容纳100kg物品的袋子,可以装各种物品。有以下5种豆子,每种豆子的总量和总价值各不相同。为了让袋子中所装物品的总价值最大,我们如何选择袋子装那些豆子,有该装多少呢?

                                                                

    这个问题很容易解决,只要先算一算每种豆子的单价,再按照单价依次从高到低来装就好了。单价从高到低排列,依次是:黑豆、绿豆、红豆、青豆、黄豆,所以,可以在袋子中装20kg黑豆、30kg绿豆、50kg红豆。这个问题解决思路显而易见,本质上借助贪心算法。

    总结一下贪心算法解决问题的步骤:

    首先要能联想到贪心算法:针对一组数据,定义了限制值和期望值,希望选出几个值,在满足限制值的情况下,期望值最大。类比刚刚的例子,限制值就是不超过100kg,期望值是豆子的总价值。

    然后,尝试用贪心算法来解决:每次选择当前情况下,在对限制值同等贡献量的情况下,对期望值贡献最大的数据。类比刚刚的例子,在重量相同的情况下,对价值量贡献最大的豆子。

    最后,举出几个例子、看贪心算法的结果是否最优。大部分情况,举几个例子验证一下就可以了。因为严格的证明贪心算法的正确性,很复杂,需要设计比较多的数学推理。另外,从实践角度来说,大部分能用贪心算法解决的问题,贪心算法的正确性都是显而易见的,不需要严格的数学证明。

    然而,贪心算法的结果并不总是最优解。接下来看一个例子,在一个有权图中,从顶点的S开始,找一条到顶点T的最短路径(边的权值和最小)。贪心算法的解决思想,每次都选择一条跟当前顶点相连的权值最小的边,直到找到顶点T。求出的最短路径是S->A->E->T,路径长度是1+4+4=9。但是,贪心算法求出的结果并不是最短路径,因为路径S->B->D->T才是最短路径,路径长度是2+2+2=6。

                                                                  

    为什么贪心算法在这种问题上不工作了呢?主要原因是,前面的选择会影响后面的选择。S->A 和S->B,接下来面对的顶点和边,是完全不同的。所以即使第一步选择最优的走法(S->A,边最短),但有可能因为这一部选择,导致后来的每一步选择都很糟糕,最终也就无缘全局最优解。

    2. 实战分析贪心算法

    分糖果:m个糖果和n个孩子(m<n),每个孩子最多只可以分到一个糖果,每个糖果大小不等,s1, s2, s3,..., sm。除此之外,每个孩子对糖果大小的需求也不一样,只有糖果大小 >= 孩子对糖果大小需求的时候,孩子才得到满足。这里的问题是,如何分配糖果,能尽可能满足最多数量的孩子?

    可以把问题抽象成,从n个孩子中,抽取一部分孩子分配糖果,让满足的孩子的个数(期望值)达到是最大值,限制值就是糖果个数m。对于一个孩子来说,如果小的糖果可以满足,就没必要用更大糖果,这样更大的糖果可以留给对糖果需求更大的孩子。而且,满足对糖果需求大的孩子和对糖果需求小的孩子,对期望值贡献一样,那么我们就从满足需求小的孩子开始分配糖果。我们每次从剩下孩子中找出对糖果需求最小的孩子然后发给他剩下的能满足他需求的最小糖果,这样得到的分配方案,也就是满足孩子个数最多的方案。

    钱币找零:假设我们1元、2元、5元、10元、20元、50元、100元这些面额的纸币,张数分别是c1、c2、c5、c10、c20、c50、c100。要支付K元,最少要用多少张纸币呢?

    显而易见,我们当然是用面额最大的优先支付,如果不够,再用更小面额的纸币,剩下的用1元补齐。在贡献相同期望值(纸币张数)的情况下,我们希望多贡献点金额,这样可以让纸币数更少,这是一种贪心算法解决思路。

    区间覆盖:假设有n个区间,起始点和结束端点分别是 [l1, r1], [l2, r2], [l3, r3], ..., [ln, rn] 。从它们中间选出一部分区间,满足两两不相交(端点相交的情况不算相交),问最多能选出多少个区间?

                                                                          

    这个问题的处理思路不是很好懂,但是最好弄懂,因为这个处理思想在很多贪心算法问题中都会用到,比如任务调度,教师排课等。思路是这样的:假设 n 个区间中最左端点是 lmin,最右端点是 rmax。这个问题相当于选择几个不相交的区间,从左到右将[lmin, rmax] 覆盖上。按照起始端点从小到大的顺序对这 n 个区间排序。每次选择的时候,左端点跟前面的已经覆盖的区间不重合,右端点尽量小,这样可以让剩下的未覆盖的区间尽可能的大,就可以放置更多的区间,这实际上就是一种贪心的选择方法。

                                                                      

    霍夫曼编码:假设我们有一个包含1000个字符的文件,每个字符占1bytes,用需要 8000bits,那有没有更加省空间的存储方式呢?为方便讨论,先假设这1000个字符只包含6个不同的字符,分别是a、b、c、d、e、f。我们知道,3个二进制位可以表示8个不同字符,所以为了尽量减少存储空间,每个字符就用3个二进制位表示,a(000)、b(001)、c(010)、d(011)、e(100)、f(101),那存储这1000个字符只需3000bits,但是还有没有更节省空间的存储方式呢?

    霍夫曼编码出现了,它是一种十分有效的编码方法,广泛用于数据压缩中,压缩率一般在 20%~90%之间。霍夫曼编码不仅会考察文本中多少个字符,还考察每个字符出现的频率,根据频率的不同,选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法,来进一步增加压缩率。如何给不同频率的字符选择不同长度的编码呢?根据贪心算法,我们可以把出现频率比较多的字符用稍微短一些的编码,出现频率比较少的字符用稍微长一些的编码。

    对于等长的编码来说,解压缩比较简单。比如刚才例子中,用3个bit表示一个字符。在解压缩的时候,每次从文本中读取3个二进制码,然后翻译成对应字符。但是霍夫曼编码是不等长的,这样就导致霍夫曼解压缩比较复杂。为了避免歧义,霍夫曼编码要求各个字符的编码之间,不会出现某个编码是另一个编码前缀的情况。

     假设6个字符,按照出现频率从高到低依次是a、b、c、d、e、f。可以按照下表进行编码,在解压缩的时候,每次读取尽可能长的可解压的二进制串。经过这种编码压缩之后,这1000个字符只需要2100 bits 就可以了。

                                                                  

    霍夫曼编码思想不难理解,但是如何根据出现频率,给不同的字符进行不同长度的编码,稍微需要一些技巧。把每个字符看作一个节点,并且辅带着把频率放到优先队列中。从队列中取出最小的两个节点A、B,然后新建一个节点C,频率是AB频率之和,并把C作为AB节点的父节点。再把C节点放到优先队列中。重复这个过程,直到队列中没有数据。

                                                                 

    现在给每一条边加上一个权值,指向左子节点的边标记为0,指向右子节点的标记为1,那么从根节点到叶节点的额路径就是叶节点对应字符的霍夫曼编码。

    贪心算法适用场景有限,一般是指导设计基础算法,如 Prim 和 Kruskal最小生成树算法、还有Dijksta 单元最短路径算法。另外,贪心算法最难的部分是如何将要解决的问题抽象成贪心算法模型,只要这一步搞定了,编码就很简单。

     

    • 分治算法

    1. 如何理解

    分治算法,核心思想是分而治之,也就是将原问题划分成 n 个规模较小,并且结构越原问题类似的子问题,递归地解决这些子问题,然后在合并结果,得到原问题的解。这个定义看起来有点像递归的定义,但其实,分治是处理问题的思想,递归是一种编程技巧,分治算法一般比较适合用递归实现。分治算法的递归实现中,每一层递归都会涉及三个操作:

    分解:将原问题分解成一系列子问题;

    解决:递归求解每个子问题,若子问题足够小,则直接求解;

    合并:将子问题的结果合并成原问题的解。

    能用分治算法解决的问题,一般需要满足下面几个条件:

    原问题和子问题具有相同的模式;

    子问题可以独立求解,子问题之间没有相关性,这是跟动态规划最明显的区别;

    具有终止分解的条件,当问题足够小的时候,可以直接求解;

    可以将子问题合并成原问题,合并操作的复杂度不能太高,否则就起不到减小算法总体复杂度的效果。

    2. 举例分析

    如何编程求出一组数据的有序对个数或者逆序对个数?

    用分治方法试试。将数组A分解为数组 A1 和 A2,分别计算 A1 和 A2的逆序对个数 K1 和 K2,然后计算 A1 与 A2之间的逆序对个数 K3,那数组A的逆序对个数就等于 K1+K2+K3。分治算法要求子问题合并的代价不能太大,那么如何快速求出 A1 与 A2之间的逆序对个数?

    这里要借助归并排序算法,其中有一个关键操作,就是将两个有序的小数组,合并成一个有序的数组。在这个过程中我们就可以计算两个小数组的逆序对个数。每次合并操作,我们都计算逆序对个数,把这些逆序对个数求和就是数组的逆序对个数。

                                                    

    看代码:

    int num = 0;
    int count(int a[], int n)
    {
        num = 0;
        mergeSortCounting(a, 0, n-1);
        return num;
    }
    
    void mergeSortCounting(int a[], int p, int r)
    {
        if(p >= r)
            return;
        int q = (p+r)/2;
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q+1, r);
        merge(a, p, q, r);
    }
    
    void merge(int a[], int p, int q, int r)
    {
        int i=p, j=q+1, k=0;
        int *tmp = new int[r-p+1];
        while(i<=q && j<=r)
        {
            if(a[i] <= a[j])
                tmp[k++] = a[i++];
            else
            {
                num += (q-i+1);
                tmp[k++] = a[j++];
            }
        }
        while(i<=q)
            tmp[k++] = a[i++];
        while(j<=r)
            tmp[k++] = a[j++];
        for(i=0; i<r-p; i++)
            a[p+i] = tmp[i];
        delete []tmp;
    }

    3. 海量数据处理的应用

    给10G的订单文件,按照金额排序,因为数据量大,如果机器内存只有几个G,就无法一次性加载到内存,也就无法单纯地使用快排、归并等基础算法来解决。要解决这个数据量大到内存装不下的问题,可以利用分治思想。可以将数据集合根据某种算法,划分成几个小的数据集合,每个小的数据集合单独加载到内存来解决,然后再将小数据集合合并成大数据集合。利用这种分治思想,还能利用多线程或者多机处理,加快处理的速度。

    给10G订单排序,可以先扫描一遍订单,根据金额划分为几个金额区间,比如1~100,101~200,等等,再将它们分别放到一个小文件。这样每个小文件都可以单独加载到内存排序,最后再合并,就是最终有序的10G订单数据了。

    如果订单存储在类似GFS这样的分布式系统上,当10G订单被划分成多个小文件时,每个文件可以并行加载到多台机器上处理,最后将结果合并,这样并行处理的速度也加快了很多。不过这里有一点要注意,数据的存储和计算所在的机器是同一个或者在网络中很靠近(比如在一个局域网内,数据存储速度很快),否则就会因为数据访问速度,导致整个处理过程不但不会变快反而更慢。

     

    • 回溯算法

    回溯算法有很多应用场景,深度优先搜索、正则表达式、编译原理中的语法分析、数学问题(数独、八皇后、0-1背包、图的着色、旅行商问题、全排列等)。

    1. 如何理解回溯算法

    人的一生有很多重要的岔路口,每个选择会影响今后的人生。有的人能做正确的选择,最后生活、事业都达到很高的高度;而有的人一路选错,最后碌碌无为。如果人生可以量化,那如何才能在岔路口做出正确的选择,让自己人生“最优”呢?

    可以借助贪心算法,在每次面对岔路口的时候,都做出看起来最优的选择,期望着一组选择,是我们的人生达到“最优”。但是,贪心算法并不一定能得到最优解,可以试试回溯。电影《蝴蝶效应》,讲的就是主人公为了达到自己目标,一直通过回溯的方法,回到童年,在关键的岔路口,重新选择。这里蕴含的思想就是回溯算法。

    笼统地讲,回溯算法很多时候都应用在“搜索”这类额问题上。不过这里的搜索并不是说的是狭义上的搜索,比如说图的搜索算法,而是是广义上的,在一组可能的解中,走做满足期望的解。

    回溯算法思想有点类似枚举搜索,枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免重复和遗漏,我们把问题求解过程分为多个阶段。每个阶段都会面对一个“岔路口”,吸纳随意选一条路走,当发现走不通的时候(不符合期望的解),就回退到刚刚的岔路口,另选一个走法继续走。

    先来看一下八皇后问题:

    我们有一个8X8的棋盘,希望往里放8个棋子,每个棋子所在行、列、对角线都不能有另一个棋子。八皇后问题就是期望找到所有满足这种要求的放旗子方式。

                                                

    我们把问题分为8个阶段。一次将8个棋子放第一行、第二行、第三行......第八行。在放置的过程中,我们不停的检查当前的方法,是否满足要求。如果满足,则跳到下一行继续放置棋子;如果不满足,那就再换一种方法,继续尝试。

    下面是八皇后算法的代码:

    int *result = new int[8];   //全局或成员变量,下标表示行,值表示列
    
    void cal8queens(int row)
    {
        if(row == 8)
        {
            printQueens(result);
            return;
        }   
        for(int column = 0; column<8; ++column)
        {
            if(isok(row, column))                //有些放法不满足要求
            {
                result[row] = column;            //第row行棋子放到column列
                cal8queens(row+1);               //考察下一行
            }
        }
    }
    
    bool isok(int row, int column)
    {
        int leftup = column - 1, rightup = column + 1;  
        for(int i=row-1; i>=0; i--)           //逐行往上考察每一行
        {
            if(result[i] == column)         //第i行column列有棋子吗
                return false;
            if(leftup >= 0)                 //考察左上对角线:第i行leftup有棋子吗
                if(result[i] == leftup)
                    return false;
            if(rightup < 8)                //考察右上对角线:第i行rightup有棋子吗
                if(result[i] == rightup)
                    return false;
            leftup--;rightup--;
        }
        return true;
    }
    
    void printQueens(int *result)
    {
        for(int row=0; row<8; row++)
        {
            for(int column =0; column<8; column++)
            {
                if(result[row] == column)
                    cout << "Q ";
                else
                    cout << "* ";
            }
            cout << endl;
        }
        cout << endl;
    }
    

    2. 两个回溯算法的经典应用

    0-1背包问题

    0-1背包是非常经典的算法问题,很多问题都可以抽象成这个问题模型。这个问题的经典解法是动态规划,但是,还有一种简单但是不那么高效的解法,就是回溯算法。0-1背包问题有很多变体,这里讲的都是比较基础的。我们有个背包,背包总的承载重量是W kg。现在我们有n 个物品,每个物品重量不等,并且不可分割,要么装要么不装,所以叫 0-1 背包问题。期望选几件物品,装到背包中。在不超过背包所能装在重量的前提下,如何使背包中的物品重量最大?

    每个物品装进背包都两种装法,n 个物品,总共有2^n 种装法,去掉超过W kg的,从剩下装法中选择总重量最接近W kg的。所以,如何才能不重复地穷举出2^n种装法呢?那么就是回溯算法了,可以把物品依次排列,整个问题就分解为 n 个阶段,每个物品对应一个物品怎么选择。先对第一个物品进行处理,选择装进去或不装,然后再递归地处理剩下物品。相关diamante已经在上一章中已经讲过,这里不赘述了。

    正则表达式

    正则表达式中最重要的一种算法思想就是回溯。通配符的应用能表达非常丰富的语义,为了方便说明,假设正则表达式只包含 "*" 和 "?" 两种通配符,并对他们的语义稍做改变,其中,"*" 匹配任意多个(>=0)任意字符,"?" 匹配零个货一个任意字符。基于以上背景假设,下面看看如何用回溯算法,判断一个给定文本,能否跟给定的正则表达式匹配?

    我们一次考察表达式的每个字符,如果是非通配符,就直接跟文本的字符匹配,如果相同则往下处理,如果不同,则回溯。

    直接看代码:

    bool matched = false;
    int plen ;
    bool match(char text[], int tlen)
    {
        matched = false;
        rmatch(0, 0, text, tlen);
        return matched;
    }
    
    void rmatch(int ti, int pj, char text[], int tlen)
    {
        if(matched)
            return false;
        if(pj == plen)   //正则到达结尾
        {
            if(ti == tlen)   //文本串也结尾了
                matched = true;
            return;
        }
        if(pattern[pj] == '*')  //  * 匹配任意字符
        {
            for(int k=0; k<tlen-ti; k++)
                rmatch(ti+k, pj+1, test, tlen);
        }
        else if(pattern[pj] == '?')  // ? 匹配0或1个字符
        {
                rmatch(ti, pj+1, test, tlen);
                rmatch(ti+1, pj+1, test, tlen);
        }
        else if(ti<tlen && pattern[pj] == text[ti])   //纯字符匹配
                rmatch(ti+1, pj+1, test, tlen);
    }
    • 四种算法的比较分析

    如果给它们分一下类,那贪心、回溯、动态规划可归为一类,而分治单独归为一类。因为前三个算法解决的问题模型,都可以抽象成多阶段决策最优解模型,而分治算法解决的问题大部分也是最优解问题,但是,大部分都不能抽象成多阶段决策模型。

    回溯算法是个“万金油”。基本上能用跟动态规划、贪心解决的问题,都可以用回溯去解决。回溯算法相当于穷举搜索,穷举所有情况,然后得到最优解。不过回溯算法时间复杂度非常高,指数级的,只能解决小规模数据问题。对于大规模数据,执行效率就相当低。

    尽管冬天规划算法高效,但并不是所有问题都可以用动态规划来解决,必须满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题上,动态规划和分治算法的区分很明显,分治算法分割成的子问题,不能有重复子问题,而动态规划则相反,之所以高效,就是因为回溯算法实现中存在大量重复子问题。

    贪心算法算是动态规划的一种特殊情况。解决问题更加高效,代码实现更简洁,不过他解决问题也更加有限。他能解决的问题必须满足三个条件,最优子结构,无后效性和贪心选择性。其中,最优子结构和无后效性跟动态规划无异,贪心选择性,就是通过局部最优选择,能产生全局最优选择。每一个阶段,我们都选择当前最优的决策,所有阶段的决策完之后,最终由这些局部最优解构成全局最优解。

     

    以上所述,是本人最近在极客时间上学习数据结构和算法相关课程做的笔记吧。

    具体参照: https://time.geekbang.org/column/intro/126

    展开全文
  •   知道了AC自动机的工作原理之后,我不得不发出感慨,这真是个十分漂亮的算法,无论是在时间上还是空间上亦或是常数上,都有非常出色的表现。 AC自动机的基本操作就是多串匹配,最朴素的思想就是跑...
  • 贪心、分治、回溯、动态规划这 4 个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易事情。所以,接下来这 4 个算法思想讲解,我依旧不会长篇大论地去讲理论,而是结合具体问题,让...
  • 基础的数据结构和算法...所以,接下来的这 4 个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让你自己感受这些算法是怎么工作的,是如何解决问题的,带你在问题中体会这些算法的本质。我觉得
  • 贪心算法、分治算法、回溯算法动态规划这 4 个算法思想,原理解释起来都不难,但是要真正掌握且灵活应用它们,并不是件容易事情。确切地说,它们应该算是算法思想,并不是具体的算法,常用来指导我们设计具体...
  • 数学建模方法:蚁群算法

    热门讨论 2010-05-21 15:35:07
    基于蚁群算法的无人机任务规划 多态蚁群算法 MCM基板互连测试的单探针路径优化研究 改进的增强型蚁群算法 基于云模型理论的蚁群算法改进研究 基于禁忌搜索与蚁群最优结合算法的配电网规划 自适应蚁群算法在序列...
  • 【笔记】算法图解

    2020-03-15 10:52:17
    文章目录0 写在前面1 算法简介1.1 引言1.2 二分查找1.3 大O表示法常见的大O运行时间旅行商问题2 选择排序2.1 内存的工作原理2.2 数组和链表2.3 选择排序3 递归3.2 基线条件与递归条件3.3 栈4 快速排序4.1 分而治之...
  • 第一次看到“装配线与工作站问题”是老师在课堂上出一个题目,当时脑子简单,直接就用穷举法给解了,后来看到《算法导论(第二版)》这本书用动态规划算法来解决,实际测试后发现其效率是穷举法四、五倍,...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 175
精华内容 70
关键字:

动态规划算法的工作原理