34
长江大学学报 (自科版 ) 2 0 1 3年3月号理工上旬刊第 1 o卷第7期 J o u r n a l o f Y a n g t z e U n i v e r s i t y( N a t S c i E d i t ) Ma r . 2 0 1 3,Vo 1 . 1 0 N o . 7
动态规划算法分析 宛楠 (皖南医学院计算机教研室,安徽芜湖 2 4 1 0 0 0 ) 张义 (安徽工程大学计算机与信息学院,安徽芜湖 2 4 1 0 o 0 ) [摘要]对动态规划算法的基本思想和设计步骤进行了阐述,以数字三角形为例对动态规划算法的解题过程进行了分析和实现,并总结了动态规划算法解题的一般思路。
[关键词]动态规划;数字三角形;状态;状态转移方程[中图分类号] T P 3 0 1 . 6 [文献标志码] A [文章编号]1 6 7 3—1 4 0 9( 2 0 1 3 )0 7— 0 0 3 4—0 3
AC M国际大学生程序设计竞赛 (简称 AC M/ I C P C )是由国际计算机界历史悠久、颇具权威性的组 织 AC M学会 ( As s o c i a t i o n f o r C o mp u t e r Ma c h i n e r y )主办,是世界上公认的规模最大、水平最高的国
际大学生程序设计竞赛,在信息技术界具有相当的影响力,竞赛的很多题目都是在实际的工程项目应用中遇到的问题,能够比较全面的考察学生对计算机以及其他学科知识的综合运用能力,通过竞赛可以系统的检验学生的计算机编程等方面的综合水平,而这些正是 I T从业者所急需的。在竞赛中涉及到各种算法,其中动态规划是较为常见的算法之一 _ 1]。下面,笔者对动态规划算法的进行了分析和研究 o。
1 动态规划算法的基本思想与步骤设计 1 )动态规划算法的基本思想动态规划算法基本思想是将所求解问题分解成若干个子问题,先求解子问题并保存已解决的子问题的答案,然后从这些子问题的解得到原问题的解。 2 )动态规划算法步骤设计动态规划算法适用于解最优化问题,一般可按以下步骤设计动态规划算法:①找出最优解的特质,并描述其结构特征;②用递归的方式定义最优值;③以自下向上的方式计算出
最优值;④根据计算最优值时得到的信息,构造最优解。 步骤①~③是动态规划算法的基本步骤。如果只需要求出最优值,则步骤④可以省去。如果从最底层的子问题开始,自底向上地逐一推导出子问题的解,则编程的时候可不写递归函数 j。
2数字三角形问题的动态规划算法求解 下面以数字三角形为例,说明动态规划算法的具体实施。 1 )数字三角形问题描述图 1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。问题是求出最佳路径上的数字之和,路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。
2 )具体实施过程
按照题目的要求,从顶点出发,假设先采用贪心法来求最佳路径,每次选择所
能选的最大值作为下一步的路径,则从顶点 7出发选择 8,从 8出发选择 1,从 1出发选择 7,从 7出发选择 5,所求最终路径为 7— 8— 1— 7— 5,如图 2所示,路径和为 2 8。然而,这个路径并非题目所要求的最优路径,最优路径应该为 7— 3— 8— 7— 5,如图 3所示,路径和为 3 0。可见该问题采用自顶至下的贪心法是不
能得到正确答案的。换言之,从顶点出发是无法直接判断是选择左下还是右下的数字。 转换思路,从倒数第 2层 ( 2、7、4、4 )出发,则可以立刻做出判断,即从 2出发选择 5,从 7出
发选择 5,从 4出发选择 6,4从出发选择 6,求和后更新该数字三角形,再从新的三角形的倒数第 2层 [收稿日期]2 0 1 2— 1 2一 O 1 [作者简介]宛楠 ( 1 9 7 9一 ),女,硕士,讲师,现主要从事数据库开发与应用、教育技术方面的教学与研究工作。 o皖南医学院校中青年科研基金项目 ( W KS 2 0 1 2 0 1 );安徽工程大学校级教研项目 ( 2 0 1 2 ̄y 5 1 )。

动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用这些子 问题带到原问题, 与分治算法的不同是,经分解得到的子问题往往是不是相互...
动态规划法设计算法一般分成三个阶段: (1)分段:将原问题分解为若干个相互重叠的子 问题; (2)分析:分析问题是否满足最优性原理,找出 动态规划函数的递推式; (3...
第8讲+动态规划算法和实例分析_电脑基础知识_IT/计算机_专业资料。动态规划算法和实例分析 ? ? ? 动态规划简介 0-1背包问题 最长公共子序列 动态规划简介 ? ...
1.3 任务与分析任务是实现多种问题的动态规划算法并分析、编程和总结,给出结论。 1、给出动态规划的基本思想; 2、给出最小代价子母树的动态规划算法和程序; 3、...
基于动态规划算法的最值问题分析_数学_自然科学_专业资料 暂无评价
第3章 动态规划学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 (1)最优子结构性质 (2)重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出...
(1≤n, m, t≤20) [算法分析] 本题要求唱片中的歌曲必须按照它们创作顺序排序,这就满足了动态规划的无后效性 要求,启发我们采用动态规划进行解题。 分析可知...
The Design and Analysis of Computer Algorithms 算法设计与分析 段明秀吉首大学...动态规划 本章学习目标: 熟练掌握利用动态规划方法解决问题的基本思想 ; 学会...
算法设计-导弹拦截问题 3页 免费 动态规划(朱全民) 60页 免费...常州市第一中学 林厚从 “拦截导弹”问题分析 假如拦截的倒数第2枚导弹是300,...
动态规划算法_IT/计算机_专业资料。动态规划算法 ——动态规划模型山东省实验...?时间复杂度O(ANS) 分析 ?算法二: ?再进一步我们通过思考总结得到 F[n]=F...
热门文档