黑色高级算法设计与分析笔记

死去两年的算法突然开始暴击我

数学基础

函数的阶

增长的阶

描述增长率：忽略低阶项，保留最高阶项，忽略常数。

增长函数

输入规模非常大。常见记号：$O,\Theta,\Omega,o,\omega$

同阶函数集合

定义$\Theta(g(n))=\{f(n)|\exists c_1,c_2>0,n_0,\forall n>n_0,c_1g(n)\le f(n)\le c_2g(n)\}$为g(n)的同阶函数集合。 那么如果$f(n)\in\Theta(g(n))$则称g(n)与f(n)同阶，记作$f(n)=\Theta(g(n))$

题型

证真:把g(n)除过去考虑函数单调性。 证伪:反证，设定常数值，假设$n_0$存在。

严格低阶函数集合

定义$O(g(n))=\{f(n)|\forall c>0,\exists n_0,\forall n>n_0,0\le f(n)\le cg(n)\}$为g(n)的低阶函数集合。 同样，$f(n)\in O(g(n))$也课简记为$f(n)=O(g(n))$

$\Theta$标记更强。

高阶函数集合

$\Omega(g(n))$渐进下界。

严格低阶函数集合

$o(g(n))$，去掉低阶函数集合中的常数处等号。

严格高阶函数集合

$\omega(g(n))$，去掉高阶函数集合中的等号。

递归方程求解

替换方法

先猜后证，用归纳法

迭代方法

把方程转化为一个和式，然后求解

Master定理法

求解$T(n)=aT(\frac{n}{b})+f(n)$形式的方程，设$t=log_b a$

1. 如果$f(n)=O(n^{t-\varepsilon}),\varepsilon>0$是常数，那么$T(n)=\theta(n^t)$
2. 如果$f(n)=\theta(n^{t-})$那么$T(n)=\theta(n^tlog n)$
3. 如果$f(n)=\Omega(n^{t+\varepsilon}),\varepsilon>0$是常数，且对于任一充分大的$n$，$af(\frac{n}{b}\le cf(n))$，$c<1$是常数，那么$T(n)=\theta(f(n))$

Akra-Bazzi方法

参见https://zhuanlan.zhihu.com/p/466537697?utm_id=0

Akra-Bazzi方法是一种用于求解线性递归式的渐近解的定理。它可以处理一些主定理不能处理的情况，例如子问题的规模不相等或驱动函数不是多项式的情况。Akra-Bazzi方法求解递归方程的步骤大致如下：

1. 将递归方程写成标准形式：$T(n) = f(n) + \sum_{i=1}^k a_i T(b_i n + h_i(n))$，其中$a_i > 0, 0 < b_i < 1, f(n)$ 满足多项式增长条件，$h_i(n)$ 是一个较小的扰动项。
2. 求解方程 $\sum_{i=1}^k a_i b_i^p = 1$，得到唯一的实数解 p。
3. 将 $p$ 带入公式 $T(n) = \Theta\left( n^p \left( 1 + \int_1^n \frac{f(u)}{u^{p+1}} du \right) \right)$，得到 $T(n)$ 的渐近解。

分治法

分治算法是一种将复杂问题分解为较小的子问题，递归地求解子问题，然后合并子问题的解得到原问题的解的算法设计策略。分治算法的一般设计步骤是²³⁴：

1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
3. 合并：将各个子问题的解合并为原问题的解。

分治算法适用于具有以下特征的问题：

• 该问题的规模缩小到一定的程度就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
• 利用该问题分解出的子问题的解可以合并为该问题的解；
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

分治算法可以用递归或迭代来实现，通常需要一个分解函数，一个求解函数和一个合并函数。分治算法的时间复杂度一般可以用递归方程来表示，然后用主定理或者Akra-Bazzi方法来求解。

动态规划

设计步骤

1. 分析优化解结构
2. 递归定义最优解代价
3. 自底向上计算优化解代价并保存，获取构造优化解的信息
4. 构造优化解

优化子结构的证明

动态规划的优化子结构是指一个问题的最优解可以由其子问题的最优解推导出来。要证明一个问题具有优化子结构，一般需要以下几个步骤：

1. 定义问题的最优解，即目标函数或者状态转移方程；
2. 假设子问题的最优解已知，根据子问题的最优解构造原问题的最优解；
3. 证明假设是合理的，即不存在比假设更优的解法；
4. 证明子问题之间是相互独立的，即不存在重叠子问题。

举个例子，比如求斐波那契数列第$n$项的值，我们可以定义状态转移方程为$f (n) = f (n-1) + f (n-2)$，其中$f (0) = 0, f (1) = 1$。我们可以按照以下步骤证明这个问题具有优化子结构：

