算法设计与分析第十章~第十四章复习重点-171主机测评

文章目录

一、回溯法
- （一）问题的解空间树
- - 1.问题的解空间
  - 2.可能解的表示方式
  - 3.解空间的表示方式
- （二）设计思想
- （三）时间性能分析
- - 1.子集树
  - 2.排列树
二、限界剪枝法
- （一）广度优先搜索的设计思想
- （二）限界剪枝法的设计思想
- （三）应用步骤
- （四）目标函数的界[down, up]的确定
- （五）从限界剪枝法看0/1背包问题
- （六）从限界剪枝法看TSP问题
三、回溯法和限界剪枝法的比较
- （一）相同之处
- （二）不同之处
四、问题的复杂性
- （一）确定性算法
- （二）P类问题
- （三）非确定性算法和NP类问题
- - 1.NP类问题的定义
  - 2.P类问题和NP类问题的区别
  - 3.常见辨析
- （四）NP完全问题（最难解的NP问题）
- - 1.基本定义
  - 2.性质
- （五）NP难问题
- - 1.定义
  - 2.NP 完全问题和 NP 难问题的联系与区别
- （六）P类问题、NP类问题、NP完全问题的关系
- - 1.图解
  - 2.具体示例
  - - （1） **P 类问题**（多项式时间可解）
    - （2）**NP 类问题**（多项式时间可验证）
    - （3）**NPC 问题**（NP 完全问题）
    - （4）**NPH 问题**（NP 难问题）
五、近似算法
- （一）基本思想
- （二）近似比和相对误差
- - 1.近似比的定义
  - 2.相对误差
六、概率算法
- （一）设计思想
- - 1.基本特征
  - 2.时间性能
- （二）舍伍德型概率算法
- - 1.算法设计思想
  - 2.算法说明
- （三）拉斯维加斯型概率算法
- - 1.基本特征
- （四）蒙特卡罗型算法
- - 1.基本特征
  - 2.一致p正确的蒙特卡罗型概率算法
- （五）三种概率算法的比较
总结

一、回溯法

（一）问题的解空间树

1.问题的解空间

复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。一般而言，解空间中应该包括所有的可能解。
需要注意的是：不正确的解空间可能会增加很多重复解，或者根本就搜索不到正确的解。

2.可能解的表示方式

问题的可能解表示为：满足某个约束条件的等长向量

X

=

(

x

1

,

x

2

,

…

,

x

n

)

X=(x_1, x_2 ,…, x_n)

$X = (x_{1}, x_{2}, \dots, x_{n})$ ，其中

x

i

x_i

$x_{i}$

(

1

≤

i

≤

n

)

(1≤i≤n)

$(1 \leq i \leq n)$ 取值范围是某个有限集合

S

=

a

1

,

a

2

,

…

,

a

k

S={a_1, a_2, …, a_k}

$S = a_{1}, a_{2}, \dots, a_{k}$ ，则所有可能的解向量构成了问题的解空间。
可能解的表示方式隐含了解空间及其大小。
对于n个物品的 0/1 背包问题，

x

i

∈

0

,

1

(

1

≤

i

≤

n

)

x_i∈ {0,1} (1≤i≤n)

$x_{i} \in 0, 1 (1 \leq i \leq n)$ 分别表示物品 i 不装入/装入背包的情况。当

n

=

3

n=3

$n = 3$ 时，其解空间是：

(

0

,

0

,

0

)

,

(

0

,

0

,

1

)

,

(

0

,

1

,

0

)

,

(

1

,

0

,

0

)

,

(

0

,

1

,

1

)

,

(

1

,

0

,

1

)

,

(

1

,

1

,

0

)

,

(

1

,

1

,

1

)

{(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) }

$(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)$ 。当输入规模为

n

n

$n$ 时，有

2

n

2^n

$2^{n}$ 种可能解。

3.解空间的表示方式

解空间表达：用解空间树（Solution Space Trees），也称状态空间树的方式组织：
- 第1层结点（根结点）：表示搜索的初始状态；
- 第2层结点：表示对解向量的第一个分量做出选择后到达的状态；
- 第1层到第2层的边上标出对第一个分量选择的结果
- 依此类推，从树的根结点->叶子结点的路径构成了解空间的一个可能解。
可行解：满足约束条件的解，是解空间的一个子集
最优解：使目标函数取极值（极大或极小）的可行解，数量较少，通常只有一个或少数几个。
例：TSP问题，有 $n^n nn种可能解， n ! n! n!种可行解，只有一个或几个是最优解。$
例：背包问题，有 $2^n 2n种可能解，有些是可行解，只有一个或几个是最优解。$
有些问题，只要求出可行解即可，不需要最优解。
例：八皇后问题和图的着色问题。

