精华内容
下载资源
问答
  • 本文翻译自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

    展开全文
  • 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

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

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

    展开全文
  • 动态规划工作原理:先解决相对简单的子问题,再逐步解决大问题 动态规划是一个难以理解的概念,真的 动态规划经典问题 背包问题 假设张三要去野营,他准备了以下物品: 每样东西都有相应的价值,可呆呆的他在收拾...

    Python 算法之 动态规划


    动态规划是个啥🤔

    动态规划(Dynamic Programming),简写为 DP,是寻找多分支下最优解的过程

    动态规划工作原理:
    先解决相对简单的子问题,再逐步解决大问题

    根据下面这些问题,来了解一下什么是动态规划🙄


    动态规划经典问题🤓

    背包问题

    背包问题1 是动态规划中中一个很经典的问题,这个问题生动有趣,所以我放在第一个来讲

    假设张三要去野营,他准备了以下物品:

    物品 重量 价值
    3斤 10
    1斤 3
    食物 2斤 9
    小刀 3斤 4
    衣物 2斤 5
    手机 1斤 10

    每样东西都有相应的价值,可呆呆的他在收拾背包时发现,他的背包 最大容量只有6斤,装不下所有的东西,只能从这堆东西中挑选 组合价值 最高的物品

    关键点

    • 约束条件: 将背包的容量大小(承重)划分成不同容量大小的子背包,计算每个子背包的最大价值
    • 物品重量不能超过当前背包容量,不可能将重量为5斤的物品放进容量为2斤的背包里,机器可不能像人一样会自己识别大小,这看起来可笑的问题确实会发生,得加上判断语句

    背包问题
    只能拿一次物品的情况下

    每个子问题取得一次物品,就不能再取相同的物品,要么这个要么这个,拿了就没
    比如此时 背包容量为6斤,拿了一瓶水后 占用了背包容量3斤剩余容量为3斤 我要么再拿一本书和一件衣服(1+2),要么再拿食物和一部手机(2+1)等,不可能再去拿一瓶水

    def dynamic_p() -> list:
        items = [  									 # 物品项
            {"name": "水", "weight": 3, "value": 10},
            {"name": "书", "weight": 1, "value": 3},
            {"name": "食物", "weight": 2, "value": 9},
            {"name": "小刀", "weight": 3, "value": 4},
            {"name": "衣物", "weight": 2, "value": 5},
            {"name": "手机", "weight": 1, "value": 10}
        ]
        max_capacity = 6                             # 约束条件为 背包最大承重为6
        dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]
    
        for row in range(1, len(items) + 1):         # row 代表行
            for col in range(1, max_capacity + 1):   # col 代表列
                weight = items[row - 1]["weight"]    # 获取当前物品重量
                value = items[row - 1]["value"]      # 获取当前物品价值
                if weight > col:                     # 判断物品重量是否大于当前背包容量
                    dp[row][col] = dp[row - 1][col]  # 大于直接取上一次最优结果 此时row-1代表上一行
                else:
                    # 使用内置函数max(),将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                    dp[row][col] = max(value + dp[row - 1][col - weight], dp[row - 1][col])
        return dp
    
    
    dp = dynamic_p()
    for i in dp:                                     # 打印数组
        print(i)
    
    print(dp[-1][-1])                                # 打印最优解的价值和
    

    可重复拿取物品的情况下

    先思考一个问题,为什么上面的代码可以不重复拿去?
    那是因为,我们是根据 当前物品的价值+剩余空间的价值 来更新最优解,可这个剩余空间价值是通过上一行来获取的,并未加上当前的商品价值,因此只需要加上当前的商品价格作为参考,即在当行获取最优解

    def dynamic_p() -> list:
        items = [  									 # 物品项
            {"name": "水", "weight": 3, "value": 10},
            {"name": "书", "weight": 1, "value": 3},
            {"name": "食物", "weight": 2, "value": 9},
            {"name": "小刀", "weight": 3, "value": 4},
            {"name": "衣物", "weight": 2, "value": 5},
            {"name": "手机", "weight": 1, "value": 10}
        ]
        max_capacity = 6                             # 约束条件为 背包最大承重为6
        dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]
    
        for row in range(1, len(items) + 1):         # row 代表行
            for col in range(1, max_capacity + 1):   # col 代表列
                weight = items[row - 1]["weight"]    # 获取当前物品重量
                value = items[row - 1]["value"]      # 获取当前物品价值
                if weight > col:                     # 判断物品重量是否大于当前背包容量
                    dp[row][col] = dp[row - 1][col]  # 大于直接取上一次最优结果 此时row-1代表上一行
                else:
                    # row-1 为上一行,row为本行,若要重复拿取,只需要在目前物品所在的那一行寻找最优解即可
                    dp[row][col] = max(value + dp[row][col - weight], dp[row - 1][col])
        return dp
    
    
    dp = dynamic_p()
    for i in dp:                                     # 打印数组
        print(i)
    
    print(dp[-1][-1])                                # 打印最优解的价值和
    

    可以看到,创建二维数组的时候,行列数都加了一🙄

    • 每个单元格的取值,要么是来自 上一 CELL(单元格) 的值,要么来自 当前物品的价值+剩余容量价值,这些取值都离不开上一行的最优解值,可二维数组中第一行的每一个单元格(即子问题) ,都没有上一个 CELL 的值,那就需要在第一行前再插入每个 CELL 都为0的一行
    • 数组的索引从0开始,1的索引在数组第二个位置,为方便编写和理解,多增一行一列,索引为0的行列不做变动

    背包问题 带占位0

    根据背包问题可以得到以下启示😮

    • 二维数组(网格、DP Table) 每个 CELL 都是一个子问题,要考虑如何将问题分解成一个个子问题,每个子问题的最优解存储在 CELL 里

    • 动态规划没办法处理只拿物品的一部分,要么全部拿走,要么不拿

    • 行的排列顺序对结果的影响无关紧要
      背包问题 行顺序影响
      如图所示最后的最优解都是 29

    • 问题的最优解不一定要把背包装满
      如果遇到一个物品的价值比其他物品都要高时,那肯定会装下此物品,可在装下此物品后剩余空间不足于再装下其他物品,就会出现背包没装满的情况
      如现有背包容量的最大容量还是为 6斤,有个 5.5斤 重,价值为100的物品,这个物品比其他所有物品价值都要高,装上背包后,剩余 0.5斤 容量别的什么都装不下


    子串、子序列又是啥🤔

    • 子串2、子序列3,一句话概括两者区别: 字串一定是连续的,而子序列

    最长递增子序列

    最长递增子序列 ( longest increasing subsequence )4,简写为 LIS

    指的是在一个给定的数值序列中,找到一个子序列,使得这个子序列元素的数值依次递增,且这个子序列长度是最长的
    给定一个数组,nums = [6, 10, 9, 2, 3, 6, 10, 661, 66],这个数组的最长递增子序列[2, 3, 6, 10, 66],算法中的输出结果应为 5

    关键点:

    • 最简单的情况下(base case),最短的子序列应该为自己,即为 1

    • 如何根据dp[ i ] 前面的结果来推出 dp[[ i ] 呢?
      加一个循环,遍历 nums[ i ] 前面的值,如果存在比 nums[ i ] 小的值,则继承 dp[ i ] 上的结果并 加一
      需要注意的是:比 nums[i] 小的子序列可能不只一个,需要继承的是最大值

      for k in range(i):
          if nums[i] > nums[k]:
              dp[i] = max(dp[i], dp[k]+1)    
      

    最长递增子序列

    结合上述内容,完整代码为👇🏻

    def length_lis(nums: list) -> int:
        length = len(nums)                       # 获取nums数组长度
        dp = [1] * length                        # 定义 dp table
        for i in range(len(nums)):
            for k in range(i):
                if nums[i] > nums[k]:            # 寻找前面那些比当前数值小的子序列
                    dp[i] = max(dp[i], dp[k]+1)  # 比当前数值小的数可能不只一个,取最大值
        return max(dp)                           # 最大的值就是最长的子串
    
    nums = [6, 10, 9, 2, 3, 6, 10, 661, 66]
    print(length_lis(nums))
    

    DP Table 的维度

    可以看到,这里关于递增的问题使用到的都是一维数组,而最开始讲到的背包问题却使用了二维数组

    数组维度并非是固定的,要根据问题提供数据的复杂度来选择 DP Table 的数组维度


    最长公共子串、子序列

    最长公共子串5

    最长公共子串(Longest common substring)

    是寻找两个或多个已知字符串最长的子串
    此问题与最长公共子序列问题的区别在于 子序列不必是连续的,而子串却必须是
    最长公共字串

    这里有两个字符串,分别是 bear 和 beear,他们两的最长公共子串值是多少呢?🙄

    def dynamic_p(s1, s2) -> list:
        r, c = len(s1), len(s2)
        dp = [[0] * (c+1) for _ in range(r+1)]
        for row in range(r):
            for col in range(c):
                if s1[row] == s2[col]:
                    dp[row+1][col+1] = dp[row][col] + 1    # 对左上角CELL值+1
                else:
                    # 匹配不成功清0,这里可以不用到else,因为默认值就为0
                    dp[row+1][col+1] = 0
        return dp
    
    
    arr = []
    dp = dynamic_p("bear", "beear")
    
    for i in dp:
        arr.extend(i)
        print(i)                                           # 打印数组
    
    print(f"最长公共子串为:{max(arr)}")
    
    • 当匹配成功时,此时单元格的值应为左上角CELL的值加一
    • 匹配不成功时,应当为零

    如何理解 DP[i-1][j-1] + 1

    beear 和 bear,此时 b 为 e 的上一个字符,若e匹配成功了,那就检查它的上一个字符 b 有没有匹配成功,上一个字符 b 在左上角单元格的位置,若 b 也匹配成功了,那在此基础上加一,保存连续的记录状态

    在这里插入图片描述

    最长长公共子序列6

    最长公共子序列(Longest Common Subsequence),简写为 LCS

    是在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题,
    这与查找最长公共子串的问题不同的地方是:子序列不需要在原序列中占用连续的位置 。

    说人话就是

    • 计算两个字符串中 能连在一块字符的最长长度

    比如输入 str1="abcdefg"str2="edge",其中最长的公共子序列为 [e, g],算法应输出 2

    比起获取最长公共子串,获取最长公共子序列,容易想到是暴力方法

    def dynamic_p(s1, s2) -> int:
        res = set()                 # 利用集合进行去重
        for i in s1:
            for k in s2:
                if i == k:
                    res.add(k)
        return len(res)
    
    
    print(dynamic_p("beear", "bear"))
    

    如何使用动态规划

    要记住动态规划原理是:先解决相对简单的子问题,再逐步解决大问题

    那如何将问题划分成子问题呢?约束条件又是什么?

    将字符串 s1 和字符串 s2 拆开,如 “b” 与 “be”、“b” 与 “bea”、“b” 与 “bear” 的最长公共子序列,这就是一个个子问题,将其表现为二维数组(网格),为下图所示👇

    最长公共子序列 空网格

    关键点:

    • DP[1][2] = 1 代表 “be” 与 “b” 的最长公共子序列为 1,DP[3][2] = 2 代表 “be” 与 “bea” 的最长公共子序列为 2,DP[3][2] = 2 代表 “bee” 与 “bea” 的最长公共子序列为 2
    • 最简单的情况(base case) 是没有公共子序列,即为 0

    在这里插入图片描述

    def dynamic_p(s1, s2) -> list:
        r, c = len(s1), len(s2)
        dp = [[0] * (c+1) for _ in range(r+1)]
        for row in range(r):
            for col in range(c):
                if s1[row] == s2[col]:
                    dp[row+1][col+1] = dp[row][col] + 1     # 上一个字符串最长公共子序列再加一
                else:
                    # 在左方CELL和上方CELL中选择 子问题中最长公共子序列 较长的那个 
                    dp[row+1][col+1] = max(dp[row+1][col], dp[row][col+1])
        return dp
    
    
    dp = dynamic_p("bear", "beear")                         # 打印数组
    for i in dp:
        print(i)
    
    print(f"最长公共子序列为:{dp[-1][-1]}")
    

    最长公共子序列 网格


    给出题目

    由于篇章实在过长,这里将每个问题分为单独的一篇博客🙄


    最大子数值问题

    输入一个整型数组,数组中的一个或连续多个整数组成一个子数组,求所有子数组的和的最大值

    比如输入 nums = [-2,1,-3,4,-1,2,1,-5,4],其中的最大子数组是 [4,-1,2,1],算法应当输出 6

    注意:
    此问题要求 计算子数组的最大和,而子数组一定是连续的,这就是为什么上面的示例 最大子数组中有个 -1,而不把除了负数之外的值全部加起来,为获取最大子数组和,那就得经过 -1

    此问题与此前提到的 最长递增序列比较类似

    Python 算法题之 子数组的最大和


    俄罗斯套娃信封

    有一个二维整数数组 envelopes ,其中 envelopes 中的每个值代表着一个信封,每个信封的宽度高度以整数对 [ w, h ] 表示,当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样
    计算 最多有多少个信封能组成一组 “俄罗斯套娃” 信封

    比如输入 envelopes = [[5,4],[6,4],[6,7],[2,3]],能组成最多套娃信封组是 [2,3] => [5,4] => [6,7],算法应当输出 3

    Python 算法题之 俄罗斯套娃信封


    不同子序列

    给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
    简单来说就是:从 s 字符串上 挑字符,求能匹配 t 字符串的次数是多少

    比输入 s="beear"t="bear ,其中从 s 身上挑字符,能匹配 t=bear 的方式有两种,算法应当输出 2

    Python 算法题之 不同子序列


    总结

    个人感觉动态规划难以理解的原因有这些🤧

    • 结构庞杂,需要将问题划分成一个个子问题,每个子问题分别运算,先解决相对简单的子问题,再逐步解决大问题,最后求最优解
    • 要充分结合问题 设计出动态规划解决方案(状态转移方程)是最困难的部分
    • 如何去设计 DP Table,问题最简单的情况(base case)是什么,每个子问题能做出什么选择发生改变

    动态规划 所带来的启示🤪

    1. 在问题可分解为彼此独立且离散的子问题时,在给定约束条件下,就能够使用动态规划来设计解决方案
    2. 每中动态规划方案背后都有着网格,如上面所展示的一系列图,每个格都是一个个子问题
    3. 动态规划先解决相对简单的子问题,再逐步解决大问题
    4. 可以先确定 最简单的情况 (base case) 和 最终答案在 DP 中的位置,再尝试找出 状态转移方程

    动态规划思路流程

    1. 先设计出DP Table,并明确其含义
    2. 找到问题最简单(base case)的情况是什么
    3. 寻找设计出 状态转移方程

    动态规划是一个难以理解算法概念,这是真的,但愿上述内容能够帮得上忙🥶

    有个更简单的例子:斐波纳契数列 ,其用到的伪动态规划的解法不妨去看看


    后记

    动态规划是一个难以理解算法概念,但深入研究时会发现动态规划还是有点意思的,让人又爱又恨,为了研究什么是动态规划,以及如何去实现,我查阅大量的资料,花费大量时间学习,在此期间我十分感谢网上大佬们各种各样的文章,给我一定的启发,我决定写下这篇笔记分享给大家。

    我是个不折不扣的新手,文章内容或许存在不足、错误,这里请大家谅解,比起博客我更喜欢称呼这为笔记

    此笔记会持续更新、改进(还未写完),要是有路过的大佬可以指出我的错误,我会感到高兴,十分感谢😋


    参考资料

    在攻克动态规划算法时,我十分感谢这些帮助过我的资料、书籍,可以说没有它们的帮助,我难以啃动 动态规划 这块硬骨头,再次感谢书写这些资料、书籍的作者们

    在这里我把这些资料、书籍给列出来,欢迎大家去查看,书籍可以在京东上能够买到

    • 题目出之力扣:
    • 维基百科中文版:
    • 书籍:
      • 图灵程序设计丛书 《算法图解》
        这是一本很棒的算法入门书,推荐给大家
      • labuladong大佬 著作 的 《labuladong 的算法小抄》
        这是一本很厉害的书,十分推荐

    由衷感谢💖


    相关博客😏


    1. 背包问题:维基百科 ↩︎

    2. 子串:维基百科 ↩︎

    3. 子序列:维基百科 ↩︎

    4. 最长递增子序列 维基百科 ↩︎

    5. 最长公共子串: 维基百科 ↩︎

    6. 最长公共子序列:维基百科 ↩︎

    展开全文
  • 第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、动态规划的基本思路 许多问题在实现的过程中都是把原问题分解为子问题进行处理,再把子问题...
  • 动态规划 ppt演示

    热门讨论 2008-09-30 13:06:29
    由于在所考虑的子问题空间中,总共只有θ(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, ...
  • 上一章已经详细地分析过动态规划,接下来还是结合具体问题,感受一下这些算法是怎么工作的,是如何解决问题的,再问体体会这些算法的本质。我觉得比单纯记忆原理和定义更有价值。 贪心算法 1. 如何理解贪心算法? ...
  • 贪心、分治、回溯、动态规划这 4 个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易的事情。所以,接下来的这 4 个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让...
  •   知道了AC自动机的工作原理之后,我不得不发出感慨,这真是个十分漂亮的算法,无论是在时间上还是空间上亦或是常数上,都有非常出色的表现。 AC自动机的基本操作就是多串匹配,最朴素的思想就是跑...
  • 算法设计与分析.rar

    2019-05-24 18:38:03
    分治策略 内容: 用分治法实现一组无序序列的两路合并排序...要求:了解密码学中加/解密的基本原理,掌握数论的基本知识,理解非对称密码体制RSA加密算法工作原理和流程;能够设计并实现一个简单的RSA公开密钥系统。
  • 贪心、分治、回溯、动态规划这 4 个算法思想,原理解释起来都很简单,但是要真正掌握且灵活应用,并不是件容易的事情。所以,接下来的这 4 个算法思想的讲解,我依旧不会长篇大论地去讲理论,而是结合具体的问题,让...
  • 贪心算法、分治算法、回溯算法动态规划这 4 个算法思想,原理解释起来都不难,但是要真正掌握且灵活应用它们,并不是件容易的事情。确切地说,它们应该算是算法思想,并不是具体的算法,常用来指导我们设计具体的...
  • 【笔记】算法图解

    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 分而治之...
  • 第一次看到“装配线与工作站问题”是老师在课堂上出的一个题目,当时脑子简单,直接就用穷举法给解了,后来看到《算法导论(第二版)》这本书用的是动态规划算法来解决的,实际测试后发现其效率是穷举法的四、五倍,...
  • 数学建模方法:蚁群算法

    热门讨论 2010-05-21 15:35:07
    蚁群算法原理的仿真研究 Hopfield neural network based on ant system 蚁群算法及其实现方法研究 分层实体制造激光头切割路径的建模与优化 配送网络规划蚁群算法 基于蚁群算法的城域交通控制实时滚动优化 基于蚁群...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 205
精华内容 82
关键字:

动态规划算法工作原理