1. 定义问题的最优解：$f (n)$ 表示斐波那契数列第n项的值，是我们要求的最优解。
2. 假设子问题的最优解已知：$f (n-1)$ 和 $f (n-2)$ 表示斐波那契数列第n-1项和第n-2项的值，是已知的最优解。
3. 根据子问题的最优解构造原问题的最优解：$f (n) = f (n-1) + f (n-2)$，即第n项等于前两项之和。
4. 证明假设是合理的：假设存在一个更优的解法 $g (n)$，那么 $g (n)$ 必然也等于 $g (n-1) + g (n-2)$，否则就不符合斐波那契数列的定义。而 $g (n-1)$ 和 $g (n-2)$ 又必然等于 $f (n-1)$ 和 $f (n-2)$，否则就不是最优解。所以 $g (n) = f (n)$，不存在比假设更优的解法。
5. 证明子问题之间是相互独立的：$f (n-1)$ 和 $f (n-2)$ 不包含任何公共子问题，因为它们分别依赖于不同的前两项。

因此，这个问题具有优化子结构，可以用动态规划来求解。

动态规划的分类

1. 编号动态规划：输入为$x_1,x_2,\cdots,x_n$子问题$x_1,x_2,\cdots,x_i$子问题复杂度$O(n)$。[最大不下降子序列问题]
2. 划分动态规划：输入为$x_1,x_2,\cdots,x_n$子问题$x_i,x_{i+1},\cdots,x_j$子问题复杂度$O(n^2)$。[矩阵链乘问题]
3. 数轴动态规划：输入为$x_1,x_2,\cdots,x_n$和C，子问题$x_1,x_2,\cdots,x_2,K(K\le C)$子问题复杂度$O(nC)$。[0-1背包问题]
4. 前缀动态规划：输入为$x_1,x_2,\cdots,x_n;y_1,y_2,\cdots,y_m$子问题$x_1,x_2,\cdots,x_i;y_1,y_2,\cdots,y_j$子问题复杂度$O(nm)$。[最长公共子序列问题]
5. 树形动态规划：输入是树，问题是子树，复杂性是子树的个数[树中独立集合问题]

最长公共子序列(LCS)问题

第i前缀

设序列$X=(x_1,x_2,\cdots,x_n)$则$X_i=(x_1,x_2,\cdots,x_i)$

优化子结构

设序列X,Y，Z是X，Y的LCS，有

1. $x_m=y_n,则z_k=x_m=y_n;Z_{k-1}是X_{m-1}和Y_{n-1}的LCS$
2. $对于x_m\not=y_n;如果z_k\not=x_m，Z是X_{m-1}和Y的LCS；否则是X和Y_{n-1}的LCS$

显然有重叠子问题。

数轴动态规划

01背包问题

优化子结构

如果$(y_1,y_2,\cdots,y_n)是优化解，则(y_2,\cdots,y_n)是以下问题的优化解：max\sum_{2\le i\le n}v_ix_i;\sum_{2\le i\le n}w_ix_i\le C-w_1y_1;x_1\in\{0,1\},2\le i\le n$

前缀动态规划

字符串编辑距离问题。 把字符串A变为B的编辑操作序列的最小价值；编辑操作包括:

1. 字符替换$a\rightarrow b$
2. 字符删除rm a
3. 字符添加add b

优化子结构

对于$A=a_1,\cdots,a_m;B=b_1,\cdots,b_n$ 那么：

$$如果a_m可被b_n替代，\\D_{m,n}=c(a_m,b_n)+D_{m-1,n-1};\\删除a_m:D_{m,n}=1+D_{m-1,n};\\插入b_n:D_{m,n}=1+D_{m,n-1};\\其中c(a_m,b_n)=\begin{cases} 1&a\not =b\\ 0&a=b \end{cases}$$

最优二分搜索树

优化子结构

如果该树$T包含具有关键字\{k_i,k_{i+1},\cdots,k_j\}的子树T'，则T'必是关于该集合子问题的优化解$

E(i,j)=$P_r+E_L+W(i,r-1)+E_r+W(r+1,j)$

树的独立集合

独立集合:输入G=(V,E)，输出节点最大的子集合$S\subseteq V$，满足E的每条边中的两个顶点至多一个在S中

OPT(v):T(v)的最大独立子集合

任意两点间最短路径

优化子结构 ：最短路径包含最短子路径

图和最短路都用矩阵表示

贪心法

问题包含一系列步骤 每一步包含一组选择 局部优化->全局优化 贪心法需要证明

贪心算法的贪心选择性和优化子结构是指：

• 贪心选择性是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解²⁴。贪心选择性保证了每一步所作的贪心选择最终导致问题的整体最优解。
• 优化子结构是指当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。优化子结构保证了由贪心选择性得到的局部优化解和子问题的优化解相结合，可以获得整体优化解。