（二）设计思想

回溯法（ back track method ）从根结点出发，按照深度优先策略搜索解空间树，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则跳过以该结点为根的子树，也就是剪枝（pruning）。
与蛮力搜索相比，回溯法的“聪明”之处在于能适时回头，如果再往下走不可能得到解，就及时回溯，退一步另找路径，从而避免无效搜索。
需要注意的是：问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径
回溯法的搜索过程涉及的结点称为搜索空间，只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：
- 用约束条件剪去得不到可行解的子树；
- 用目标函数剪去得不到最优解的子树。
这两类函数统称为剪枝函数（Pruning Function）

以 0 / 1 背包为例子，如图所示

在这里插入图片描述

（三）时间性能分析

回溯法求解问题时，常用到两种典型的解空间树：

1.子集树

当问题是从 n 个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。若在子集树中， $|S_1| = |S_2| = … = |S_n| = c ∣S1∣=∣S2∣=…=∣Sn∣=c，即:每个结点有相同数目的子树，当 c = 2 c = 2 c=2 ，则子集树中共有 2 n 2^n 2n 个叶子结点，因此，遍历子集树需要 Ω( 2 n 2^n 2n) 时间。如：0/1背包问题。$

2.排列树

当问题是确定

n

n

$n$ 个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，

∣

S

1

∣

=

n

，

∣

S

2

∣

=

n

−

1

，

…

，

∣

S

n

∣

=

1

|S_1| = n，|S_2| = n-1，…，|S_n| = 1

$∣ S_{1} ∣ = n ， ∣ S_{2} ∣ = n - 1 ， \dots ， ∣ S_{n} ∣ = 1$ ，所以，排列树中共有

n

!

n!

$n!$ 个叶子结点，因此，遍历排列树需要

Ω

(

n

!

)

Ω(n!)

$Ω (n!)$ 时间。如：TSP问题。
回溯法本质上属于蛮力穷举，搜索具有指数阶个结点的解空间树，在最坏情况下，时间代价肯定为指数阶。
其有效性往往体现在当问题规模 n 很大时，在搜索过程中对问题的解空间树大量剪枝。
但是对于具体的问题实例，很难预测回溯法的搜索行为，特别很难估计出在搜索过程中所产生的结点数，这也是分析回溯法的时间性能的主要困难。

二、限界剪枝法

（一）广度优先搜索的设计思想

广度优先搜索（ breadth-first-search）简称 BFS 或广搜，是从某个顶点出发，由近及远，优先搜索距离起点最近的顶点。
假设从顶点 u 出发，广度优先搜索的基本思想是：访问顶点 u，然后依次访问 u 的各个未被访问的邻接点 $v_1、v_2、…、v_k v1、v2、…、vk，再分别从 v 1 、 v 2 、 … 、 v k v_1、v_2、…、v_k v1、v2、…、vk 出发依次访问它们未被访问的邻接点，直至图中所有和 u 有路径相通的顶点都被访问到。$
为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，设置队列存储已被访问的顶点。

（二）限界剪枝法的设计思想

按广度优先策略遍历问题的解空间树，在遍历过程中，对已经处理的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度优先搜索，从而不断调整搜索方向，尽快找到问题的解。

（三）应用步骤

首先，确定一个合理的限界函数；
并根据限界函数确定目标函数的界[down, up]；
仍以穷举法的解空间树为基础，但以广度优先策略搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数值；
如果某孩子结点的目标函数值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入open表中；
依次从open表中选取使目标函数取极值的结点成为当前扩展结点，重复上述过程，直到找到最优解。

（四）目标函数的界[down, up]的确定

对最大化问题：up由限界函数确定，down由某种启发方式得到，如贪心算法。
对最小化问题：down由限界函数确定，up由某种启发方式得到，如贪心算法。
因为限界函数常常基于问题的目标函数而确定，所以，限界剪枝法适用于求解最优化问题。

