动态规划思想:
把问题规模不断缩小成小问题,并求解出小问题的结果,然后返回最优结果。
动态规划必须满足最优化原理和无后效性。
什么叫做最优化原理(最优子结构性质):
简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
额外增加知识:
动态规划和递归不一样,递归是没有记录,对于同一个问题,出现多少次,会计算多少次。而动态规划不一样,对于相同的问题,只会计算一次。
下面以求最长公共子序列(LCS)为例:
问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列(元素的相对位置还是保持不变)。确切地说,若给定序列X=<x1, x2,…, xm>,则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>,使得对于所有j=1,2,…,k有
例如,序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。
给定两个序列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的一个公共子序列,序列<B, C, B, A>也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。
最长公共子序列(LCS)问题:给定两个序列X=<x1, x2, …, xm>和Y=<y1, y2, … , yn>,要求找出X和Y的一个最长公共子序列。
解答
首先,要证明LCS是否有最优子结构性质。
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>,则:
(1)若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;
(2)若xm≠yn且zk≠xm ,则Z是Xm-1和Y的最长公共子序列;
(3)若xm≠yn且zk≠yn ,则Z是X和Yn-1的最长公共子序列。
其中Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。
在这里,重新描述一下。
问题对象(PO)是X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>
把PO问题不断降低规模,也就是
x<1,m-1> y<1,n-1>
x<1,m-2> y<1,n-2>
x<1,m-3> y<1,n-3>
......
求出这一系列问题的值,选择最优值。
这个就是动态规划思想啦。
根据上面(1)、(2)、(3),可以看出是不断降低问题规模,求出问题最优(最长)值。
因此,最长公共子序列问题具有最优子结构性质。
由性质导出子问题的递归结构
当 i = 0 or j = 0 时 , c[i][j] = 0
当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }
如图所示:
相关代码如下:
int[][] b = new int[x.length][y.length]; //记录c[i][j]是通过哪一个子问题的值求得的
int[][] c = new int[x.length][y.length]; //记录X[i]与Y[j] 的LCS 的长度
for(int i = 0; i < x.length; i++)
c[i][0] = 0;
for(int j = 1; j < y.length; j++)
c[0][j] = 0;
for(int i=1; i<x.length; i++)
{
for(int j=1; j<y.length; j++)
{
if( x[i] == y[j])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 0;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
具体的LCS实现,请看这里
http://lzj0470.iteye.com/blog/1135649
![点击查看原始大小图片](http://dl2.iteye.com/upload/attachment/0052/6371/b5c2cab7-d6e2-36c9-a472-fc4a6b11a01c-thumb.gif)
- 大小: 256 Bytes
![点击查看原始大小图片](http://dl2.iteye.com/upload/attachment/0052/6513/316bfca4-4d05-3491-b6b6-b6e0f7373879-thumb.png)
- 大小: 12.8 KB
分享到:
相关推荐
本篇文章将深入探讨三种常用的算法:分治、递归、动态规划以及贪心策略,并通过实例来阐述它们的应用和重要性。 首先,让我们来看分治算法。分治法是一种处理大问题的策略,它将大问题分解为若干个规模较小、相互...
本篇文章将深入探讨这两个背包问题以及如何使用动态规划来解决它们。 **0-1背包问题**: 0-1背包问题是一个典型的优化问题,它假设有一个容量有限的背包(背包容量为W),以及一系列物品,每件物品都有一个重量w[i]...
本篇文章将深入探讨标题和描述中提到的一些核心算法,包括动态规划、分治算法、概率算法、模拟退火算法、搜索算法、贪婪算法、在线MATLAB应用、遗传算法以及组合算法。 1. **动态规划**:动态规划是一种解决具有...
在本篇内容中,我们将深入探讨这些概念,并通过一个实际问题来阐述它们如何应用于动态规划。 1. **最优子结构**:最优子结构是动态规划问题的核心特性,它表明问题的最优解可以由其子问题的最优解构建。在动态规划...
总的来说,《从《鹰蛋》一题浅析对动态规划算法的优化》这篇文章为我们提供了一个生动的实例,展示了如何通过多种方法优化动态规划算法,以及优化背后的思想。这对于我们学习和应用动态规划有着重要的指导意义,提醒...
这篇博士学位论文《嵌套结构并行多维动态规划算法及其应用研究》主要关注的是在大数据背景下,如何利用算法解决大规模复杂问题,特别是针对梯级水电站水库群的联合优化调度。作者提出了一种新的算法——嵌套结构多维...
7. **AI设计**:高级篇可能涵盖如何创建智能非玩家角色(NPCs),包括路径规划、行为树和决策逻辑。这部分内容有助于增加游戏的挑战性和可玩性。 8. **优化技术**:3D游戏对性能要求高,了解内存管理、多线程和绘制...
它在第一波基础篇的基础上,进一步深入探讨了动态规划和查并集这两个核心算法领域,同时涵盖了字符串处理和进位制转换等多元化的编程挑战。 动态规划是解决多阶段决策问题的一种有效方法,它的核心思想在于将复杂...
接下来,教程将深入探讨路由协议,包括静态路由和动态路由协议,如RIP(Routing Information Protocol)、OSPF(Open Shortest Path First)和EIGRP(Enhanced Interior Gateway Routing Protocol)。理解这些路由...
在本篇ASP动态网页制作教程中,我们将聚焦于一个综合开发实例——构建一个博客网站,其中包括相册展示模块的设计。博客网站是个人在线表达和分享想法的重要平台,其设计涉及多个关键模块,从网站架构到数据库设计,...
本篇文章将深入探讨WinCC 6.0项目实例,旨在帮助读者全面了解和掌握WinCC的组态与项目实施过程。 WinCC 6.0是西门子在2004年推出的一个重要版本,它在前代的基础上进行了许多优化和增强,包括更强大的图形编辑工具...
9. **地图交互**:集成地图API,实现地点搜索、路线规划等功能。 10. **图表绘制**:如饼图、柱状图、折线图等,用于数据可视化。 在《Javascript特效大全(上册)》中,你将深入学习如何利用JavaScript实现上述及更...
标题中的“基于TOC的半导体生产线动态分层规划调度方法”指的是在半导体制造过程中,采用...实例验证表明,这个基于TOC的动态分层规划调度模型能够有效提高半导体生产线的运营效率,解决实际生产中遇到的各种复杂问题。
本篇文章将深入探讨五种基础且重要的算法:递归与分治法、动态规划、贪心算法、回溯法和分支限界法。通过对这些算法的详细分析和实例演示,我们将更深入地理解它们的原理、适用场景以及如何实现。 1. 递归与分治法 ...
本篇将深入探讨SuperMap与C#结合的实例,帮助初学者快速入门,并逐步提升技能。 一、SuperMap简介 SuperMap是一款跨平台的GIS软件,它支持多种操作系统,如Windows、Linux、Unix等,并且具有丰富的数据格式支持。...
在这篇文章中,我们详细解释了最大加权区间调度问题,并提供了动态规划的递推公式。我们首先介绍了问题的定义和要求,然后通过实例分析了问题的思路和每一步的运算结果。最后,我们提供了问题的解决方案和代码实现。...
本篇文章将深入探讨通过实例学习SAP ABAP编程的关键知识点,旨在帮助初学者及有经验的开发者更好地理解和实践SAP程序开发。 1. SAP ABAP基础: - ABAP数据类型:理解基本数据类型如CHAR、INT、FLOAT等,以及结构化...
通过编程实现的demo实例,不仅可以提高工作效率,还能提供更加直观、动态的视图,为决策者和团队成员提供有力的支持。如果你正在寻找如何创建组织架构图的解决方案,那么"orgchart 组织架构图 demo 实例"无疑是值得...
(4)\12 算法篇-动态规划;目录中文件数:2个 ├─1 动态规划.mp4 ├─2 案例分析.mp4 (5)\13 算法篇-图与网络;目录中文件数:3个 ├─1 图与网络.mp4 ├─2 树.mp4 ├─3 案例分析.mp4 (6)\14 算法篇-图像处理;目录...
本篇文章将深入探讨Quidway系列路由器的典型配置实例,旨在帮助读者掌握基本的网络配置技能。 首先,我们关注的是"交换机.chm"文档,它可能包含了关于交换机基础知识的详细介绍,包括但不限于以下几点: 1. **...