算法策略

贪心算法

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。

确定贪心策略 选择当前看上去最好的方案

一步一步得到局部最优解

将所有局部最优解合并称为一个原来问题的最优解

原则

选择一个最好的贪心策略

物品可分割称为背包问题 物品不可分割称为0-1背包问题

递推法

由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系

递归法

解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法

特别地，当规模N=1时，能直接得解

写递归代码最关键的是写出递推公式，找到终止条件。实现递归代码要注意的两个问题：调用栈溢出与重复计算

暴力递归有着十分明显的缺陷，有剪枝与优化这两种方法：

  1. 利用预设条件减少搜索路径，优化最优组合搜索方案
  2. 利用重叠子问题，避免重叠子问题的计算，如使用备忘录

重叠子问题的处理模式：

当目标为 $x$，求最优解 $f(x)$

数值函数 $g(t)$。如果求最小值，那么 $g$ 是 min，如果求最大值，那么 $g$ 就是 max

假定当前得到子问题的参数为 $c$，得到后续子问题的函数是 $s$，那么这个函数就是 $s(x, c)$

函数 $v(x)$，该函数可以聚合当前参数 $c$ 和当前子问题的结果

叠加函数 $h(x)$ 定义了每一步如何与子问题进行叠加

$$f(x)=h(g(v(f(s(x,c)),c)))$$

枚举法

对所有可能的解逐一尝试，从而找出问题的真正解

这就要求所解的问题可能的解是有限的、固定的，不会产生组合爆炸、容易枚举的

分治法

其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之, 递归地求解问题

每层递归应用：

对于递归的问题，当不需要再继续递归分解子问题时，就是一个基本情况，此时可直接得出解，否则就是递归情况

递归式则可以用来描述复杂度，如归并排序的递归式

O(1)           若 n = 12T(n/2) + O(n) 若 n > 1

分治算法要素

典型算法

动态规划

贪心算法根据局部最优解得到全局次优解，为了得到全局最优解，可以在贪心算法中引入回溯的过程，通过暴力的方式递归枚举出所有组合找到最优解，递归枚举的过程中，有些大问题是由小问题的解组成的，这部分就可以进行优化，从而引入动态规划

通过子问题的最优解，推导出最终问题的最优解，把这些子问题之间的转移称为状态转移，并把用于刻画这些状态转移的表达式称为状态转移方程

动态规划的思想类似于分治法，不过动态规划是从最小子问题求起 将小问题的解存储起来，求解大问题时 如果需要用到小问题的解 直接使用即可 无需再重复计算

状态转移方程，为了写出它，需要按照套路找出以下项目：

$$f(x)=\left{\begin{array}{c}d(x),x\in V_I\g({v(f(s(x,c)),c)}),c\in values(x)\end{array}\right.$$

  1. 如果一个 $x$ 不用再划分子问题，就可以直接返回
  2. 否则需要从可选组合 $values$ 中取出用于划分子问题的备选值，$values$ 可能会随着 $x$ 变化而变化
  3. 对每一个备选值 $c$ ，通过函数 $s(x,c)$ 求得当前备选值的子问题的 $x$, $c$。然后，通过 $f(s(x,c))$ 得到这个子问题的结果
  4. 接下来通过子问题 $v(f(s(x,c)),c)$ 的结果和当前备选值 $c$，来求得当前问题的解
  5. 最后通过最优化函数 $g(t)$ 进行求解最优值

要素

典型算法

回溯法

回溯法是一种选优搜索法，按照选优条件深度优先搜索，以达到目标。当搜索到某一步时，发现原先选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态称为“回溯点”。

要素

典型算法

分支限界法

回溯法找出所有解

分支限界法找出一个接

回溯法深度优先分支限界法广度优先

回溯法搜索一次生成一个孩子节点分支限界法一次生成所有节点

线性规划网络流

解决

算法思想

数据结构决定程序

使用更合适的数据结构能减少代码量

正确的程序

性能分析

估算

使用小实验获取关键参数

任何事都应尽量简单 但不宜过于简单

算法设计

代码调优

一些优化方案：

节省空间

自描述数据

技巧