（五）从限界剪枝法看0/1背包问题

在这里插入图片描述

（六）从限界剪枝法看TSP问题

在这里插入图片描述

三、回溯法和限界剪枝法的比较

回溯法依靠深度优先+递归回溯深挖一条路径，适合寻找所有可行解或单个最优解；
而限界剪枝法依靠广度优先+限界择优横向扩展，适合快速定位最优解，尤其强调目标函数界限的确定（如笔记中0/1背包和TSP的图示分析）。两者的核心差异在于搜索的方向与剪枝的策略。

（一）相同之处

相同点具体说明

搜索基础	两者都基于问题的解空间树（状态空间树），将可能解表示为等长向量，从根结点出发搜索路径。
剪枝策略	都使用剪枝函数来避免无效搜索，本质上都是对蛮力穷举法的改进，旨在减少搜索空间。
时间复杂度	在最坏情况下，时间代价均为指数阶（如遍历子集树的 $2^n 2n 或排列树的 n ! n! n!）。$

（二）不同之处

比较维度回溯法分支限界法

搜索策略	采用深度优先策略，沿一条路径向下搜索，遇死路则回溯。	采用广度优先策略（常结合优先队列），按层级由近及远扩展结点。
数据结构	通常使用递归或栈，仅需存储从根结点到当前结点的路径。	使用队列（open表）存储待扩展的活结点，便于按广度顺序取出。
剪枝依据	利用约束函数剪去不满足约束的子树，同时用限界函数剪去不可能产生最优解的子树。	主要依赖限界函数，估算结点目标函数值，并与当前界 [down, up] 比较，超出范围的结点直接丢弃。
适用问题	既可求解可行解（如八皇后、图着色），也可求解最优解。	主要适用于最优化问题（如 0/1 背包、TSP 问题），限界函数需基于目标函数确定。
扩展方式	遇到满足约束条件的结点才进入其子树继续搜索，否则回溯剪枝。	从 open 表中选取使目标函数取极值的结点作为当前扩展结点，优先扩展“最有希望”的分支。

四、问题的复杂性

（一）确定性算法

$A$ 是求解问题

$Π$ 的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，并且对于同一输入实例运行算法，所得的结果严格一致，则称算法

$A$ 是确定性(Determinism)算法。

（二）P类问题

判定问题（decision problem）是要求回答“yes”或“no”的问题。

如果对于某个判定问题

$Π$ ，存在一个非负整数

$k$ ，对于输入规模为

$n$ 的实例，能够以

(

)

O(n^k)

$O (n^{k})$ 的时间运行一个确定性算法，得到 yes 或 no 的答案，则该判定问题

$Π$ 是一个

$P$ 类（Polynomial）问题。

通俗地讲，P类问题是具有多项式时间的确定性算法来求解的判定问题。
采用判定问题定义 P 类问题，主要是为了给出 NP 类问题的定义。
事实上，所有易解问题都是P类问题。

（三）非确定性算法和NP类问题

在这里插入图片描述

非确定性算法不是一个实际可行的算法。引入非确定性算法的目的在于给出 NP 类问题的定义，从而将验证过程为多项式时间的问题归为一类进行研究。

1.NP类问题的定义

如果对于某个判定问题 $O(n^k) O(nk) 的时间运行一个非确定性算法，得到 yes 或 no 的答案，则该判定问题 Π Π Π 是一个NP类（Nondeterministic Polynomial）问题。$
通俗地讲，NP类问题是指能采用某种非确定性算法在多项式时间内验证的判定问题。
对于 NP 类判定问题，关键是该问题存在一个确定性算法，并且能够以多项式时间检查和验证在猜测阶段所产生的答案。

NP类问题不一定是难解问题；难解问题也不一定是NP类问题

2.P类问题和NP类问题的区别

- P类问题存在一个多项式时间的确定性算法来判定或求解，显然，也可以构造一个多项式时间的非确定性算法进行判定，因些 P类问题属于NP类问题，即。

3.常见辨析