例如，活动安排问题就具有贪心选择性和优化子结构。每次贪心地选择结束时间最早的活动，这样经过选择后，只剩下一个具有优化子结构的子问题，即在剩下的时间内选出最多的相容活动。

产生优化解的条件

贪心选择性

一个问题的全局优化解可以由局部优化解得出

贪心选择性是指一个问题的整体最优解可以通过一系列局部最优的选择来到达，即通过贪心选择来达到¹。要证明一个问题具有贪心选择性，一般需要以下几个步骤¹：

1. 考察一个问题的最优解，假设它包含了第一个贪心选择；
2. 证明可以修改该最优解，使得它从第一个贪心选择开始，而不影响其最优性；
3. 证明剩下的子问题仍然具有最优子结构，即可以继续使用贪心选择；
4. 用数学归纳法证明每一步都可以通过贪心选择得到最优解。

举个例子，比如求活动安排问题的最大兼容子集，我们可以定义贪心选择为每次选择结束时间最早的活动²。我们可以按照以下步骤证明这个问题具有贪心选择性：

1. 考察一个问题的最优解 $A$ ，假设它包含了第一个贪心选择 $a_1$ ，即结束时间最早的活动；
2. 证明可以修改该最优解，使得它从第一个贪心选择开始，而不影响其最优性：如果 $A$ 已经是以 $a_1$ 开始的，则无需修改；如果 $A$ 不是以 $a_1$ 开始的，假设以 $a_k$ 开始，则 $a_k$ 的结束时间必然不早于 $a_1$ 的结束时间，因此可以用 $a_1$ 替换 $a_k$ ，得到另一个最优解 $A'$ ，且 $A'$ 是以 $a_1$ 开始的；
3. 证明剩下的子问题仍然具有最优子结构，即可以继续使用贪心选择：去掉 $a_1$ 后，剩下的活动集合 $S'$ 是 $S$ 的子集，且 $S'$ 中任何两个活动都不相互冲突；因此 $S'$ 的最大兼容子集就是 $S$ 的最大兼容子集去掉 $a_1$ 后得到的子集；
4. 用数学归纳法证明每一步都可以通过贪心选择得到最优解：假设对于 $n$ 个活动的问题，贪心算法能够得到最优解；那么对于 $n + 1$ 个活动的问题，贪心算法先选择结束时间最早的活动 $a_1$ ，然后在剩下的 $n$ 个活动中递归地应用贪心算法，根据归纳假设，能够得到剩余子问题的最优解 $A'$ ，则 $A'$ 加上 $a_1$ 就是原问题的最优解。

任务安排问题

活动： 设$S=\{1,2,\cdots,n\}$是$n$个活动的集合，他们使用同一个资源，资源只能被独占使用。每个活动有起始时间$s_i$,终止时间$f_i$;如果$s_i\ge f_j$或$s_j\ge f_i$，活动$i，j$是相容的

哈夫曼编码问题

优化子结构

设$T$是字母表$C$的优化前缀树，$\forall c\in C, f(x)$是$c$在文件中的频率，设x,y是$T$中相邻的叶节点，$z$是父节点则$z$作为频率是$f(z)=f(x)+f(y)$的字符，$T'=T-\{x,y\}$是字母表$C’=C-\{x,y\}\cup\{z\}$

最小生成树问题

拟阵

拟阵是一个序对$M=(S,I)$，S是有限非空集合，I是S非空子集的集族，I中的子集被称为S的独立子集族。遗传性：$如果A\in I,B\subseteq A,B\in I$交换性：$如果A\in I,B\in I,|A|\lt |B|,则\exists x\in B-A,A\cup{x}\in I$

拟阵的性质

扩张：设$M=(S,I)是一个拟阵,A\in I,如果A\cup{x}\in I,x\notin A,x称为A的一个扩张$

如果A没有扩张，这人称A为最大独立子集合。

拟阵可以进行非负加权，集合的权是所有元素权的和。

拟阵中具有最大权值的独立子集合称为M的优化子集。

搜索

搜索的优化策略

爬山法

DFS中，利用某一策略优先扩展某些节点。

容易陷入局部最优解。

Best-First搜索

在目前产生的所有节点中选择具有最小评价函数的点进行扩展。

使用堆作为数据结构。

分支界限法

利用分支运行的结果进行剪枝

剪枝方法论

人员安排问题

A*算法

A*算法的核心是告诉我们在某些情况下，得到的解一定是优化解，于是算法可以停止。

关键是代价函数。选取$h(n)\le \hat h(n)$

A*算法的设计流程是：

