zz的算法小抄

动态规划

DP=“递归”+“记忆”+“猜测”

求解步骤

1. 定义子问题:$x\in X$，子问题，原问题（输入数据的规模不同）
   1. 子问题：描述（语言），参数。
   2. 输入数据-序列，数据的前缀，后缀，中缀，连续的一段数据。
2. 建立子问题间的关系（递归）
   1. 猜测（递归，分治中的不妨设类似）启动求解过程
   2. 子问题的解看成节点
   3. 子问题求解过程看成节点的遍历
   4. 节点遍历需满足拓扑排序（当前节点只与已经求得值的节点有关）
3. 明确边界条件
4. 得到原问题的解
   1. 表上遍历
5. 分析时间复杂度
   1. $T(n)=子问题个数*每一子问题求解时间$

---

递归算法

求解步骤

1. 分解问题
2. 递归求解
3. 边界条件

递归算法的两个要素

• 必须有最终停止发展下线的边界条件。

• 必须有与原始问题结构一致，但输入规模小于原始问题规模的递归结构。

主成分方法

递推式为：$T(n)=aT(n/b)+f(n)$

$T(n)=f(n)+af(n/b)+a^2f(n/b^2)+…+n^{log_b^a}$
(1)渐进上升
$f(n)=o(n^{log_b^a-\epsilon})$
$T(n)=o(n^{log_b^a})$

(2)渐进相等
$f(n)=o(n^{log_b^a}(log_2^n)^k)$(存在常数k)
$T(n)=o(n^{log_b^a}(log_2^n)^{k+1})$

(3)渐进下降
$f(n)=o(n^{log_b^a+\epsilon})$
$T(n)=o(f(n))$

---

分治算法

求解步骤

1. 把原问题分解成若干个子问题
2. 递归求解每一个子问题的解
3. 合并子问题的解

与递归相比，多了合并子问题的解

合并时需要技巧，有时关系到时间复杂度

---

贪心算法

• 求解优化问题的一类算法（最少，最多，最长，最短）

求解步骤

1. 遍历备选元素
2. 贪心策略确定选择一个元素

• 决策过程
  • s集合大小依次增大
  • I集合大小依次减小
    • 剩余元素状态不变
    • 剩余元素状态改变（复杂）

掌握局部信息，选择当前最优的方案，不一定能得到最优解，需证明

回溯与分支界限算法

回溯基本用深度优先，分支界限基本用宽度优先。

回溯BackTrack

• 穷举
• 状态空间（状态空间树）
• 路径（根->叶子）对应解
• 求解问题过程就是状态树上遍历的过程
• DFS/BFS
• 为了提高效率，很多时候会用到剪枝

分支界限 Branch and Bound

• 常用于求解优化问题
• 穷举所有的“状态”，利用上界或下界提高搜索效率。
• 术语：
  • 活节点：该节点刚被生成，子节点还未产生。
  • 当前节点（E-node）：当前正在展开节点。
  • 死节点：不需要展开的节点。
• 搜索方法：E-node需要确定
  • 注意力（优先级的设定）

• FILO（栈）宽度优先（右->左）

• FIFO（队列）宽度优先（左->右）

• LC

  • 在状态树上搜索
  • 在树t中设定各节点的值函数$c()$
  • x是树上的节点（$c(x)$最小耗费量），$c(t)$问题的最优解）
  • $c’(x)$近似的值函数
  • 两个函数维护活节点
    • least(活节点的优先级)
    • add(x) (把新的节点加入到活节点中)

• Bounding(剪枝)

  • $c’(x)<=c(x)$
  • $c’(x)$解的下界
  • if $c’(x)>u$剪枝(u表示最小值)
  • u的初始值，设为无穷大
  • 每次处理完E-node,更新u

赏

谢谢你请我吃糖果

支付宝