#mermaid-svg-4qtXQHaI54smLgCx{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-4qtXQHaI54smLgCx .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-4qtXQHaI54smLgCx .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-4qtXQHaI54smLgCx .error-icon{fill:#552222;}#mermaid-svg-4qtXQHaI54smLgCx .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-4qtXQHaI54smLgCx .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-4qtXQHaI54smLgCx .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-4qtXQHaI54smLgCx .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-4qtXQHaI54smLgCx .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-4qtXQHaI54smLgCx .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-4qtXQHaI54smLgCx .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-4qtXQHaI54smLgCx .marker{fill:#333333;stroke:#333333;}#mermaid-svg-4qtXQHaI54smLgCx .marker.cross{stroke:#333333;}#mermaid-svg-4qtXQHaI54smLgCx svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-4qtXQHaI54smLgCx p{margin:0;}#mermaid-svg-4qtXQHaI54smLgCx .edge{stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .section–1 rect,#mermaid-svg-4qtXQHaI54smLgCx .section–1 path,#mermaid-svg-4qtXQHaI54smLgCx .section–1 circle,#mermaid-svg-4qtXQHaI54smLgCx .section–1 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section–1 path{fill:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section–1 text{fill:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon–1{font-size:40px;color:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge–1{stroke:hsl(240, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth–1{stroke-width:17;}#mermaid-svg-4qtXQHaI54smLgCx .section–1 line{stroke:hsl(60, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-0 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-0 path,#mermaid-svg-4qtXQHaI54smLgCx .section-0 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-0 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-0 path{fill:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-4qtXQHaI54smLgCx .section-0 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-0{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-0{stroke:hsl(60, 100%, 73.5294117647%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-0{stroke-width:14;}#mermaid-svg-4qtXQHaI54smLgCx .section-0 line{stroke:hsl(240, 100%, 83.5294117647%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-1 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-1 path,#mermaid-svg-4qtXQHaI54smLgCx .section-1 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-1 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-1 path{fill:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-1 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-1{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-1{stroke:hsl(80, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-1{stroke-width:11;}#mermaid-svg-4qtXQHaI54smLgCx .section-1 line{stroke:hsl(260, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-2 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-2 path,#mermaid-svg-4qtXQHaI54smLgCx .section-2 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-2 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-2 path{fill:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-2 text{fill:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-2{font-size:40px;color:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-2{stroke:hsl(270, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-2{stroke-width:8;}#mermaid-svg-4qtXQHaI54smLgCx .section-2 line{stroke:hsl(90, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-3 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-3 path,#mermaid-svg-4qtXQHaI54smLgCx .section-3 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-3 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-3 path{fill:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-3 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-3{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-3{stroke:hsl(300, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-3{stroke-width:5;}#mermaid-svg-4qtXQHaI54smLgCx .section-3 line{stroke:hsl(120, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-4 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-4 path,#mermaid-svg-4qtXQHaI54smLgCx .section-4 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-4 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-4 path{fill:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-4 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-4{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-4{stroke:hsl(330, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-4{stroke-width:2;}#mermaid-svg-4qtXQHaI54smLgCx .section-4 line{stroke:hsl(150, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-5 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-5 path,#mermaid-svg-4qtXQHaI54smLgCx .section-5 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-5 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-5 path{fill:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-5 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-5{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-5{stroke:hsl(0, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-5{stroke-width:-1;}#mermaid-svg-4qtXQHaI54smLgCx .section-5 line{stroke:hsl(180, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-6 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-6 path,#mermaid-svg-4qtXQHaI54smLgCx .section-6 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-6 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-6 path{fill:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-6 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-6{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-6{stroke:hsl(30, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-6{stroke-width:-4;}#mermaid-svg-4qtXQHaI54smLgCx .section-6 line{stroke:hsl(210, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-7 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-7 path,#mermaid-svg-4qtXQHaI54smLgCx .section-7 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-7 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-7 path{fill:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-7 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-7{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-7{stroke:hsl(90, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-7{stroke-width:-7;}#mermaid-svg-4qtXQHaI54smLgCx .section-7 line{stroke:hsl(270, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-8 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-8 path,#mermaid-svg-4qtXQHaI54smLgCx .section-8 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-8 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-8 path{fill:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-8 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-8{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-8{stroke:hsl(150, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-8{stroke-width:-10;}#mermaid-svg-4qtXQHaI54smLgCx .section-8 line{stroke:hsl(330, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-9 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-9 path,#mermaid-svg-4qtXQHaI54smLgCx .section-9 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-9 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-9 path{fill:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-9 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-9{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-9{stroke:hsl(180, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-9{stroke-width:-13;}#mermaid-svg-4qtXQHaI54smLgCx .section-9 line{stroke:hsl(0, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-10 rect,#mermaid-svg-4qtXQHaI54smLgCx .section-10 path,#mermaid-svg-4qtXQHaI54smLgCx .section-10 circle,#mermaid-svg-4qtXQHaI54smLgCx .section-10 polygon,#mermaid-svg-4qtXQHaI54smLgCx .section-10 path{fill:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-10 text{fill:black;}#mermaid-svg-4qtXQHaI54smLgCx .node-icon-10{font-size:40px;color:black;}#mermaid-svg-4qtXQHaI54smLgCx .section-edge-10{stroke:hsl(210, 100%, 76.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .edge-depth-10{stroke-width:-16;}#mermaid-svg-4qtXQHaI54smLgCx .section-10 line{stroke:hsl(30, 100%, 86.2745098039%);stroke-width:3;}#mermaid-svg-4qtXQHaI54smLgCx .disabled,#mermaid-svg-4qtXQHaI54smLgCx .disabled circle,#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:lightgray;}#mermaid-svg-4qtXQHaI54smLgCx .disabled text{fill:#efefef;}#mermaid-svg-4qtXQHaI54smLgCx .section-root rect,#mermaid-svg-4qtXQHaI54smLgCx .section-root path,#mermaid-svg-4qtXQHaI54smLgCx .section-root circle,#mermaid-svg-4qtXQHaI54smLgCx .section-root polygon{fill:hsl(240, 100%, 46.2745098039%);}#mermaid-svg-4qtXQHaI54smLgCx .section-root text{fill:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .section-root span{color:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .section-2 span{color:#ffffff;}#mermaid-svg-4qtXQHaI54smLgCx .icon-container{height:100%;display:flex;justify-content:center;align-items:center;}#mermaid-svg-4qtXQHaI54smLgCx .edge{fill:none;}#mermaid-svg-4qtXQHaI54smLgCx .mindmap-node-label{dy:1em;alignment-baseline:middle;text-anchor:middle;dominant-baseline:middle;text-align:center;}#mermaid-svg-4qtXQHaI54smLgCx :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

