算法是为解决某个具体问题设计的解题步骤,根据问题分类有:
- 排序
- 查找
- 字符串:字符串匹配等
- 图问题:对复杂关系的建模
- 组合问题:排列组合,选取满足目标的对象,比如成本最小等
- 几何问题:处理点、线、面等几何对象,应用于计算机图形学
- 数值问题:数学问题,比较解方程,计算定积分等
因算法依赖具体问题,局限性较强,但很多算法设计思想有相通之处,根据设计思想分类有:
- 蛮力法:比如 BFS,DFS,顺序遍历等,遍历所有解空间,找满足条件的解
- 分治法:
- 动态规划:主要是多阶段决策问题
- 贪心:图相关算法,最小生成树(Prim 算法和 Kruskal 算法),最短路径(dijkstra 算法)都属于贪心算法
一些个人总结:
不论什么问题,第一步都可以将问题规模降到最低,然后求解,然后问题规模再变大一点,再去求解
根据这个过程,就可以利用不同的设计技巧
- 如果增大问题规模,求解需要使用原来已求解的结果,这就是动态规划,保存每个阶段的结果,递推下去,就可以找到最终解
- 如果增大问题规模,求解过程不依赖原来已求解的结果,这就是分治,分成独立的子问题,分别求解,然后合并解就是最终解
- 如果增大问题规模,
一些个人文章:
动态规划的解释
labuladong 个人文章
程序员小吴