保研资料：算法设计与分析

算法

有限条指令构成，规定了解决特定问题的一系列操作。

算法分析

确定运算+确定数据集、分析时间复杂度（事前分析）、作时空性能分布图（事后测试）

分治法

缺点：子问题过多（治：反复使用分治策略，直到可以直接求解子问题）、递归工作量过多（分合）。

多阶段决策过程（组合问题）

前后关联的有链状结构的过程。在每一个阶段都有很多选择。多阶段决策问题的解决：贪心、动态规划，分支限界、回溯法。

贪心和动态规划

贪心-寻找最优量度标准
解决寻找一个输入的子集的问题，满足约束条件（可行解）和目标函数（最优解）的解。一旦证明成立后，是简单易行的高效算法。同时对许多不一定能产生最优解的问题都能产生近似最优解。

动态规划-最优子结构、无后效性、子问题重叠
最优子结构：问题的最优解所包含的子问题的解也是最优的。反例：求一系列数的异或最大值
无后效性：当前阶段的求解只与之前阶段有关，而与之后的阶段无关。反例：带负权边的最短路
决策并不是线性的，而需要全面考虑不同情况，分别决策。
步骤：寻找子问题、定义状态、导出状态转移方程、确定边界条件。

回溯法和分支限界法-搜索和剪枝

回溯法-多米诺性质（如果部分解向量不成立，则后续所有解向量都不成立）
需要约束条件和目标函数。 影响回溯法（DFS）的效率（即剪枝）的因素：限界函数的计算时间（重）、通过限界函数的数目。

分支限界法（BFS、LC、D）-估价函数≤成本函数≤上界函数
若估价函数≤成本函数，且对于答案叶节点相同，则LC终止时就是最小成本答案节点。需要额外的存储空间维护活节点表，更利于求最优解问题。

现实世界的问题-P、NP、非P

多项式级、指数级、不可计算（希尔伯特第十问题）、尚不确定多项式级（图着色、货郎担）。
P：多项式时间内用确定算法求解的判定问题。
NP：多项式时间内用不确定算法（猜想+验证）求解的判定问题。
NP完全：所有属于NP的问题都可以规约的NP问题。
NP-hard：所有属于NP的问题都可以规约的问题。
非P：不存在确定算法的多项式时间内的解。
如果存在一个NPC可在多项式时间解决，则所有NP问题均可在多项式时间解决，即P=NP。
P包含于NP，NP真包含于非P
Cook定理：SAT问题是NPC问题。（还有最大可满足性问题）
证明一个问题是NPC问题：L是NP问题，一个NPC问题能多项式规约为此问题。