计算问题

可计算问题

易解问题

核心特性

可转换成判定问题

所属类别

P类问题

NP类问题

（补充说明）

P ⊆ NP，即 P 类属于 NP 类

难解问题

核心特性

转换成判定问题

⚠️ 重要推论（双向均不成立）

难解问题不一定是 NP类问题

NP类问题也不一定是难解问题

典型反例：P类问题属于NP，但它是易解的

不可计算问题

定义

不存在任何算法可以解决

经典代表

停机问题（Halting Problem）

（四）NP完全问题（最难解的NP问题）

1.基本定义

2.性质

NP 完全问题是 NP 类问题中最有代表性的一类问题，NP 完全问题有一个重要性质：如果一个NPC问题能在多项式时间内得到解决，那么NP类中每个问题都可以在多项式时间内得到求解，即P=NP成立。
多年的研究表明，目前还没有一个NPC问题有多项式时间算法。这些问题也许存在多项式时间算法，但还有待发现；这些问题也许根本就不存在多项式时间算法，但目前缺乏足够的技术来证明这一点。

（五）NP难问题

1.定义

2.NP 完全问题和 NP 难问题的联系与区别

NP 完全问题必定是 NP 类问题，NP 难问题不一定是NP 类问题。 NPH 问题比 NPC 问题更广。
一般而言，若判定问题属于 NP 完全问题，则相应的最优化问题属于 NP 难问题。

在这里插入图片描述

（六）P类问题、NP类问题、NP完全问题的关系

1.图解

在这里插入图片描述

2.具体示例

（1） P 类问题（多项式时间可解）

定义：存在确定性图灵机在多项式时间

(

)

O(n^k)

$O (n^{k})$ 内求解的问题。通俗说，既能快速找到解，也能快速验证解。

问题类别经典实例核心说明

排序与查找	快速排序、归并排序、二分查找	时间复杂度 $\\log n) O(nlogn)，工业级基础算法$
图论基础	单源最短路径（Dijkstra）、最小生成树（Prim/Kruskal）	网络路由、电路设计中的核心子程序
数论与代数	整数加减乘除、矩阵乘法、素数判定（AKS算法）	AKS 算法证明了素数判定属于 P 类
字符串匹配	KMP 算法、Boyer-Moore 算法	文本编辑器中的查找替换功能