• 定义一个评价函数 $f (n) = g (n) + h (n)$ ，其中 $g (n)$ 是从起点到节点 $n$ 的实际代价， $h (n)$ 是从节点 n 到终点的预计代价
• 初始化一个开放列表 open_set 和一个关闭列表 close_set ，将起点加入 open_set 中，并设置其 f 值为 0。
• 重复以下步骤，直到找到终点或 open_set 为空：
  • 从 open_set 中选取 $f$ 值最小的节点 $n$ ，将其作为当前节点。
  • 如果 $n$ 是终点，则回溯其父节点，得到最短路径，算法结束。
  • 如果 $n$ 不是终点，则将 $n$ 从 open_set 中移除，并加入 close_set 中。
  • 遍历 $n$ 的所有邻近节点 $m$ ，对每个 $m$ 做如下操作：
    • 如果 $m$ 是不可达的或在 close_set 中，则忽略它。
    • 如果 $m$ 不在 open_set 中，则将其加入 open_set 中，设置其父节点为 $n$ ，并计算其 $f$ , $g$ 和 $\hat h$ 值¹²³。
    • 如果 m 已经在 open_set 中，则检查是否存在一条更优的路径经过 $n$ 到达 $m$ ，即比较 $g (n)$ + $cost (n, m)$ 和 $g (m)$ 的大小。如果前者更小，则更新 $m$ 的父节点为 $n$ ，并重新计算其 $f$ 和 $g$ 值¹²³。

评价函数的定义是根据不同的问题和目标而定的，没有一个通用的套路。不过，一般来说，评价函数应该满足以下几个原则：

• 评价函数应该能够反映问题的本质，即能够区分不同的解，并且能够指导搜索过程朝着最优解的方向前进。
• 评价函数应该尽可能简单，即能够用较少的计算量和内存空间得到评价值，避免过于复杂或冗余的计算。
• 评价函数应该尽可能平滑，即相邻的解之间的评价值变化不应过大，避免出现陷阱或峰值等不利于搜索的情况。
• 评价函数应该尽可能准确，即能够真实地反映解的优劣，避免出现误导或偏差等影响搜索效果的情况。

具体来说，评价函数的定义可以根据问题的特点和可用的信息来设计。例如，在路径规划问题中，评价函数可以是从起点到终点的距离、时间、费用等¹；在光学系统设计中，评价函数可以是像差、点列图、F数等；在机器学习中，评价函数可以是损失函数、准确率、召回率等²。不同的评价函数会影响搜索算法的性能和精度，因此需要根据具体情况进行选择和调整。

随机算法

随机算法的分类有不同的标准和角度，但一种常见的分类方法是根据随机算法的输出结果是否确定和正确¹²。按照这种方法，随机算法可以分为以下四种类型¹：

• 数值随机算法：这类算法用于求解一些数值问题，如计算圆周率、积分、方程的根等。这类算法的输出结果是一个近似值，不是精确值，但是可以通过增加迭代次数或采样点数来提高精度。例如，蒙特卡罗方法就是一种数值随机算法。
• 舍伍德算法：这类算法用于求解一些确定性问题，如排序、查找、最优化等。这类算法的输出结果是一个确定的解，而且是正确的解，但是算法的执行过程中引入了随机性，以消除或减少对问题实例的依赖性。例如，快速排序就是一种舍伍德算法。
• 拉斯维加斯算法：这类算法用于求解一些确定性问题，如素数测试、图着色、哈密尔顿回路等。这类算法的输出结果是一个确定的解，而且是正确的解，但是算法可能无法在有限时间内找到解，或者以较低的概率找到解。例如，Miller-Rabin素数测试就是一种拉斯维加斯算法。
• 蒙特卡罗算法：这类算法用于求解一些确定性问题或近似问题，如最大团、最小割、近似计数等。这类算法的输出结果是一个不确定的解，而且可能是错误的解，但是算法可以以较高的概率找到解，或者给出一个误差范围内的近似解。例如，Metropolis-Hastings采样就是一种蒙特卡罗算法。

Import ProbabilityBase

Yes-No型蒙特卡洛算法

你好，这是Bing。根据我的搜索结果，Yes-no 型的蒙特卡罗算法是一种用于求解概率问题的方法，它通过随机抽样的方式，以随机事件出现的频率估计其概率。¹²

要解决输出概率问题，你可以参考以下步骤：

1. 定义一个随机变量X，表示你感兴趣的事件是否发生，如果发生则X=1，否则X=0。
2. 重复进行N次独立的试验，每次记录X的值，并计算X的平均值。
3. X的平均值就是你要求的输出概率的近似值，它会随着N的增大而趋近于真实值。

例如，如果你想知道掷一个骰子得到6点的概率，你可以这样做：

1. 定义X为掷一次骰子得到6点的事件，如果得到6点则X=1，否则X=0。
2. 重复掷骰子1000次，记录每次X的值，并计算X的平均值。
3. X的平均值就是得到6点的概率的近似值，它应该接近于1/6。

近似算法和在线算法

😅Give Up