什么是算法，为什么需要学算法，以及算法学到什么程度

梦里梦外; 2022-06-15 09:14 185阅读 0赞

第一个问题我觉得我无法给出完美的答案，这里搞竞赛的牛人蛮多，不妨说说体会。

我个人觉得算法里面极大一部分内容是如何有效地进行搜索，这里的”有效”可以分为：避免不必要的计算（如A\*寻路以及所有的启发式剪枝），缓存重复计算（如所有的动态规划）。当然，知道这些跟具体的设计出一个算法至少还有十万八千里，只能说有了这个大体的思路，就可以从这两个角度去审视手头的问题，往往是会有启发意义的罢了。如何避免不必要的计算？也有很多 rules of thumb 可以遵循，如启发式剪枝里面就要求去设计一个最优下界，而最一般的思路则是使劲瞅瞅问题里面有什么条件是没有利用的，这些条件组合起来可以得出什么性质，也许某个性质就能够被利用来减掉一大堆计算，至于如何从题目条件推出有价值的性质，有两个办法，一是试错（想到的结论都给写出来，陶哲轩在 Solving Mathematical Problems 里面就提到过这个办法。）；另一个方向则是脑袋里揣着想要实现的目的往反方向归约。如何缓存重复计算？简单的动态规划问题如fibonacci数列计算，其重复计算是非常明显的，计算的过程本身就指明了哪些计算是重复的（An 项的计算是重复的）——当然，正如早前邓同学发的一个题目[https://groups.google.com/group/pongba/browse\_frm/thread/2ca1f2bda0c8…][https_groups.google.com_group_pongba_browse_frm_thread_2ca1f2bda0c8]里面说的，其实fibonacci数列计算里面的线性变换本身也是有重复计算的——后者便是更隐蔽的重复计算了，一个 non-trivial 的动态规划问题往往涉及到非常隐蔽的重复计算，或者更难的是，你遍历组合空间的方式决定了你所能够缓存的重复计算到底有多少，也许某个遍历方式之下就没有办法去缓存计算。当然，算法的范畴其实是很大的，算法是一个AI-Complete 的问题，所有的 Problem-Solving 过程都可以叫做算法。只是有很多实际当中的算法会掉入以上两类而已。

第二个问题我举一个例子：不像很多牛人在高中和本科就竞赛奖牌一堆，我直到大四的时候还不知道什么是动态规划，因为本科四年我一直只对底层技术感兴趣，最喜欢看 比如 Petzold 的《编码的奥秘》和 Richter 的《.NET 框架程序设计》（事实上这是我看的第一本英文原版书）这类书。研一的时候由于方向是自然语言处理，看的第一篇 paper 是 Rabiner 的 A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition。Paper 的内容倒是完全能够理解，但是理解其实只是第一步，我发现理解了之后很快就忘掉了，这就说明理解得不够深刻。比如里面的 Viterbi 算法，花了时间去理解，但是一转头很快又忘掉了。一年后因为机缘巧合，对算法发生了一段短暂的兴趣，并学习了一些基础的算法，尤其是算法的思想，因为思想是有穷的，但算法是无穷的，尤其是题目是做不完的。之后一段时间，碰巧又需要翻一翻马可夫模型，搜出吴军的数学之美以及那篇 Paper ，发现 Viterbi 算法其实就是最简单的一类动态规划，由于对于动态规划的理解深刻了很多，所以对于 Viterbi 算法，在脑袋里面记住的不再是什么 Forward Variable/Backward Variable 之类的技术细节，而是它的本质，于是便不再容易忘掉，而即便忘掉，就如庞加莱所说，也可以非常迅速的将算法的细节自行构建出来。

其实我相信这样的例子是数不胜数的，所以我这个只是算一个 Yet Another Example ，由于对我来说比较特殊，所以印象较为深刻。

这个例子是关于”理解”的。有时候算法也会非常有用，如有一次写程序时需要用到 LCS 和 Edit-Distance （这样的机会很少，但遇到了时如果不知道有多项式复杂度的算法就很悲惨了），而做机器学习和数据挖掘的更是少不了一坨坨的算法，如果光是理解别人的做法然后实现出来，那么对算法的思想的把握有助于理解和记忆；如果需要自己设计算法，那就需要算法基础知识的辅助才行了。绝大多数人应该属于前者。

学习到什么程度？我觉得视人群而定。如果做底层开发、应用开发、系统开发，只要知道一个大概就可以了，知道经典的数据结构和算法没有任何困难，而且反正经典算法都有现成的库可用。对于有兴趣做一点 research 沾边的事情的人，则需要了解这些算法背后的一般性思路是什么，否则来一个特定的算法你就特定的理解记忆一下，肯定不牢靠，而且浪费大脑资源。对于搞 real deal 的 original research 的那就需要广泛的知识积累了，光知道一般性思路都不够。

另一方面，我觉得学完了经典算法，深刻理解了算法背后的一般性思路之后，如果再进一步去玩题目，做题库。效益却不是很大的，因为刀磨了是要用的，玩题目做题库就是进一步磨刀而不用（不去解决实际问题，能够产生影响力的，或生产力的问题）。实际上做了一些题目之后就完全没必要进一步做题目了，因为做来做去，拼的基本也就是谁的知识积累多（套路多），谁的耐心大（肯使劲去磨一道题目）；实际上谁也不比谁笨，到最后区别就基本上显露在知识积累和耐心上了。所以接着做，刀也不会磨得更锋利，更何况大好的时光应该去做点有意义的事情（如果是为了 fun 而做题的，那么有意义的事情同样也可以是 extremely fun），比如我觉得最吸引人也最根本的问题就是人工智能问题（想想看，人脑是世界上迄今为止所知最为复杂的结构，这个结构具备了认识自然界”规律”的能力，具备了认识”自我”的能力，具备了归纳和演绎推理的能力，类比的能力，具备了难以置信的启发式搜索能力，具备完美的模式识别能力，而根据进化论的观点，这样的结构居然仅仅是通过变异——筛选得来的，如果真有上帝，那么利用上帝赋予我们的大脑去破解上帝这个顶级牛逼程序员写的程序——人脑的秘密，还有比这更带劲儿的事情吗？），所以我觉得有那么好的基础的牛人，不去直面真正 fundamental 的 problems ，就可惜了，须知题目是永远做不完的，一个公理系统的定理也是永远推导不完的，永远可以设计出题目来给你做，但是真正的问题其实只有一个。如果穷举不了世界上所有的问题，至少可以举出那些有趣、有意义的问题。

刘未鹏(pongba)  
Blog|C++的罗浮宫  
[http://blog.csdn.net/pongba][http_blog.csdn.net_pongba]

[https_groups.google.com_group_pongba_browse_frm_thread_2ca1f2bda0c8]: https://groups.google.com/group/pongba/browse_frm/thread/2ca1f2bda0c8...
[http_blog.csdn.net_pongba]: http://blog.csdn.net/pongba