（2）NP 类问题（多项式时间可验证）

定义：非确定性图灵机在多项式时间内可解，或者给定一个“解”（证书），我们能在多项式时间内验证其正确性。核心是“验证快”，但“求解难”。

经典实例问题描述验证方式（为什么属于 NP）

整数分解	给定大整数	给出两个因子 $\\times q = N p×q=N$
子集和问题（判定版）	给定集合 $\\{a_1, a_2, …, a_n\\} {a1,a2,…,an}，是否存在子集和为 T T T$	给出子集索引，将对应元素相加即可验证是否等于
图同构问题	判断两个图是否结构完全相同	给出一个顶点映射关系，检查所有边是否一一对应
3-SAT（布尔可满足性）	给定一个合取范式（3-CNF），判断是否存在一组真值赋值使结果为真	给出一组布尔赋值（True/False），代入表达式即可验证结果

（3）NPC 问题（NP 完全问题）

定义：同时满足两个条件——① 本身属于 NP 类；② 所有 NP 问题都能在多项式时间内归约到它。它是 NP 类中最难的一批“硬骨头”。

💡 历史里程碑：SAT 问题（布尔可满足性问题）是第一个被证明的 NPC 问题（库克-莱文定理，1971年）。

经典实例（均为判定版本）问题描述（核心特征）

SAT / 3-SAT	判断是否存在一组布尔变量赋值使逻辑表达式为真。3-SAT 是 NPC 的“万恶之源”。
顶点覆盖问题	给定图
哈密顿回路问题	给定图
旅行商问题（TSP 判定版）	给定城市集合和距离，是否存在一条总长度 ≤ B 的路线经过所有城市？
团问题（Clique）	给定图
集合覆盖问题（判定版）	给定全集

（4）NPH 问题（NP 难问题）

定义：所有 NP 问题都能归约到它，但它本身不一定是 NP 问题（甚至可能无法在多项式时间内验证解）。比 NP 更难，范围更广。

经典实例与 NPC 的本质区别（难点所在）

旅行商问题（TSP 优化版）	求最短路径的具体值。你要证明一个路线是“最短”的，验证难度远超判定版（仅验证 ≤ B）。
0-1 背包问题（优化版）	求能装下的最大价值。验证最优性通常需要穷举所有可能。
图着色问题（优化版）	求最少需要多少种颜色来给图上色。
⚠️ 停机问题（Halting Problem）	判断任意程序是否会停止运行。这是经典的不可判定（Undecidable）问题，属于 NPH 但完全不属于 NP。

判定版 vs 优化版的关键区别：
- 判定版（问“是否存在≤B的路线？”）→ 属于 NPC
- 优化版（问“最短路线是多少？”）→ 属于 NPH
因为优化问题的解（最短路径长度）很难在多项式时间内验证其是否真正最优

五、近似算法

（一）基本思想

近似算法是求解 NP 类问题的一种有效策略，其基本思想是放弃求最优解，用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低。核心：用精度换时间
换言之，近似算法找到的可能不是一个最优解，但一定会为待求解的问题提供一个解。

（二）近似比和相对误差

1.近似比的定义

近似比

η

η

$η$ ：若一个最优化问题的最优值为

c

∗

c*

$c *$ ，求解该问题的一个近似算法求得的近似最优值为

c

c

$c$ ，则该近似算法的近似比可定义为：

η

=

max

⁡

{

c

c

∗

,

c

∗

c

}

\\eta = \\max \\left\\{ \\frac{c}{c^*}, \\frac{c^*}{c} \\right\\}

$η = max {\frac{c}{c ^{*}}, \frac{c ^{*}}{c}}$
对最小化问题，有

c

≥

c

∗

c ≥ c*

$c \geq c *$ ；对最大化问题，有

c

≤

c

∗

c ≤ c*

$c \leq c *$ ，因而近似算法的近似比总大于或等于1。
近似算法的近似比越小，则算法的性能越好；
近似算法的近似比越大，则算法的性能越差。

2.相对误差

相对误差 λ 若一个最优化问题的最优值为 c*，求解该问题的一个近似算法求得的近似最优值为 c，则该近似算法的相对误差 λ 可定义为：

∣

−

∗

