《算法设计与分析》复习笔记

计算复杂度

$$T(n)\in O(f(n)) \iff \lim_{n\rarr \infty} \frac{T(n)}{f(n)}\le c\iff \forall n\ge n_0 \ T(n)\le f(n)\\ O(f(n))+O(g(n))=O(\max\{f(n),g(n)\})\\ O(f(n))+O(g(n))=O(f(n)+g(n))\\ O(f(n)*g(n))=O(f(n)*g(n))\\ O(cf(n))=O(f(n))$$

$$T(n)\in O(g(n))\iff \lim_{n\rarr \infty}\frac{T(n)}{g(n)}\le c\iff \forall n\ge n_0 \ T(n)\ge cg(n)$$

$$T(n) \in \Theta(g(n)) \iff\forall n\ge n_0\ c_1g(n)\le T(n)\le c_2(g_n)$$

可计算理论

分类

• P问题：可在多项式时间内求解的问题；
• NP问题：可在多项式时间内验证的问题；
• NP完全问题：任何NP问题都可以在多项式时间内归约为NPC完全问题；
• NP难问题：任何判定问题在多项式时间内可以

经典NP完全问题

---

1. 3-CNF 可满足性问题 (3SAT) 问题描述 ：给定一个布尔公式，该公式是由逻辑“与”连接的若干“或”子句组成，每个子句包含三个字面值（变量或其否定）。目标是判断是否存在一种变量赋值使得整个公式为真。
   意义 ：这是第一个被证明为NP完全的问题，许多其他问题都可以归约到3SAT。

---

2. 团问题 (DCLIQUE) 问题描述 ：在一个无向图中，给定一个整数k，判断是否存在一个大小为k的完全子图（即所有节点两两相连的子图）。
   应用 ：在社交网络分析中，用于寻找“最大团”，即所有成员彼此互相关联的最大群体。

---

3. 顶点覆盖问题 (DVC) 问题描述 ：在一个无向图中，寻找一个顶点集合，使得每条边至少有一个端点在该集合中，且集合大小最小。
   应用 ：网络保护、覆盖监控等。

---

4. 独立集问题 (DIS) 问题描述 ：在一个无向图中，寻找一个独立集（任意两点间无边相连）的最大子集。
   应用 ：用于资源分配、冲突避免等场景。

---

5. 集合覆盖问题 (SC) 问题描述 ：给定一个元素集合U和一组子集，确定是否存在k个子集的集合覆盖U中的所有元素。
   应用 ：常用于优化问题，例如选址、任务分配等。

---

6. 子集和问题 (SS) 问题描述 ：给定一个整数集合S和一个目标值T，判断是否存在S的某个子集，其和等于T。
   意义 ：这是一个经典的NP完全问题，也是背包问题的特例。

---

7. 带开放时间和截止时间的调度问题 (SRD) 问题描述 ：为一组任务分配开始和结束时间，满足每个任务的时间限制，并最小化某种资源（例如机器时间）。
   应用 ：工厂调度、任务规划等领域。

---

8. 有向哈密顿回路问题 (DHC) 问题描述 ：在一个有向图中，判断是否存在一个哈密顿回路，即访问每个顶点一次且仅一次的闭环路径。
   应用 ：物流、路径优化。

---

9. 哈密顿回路问题 (HC) 问题描述 ：这是DHC的无向图版本，判断是否存在这样的回路。
   应用 ：类似DHC，多用于路径规划问题。

---

10. 旅行商问题 (DTSP) 问题描述 ：给定一组城市和它们之间的距离，找到一条路径，使得旅行商访问每个城市一次后返回出发城市，且路径总距离最短。
    应用 ：物流配送、巡逻路径规划等。

动态规划

• 将过程划分为若干个阶段；

• 每个阶段做出决策；

• 各个阶段所确定的决策构成决策序列，通常称为一个策略；

• 描述决策的变量，称为决策变量；

• 决策变量的取值往往限制在某一范围内，此范围称为允许决策集合；