教育局网站建设管理工作意见,怎么注册网站域名备案,wordpress英文版下载,做外贸阿里巴巴有哪些网站P216 第15章动态规划 最优子结构 具有它可能意味着适合应用贪心策略
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。
剪切-粘贴技术证明 每个子问题的解就是它本身的最优解#xff08;利用反证法#xff0…P216 第15章动态规划 最优子结构 具有它可能意味着适合应用贪心策略
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。
剪切-粘贴技术证明 每个子问题的解就是它本身的最优解利用反证法
保持子问题空间尽可能简单
P217 在第16章介绍贪心算法它与动态规划有很多相似之处最大的不同在于贪心算法不是首先寻找子问题的最优解然后在其中进行选择而是首先做出一次贪心选择得到当时局部最优解然后求解选出的子问题——感觉这点也可以用于生活琐事是不是最优选择先做了再说当然也有一定的基础证明这么做结果不会太差
P218 两个最长简单路径子问题是相关的两个最短路径子问题是无关的什么是无关无关是同一个原问题的一个子问题的解不影响另一个子问题的解
重叠子问题 适合动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须是足够小即问题的递归算法会反复求解的相通的子问题这就是重叠子问题而不是一直生成新的子问题。
P219 15.1节 钢条切割问题的递归算法是如何通过指数次的递归调用来求解小的子问题。动态规划算法讲运行时间从递归算法的指数阶降为平方阶。
P222 最长公共子序列LCS 举例用于比较两个DNA串的相似度
定理15.1 LCS的最优子结构
步骤1刻画最长公共子序列的特征
步骤2一个递归解
步骤3计算LCS长度
步骤4构造LCS
P226 LCS_LENGTH 的空间需求是可以逐渐减小的
应用案例设计程序实现语言之间翻译用最优二叉搜索树optimal binary search tree求解它与矩阵乘法相似提高搜索效率让频繁出现的单词靠近跟冷门的词汇远离根。
P237 第16章 贪心算法greedy algorithm这章有拟阵matroid的概念从贪心算法中衍生出来的
P238 用举办活动的选择问题来解释贪心算法
P242 贪心选择的性质贪心算法通常是自顶向下的
贪心算法和动态规划算法二者间有细微差别。
研究一个经典最优化问题的两个变形0-1背包问题分数背包问题
0-1背包问题小偷偷商品对于任何一个商品要么完整拿走要么留下不能只拿一部分或一个商品反复拿
分数背包问题具备贪心选择性质
引申检索贪心算法有什么应用
1 关于视频传输领域查找到一个专利一种基于贪心算法的全景视频传输方法
针对的是全景视频对接收到的全景视频进行片段划分得到若干视频片段对每个所述视频片段进行块划分得到与每个所述视频片段对应的基本块集根据预设的贪心合并分块算法对每个所述基本块集进行处理得到对应的目标分块集根据所述目标分块集对所述全景视频进行视频传输。
2 关于视频拼接领域查找到一个算法题
获得一系列视频片段这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠也可能长度不一。视频片段 clips[i] 都用区间进行表示开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑并将剪辑后的内容拼接成覆盖整个运动过程的片段[0, T]。返回所需片段的最小数目。