∣

\\lambda = \\left| \\frac{c – c^*}{c^*} \\right|

$λ =$

c∗c−c∗

六、概率算法

（一）设计思想

1.基本特征

概率算法在运行过程中，包括一处或若干处随机选择，根据随机值来决定算法的运行，因此，对于相同的输入实例，概率算法的执行时间可能不同。
概率算法的结果不能保证一定是正确的，但可以限定其出错概率。
概率算法在不同的运行中，对于相同的输入实例可能会得到不同的结果。

2.时间性能

对于确定性算法，通常分析在平均情况下的时间复杂性，即算法在每个可能的输入实例上花费的平均时间。
对于概率算法，通常分析在平均情况下的期望时间复杂性，即在相同输入实例上反复执行概率算法的平均运行时间。

（二）舍伍德型概率算法

1.算法设计思想

分析确定性算法在平均情况下的时间复杂性时，通常假定算法的输入实例满足某一特定的概率分布。事实上，很多算法对于不同的输入实例，其运行时间差别很大。因而可采用舍伍德型概率算法来消除算法的时间复杂性与输入实例间的这种联系，通常有两种方式：
(1) 在确定性算法的某些步骤引入随机因素，将确定性算法改造成舍伍德型概率算法。
(2) 借助于随机预处理技术，不改变原有的确定性算法，仅对其输入实例随机排列（称为洗牌），然后再执行确定性算法。

2.算法说明

舍伍德型（ sherwood ）概率算法设法消除了算法的不同输入实例对算法时间性能的影响，对于任何输入实例，舍伍德型概率算法能够以较高的概率与原有的确定性算法在平均情况下的时间复杂度相同。

（三）拉斯维加斯型概率算法

拉斯维加斯型（Las Vegas）概率算法对同一个输入实例反复多次运行算法，直至运行成功，获得问题的解。如果运行失败，在相同的输入实例上再次运行算法。

1.基本特征

拉斯维加斯型概率算法的随机性选择**有可能导致算法找不到问题的解，**即算法运行一次，或者得到一个正确的解，或者无解。
只要出现失败的概率不占多数，当算法运行失败时，在相同的输入实例上再次运行概率算法，就又有成功的可能。

在这里插入图片描述

（四）蒙特卡罗型算法

1.基本特征

蒙特卡罗型概率算法用于求问题的准确解。
蒙特卡罗型概率算法偶尔会出错，但无论任何输入实例，总能以很高的概率找到一个正确解。
蒙特卡罗型概率算法总是给出解，但是，这个解偶尔可能是不正确的，一般情况下，也无法有效地判定得到的解是否正确。
蒙特卡罗型概率算法求得正确解的概率依赖于算法的运行次数，算法运行的次数越多，得到正确解的概率就越高。

2.一致p正确的蒙特卡罗型概率算法

如果蒙特卡罗型概率算法对于问题的任一输入实例得到正确解的概率不小于 p（
如果对于同一输入实例，蒙特卡罗型概率算法不会给出两个不同的正确解，则称该算法是一致的。如果重复运行一个一致的 p 正确的蒙特卡罗型概率算法，每次运行都独立地进行随机选择，就可以使产生不正确解的概率变得任意小。

（五）三种概率算法的比较

舍伍德（Sherwood）：“一定对，一定停，只改性能不改命”（不改变正确性，只消除最坏情况依赖）。
拉斯维加斯（Las Vegas）：“一定对，未必停，赌的是时间”（答案永真，但可能算到天荒地老，需要重试）。
蒙特卡洛（Monte Carlo）：“一定停，未必对，赌的是答案”（掐点交卷，但答案可能错，需要多交几次卷来降低错误率）。

高频陷阱题：问“哪种概率算法可能返回错误结果”？——选蒙特卡洛。问“哪种算法运行时可能永远不结束”？——选拉斯维加斯。

考试核心维度舍伍德 (Sherwood)拉斯维加斯 (Las Vegas)蒙特卡洛 (Monte Carlo)

