算法之动态规划

栏目: 编程工具 · 发布时间: 4个月前

来源: segmentfault.com

本文转载自:https://segmentfault.com/a/1190000019466187,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有。

动态规划总结

最优解 依赖重复计算的 独立的 子过程

1.发现最优解结构

2.推到递归式

3.自低向上存储子过程结果过(备忘录,非最优子过程,只是存储,类似迷宫)

4.最优解的存储和计算

这里1:

1)子问题发现/定义、假设已经有了最优解,怎么通过子问题解决。比如工厂最快流水线,已经选了一条路径,要知道如何选择的,需要知道除固定节点后前面如何选择的。矩阵乘法,知道划分后,需要知道最外层两个括号分别如何计算。LCS知道最终解后,需要知道除最后一个节点外前面解如何选择的。

2)选择 需要依赖哪些子问题(越少越好,矩阵乘法无法做到只依赖一个,依赖两个。工厂流水和LCS可以选择多个,但是一个很简单直接求取,选择依赖一个);需要选择依赖(矩阵循环所有一对可能选择其1,LCS和工厂选择满足更优的)

3)注意满足重复计算和独立(最长非重复路径这种问题因为一个子问题用的点其他子问题不能用,所以子问题的最优不是独立的,无法用动态规划),需要简单的证明最优子解的选择会导致最优解

4)局部计算(i-k或者0-2)

LCS:

两个串最长非连续公共子串

算法之动态规划

算法之动态规划

假设最优解已有去推子问题(固有思维就是对两个串加节点,才是n与n-1的关系,不太一样的思维)

矩阵

矩阵最小乘法次数的组合

算法之动态规划

同样的,考虑矩阵多一个n,n-1的关系,改思维习惯

生产线

算法之动态规划

算法之动态规划

这个虽然可以用加一个节点,但是从最终最优解来推也可以的。

climits的INT_MAX

vector > ret(row,vector(col));


以上所述就是小编给大家介绍的《算法之动态规划》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

关注码农网公众号

关注我们,获取更多IT资讯^_^


为你推荐:

相关软件推荐:

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数学规划

数学规划

黄红选 / 清华大学出版社 / 2006-3 / 45.00元

《数学规划》以数学规划为对象,从理论、算法和计算等方面介绍,分析和求解常见的最优化问题的一些方法,全书共分8章,其中第l章介绍了数学规划的实例、模型以及在分析最优化问题时所涉及的基础知识,第2章至第8章分别讨论了凸分析、线性规划、无约束优化、约束优化、多目标规划、组合优化和整数规划以及全局优化等七个方面的内容,此外,书中每章的最后一节给出了一些习题,书末列出了参考文献和索引。《数学规划》可作为应用......一起来看看 《数学规划》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具