关于程序算法解决问题的总结

用程序算法来解决问题,需要具备什么样的indispensable knowledge呢? 个人认为以下5点是不可或缺的:

1. Problem-solving skills.
   首先是要有解决问题的技能,就是要有固定成型的解决问题的思考模式,这个很重要,遇到千变万化的问题,采用一套有效的思考模式会事半功倍!究竟是什么样的思考模式比较有效呢,数学大师波利亚的巨著《How to solve it》给出了很好的解决问题的思考模式!对于程序解题来说,可以把波利亚的思考模式具体化,借用一下面向对象里的继承机制,Problem-solving-by-algorithm派生自Polya's-problem-solving-skills. 计算机科学家Steven Skiena在他的典著《The Algorithm Design Manual》中给出了程序算法解题的分析思考模式,非常值得借鉴。

2. Algorithm Design Skills.
    其次是要选择正确的算法策略。算法设计时要区分strategy和tactics。算法设计的策略有贪心、分治、动态规划、启发式、蛮力、穷举。。。,当策略选择正确后,再选择tactics。要很好地理解策略的思想,思想是旗帜,是行动指南!
  
3. Data Structure Knowledge
   常见的数据结构有set, array, list, tree, graph, string, stack, heap, queue, priority queue等

4. Algorithm Knowledge
   这里的算法相对于前面的strategy就是tactics,是具体的做法了,如排序算法(快速排序,归并排序,堆排序,基数排序,插入排序等等)、搜索算法(DFS, BFS,A*等等)、字符串模式匹配、排列组合算法、几何算法等等。 这些算法往往是针对一定的Data Structure的操作。应该熟练掌握常见算法的实现。

5. Problem Base
    问题库就是各种类型的问题的集合,它们很典型,熟练掌握这些问题的算法分析设计对于解决新问题是绝对有好处的,遇到新问题时,通过类比,把未知规约成已知的解决过的问题。因此,储备很重要,应熟知各种经典问题。

这五点的关系可以用下图形象化地表示(用graphviz画图):




posted on 2010-01-30 18:02 挑灯看剑 阅读(323) 评论(0)  编辑 收藏 引用 所属分类: 工作随笔

只有注册用户登录后才能发表评论。
<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

公告

【自我介绍】 08年南开大学硕士毕业 最近关注:算法、Linux、c++、高并发 爱好:滑旱冰、打乒乓球、台球、保龄球

常用链接

随笔分类(139)

文章分类

我常去的网站

技术博客(都是大牛)

技术站点

搜索

积分与排名