1. 解的正确性	必定正确 (100%)	必定正确 (100%)	未必正确 (存在单侧/双侧误差)
2. 解的确定性	总能得到确定解	可能无解/失败 (需重启动)	总能给出一个解（哪怕是错的）
3. 运行时间	有穷且确定 (复杂度固定)	期望时间有限，但最坏无限	多项式时间绝对有界 (硬时限)
4. 核心本质	去随机化（用随机消除输入实例的差异性）	赌运气（赌随机选择能快速命中正确路径）	赌概率（赌抽样足够代表总体）
5. 错误可控性	无错误	无错误（失败可重试直到成功）	错误概率可通过多次重复指数级降低（如：重复k次，错误率降为εᵏ）
6. 典型必考例题	随机化快速排序（随机选主元）随机洗牌算法	随机化N皇后问题因数分解（Pollard Rho）	Miller-Rabin素数测试计算π值（投点法）主元素判定

“综上所述，舍伍德侧重于平衡输入差异，拉斯维加斯侧重于保证解的质量，而蒙特卡洛侧重于保证时间的边界。在实际应用中，若无法承受错误则首选拉斯维加斯；若要求实时响应则优先选择蒙特卡洛并配合多次抽样。”

总结

本文围绕算法求解复杂问题的不同策略，可归纳为以下几个核心要点：

搜索策略的分野：回溯法依靠“深度优先 + 递归回溯”，适合寻找所有可行解或单个最优解，其剪枝依赖约束函数和限界函数；分支限界法采用“广度优先 + 优先队列”，利用限界函数估算目标函数极值，适用于最优化问题，两者在最坏情况下均呈指数阶复杂度，但实际效率取决于剪枝效果。
复杂性理论的层级结构：P 类问题存在多项式时间的确定性算法；NP 类问题可在多项式时间内验证解；NPC 问题是 NP 类中最难的一类，若任一 NPC 问题有多项式算法则 P=NP；NPH 问题不要求属于 NP，但所有 NP 问题均可归约至它，其范围比 NPC 更广。理解这些分类是判断问题“难易”的理论基础。
近似算法与概率算法的实用价值：近似算法以牺牲最优性换取多项式时间，通过近似比和相对误差度量性能；概率算法则引入随机性，分为三类——舍伍德型（保证正确性，平滑输入差异）、拉斯维加斯型（保证正确性但可能失败重试）、蒙特卡洛型（保证时间边界但可能出错，可重复运行降低错误率）。三者分别应对“输入敏感”、“求解时间不确定”和“实时性要求”三种场景。
整体而言，本文展现了算法设计中“效率”与“精确性”之间的权衡艺术：回溯与分支限界面向中小规模精确求解，复杂类理论划定了计算能力的理论边界，而近似与概率方法则为大规模难解问题提供了现实可行的落地方案。掌握这些策略，不仅有助于理解算法内在机理，更能指导实际问题中方法的选择与改进方向。

文章目录

一、回溯法

（一）问题的解空间树

1.问题的解空间

2.可能解的表示方式

3.解空间的表示方式

（二）设计思想

（三）时间性能分析

1.子集树

2.排列树

二、限界剪枝法

（一）广度优先搜索的设计思想

（二）限界剪枝法的设计思想

（三）应用步骤

（四）目标函数的界[down, up]的确定

（五）从限界剪枝法看0/1背包问题

（六）从限界剪枝法看TSP问题

三、回溯法和限界剪枝法的比较

（一）相同之处

（二）不同之处

四、问题的复杂性

（一） 确定性算法

（二）P类问题

（三）非确定性算法和NP类问题

1.NP类问题的定义

2.P类问题和NP类问题的区别

3.常见辨析

（四）NP完全问题（最难解的NP问题）

1.基本定义

2.性质

（五）NP难问题

1.定义

2.NP 完全问题和 NP 难问题的联系与区别

（六）P类问题、NP类问题、NP完全问题的关系

1.图解

2.具体示例

（1） P 类问题（多项式时间可解）

（2）NP 类问题（多项式时间可验证）

（3）NPC 问题（NP 完全问题）

（4）NPH 问题（NP 难问题）

五、近似算法

（一）基本思想

（二）近似比和相对误差

1.近似比的定义

2.相对误差

六、概率算法

（一）设计思想

1.基本特征

2.时间性能

（二）舍伍德型概率算法

1.算法设计思想

2.算法说明

（三）拉斯维加斯型概率算法

1.基本特征

（四）蒙特卡罗型算法

1.基本特征

2.一致p正确的蒙特卡罗型概率算法

（五）三种概率算法的比较

总结

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

（一）确定性算法

评论抢沙发