目录
写在前面
臭打 ACM 的懂个屁的算法。
记录一些会考但是 ACM 中不会在意或者概念不一样的东西。
判断
- 背包问题的最佳解决方案始终包含具有最大单位价值比vi/ci的对象i （错误）可能放不下。
- 输入规模不是指输入数据的个数，而是数据在内存中所占空间的大小，也要考虑输入数据的长度。
简答
影响时间复杂度的因素
算法执行次数、数据规模、算法基本操作、输入数据特征（是否有序）
排序
- 稳定排序算法：冒泡，插入，归并，计数，基数。
- 不稳定排序算法：选择，快速，堆。
Prim 和 Kruskal 的异同
相同点：都是利用了最小生成树性质的贪心。
不同点：Prim：通过扩充连通节点子集来进行贪心选择；Kruskal 通过选择具有最小权的边的集合来进行贪心选择。
贪心和 DP 的区别
相同点：都是推导算法，都具有最优子结构性质。
不同点：
-
贪心：
- 每步决策仅由上一步的最优解推导下一步的最优解，上一步以前的最优解不做保留。
- 每一步的最优解必定包含上一步的最优解。
- 自顶向下的，当前的求解不依赖于有待于做出的选择和子问题（即子树的状况），仅需选择当前局部最优解。
- 只有一个子问题。
-
动态规划：
- 全局最优解中必定包含某个局部最优解，但不必定包含前一个局部最优解，所以须要记录以前的全部最优解 （无后效性）
- 关键是状态转移方程，即如何由已求出的局部最优解来推导全局最优解。
- 自底向上的，通过子节点求出根节点，相对于贪心算法来说开销比较大。
- 有多个子问题
优缺点：
DP：优点是可以得到全局最优解；缺点是空间开销大，需要计算所有子问题
贪心：优点是思维复杂度低、代码量小、时空复杂度低；缺点是有时只能得到局部最优解。
DP 与分治的区别
相同点：都是把原问题划分为多个子问题求解。
不同点：
动态规划：
- 子问题并不是互相独立，同一个子问题可以同来求解多个问题。
- 多数自底而上来求解问题，利用额外的空间存储子问题的结果。
- 一般用于解决最优问题。
分治：
- 分子问题相互独立的，一个子问题只能求解一个问题。
- 分治一般自顶向下递归求解。
- 解决通用问题。
贪心，DP 与分治
| 标准分治 | 动态规划 | 贪心算法 | |
|---|---|---|---|
| 适用类型 | 通用问题 | 优化问题 | 优化问题 |
| 子问题结构 | 子问题不同 | 子问题重复(不独立) | 只有一个子问题 |
| 最优子结构 | 不需要每个 | 必须满足 | 必须满足 |
| 子问题数 | 全部子问题 | 全部子问题 | 只要解决一个 |
| 子问题在最优解里 | 全部 | 部分 | 部分 |
| 选择与求解次序 | 先选择后解决子问题 | 先解决子问题后选择 | 先选择子问题后解决 |
分支界限法和回溯法的异同
- 求解目标不同：回溯法的一般是找出解空间树中满足条件的所有解。分支限界法则是尽快找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
- 搜索方式不同：回溯法深度优先，遍历结点搜索解空间树；分支限界法广度优先或最小耗费优先搜索解空间树。
- 存储空间不同：分支限界法加入了活结点表，存储空间比回溯法大得多。
- 扩展结点的方式不同：分支限界法中每个活结点只有一次机会变成扩展结点，一旦成为扩展结点便一次性生成其所有子结点。
应用：回溯法空间效率更高，分支限界法由于只需求一个解因此一般效率更高。
| 方法 | 回溯法 | 分支限界法 |
|---|---|---|
| 对解空间树的搜索方式 | 深度优先搜索 | 广度优先或最小耗费优先搜索 |
| 存储结点的常用数据结构 | 搜索过程中动态产生问题的解空间 | 队列、优先队列 |
| 结点存储特性 | 活结点的所有可行子结点被遍历后才被从栈中弹出 | 每个结点只有一次成为活结点的机会 |
| 主要应用 | 找出满足约束条件的所有解 | 找出满足约束条件的一个解或特定意义下的最优解 |
计算与算法应用题
复杂度计算
见：「笔记」递归算法复杂度分析 - Luckyblock - 博客园
分支界限法
类似于回溯法，是一种在问题的解空间树T上搜索问题解的算法。但一般情况下与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
分支限界法首先生成当前扩展结点的所有分支，然后再从所有活结点中选择一个作为扩展结点。每一个活结点都要计算限界，根据限界情况判断是否剪枝，或选择最有利的结点。
分支限界法有两种不同的搜索空间树方式，分别为广度优先和最小耗费优先，它们对应两种不同的方法：
- 队列式分支限界法(FIFO)：常规的广度优先策略。按照先进先出的原则选取下一个扩展结点，以队列储存活结点。
- 优先队列式分支限界法/最小耗费优先分支限界法(LC)：按照优先队列中指定的优先级，选取优先级最高的结点作为下一个扩展结点，以优先队列储存。
上述两种方法分别与两种策略对应：
- 按顺序选择结点作为下一次的扩展结点。优点是节省空间，缺点是需要计算的分支数较多，时间花费大；
- 每次计算完限界后，找出限界最优的结点，作为下一次的扩展结点。优点是计算的分支数少，缺点是需要额外空间。
限界函数很大程度上决定了算法的效率。同一问题可以设计不同的限界函数。
- FIFO 分支限界法中，常以约束条件作为限界函数，满足约束条件才可入队，不满足约束条件的舍弃。
- LC 分支限界法中，还可以设计一个启发函数作为限界函数。
对于有约束的问题，FIFO法和LC法均可以求解；对于无约束问题，宜使用LC法。
实际上是一种基于剪枝的启发式搜索。
例题见下。
分支界限法背包
定义：\(W\) 表示当前所有选择物品的重量之和，\(P\) 表示当前所有选择物品的价值之和，\(BP\) 表示搜索到的所有可行解中的价值的最大值。
根节点代表扩展结点，其余每一层代表一个物品的选择情况，选中该物品则向左子树进行递归判断，否则向右子树递归。发现这是一棵二叉树，且从根节点到叶节点的 \(2^n\) 条路径与 \(2^n\) 种可能的选择方案一一对应。具体执行操作如下所示：
- 所有物品按单位价值降序排列。
- 从根节点（扩展节点）出发开始搜索；
- 对于第 \(i\) 层（代表物品 \((w_i, p_i)\)）的节点，先尝试搜索左子树表示尝试选择该物品，判断是否满足约束条件（当前该物品是否可以装入背包？）：
- 若可以选择则令 \(W:=W + w_i, P:=P + p_i\)，继续向下搜索；
- 直至遇到不可行解时，开始向上回溯，取出最后一个装入的物品，进入右子树。
- 否则进入右子树，首先计算当前节点的上界 \(U\)，若 \(U > BP\) 则剪去右子树继续向上回溯；否则回到步骤 3；
- 遇到叶子节点，比较当前价值与 \(BP\)，若 \(P>BP\)，则 \(BP:=P\)。
- 直到遍历完所有的节点（除剪枝部分外）。
一张我自己都懒得看的图：
分支界限法求单源最短路径
参考：算法分析与设计：分支限界法_分支界限法的效率与哪些因素有关-CSDN博客
求最短的路径，考虑使用优先队列式分支限界法，以减少计算的分支数。以下图为例：
- 生成根节点的所有分支，全部入队列并记录路径；
- 在队列中选择路径最短的分支作为扩展结点
- 逐个生成分支，并判断分支的路径是否小于记录的最短路径；
- 若不小于，舍弃该分支；
- 若小于，该分支入队列；
- 生成所有分支后，回到2；
- 当队列为空时，算法结束。
分支界限搜索树：
树上所有根节点到其他节点的路径均代表一条搜索过程中访问到的路径，对于每个节点最后搜索到的从根节点到该节点的路径即为到达该节点的最短路径。
算法设计题
这个真是随便 AK。
写在最后
参考：
标签：结点,杂文,ACMer,算法,最优,节点,限界,分支 From： https://www.cnblogs.com/luckyblock/p/18242695