算法设计与分析课程的心得体会

《算法设计与分析》课程的心得体会

以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为，算法是一种创造性思维活动，并且处于计算机科学与技术学科的核心。

在计算机软件专业中算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。 算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。 那么，什么是算法呢？算法是指解决问题的方法或过程。算法

满足四个性质，即输入、输出、确定性和有限性。为了了解算法，这个学期马老师带我们走进了算法的世界。

马老师这学期提出不少实际的问题，以及解决问题的算法。我在此只说比较记忆深刻的问题，即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背包问题，我深刻体会到算法的魅力，体会到同一个问题用不同的方法解决的妙处。学无止境，《算法设计与分析》仅仅是我学习算法知识入门课，我不会停下脚步，在此之后我依然会努力学习算法知识。