现在的位置: 首页 > 综合 > 正文

从如何解决问题到如何学习算法

2012年12月12日 ⁄ 综合 ⁄ 共 1980字 ⁄ 字号 评论关闭

从如何解决问题到如何学习算法

      学习算法也有一段时间了,感觉学习了很久,遇到问题还是一点感觉也没有,直到最近学习动态规划,看了《算法设计》这本书的第六章后,突然有了一些感悟。其中也包含上学期学习算法课的一些总结和体会。

       算法的学习有两个部分:

  •        算法设计,即想出一个好办法来解决问题。
  •        算法分析,即证明算法的正确性,分析时间复杂度。

       对于初学者而言,我认为第一点要比第二点重要的多,如果遇到了问题,你无法设计出一个算法,那么即使你会证明正确性,会分析复杂度,又有什么用呢?还有一点在于,初学的时候,我们遇到的多数都是不知道怎么设计算法,而不是不会分析复杂度。

       基于这个原因,我认为《算法设计》要比《算法导论》更适合初学者。前者通过大量的例子教授解决问题的思路,后者花了大量的篇幅在做证明。前者会教你如何通过不断地尝试来解决问题,例如动态规划中,为什么这个问题描述时用了二维数组,而不是一维的。后者通常会给出一些结论,但是你却不知道如何想到这一点的。前者的习题经常会让你先分析为什么一个算法是错的,让你先对这个问题有一个良好的认识,发现问题的性质和特点,再让你设计出一个正确的算法,后者通常没有什么提示,直接给出题目。好的书,不仅传授知识,更重要的是,要有启发性。从这一点看,《算法设计》要比《算法导论》优秀。
       记得算法课第一节课上,老师就给我们画了一个大图,告诉我们遇到一个问题,应该沿着什么样的思路走。遇到一个实际的问题,首先应该把它形式化(Formulation),即用数学的方式将它描述出来。其次,需要观察问题(Observation),即观察问题的结构和性质
       为什么我们要用这样一种方式来解决问题呢?
  每一个实际问题都有它相应的性质和结构。每一种算法技术和思想,例如分治算法,贪心算法,动态规划,线性规划,网络流,都有他们适宜解决的问题。什么叫适宜解决的问题呢?其实就是这一类问题有着某种结构和性质。例如动态规划适宜解决的问题需要有最优子结构和重复子问题。一旦我们观察出问题的结构和性质,就可以用现有的算法技术和思想去解决它,而用数学的方式表述问题,更有利于我们观察出问题的结构和性质。这就是我们解决问题时,需要两步走的原因。
       这其实给我们学习算法提供了非常好的启示,首先需要我们养成一种习惯,那就是遇到问题,首先用数学的形式来描述它。先不要管是否合适,总之先去描述它。然后通过这种描述来寻找问题的结构和性质,看看这种描述是不是合适,如果不合适,再换一种方式。在《算法设计》第六章动态规划中,曾经有过多次这样的尝试,首先用一维数组来描述,发现不容易表示子问题,然后发现这种困难以后,就自发地转向了二维数组描述问题。通过反复地尝试,不断地修正来达到一个满意的结果,我想这也是“研究”这个词的英文为什么叫
Re-search 的原因吧,通过反复的寻找(research),得出一个美妙的想法。我最为反感的就是不问缘由,突然就冒出一个结果,仿佛它本来就应该是这样的。上算法课时,老师讲了一个图灵奖获得者如何解决问题。在遇到一个新问题时,他通常都是先用各种各样的小例子去不断地尝试,在尝试的过程中,不断地与问题进行各种各样的碰撞,然后发现问题的关键性质。当然,这种能力的一个重要前提是,我们需要学习各种算法技术,学习的重点在于了解每种算法技术分别适用于什么样的问题,这些问题有着怎样的性质和结构。
       所以我们需要提高观察问题结构的能力,又要积累一定的算法技术,这需要耐下心来读书,观察模仿别人解决问题的思路和想法,多积累多思考,还需要大量的实践。所以我觉得初学的时候,最好是先对各种算法技术有一个初步的认识,掌握解决问题的思路,然后分专题深入学习,专题学习时,可以把经典教材的相应章节都看看,题目都做了,做不出来,也要思考一段时间,另外读算法书时,要经常手工模拟算法的执行过程,不要怕麻烦,模拟的过程可以对算法的细节有深入的理解,也会培养起一些解决问题的感觉。然后读这个领域经典的论文,比如动态规划,最早提出是哪篇论文,重要的问题有哪些,看看科学家们是如何做问题的。最后,把OJ上关于这个专题的题目做一做,实际用程序跑一下。完成这些后,相信对这个领域会变得非常熟悉。专题学习最大的好处就是利于建立问题之间的联系,加强理解,如果注意力太分散,盲目地做各类题,是很难有长进的。
       最后这幅图,是算法课第一节和最后一节课老师在黑板上画的图,描述遇到一个问题,应该沿着怎样的思路去思考。

       算法课一般主要讲的是组合优化方面的算法,另一个分支是基于统计的,这里没有给出,但是他们是同等重要的。

转载请注明出处:http://blog.csdn.net/on_1y/article/details/8625728

抱歉!评论已关闭.