算法设计技巧总结

前言

对《数据结构与算法分析——C语言描述》中算法设计技巧的总结。


一、贪婪算法

主要思想

分阶段工作,在每一个工作阶段,可以认为所做决定是好的,而不考虑将来的后果。如果局部最优能达到全局最优,则算法是正确的,否则只是次最优解。

例子

  1. 找零钱问题。
  2. Dijkstra算法:图论问题。用于解决单源最短路径问题。
  3. Prim算法:图论问题。基本上与Dijkstra算法相同,用于形成无向图的最小生成树(连接所有顶点的总价值最低的数)。
  4. 调度问题:
    • 使平均完成时间最小,需要优先完成更短的作业。
    • 使最后完成时间最小,属于NPC问题。
  5. Huffman编码:每次树的合并只考虑当前权最短。
  6. 近似装箱问题:(NP问题)
    • 联机算法:当前工作完成,才可进行下面的工作。包括:下项适合算法、首次适合算法、最佳适合算法。
    • 脱机算法:能够观察全部的物品之后再算出答案,自然比联机算法更优。做法是排序,包括:首次适合递减算法、最佳适合递减算法。

二、分治算法

主要思想

分:递归解决较小的问题(BASE情况除外)。
治:从子问题的解构建原问题的解。

例子

  1. 最大子序和问题
  2. 树的遍历
  3. 归并排序及快速排序
  4. 最近点问题:在平面上的点集中寻找一对最近的点。
  5. 选择问题:在N个元素中选出第K小的元素,采用快速排序的变体达到平均运行时间为O(N)。枢纽的选取很重要,采用五分化中项的中项。
  6. 运算问题的理论改进:例如将O(N^2) 的整数乘法降低为O(N^1.59)。 O(N^3) 的矩阵乘法降低为O(N^2.81)。

三、动态规划

主要思想

有些问题的递归解法虽然逻辑简单,但是时间复杂度太高,重复计算太多,例如斐波那契数列递归解法。利用额外的空间复杂度来记录一些子问题的答案,将递归算法重新写成非递归算法,即动态规划。

例子

  1. 斐波那契数列的线性算法。
  2. 一些递归表达式的解法。
  3. 矩阵乘法的顺序安排。
  4. 最优二叉查找树(类似huffman方法的贪婪算法并不能最好的解决)
  5. 所有点对的最短路径。

四、随机化算法

五、回溯算法

主要思想

穷举搜索的巧妙实现。到了不合适的地步就往回一步,后面不再考虑。

例子

  1. 收费公路重建问题:根据站点间的距离,放置站点。
  2. 博弈问题:极小极大策略。改进技术:裁剪。

后续可能会用代码实现上述问题。

您的支持是我创造源源不断地动力