算法设计与分析课程的心得体会
更新时间:2023-08-26 17:03:01 阅读量: 教育文库 文档下载
《算法设计与分析》课程的心得体会
以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为,算法是一种创造性思维活动,并且处于计算机科学与技术学科的核心。
在计算机软件专业中算法分析与设计是一门非常重要的课程,很多人为它如痴如醉。很多问题的解决,程序的编写都要依赖它,在软件还是面向过程的阶段,就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的,它可以培养我们养成思考分析问题,解决问题的能力。
如果一个算法有缺陷,或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件,都必须使用具体的算法来实现。 算法设计与分析是计算机科学与技术的一个核心问题。因此,学习算法无疑会增强自己的竞争力,提高自己的修为,为自己增彩。 那么,什么是算法呢?算法是指解决问题的方法或过程。算法
满足四个性质,即输入、输出、确定性和有限性。为了了解算法,这个学期马老师带我们走进了算法的世界。
马老师这学期提出不少实际的问题,以及解决问题的算法。我在此只说比较记忆深刻的问题,即0-1背包的问题。
0-1背包问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
首先,0-1背包问题具有最优子结构性质和子问题重叠性质,适于采用动态规划方法求解。动态规划算法与分治法类似,其基本思想是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的,若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。
用动态规划法解决问题的思路如下:
最优决策序列由最优决策子序列组成。假设f (i,y)表示剩余容
量为y,剩余物品为i, i+1, , n时的最优解的值,即:
f (n,y) = Pn,if y≥Wn
f (n,y) = 0, if 0≤y≤Wn
和
f(i,y)=max(f(i+1,y),f(i+1,y-Wi)+Pi) y≥Wi
f(i,y)=f(i+1,y) 0≤y≤Wi
这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的,所以有必要将它详细解释一下:“将前i件物品放入容量为y的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为y的背包中”,价值为f[i-1][y];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为y-Wi的背包中”,此时能获得的最大价值就是f[i-1][y-Wi]再加上通过放入第i件物品获得的价值Pi。
用贪心算法解决问题的基本思路如下:
由所有解元素组合成问题的一个可行解;从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。
实现该算法的过程: 从问题的某一初始解出发;while 能朝给定总目标前进一步do求出可行解的一个解元素;
该算法存在问题:首先不能保证求得的最后解是最佳的;其次不
能用来求最大或最小解问题,并且只能求满足某些约束条件的可行解的范围。
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。所以0-1背包问题也可以用回溯法解决。其基本思路是可先将物品依其单位重量价值从大到小排序,此后只要顺序考察各物品即可,这是为了便于计算上界,。在实现时,由bound计算当前结点处的上界。在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。
当然0-1背包问题还有许多的解决方案,此处就不一一列出。不过通过0-1背包问题,我深刻体会到算法的魅力,体会到同一个问题用不同的方法解决的妙处。学无止境,《算法设计与分析》仅仅是我学习算法知识入门课,我不会停下脚步,在此之后我依然会努力学习算法知识。
正在阅读:
算法设计与分析课程的心得体会08-26
软件测试期末总复习 - 图文05-01
单利复利计算方法05-23
十四五中医药发展规划04-13
2011-2012年土地估价师考试《土地估价实务基础》模拟试卷(1)-中大网校09-20
法理学张文显第三版笔记 讲义整理 超全06-21
登高架设作业题库101-06
室内装饰工程造价的组成04-22
班组长培训课程大纲目录03-02
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 心得体会
- 算法
- 课程
- 分析
- 设计
- 基于TSL2561的温室智能调光系统设计
- 硕士研究生毕业论文致谢
- 新兴铸管官网招聘2013薪酬福利(冶金金属制品业绩效考评指标)新兴铸管股份有限公司_九舍会智库
- 2014年10月自学考试审计学试卷及答案
- 冀教版二年级下册数学全册教案
- 十三五(2016-2020年)中国干冰保温箱行业运行模式及发展前景预测报告(目录)
- 《中国银监会中资商业银行行政许可事项实施办法》中国银行业监督管理委员会令2015年第2号(全文)
- 机动车牌证申请表填写样式
- 2017年南京师范大学心理学院660心理学基础之普通心理学考研导师圈点必考题汇编
- 三年级军棋班兴趣小组活动计划
- 选修3《20世纪的战争与和平》(复习提纲)
- 供电所先进班组事迹材料范例事迹材料
- 等径异径三通规格表1
- 农业推广硕士研究生大纲_教育信息管理与利用
- 中国双筒洗衣机行业研究与投资前景评估报告(2015-2020)
- 五年级省情礼仪 心理健康 综合知识教案
- 内外部环境分析1
- “中国新闻事业史”知识点
- 金融学chpt1
- 若羌县第二小学义务教育学校标准化建设工作责任追究制度