算法思想浅谈

第1页第一章算法回顾分享一下我这几年来总结的学习方法。1.算法回顾首先我先把看过的算法思想说一下，再介绍几种最近出现的新思想。1.1贪心思想顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。在面临选择时，贪心算法都作出对眼前来讲最有利的选择，不考虑对将来的不良影响，每个选择一旦做出，不可更改，不允许回溯，根据不同的贪心策略，贪心算法就不同，贪心解的质量也不同，所以贪心策略很重要。可以看出，此算法思想很简单，具有高效性，但不一定得出最优解。第2页1.2分治法当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。1.3动态规划动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。第3页1.4搜索法搜索法包含穷举搜索，深度优先搜索，广度优先搜索，回溯法，分支限界法，其实这些算法的基础就是穷举搜索，只是加上一定的原则来优化过程，就形成了后面的几种算法，回溯法就是在深度优先搜索的基础上允许回溯，分支限界法是在广度优先搜索基础上允许剪枝，学习时主要学习思想，这些算法名字不要太在意。1.5基于数学理论的算法思想随机化算法，线性规划问题，数论算法等，这些算法都是基于严格的数学理论，没有很好的数学基础看起来就有点难了。1.6新近出现的部分算法简介①遗传算法：从达尔文的生物进化论中得到启发，借鉴自然选择和进化的原理，模拟生物在自然界的进化过程所形成的一种优化求解方法，遗传算法从代表问题的可能潜在解集的一个种群出发，一个种群有一定数量的个体组成，每个个体实际上是染色体带有特征的实体，每一代根据个体的适应度大小挑选个体，并借助遗传算子进行交叉和变异，得到近似最优解。②模拟退火算法：他的出发点是物理中固体的退火过程与一般组合优化之间的相似性，固态物质退火时，通常先加温，使其中的粒子自由游动，然后逐渐降低温度，粒子也逐渐形成低能态的晶格，最终形成最低能量的基态。所以他从某一较高初温开始，伴随温度参数第4页的不断下降重复抽样，最终得到全局最优解，他是基于概率的。③蚁群算法：蚁群算法是模拟自然界蚂蚁觅食过程的一种分布式，启发式群体智能算法，用于求解复杂的组合优化问题，如TSP,JSSP,GCP等问题。第5页第二章算法感悟1.什么是算法算法最初就是为了解决某一具体问题而想出来的一种解决方案，随着对这一问题进行抽象，会得到一种解决这种类型相似问题的方案，这就是算法，或者说算法思想。并不是很复杂的解决方案才能称算法，其实解决每一问题的设计都是一个算法，只不过可能没有对他们进行抽象，导致只能解决这一具体问题。2.算法是什么算法并不像一些人想的那么死板，也不像那么复杂。并不是没学过算法分析设计就不会设计算法，从上面我对算法的解释看出，任何人都能设计，有的人甚至比学过那门课的人设计的还好，究其原因，因为算法实质上是一种解决问题的思想。学过《算法分析与设计》的人知道，书里面有很多优秀算法，每一个都不很简单，大部分人可能简单地认为“以后只要见到类似的问题，直接套现成算法就行了”。事实上，那些算法中蕴含的思想才是我们真正应该掌握的，并内化到自己的思想中。当我们遇到问题时，可能会有两种解决方法：学过算法分析设计的人可能会回想之前学过的算法和问题，看哪个可以套的上；另一种没学过的，应该就是不管三七二十一，先想出解决问题的原始方案，然后再对其优化。这两种方法都行，可能大部分人用的是后一种方法，其实这些优秀算法，在一开始也是这么来的。如果将两第6页种方法结合，利用已内化的算法思想找出原始方案，在对其优化，这才是最好的解决步骤。可以看出，这些算法思想还是要学习的，他可以帮助尽快想出比较好的解决方案，如果不用这些思想，自己慢慢想，优化到最后，可能会发现，这不就是某种算法思想吗！所以我们要站在巨人的肩膀上。学习思想最重要的用处是，当遇到从没见过的问题时，这时已经不能套用已有的模板，就只能厚积薄发，靠积累的算法思想了，有可能会发现一种新思想！3.算法为什么很重要程序=算法+数据结构其中算法才是关键，数据结构和具体的编程语言只是工具，只有算法思想是核心，是不变的。我们编写的程序实质是解决某一问题的自动化实现方式，而当遇到一系列问题时，我们可以逐个解决，最终组合一起来解决总的问题，那么怎么解决某个具体问题就是关键，而解决这一问题的过程其实就是算法，从这可以看出，程序从头到尾都是在编写算法，这就是算法重要的原因。优秀的算法可以让程序更加高效，健壮，能够解决一类问题。这里有一个陷阱，算法由于实质上还是为了解决问题，它受多种因素例如环境，理解力，程序架构等影响，所以只要他能很好的解决问题就可以了，不要一味的追求其所谓的“完美”。第7页4.怎么学习算法算法的学习最重要的是，一定要注重实践，自己多想多实现，只有这样才能把算法思想内化。不是在课堂上听听课，做两道课后习题就能掌握的。平时，遇到问题，可以先按照自己的想法或者逻辑，写出初步解决方案，再对其优化。当然，也可以根据已有的类似算法类比，但是一定要自己想出来，不是按照书上的算法套。对于学习这门课程，并不要求里面的每一个算法都会写出来，但解决问题的思想一定要掌握，具体来说，对于每个算法或者问题，都要深入理解，理解他为什么要这样做，不这样行不行，知道他每一步是怎么走的，虽然我强调最重要掌握思想，但理解具体的算法和这并不矛盾，只有具体的理解了，才能掌握思想，否则都是空话。只不过最后落下的就只有思想，无招胜有招。什么背包问题，旅行商问题，最短路径....都只是具体问题而已。当然，如果这些具体算法能记住那更好，但这不是必须的。有的算法有数学理论基础，比如数论算法，这一类算法主要靠数学建模，如果数学好，那就很简单了，这一类思想实质就是数学理论。另外，做笔记是必要的，在把这些思想内化之前，要把看过的优秀算法的过程描绘并记下来，并总结出思想，在某一天忘了，可以很快看懂。这就是积累！