首页algorithms

# 算法概述

# 算法的定义

算法是由若⼲条指令组成的有穷序列

# 算法的性质

输入、输出、确定性、有限性

# 程序与算法的区别

程序是算法用某种程序设计语言的具体实现
程序可以不满足算法的有限性

# 问题求解

图 0

# 算法复杂度

# 复杂性的计量

C=F(N,I,A)  ⟹  T=T(N,I),S=S(N,I)C = F(N,I,A) \implies T = T(N,I), S = S(N,I)

其中，NN 为问题规模，II 为问题的输入，AA 为算法，FF 为复杂性函数，TT 为时间复杂度，SS 为空间复杂度，CC 为复杂性

# 时间复杂度

T=T(N,I)=∑i=1ktiei(N,I)T = T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I)

其中，tit_i 为第 ii 条指令的执行时间（元运算时间），ei(N,I)e_i(N,I) 为第 ii 条指令的执行次数（元运算次数），kk 为算法的指令数（元运算种类）

不可能精确计算出 T(N,I)T(N,I)，只能估计

  • 最坏情况时间复杂度：Tmax⁡(N)=max⁡I∈DNT(N,I)=max⁡I∈DN∑i=1ktiei(N,I)=∑i=1ktiei(N,I∗)=T(N,I∗)T_{\max}(N) = \max\limits_{I \in D_N} T(N,I) = \max\limits_{I \in D_N} \sum\limits_{i=1}^{k} t_i e_i(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I^\ast) = T(N, I^\ast)，其中 I∗I^\ast 为使得 T(N,I)T(N,I) 最大的输入
  • 最好情况时间复杂度：Tmin⁡(N)=min⁡I∈DNT(N,I)=∑i=1ktiei(N,I~)=T(N,I~)T_{\min}(N) = \min\limits_{I \in D_N} T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,\tilde{I}) = T(N, \tilde{I})，其中 I~\tilde{I} 为使得 T(N,I)T(N,I) 最小的输入
  • 平均时间复杂度：Tavg(N)=∑I∈DNP(I)T(N,I)=∑I∈DNP(I)∑i=1ktiei(N,I)T_{\text{avg}}(N) = \sum\limits_{I \in D_N} P(I) T(N,I) = \sum\limits_{I \in D_N} P(I) \sum\limits_{i=1}^{k} t_i e_i(N,I)，其中 P(I)P(I) 为输入 II 出现的概率

可操作性最好且最有实际价值的是最坏情况下的复杂度

# 复杂性的渐进性态

# 渐进性态

设T(N)T(N) 为算法AA 的时间复杂度，则它是NN 的单增函数。如果存在一个函数T~(N)\tilde{T}(N)，使得对于N→∞N \rightarrow \infty，有T(N)−T~(N)T(N)→0\frac{T(N)-\tilde{T}(N)}{T(N)} \rightarrow 0，则称T~(N)\tilde{T}(N) 是T(N)T(N) 当N→∞N \rightarrow \infty 时的渐进性态（渐进复杂性）

# 渐进性态的阶

设f(N)f(N) 和g(N)g(N) 是定义在正整数集合上的正函数

# 大OO 表示法（上限）

如果存在正常数CC 和N0N_0，使得对于一切N>N0N>N_0，有f(N)≤Cg(N)f(N) \leq Cg(N)，则称f(N)f(N) 在N→∞N \rightarrow \infty 时有上界，且g(N)g(N) 是f(N)f(N) 的一个上界，记作f(N)=O(g(N))f(N) = O(g(N))

上界的阶越低，则评估越精确，结果就越有价值。

  1. O(f)+O(g)=O(max⁡(f,g))O(f) + O(g) = O(\max(f,g))
  2. O(f)+O(g)=O(f+g)O(f) + O(g) = O(f+g)
  3. O(f)⋅O(g)=O(f⋅g)O(f) \cdot O(g) = O(f \cdot g)
  4. 如果g(N)=O(f(N))g(N) = O(f(N))，则O(f)+O(g)=O(f)O(f) + O(g) = O(f)
  5. f=O(f)f = O(f)
  6. O(Cf(N))=O(f(N))O(Cf(N)) = O(f(N))

图 1

# 大Ω\Omega 表示法（下限）

如果存在正常数CC 和N0N_0，使得对于一切N>N0N>N_0，有f(N)≥Cg(N)f(N) \geq Cg(N)，则称f(N)f(N) 在N→∞N \rightarrow \infty 时有下界，且g(N)g(N) 是f(N)f(N) 的一个下界，记作f(N)=Ω(g(N))f(N) = \Omega(g(N))

下界的阶越高，则评估越精确，结果就越有价值。

# 大Θ\Theta 表示法

f(N)=Θ(g(N))f(N) = \Theta(g(N))，当且仅当f(N)=O(g(N))f(N) = O(g(N)) 且f(N)=Ω(g(N))f(N) = \Omega(g(N))，称f(N)f(N) 与g(N)g(N) 同阶

# NP 完全性理论

# P 类问题

多项式时间内可解决的问题

# NP 类问题

多项式时间内可验证的问题，NP 问题不要求给出一个算法来求解问题本身，而只要求给出一个确定性算法在多项式时间内验证它的解

# 递归与分治策略

# 递归的概念

  • 递归函数：用函数自身定义的函数，两要素：边界条件与递归方程
  • 递归算法：直接或间接调用自身的算法
  • 双递归函数：一个函数及它的一个变量是由函数自身定义（不能转换成循环）

# 排列问题

设 R={r1,r2,…,rn}R = \{r_1, r_2, \dots, r_n\} 是要进行排列的 nn 个元素，R=R−{r}R = R - \{r\}。集合 XX 中元素的全排列记为 Perm(X)Perm(X)。(r)Perm(X)(r)Perm(X) 表示在全排列 Perm(X)Perm(X) 的每个排列前加上前缀 rr 得到的排列。RR 的全排列可归纳定义如下：

  • 当 n=1n = 1 时，Perm(R)=(r)Perm(R) = (r)，其中 rr 是集合 RR 中唯一的元素；
  • 当 n>1n > 1 时，Perm(R)={r1Perm(R1),r2Perm(R2),…,rnPerm(Rn)}Perm(R) = \{ r_1 Perm(R_1), r_2 Perm(R_2), \dots, r_n Perm(R_n) \}。

依此递归定义，可设计产生 Perm(R)Perm(R) 的递归算法如下：

template <class T>
void Perm(T list[], int k, int m) { // 产生 list [ ] 数组中从 k 到 m 元素的全排列.
  if (k == m) {    // 只剩下一个元素
    for (int i = 0; i <= m; i++)
      cout << list[i];
    cout << endl;
  } else // 还有多个元素，递归产生排列
    for (int i = k; i <= m; i++) {
      swap(list[k], list[i]); // 固定第一个元素
      Perm(list, k + 1, m);
      swap(list[k], list[i]); // ! 还原，不然会有重复排列
    }
}

# 整数划分

将正整数 nn 表示成一系列正整数之和，n=n1+n2+⋯+nkn = n_1 + n_2 + \dots + n_k（n≥n1≥⋯≥nk≥1, k≥1n \geq n_1 \geq \dots \geq n_k \geq 1, \ k \geq 1）。正整数 nn 的这种表示称为正整数 nn 的划分。正整数 nn 的不同的划分个数称为正整数 nn 的划分数，记为 p(n)p(n)。

q(n,m)={1n=1,m=1q(n,n)n<m1+q(n,n−1)n=mq(n,m−1)+q(n−m,m)n>m>1q(n,m) = \begin{cases} 1 & n=1,m=1\\ q(n,n) & n<m\\ 1+q(n,n-1) & n=m\\ q(n,m-1)+q(n-m,m) & n>m>1 \end{cases}

对于数据 n，最大加数 n1 不大于 m 的划分个数记作 q (n, m)。

int q(int n, int m) {
  // 如果 n 或 m 小于 1，没有有效的划分
  if ((n < 1) || (m < 1))
    return 0;
  // 如果 n 或 m 等于 1，只有一种划分方式
  if ((n == 1) || (m == 1))
    return 1;
  // 如果 n 小于 m，将 m 调整为 n，避免重复计算
  if (n < m)
    return q(n, n);
  // 如果 n 等于 m，增加一种包含 m 本身的划分
  if (n == m)
    return q(n, m - 1) + 1;
  // 递归计算不包含 m 的划分数量加上包含 m 的划分数量
  return q(n, m - 1) + q(n - m, m);
  // 示例说明：
  // q(6, 4) = q(6, 3) + q(2, 4)
  //q (n - m, m) 固定了 6 = 4 + x 中的 4，只对 x 进行讨论
}
# 递归的优缺点


    

  • 优点：

      

    • 算法简明；
      • 

    • 正确性易证明，是分析、设计的有力工具。
      • 

    

    • 

  • 缺点：

      

    • 执行效率不高；
      • 

    • 堆栈空间耗费
      • 

    

    • 



# 分治法


# 分治法所能解决的问题特征


    

  • 该问题可以分解为若干个规模较小的相同问题；
    • 

  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；
    • 

  • 该问题的规模缩小到一定的程度就可以容易地解决；
    • 

  • 利用该问题分解出的子问题的解可以合并为该问题的解。
    • 



# 分治法基本思想


将规模为nn 的问题分解为kk 个规模较小的子问题，使这些子问题相互独立且与原问题相同，递归地解这些子问题，然后各个子问题的解合并得到原问题的解。


# 分治法基本步骤


Divide-and-Conquer(P):
  if |P| ≤ n₀:
    return Adhoc(P)
  divide P into P₁, P₂, ..., Pₖ
  for i from 1 to k:
    yᵢ = Divide-and-Conquer(Pᵢ)
  return Merge(y₁, y₂, ..., yₖ)
# 分治法求解过程


    

  1. 分解：把原问题分解为若干个规模较小、相互独立，与原问题相同的子问题；
    2. 

  2. 求解：若子问题规模较小且容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；
    3. 

  3. 合并：将已求解的各个子问题的解，逐步合并为原问题的解。
    4. 



# 分治法的时间复杂性


设T(n)T(n) 为规模为nn 的问题的解所需的时间，则有


T(n)≤{O(1)n=n0kT(nm)+f(n)n>n0T(n) \leq \begin{cases}
O(1) & n = n_0\\
kT(\frac{n}{m}) + f(n) & n > n_0
\end{cases}



其中，kk 为分解出的子问题个数，mm 为分解问题的规模，f(n)f(n) 为合并子问题解的时间


设n=man=m^a，则有a=log⁡mna=\log_m n，则有


ka=klog⁡mn=nlog⁡mkk^a=k^{\log_m n}=n^{\log_m k}



T(n)=nlog⁡mkT(1)+∑i=0log⁡mn−1kif(nmi)T(n) = n^{\log_m k}T(1) + \sum\limits_{i=0}^{\log_m n-1} k^i f(\frac{n}{m^i})



# 二分法


picture 17


template <class T>
int BinarySearch(T a[], const T &x, int n) {
  int left = 0, right = n - 1; // 初始化左右边界
  while (left <= right) { // 当左边界小于等于右边界时继续搜索
    int middle = (left + right) / 2; // 计算中间位置
    if (x == a[middle]) // 如果找到目标值，返回其位置
      return middle;
    if (x > a[middle]) // 如果目标值大于中间值，调整左边界
      left = middle + 1;
    else // 如果目标值小于中间值，调整右边界
      right = middle - 1;
  }
  return -1; // 如果未找到目标值，返回 - 1
}


    

  • 递推式：T(n)={O(1)n=1T(n2)+O(1)n>1T(n)=\begin{cases}O(1) & n=1\\T(\frac{n}{2})+O(1) & n>1\end{cases}
    • 

  • 时间复杂度：O(log⁡n)O(\log n)
    • 





# 找金块


老板有一袋金块（共nn 块，nn 是 2 的幂（n≥2n≥2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块


auto findMaxandMin(vector<int> &gold) {
  // 如果数组只有两个元素，直接返回最大值和最小值
  if (gold.size() == 2) {
    return gold[0] > gold[1] ? make_pair(gold[0], gold[1])
                             : make_pair(gold[1], gold[0]);
  }
  // 将数组分成左右两部分
  vector<int> left(gold.begin(), gold.begin() + gold.size() / 2);
  vector<int> right(gold.begin() + gold.size() / 2, gold.end());
  // 递归求解左右两部分的最大值和最小值
  pair<int, int> leftMaxNMin = findMaxandMin(left);
  pair<int, int> rightMaxNMin = findMaxandMin(right);
  // 返回左右两部分的最大值和最小值
  return make_pair(max(leftMaxNMin.first, rightMaxNMin.first),
                   min(leftMaxNMin.second, rightMaxNMin.second));
}
# 棋盘覆盖


在一个2k×2k2^k \times 2^k 的棋盘中，有一个方格与其他方格不同，要求用 L 型骨牌覆盖其余方格

用分治法解决，将棋盘分为四个2k−1×2k−12^{k-1} \times 2^{k-1} 的子棋盘，分别覆盖，特殊方格必位于其中一个子棋盘中，其余三个子棋盘的特殊方格用 L 型骨牌覆盖


picture 13


picture 14


/**
  * @brief 棋盘覆盖
  * @param tr 棋盘左上角行号
  * @param tc 棋盘左上角列号
  * @param dr 特殊方格行号
  * @param dc 特殊方格列号
  * @param size 棋盘大小
  */
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
  if (size == 1) return; // 基本情况：棋盘大小为 1 时，直接返回
  int t = tile++, s = size / 2; //t 表示当前 L 型骨牌编号，s 表示子棋盘的大小
  // 覆盖左上角子棋盘
  if (dr < tr + s && dc < tc + s)
    ChessBoard(tr, tc, dr, dc, s); // 特殊方格在左上角子棋盘
  else {
    board[tr + s - 1][tc + s - 1] = t; // 用 L 型骨牌覆盖右下角
    ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s); // 递归处理左上角子棋盘
  }
  // 覆盖右上角子棋盘
  if (dr < tr + s && dc >= tc + s)
    ChessBoard(tr, tc + s, dr, dc, s); // 特殊方格在右上角子棋盘
  else {
    board[tr + s - 1][tc + s] = t; // 用 L 型骨牌覆盖左下角
    ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); // 递归处理右上角子棋盘
  }
  // 覆盖左下角子棋盘
  if (dr >= tr + s && dc < tc + s)
    ChessBoard(tr + s, tc, dr, dc, s); // 特殊方格在左下角子棋盘
  else {
    board[tr + s][tc + s - 1] = t; // 用 L 型骨牌覆盖右上角
    ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); // 递归处理左下角子棋盘
  }
  // 覆盖右下角子棋盘
  if (dr >= tr + s && dc >= tc + s)
    ChessBoard(tr + s, tc + s, dr, dc, s); // 特殊方格在右下角子棋盘
  else {
    board[tr + s][tc + s] = t; // 用 L 型骨牌覆盖左上角
    ChessBoard(tr + s, tc + s, tr + s, tc + s, s); // 递归处理右下角子棋盘
  }
}
# 大整数的乘法


将nn 位二进制整数XX 和YY 都分为两段，每段的长为n2\frac{n}{2}。


picture 15


X=A×2n2+BY=C×2n2+DXY=AC×2n+(AD+BC)×2n2+BD\begin{align*}
X &= A \times 2^{\frac{n}{2}} + B \\
Y &= C \times 2^{\frac{n}{2}} + D \\
XY &= AC \times 2^n + (AD + BC) \times 2^{\frac{n}{2}} + BD
\end{align*}



时间复杂度为：


T(n)={O(1)n=14T(n2)+O(n)n>1  ⟹  T(n)=O(n2)T(n) = \begin{cases}
  O(1) & n=1\\
  4T(\frac{n}{2}) + O(n)& n>1
\end{cases}
\implies T(n) = O(n^2)





改进：


XY=AC×2n+((A−B)(D−C)+AC+BD)×2n2+BDXY = AC\times 2^n + ((A-B)(D-C)+AC+BD)\times 2^{\frac{n}{2}} + BD



时间复杂度：


T(n)={O(1)n=13T(n2)+O(n)n>1  ⟹  T(n)=O(nlog⁡3)=O(n1.59)T(n) = \begin{cases}
  O(1) & n=1\\
  3T(\frac{n}{2}) + O(n) & n>1
\end{cases}
\implies T(n) = O(n^{\log 3}) = O(n^{1.59})





auto Karatsuba(const string &X, const string &Y) {
  if (X.size() == 1) {
    return to_string(stoi(X) * stoi(Y));
  }
  string A = X.substr(0, X.size() / 2);
  string B = X.substr(X.size() / 2);
  string C = Y.substr(0, Y.size() / 2);
  string D = Y.substr(Y.size() / 2);
  string AC = Karatsuba(A, C);
  string BD = Karatsuba(B, D);
  string AD_BC = to_string((stoi(A) + stoi(B)) * (stoi(C) + stoi(D)) - stoi(AC) - stoi(BD));
  return to_string(stoi(AC) * pow(10, X.size()) + stoi(AD_BC) * pow(10, X.size() / 2) + stoi(BD));
}
# Strassen 矩阵乘法


将两个n×nn \times n 的矩阵分为四个n2×n2\frac{n}{2} \times \frac{n}{2} 的子矩阵，可将方程C=A×BC = A \times B 分解为


[C11C12C21C22]=[A11A12A21A22]×[B11B12B21B22]\begin{bmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{bmatrix}=
\begin{bmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{bmatrix}
\times
\begin{bmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{bmatrix}



时间复杂度：


T(n)={O(1)n=28T(n2)+O(n2)n>2  ⟹  T(n)=O(n3)T(n) = \begin{cases}
  O(1) & n=2\\
  8T(\frac{n}{2}) + O(n^2) & n>2
\end{cases}
\implies T(n) = O(n^3)





改进：将矩阵分解为七个n2×n2\frac{n}{2} \times \frac{n}{2} 的子矩阵，可将时间复杂度降为O(nlog⁡7)O(n^{\log 7})


M1=A11(B12−B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21−B11)M5=(A11+A22)(B11+B22)M6=(A12−A22)(B21+B22)M7=(A11−A21)(B11+B12)\begin{aligned}
M_1 = A_{11}(B_{12}-B_{22}) \\
M_2 = (A_{11}+A_{12})B_{22} \\
M_3 = (A_{21}+A_{22})B_{11} \\
M_4 = A_{22}(B_{21}-B_{11}) \\
M_5 = (A_{11}+A_{22})(B_{11}+B_{22}) \\
M_6 = (A_{12}-A_{22})(B_{21}+B_{22}) \\
M_7 = (A_{11}-A_{21})(B_{11}+B_{12})
\end{aligned}



可得：


C11=M5+M4−M2+M6C12=M1+M2C21=M3+M4C22=M5+M1−M3−M7\begin{aligned}
C_{11} &= M_5+M_4-M_2+M_6 \\
C_{12} &= M_1+M_2 \\
C_{21} &= M_3+M_4 \\
C_{22} &= M_5+M_1-M_3-M_7
\end{aligned}



时间复杂度：


T(n)={O(1)n=27T(n2)+O(n2)n>2  ⟹  T(n)=O(nlog⁡7)=O(n2.81)T(n) = \begin{cases}
  O(1) & n=2\\
  7T(\frac{n}{2}) + O(n^2) & n>2
\end{cases}
\implies T(n) = O(n^{\log 7}) = O(n^{2.81})





# 合并排序


将一个数组分为两个规模相等的子数组，分别排序，然后将两个有序子数组合并为一个有序数组


void mergeSort(std::vector<int>& arr) {
    if (arr.size() <= 1)
        return;
    size_t mid = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + mid);
    std::vector<int> right(arr.begin() + mid, arr.end());
    mergeSort(left);
    mergeSort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(), arr.begin());
}
// 一种 merge 实现
template <typename T>
void my_merge(const std::vector<T>& left, const std::vector<T>& right, std::vector<T>& result) {
    size_t i = 0, j = 0;
    result.reserve(left.size() + right.size());
    while(i < left.size() && j < right.size()) {
        if(left[i] <= right[j]) {
            result.push_back(left[i++]);
        }
        else {
            result.push_back(right[j++]);
        }
    }
    while(i < left.size()) {
        result.push_back(left[i++]);
    }
    while(j < right.size()) {
        result.push_back(right[j++]);
    }
}
时间复杂度：


T(n)={O(1)n=12T(n2)+O(n)n>1  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n=1\\
  2T(\frac{n}{2}) + O(n) & n>1
\end{cases}
\implies T(n) = O(n\log n)





改进：消除算法中的递归：自然归并排序


template <typename T>
void MergeSort(T a[], int n) {
  T *b = new T[n]; // 动态分配辅助数组
  int s = 1; // 初始子数组大小为 1
  while (s < n) {
    MergePass(a, b, s, n); // 将数组 a 中的子数组合并到 b 中
    s += s; // 子数组大小加倍
    MergePass(b, a, s, n); // 将数组 b 中的子数组合并到 a 中
    s += s; // 子数组大小加倍
  }
  delete[] b; // 释放辅助数组
}
template <typename T>
void MergePass(T a[], T b[], int s, int n) {
  int i = 0;
  while (i <= n - 2 * s) {
    Merge(a, b, i, i + s - 1, i + 2 * s - 1); // 合并相邻的两个子数组
    i = i + 2 * s; // 移动到下一个待合并的子数组
  }
  if (i + s < n) Merge(a, b, i, i + s - 1, n - 1); // 合并最后两个子数组
  else
    for (int j = i; j < n; j++) b[j] = a[j]; // 将剩余的元素复制到 b 中
}
template <typename T>
void Merge(T a[], T b[], int l, int m, int n) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= n) {
    if (a[i] <= a[j])
      b[k++] = a[i++]; // 将较小的元素复制到 b 中
    else
      b[k++] = a[j++]; // 将较小的元素复制到 b 中
  }
  while (i <= m) b[k++] = a[i++]; // 将剩余的左半部分元素复制到 b 中
  while (j <= n) b[k++] = a[j++]; // 将剩余的右半部分元素复制到 b 中
}


# 快速排序


选取一个基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，然后递归地对左右两部分进行排序


template <typename T>
int partition(T a[], int p, int r) {
  int i = p, j = r + 1;
  T x = a[p]; // 基准值 x
  while (true) {
    while (a[++i] < x && i < r)
      ; // 左指针 i 向右扫描
    while (a[--j] > x)
      ; // 右指针 j 向左扫描
    if (i >= j)
      break; // 当 i >= j 时退出循环
    swap(a[i], a[j]); // 交换 a [i] 和 a [j]
  }
  a[p] = a[j]; // 基准值放到最终位置
  a[j] = x;    //j 为基准值的位置
  return j;    // 返回基准值最终位置
}
template <typename T>
void quickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = partition(a, l, r);
    quickSort(a, l, pivot - 1);
    quickSort(a, pivot + 1, r);
  }
}
    

  1. 什么时候以 i > j  退出循环？什么时候以 i == j  退出循环？
    2. 





i > j  正常情况

 i == j  当  a[i]  和  a[j]  都等于基准值时（数组中有且只有奇数个等于基准值的元素）或数组递减




时间复杂度：


T(n)={O(1)n=1T(i−1)+T(n−i)+O(n)n>1  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n=1\\
  T(i-1)+T(n-i)+O(n) & n>1
\end{cases}
\implies T(n) = O(n\log n)





最坏情况下时间复杂度为


T(n)={O(1)n=1T(n−1)+O(n)n>1  ⟹  T(n)=O(n2)T(n) = \begin{cases}
  O(1) & n=1\\
  T(n-1)+O(n) & n>1
\end{cases}
\implies T(n) = O(n^2)







改进：随机化快速排序


template <typename T>
int RandomizedPartition(T a[], int l, int r) {
  int i = rand() % (r - l + 1) + l;
  swap(a[i], a[l]);
  return partition(a, l, r);
}
template <typename T>
void RandomizedQuickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = RandomizedPartition(a, l, r);
    RandomizedQuickSort(a, l, pivot - 1);
    RandomizedQuickSort(a, pivot + 1, r);
  }
}


# 线性时间选择


给定线性序列XX 和整数kk，求XX 中第kk 小的元素


思路：

随机选取一个元素作为基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，若基准元素的位置为kk，则返回基准元素，否则递归地在左边或右边进行查找


template <typename T>
T RandomizedSelect(T a[], int low, int high, int k) {
  if (low == high) return a[low];
  int pivot = RandomizedPartition(a, low, high);
  int i = pivot - low + 1; // 前半部分元素个数
  if (k <= i) return RandomizedSelect(a, low, pivot, k);
  else return RandomizedSelect(a, pivot + 1, high, k - i);
}
时间复杂度：


T(n)={O(1)n=1T(n2)+O(n)n>1  ⟹  T(n)=O(n)T(n) = \begin{cases}
  O(1) & n=1\\
  T(\frac{n}{2})+O(n) & n>1
\end{cases}
\implies T(n) = O(n)





优化

选取基准点时，不是随机选取，而是选取中位数的中位数


    

  1. 将序列分为⌈n5⌉\lceil\frac{n}{5}\rceil 组，找出每组的中位数
    2. 

  2. 递归地找出这些中位数的中位数，以这个中位数的中位数作为基准点
    3. 



template <typename T>
T Select(T a[], int low, int high, int k) {
  if (high - low < 75) {
    sort(a + low, a + high + 1);
    return a[low + k - 1];
  }
  // 计算五元组的数量
  int numMedians = (high - low + 1 + 4) / 5;
  for (int i = 0; i < numMedians; i++) {
    // 获取五元组的起始和结束位置
    int subLow = low + i * 5;
    int subHigh = min(subLow + 4, high);
    // 对五元组进行排序
    sort(a + subLow, a + subHigh + 1);
    // 将五元组的中位数放到数组前部
    swap(a[low + i], a[subLow + (subHigh - subLow) / 2]);
  }
  // 递归调用 Select 获取中位数的中位数
  T pivot = Select(a, low, low + numMedians - 1, (numMedians + 1) / 2);
  // 按照主元 pivot 进行划分
  int idx = partition(a, low, high, pivot);
  int i = idx - low + 1;
  if (k == i)
    return a[idx];
  else if (k < i)
    return Select(a, low, idx - 1, k);
  else
    return Select(a, idx + 1, high, k - i);
}


# 最接近点对问题


# 一维最接近点对


给定一组一维坐标，求最接近的两个点


    

  1. 排序 O(nlog⁡n)O(n\log n)
    2. 

  2. 分治
    3. 

  3. 合并
    4. 



template <typename T> T ClosestPair(vector<T> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<T>::max(); // 返回一个最大值表示无效情况
  auto m = len / 2;
  auto S1 = vector<T>(S.begin(), S.begin() + m);
  auto S2 = vector<T>(S.begin() + m, S.end());
  auto d1 = ClosestPair(S1);
  auto d2 = ClosestPair(S2);
  auto d3 = abs(S2.front() - S1.back());
  return min({d1, d2, d3});
}
时间复杂度：


T(n)={O(1)n<42T(n2)+O(nlog⁡n)n>=4  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n<4\\
  2T(\frac{n}{2})+O(n\log n) & n>=4
\end{cases}
\implies T(n) = O(n\log n)



# 二维最接近点对


给定平面上nn 个点，求最接近的两个点


选取一垂直线（x 坐标中位数）将平面分为两部分，分别求出两部分的最接近点对，

然后求出跨越垂直线的最接近点对，易证矩形中最多只有 6 个点


图 2


class Point {
public:
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
  // 计算两个点的欧几里得距离
  auto operator-(const Point &p) const {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
  }
};
double ClosestPair2D(vector<Point> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<double>::max(); // 无效情况，返回最大值
  if (len == 2)
    return S[0] - S[1];
  if (len == 3)
    return min({S[0] - S[1], S[1] - S[2], S[0] - S[2]});
  // 按 x 坐标排序
  sort(S.begin(), S.end(),
       [](const Point &a, const Point &b) { return a.x < b.x; });
  auto m = len / 2;
  auto S1 = vector<Point>(S.begin(), S.begin() + m); // 左半部分
  auto S2 = vector<Point>(S.begin() + m, S.end());   // 右半部分
  // 递归计算左右两部分的最小距离
  auto d1 = ClosestPair2D(S1);
  auto d2 = ClosestPair2D(S2);
  double d = min(d1, d2); // 获取左右两部分的最小距离
  // 查找分界线附近的最接近点对
  vector<Point> strip; // 存放 x 坐标在 d 范围内的点
  for (const auto &p : S) {
    if (abs(p.x - S[m].x) < d) {
      strip.push_back(p);
    }
  }
  // 按 y 坐标排序
  sort(strip.begin(), strip.end(),
       [](const Point &a, const Point &b) { return a.y < b.y; });
  // 查找 strip 中距离小于 d 的点对
  for (size_t i = 0; i < strip.size(); ++i) {
    for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d;
         ++j) {
      d = min(d, strip[i] - strip[j]);
    }
  }
  return d; // 返回最小距离
}
# 动态规划


# 动态规划的基本思想


与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的。


# 动态规划的实质


动态规划的实质是分治思想和解决冗余。


    

  1. 一种将问题实例分解为更小的、相似的子问题。
    2. 

  2. 存储子问题的解而避免计算重复的子问题。
    3. 



# 动态规划的特点


    

  • 动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解。
    • 

  • 对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解。
    • 



# 动态规划的基本步骤


    

  1. 分析最优解的性质，并刻划其结构特征；
    2. 

  2. 递归地定义最优值；
    3. 

  3. 以自底向上的方式计算出最优值；
    4. 

  4. 根据递归计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解
    5. 



# 动态规划基本要素


# 最优子结构性质


当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。


A1,A2,⋯ ,An  ⟹  {A1,A2,⋯ ,AkAk+1,Ak+2,⋯ ,AnA_1,A_2,\cdots,A_n \implies \begin{cases}
  A_1,A_2,\cdots,A_{k}\\
  A_{k+1},A_{k+2},\cdots,A_n
\end{cases}



假设由最优解导出的其子问题的解不是最优的；

 构造出比原问题最优解更好的解；


# 重叠子问题性质


每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。


# 矩阵连乘问题


给定nn 个矩阵A1,A2,⋯ ,AnA_1,A_2,\cdots,A_n，其中AiA_i 与Ai+1A_{i+1} 是可乘的，求矩阵连乘的最优计算次序


定义A[i:j]A[i:j] 为Ai,Ai+1,⋯ ,AjA_i,A_{i+1},\cdots,A_j 的连乘积，m[i][j]m[i][j] 为计算A[i:j]A[i:j] 所需的标量乘法次数


# 分析最优解结构


设A[1:n]A[1:n] 的最优计算次序为A[1:k]A[k+1:n]A[1:k]A[k+1:n]，则有子矩阵链A[1:k]A[1:k] 和A[k+1:n]A[k+1:n] 的计算次序也应该是最优的。




反证法：

设A[1:n]=A[1:k]A[k+1:n]A[1:n]=A[1:k]A[k+1:n] 的计算次序是最优的，若存在一个计算次序A′[1:k]A'[1:k] 其需要的标量乘法次数少于A[1:k]A[1:k]，则A′[1:k]A[k+1:n]A'[1:k]A[k+1:n] 的计算次序也应该是最优的，与假设矛盾。

可以证明矩阵连乘问题具有最优子结构性质。




# 建立递归关系


m[i][j]={0i=jmin⁡i≤k<j{m[i][k]+m[k+1][j]+pi−1pkpj}i<jm[i][j]=\begin{cases}
  0 & i=j\\
  \min\limits_{i\leq k<j}\{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\} & i<j
\end{cases}



    

  1. 为什么是pi−1pkpjp_{i-1}p_kp_j？
    2. 





因为AiA_i 的维数为pi−1×pip_{i-1} \times p_i，AkA_k 的维数为pk−1×pkp_{k-1} \times p_k，AjA_j 的维数为pj−1×pjp_{j-1} \times p_j，所以AiAkAjA_iA_kA_j 的维数为pi−1×pjp_{i-1} \times p_j，所以需要pi−1pkpjp_{i-1}p_kp_j 次乘法




# 自底向上计算最优值


void MatrixChain(vector<int> &p, vector<vector<int>> &m,
                 vector<vector<int>> &s) {
  /**
    * p: 矩阵链的维数
    * m: 存储计算代价
    * s: 存储最优分割点
   */
  int n = p.size() - 1; // 矩阵链的长度
  for (int i = 1; i <= n; i++) {
    m[i][i] = 0; // 初始化对角线元素为 0，因为单个矩阵的计算代价为 0
  }
  for (int r = 2; r <= n; r++) { //r 表示当前考虑的矩阵链的长度，从 2 到 n
    for (int i = 1; i <= n - r + 1; i++) { //i 表示矩阵链的起始位置
      int j = i + r - 1; //j 表示矩阵链的结束位置
      m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 初始代价，假设最优分割点为 i
      s[i][j] = i; // 记录最优分割点
      for (int k = i + 1; k < j; k++) { // 遍历所有可能的分割点
        int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 计算当前分割点的代价
        if (t < m[i][j]) { // 如果当前代价小于已知最小代价
          m[i][j] = t; // 更新最小代价
          s[i][j] = k; // 更新最优分割点
        }
      }
    }
  }
}
# 构造最优解


void Traceback(vector<vector<int>> &s, int i, int j) {
  if (i == j) { // 如果 i 等于 j，说明矩阵链中只有一个矩阵
    cout << "A" << i; // 输出矩阵的标识符
    return;
  }
  cout << "("; // 输出左括号表示开始一个新的矩阵链
  Traceback(s, i, s[i][j]); // 递归处理第一个子链
  Traceback(s, s[i][j] + 1, j); // 递归处理第二个子链
  cout << ")"; // 输出右括号表示结束一个矩阵链
}
# 最长公共子序列


子序列：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X={x1,x2,⋯ ,xm}X=\{x_1,x_2,\cdots,x_m\}，则另一个序列Z={z1,z2,⋯ ,zk}Z=\{z_1,z_2,\cdots,z_k\} 是XX 的子序列是指存在一个严格递增的序列{i1,i2,⋯ ,ik}\{i_1,i_2,\cdots,i_k\}，使得对于所有j=1,2,⋯ ,kj=1,2,\cdots,k，有zj=xijz_j=x_{i_j}。


# 最长公共子序列的结构


设序列X={x1,x2,…,xm}X = \{x_1,x_2,\dots,x_m\} 和Y={y1,y2,…,yn}Y = \{y_1,y_2,\dots,y_n\} 的最长公共子序列为Z={z1,z2,…,zk}Z=\{z_1,z_2,\dots,z_k\}，则


    

  1. 若xm=ynx_m=y_n，则zk=xm=ynz_k=x_m=y_n，且Zk−1Z_{k-1} 是Xm−1X_{m-1} 和Yn−1Y_{n-1} 的最长公共子序列
    2. 

  2. 若xm≠ynx_m\neq y_n 且zk≠xmz_k\neq x_m，则ZZ 是Xm−1X_{m-1} 和YY 的最长公共子序列
    3. 

  3. 若xm≠ynx_m\neq y_n 且zk≠ynz_k\neq y_n，则ZZ 是XX 和Yn−1Y_{n-1} 的最长公共子序列
    4. 





证明：


    

  1. 如果zk≠xmz_k\neq x_m，那么可以将xm=ynx_m=y_n 加入到ZZ 中，得到一个更长的公共子序列，与ZZ 的定义矛盾。因此必然有xm=yn=zkx_m=y_n=z_k。由此可知，Zk−1Z_{k-1} 是Xm−1X_{m-1} 和Yn−1Y_{n-1} 的最长公共子序列。若Xm−1X_{m-1} 和Yn−1Y_{n-1} 有长度大于k−1k-1 的公共子序列WW，则将xmx_m 加在WW 的末尾，得到一个长度大于kk 的公共子序列，与ZZ 的定义矛盾。
    2. 

  2. 如果zk≠xmz_k\neq x_m，那么ZZ 是Xm−1X_{m-1} 和YY 的最长公共子序列。若Xm−1X_{m-1} 和YY 有长度大于kk 的公共子序列WW，那么WW 也是XX 和YY 的公共子序列，与ZZ 的定义矛盾。
    3. 

  3. 同理，ZZ 是XX 和Yn−1Y_{n-1} 的最长公共子序列。
    4. 





# 子问题的递归结构


设c[i][j]c[i][j] 为XiX_i 和YjY_j 的最长公共子序列的长度，则有


c[i][j]={0i=0或j=0c[i−1][j−1]+1i,j>0且xi=yjmax⁡{c[i][j−1],c[i−1][j]}i,j>0且xi≠yjc[i][j]=\begin{cases}
  0 & i=0\text{或}j=0\\
  c[i-1][j-1]+1 & i,j>0\text{且}x_i=y_j\\
  \max\{c[i][j-1],c[i-1][j]\} & i,j>0\text{且}x_i\neq y_j
\end{cases}



# 计算最优值


void LCSLength(const string &X, const string &Y, vector<vector<int>> &c,
               vector<vector<string>> &b) {
  int m = X.size();
  int n = Y.size();
  // for (int i = 1; i <= m; i++) {
  //   c[i][0] = 0;
  // }
  // for (int j = 0; j <= n; j++) {
  //   c[0][j] = 0;
  // }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) { // 注意这里的下标，因为 X 和 Y 的下标是从 0 开始的，所以要减 1
        c[i][j] = c[i - 1][j - 1] + 1;
        b[i][j] = "↖";
      } else if (c[i - 1][j] >= c[i][j - 1]) {
        c[i][j] = c[i - 1][j];
        b[i][j] = "↑";
      } else {
        c[i][j] = c[i][j - 1];
        b[i][j] = "←";
      }
    }
  }
}
# 构建 LCS


string LCS(const string &X, const string &Y, const vector<vector<string>> &b,
           int i, int j) {
  if (i == 0 || j == 0) {
    return "";
  }
  if (b[i][j] == "↖") {
    return LCS(X, Y, b, i - 1, j - 1) + X[i - 1];
  } else if (b[i][j] == "↑") {
    return LCS(X, Y, b, i - 1, j);
  } else {
    return LCS(X, Y, b, i, j - 1);
  }
}


↑ 和 ← 只指引构造 LCS 的方向，不是 LCS 的一部分，只有 ↖ 才是 LCS 的一部分。




# 算法改进


省去 b  数组，直接构造 LCS


string LCSWithoutB(const string &X, const string &Y) {
  int m = X.size();
  int n = Y.size();
  vector<vector<int>> c(m + 1, vector<int>(n + 1, 0));
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) {
        c[i][j] = c[i - 1][j - 1] + 1;
      } else {
        c[i][j] = max(c[i - 1][j], c[i][j - 1]);
      }
    }
  }
  string lcs;
  int i = m, j = n;
  while (i > 0 && j > 0) {
    if (X[i - 1] == Y[j - 1]) {
      lcs = X[i - 1] + lcs;
      i--;
      j--;
    } else if (c[i - 1][j] >= c[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}
只计算 LCS 的长度，不构造 LCS，仅用一维 dp


int LCSLengthOnly(const string &X, const string &Y) {
  //m 保存字符串 X 的长度
  int m = X.size();
  //n 保存字符串 Y 的长度
  int n = Y.size();
  // 创建一个大小为 (n+1) 的一维数组 'c'，初始值为 0。
  // 该数组用于存储到目前为止，X 和 Y 每个位置的最长公共子序列长度。
  vector<int> c(n + 1, 0);
  // 遍历字符串 X 的每一个字符
  for (int i = 1; i <= m; i++) {
    // 'prev' 保存上一次 i 循环中 c [j-1] 的值 (上一行)
    int prev = 0;
    // 遍历字符串 Y 的每一个字符
    for (int j = 1; j <= n; j++) {
      // 'temp' 临时保存当前 c [j] 的值，在它被更新前
      int temp = c[j];
      // 如果字符相同，则当前位置的 LCS 长度增加 1
      if (X[i - 1] == Y[j - 1]) {
        c[j] = prev + 1;
      } else {
        // 如果字符不同，则取当前列和前一列的最大值
        c[j] = max(c[j], c[j - 1]);
      }
      // 更新 prev 为 c [j] 原来的值
      prev = temp;
    }
  }
  // 返回最终的 LCS 长度
  return c[n];
}
# 最大子段和


给定由nn 个整数组成的序列a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，求该序列形如∑k=ijak\sum\limits_{k=i}^{j}a_k 的连续子段的最大和，当所有整数均为负数时，最大子段和为 0。


定义 dp[i]  为max⁡1≤j≤i∑k=jiak\max\limits_{1\leq j\leq i}\sum\limits_{k=j}^{i}a_k，即以1−i1-i 为左端点，以ii 为右端点的最大子段和。


当 dp[i-1] >= 0  时， dp[i] = dp[i-1] + a[i] ，否则 dp[i] = a[i] 。


dp[i]={0i=0max⁡{dp[i−1]+a[i],a[i]}i≤1dp[i]=\begin{cases}
  0 & i=0\\
  \max\{dp[i-1]+a[i],a[i]\} & i\leq 1
\end{cases}



auto LSS(vector<int> a) {
  vector<int> dp(a.size() + 1);
  dp[0] = 0;
  for (int i = 1; i <= a.size(); i++) {
    dp[i] = max(dp[i - 1] + a[i - 1], a[i - 1]);
  }
  auto res = max_element(dp.begin(), dp.end());
  return *res;
}
// 状态压缩
auto LSS2(vector<int> a) {
  int dp = 0, res = 0;
  for (const auto &x: a) {
    dp = dp > 0 ? dp + x : x;
    res = max(res, dp);
  }
  return res;
}
# 凸多边形三角剖分


给定一个凸多边形以及定义在由多边形的边和弦组成的三角形上的权函数ω\omega，将其分割成若干个三角形，使得分割后的三角形的总的权值和最小。


图 3


定义dp[i][j]dp[i][j] 为凸子多边形{vi−1,vi,⋯ ,vj}\{v_{i-1}, v_i,\cdots, v_j\} 的最优三角剖分的权值和，


dp[i][j]={0j=imin⁡i<=k<j{dp[i][k]+dp[k+1][j]+ω(vi−1,vk,vj)}j>idp[i][j]=\begin{cases}
  0 & j=i\\
  \min\limits_{i<=k<j}\{dp[i][k]+dp[k+1][j]+\omega(v_{i-1},v_k,v_j)\} & j>i
\end{cases}



void MinWeightTriangulation(vector<vector<double>> &dp, vector<vector<int>> &s) {
  int n = dp.size() - 2; // 边数 = 多边形的顶点数 - 1
  for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;
  }
  for (int r = 2; r <= n; r++) {
    for (int i = 1; i <= n - r + 1; i++) {
      auto j = i + r - 1;
      dp[i][j] = dp[i + 1][j] + w(i - 1, i, j);
      s[i][j] = i;
      for (int k = i + 1; k < j; k++) {
        auto t = dp[i][k] + dp[k + 1][j] + w(i - 1, k, j);
        if (t < dp[i][j]) {
          dp[i][j] = t;
          s[i][j] = k;
        }
      }
    }
  }
}
# 图像压缩


数字化图像是n×nn\times n 的像素阵列。 假定每个像素有一个 0~255 的灰度值，存储一个像素需 8 位。 为了减少存储空间，采用变长模式，即不同像素用不同位数来存储。


将像素分成连续的mm 段S1,S2,⋯ ,SmS_1,S_2,\cdots,S_m，使每段中的像素存储位数相同。第ii 段的存储像素数为 l[i] ，且该段中的每个像素只用 b[i]  表示。


存储空间为∑i=1ml[i]×b[i]+11m\sum\limits_{i=1}^{m}l[i]\times b[i]+11m，其中 11m 为存储段的信息所需的位数。


# 图像压缩的最优子结构


设l[i],b[i],1≤i≤ml[i],b[i],1\leq i\leq m 是{p1,p2,⋯ ,pi}\{p_1,p_2,\cdots,p_i\} 一个最优方案，显然l[1],b[1]l[1],b[1] 是{p1,⋯ ,pl[1]}\{p_1,\cdots,p_{l[1]}\} 的最优方案，且l[i],b[i],2≤i≤ml[i], b[i], 2\leq i \leq m 是{pl[i]+1,⋯ ,pn}\{p_{l[i]+1},\cdots,p_{n}\} 的最优方案。


# 图像压缩的递归结构


设s[i]s[i] 为{p1,p2,⋯ ,pi}\{p_1,p_2,\cdots,p_i\} 的最优存储位数


    

  1. 考察最后一个元素pip_i 的分段情况​
    2. 

  2. 假设 pip_i 自成一段，则 S[i]=s[i−1]+保存 pi 的代价S[i] = s[i-1] + \text{保存 } p_i \text{ 的代价}；
    3. 

  3. 假设最后 2 个像素点为一段，则 s[i]=s[i−2]+保存最后 2 个像素点的代价s[i] = s[i-2] + \text{保存最后 2 个像素点的代价}；
    4. 

  4. 假设最后 ii 个像素点为一段，则 s[i]=s[0]+保存最后 i 个像素点的代价s[i] = s[0] + \text{保存最后 } i \text{ 个像素点的代价}；
    5. 

  5. 取 s[i]s[i] 为 min⁡\min 时对应的元素个数。假设为 kk。
    6. 

  6. 此时，则 S[i]=s[i−k]+保存最后 k 个像素的代价S[i] = s[i-k] + \text{保存最后 } k \text{ 个像素的代价}；
    7. 

  7. 后者 =k×max⁡{k 个灰度值二进制位数}+11= k \times \max\{\text{k 个灰度值二进制位数}\} + 11；
    8. 

  8. 求解 s[i−k]s[i-k] 即可；
    9. 

  9. 考察最后一个像素点的分段情况，自成 1 段？后 2 个点？后 3 个点？…… 重复上述过程。
    10. 



s[n]=min⁡1≤k≤min⁡{n,256}{s[n−k]+k×amax⁡(n−k+1,n)}+11amax⁡(i,j)=⌈log⁡2(max⁡i≤k≤j{pk}+1)⌉\begin{align*}
  &s[n] = \min\limits_{1\leq k\leq\min\{n,256\}}\{s[n-k]+k\times a\max(n-k+1,n)\}+11\\
  &a\max(i,j) = \lceil\log_2(\max\limits_{i \leq k \leq j}\{p_k\} + 1)\rceil
\end{align*}



    

  • l[i] ：前 i 个像素点最后一段包含的个数。
    • 

  • b[i] ：前 i 个像素点最后一段位数 / 最大值。
    • 

  • a[i] ：第 i 个像素点的位数。
    • 



int length(int x) {
  int l = 1;
  x >>= 1;
  while (x > 0) {
    l++;
    x >>= 1;
  }
  return l;
}
void ImageCompression(vector<int> &p, vector<int> &l, vector<int> &b,
      vector<int> &s) {
  const int n = p.size();
  constexpr int L_MAX = 256, HEADER = 11; // 定义最大块长度和头部长度
  s[0] = 0;
  vector<int> a(n, 0);
  // 计算每个像素值的位数，存储在数组 a 中
  for (int i = 0; i < n; i++) { // 遍历所有像素
    a[i] = length(p[i]); //length () 函数计算 p [i] 的二进制位数
    int bMax = numeric_limits<int>::min(); // 初始化当前块中位数的最大值
    s[i] = numeric_limits<int>::max(); // 初始化 s [i] 为最大整数
    // 考虑从位置 i 向前的不同块大小 j
    for (int j = 1; j <= i + 1 && j <= L_MAX; j++) { //j 是当前块的长度
      // 更新当前块中像素位数的最大值
      bMax = max(bMax, a[i - j + 1]); // 在当前块中找到最大的位数
      // 计算将当前块划分为长度为 j 的块后的总存储位数，并与之前的最小值比较
      if (s[i] > s[i - j] + j * bMax) {
        s[i] = s[i - j] + j * bMax; // 更新最小存储位数
        l[i] = j; // 记录当前最优块的长度
        b[i] = bMax; // 记录当前最优块的位数
      }
    }
    s[i] += HEADER; // 加上存储段信息所需的位数
  }
}
# 电路布线


一块电路板的上下两端分别有nn 个引脚，用导线(i,π(i))(i, \pi(i)) 连接引脚ii 和π(i)\pi(i)，其中π\pi 是一个排列。第ii 条连线和第jj 条连线相交当且仅当π(i)>π(j)\pi(i) > \pi(j) 且i<ji < j。要求确定导线集的最大不相交子集。


图 4


化为多步决策，自底向上，先求出​只有一条连线的最大不相交子集，再求有 2 条连线的最大不相交子集...


# 电路布线的最优子结构


记N(i,j)={t∣(t,π(t))∈Nets,t≤i,π(t)≤j}N(i,j) = \{t|(t, \pi(t)) \in Nets, t \leq i, \pi(t) \leq j\}，N(i,j)N(i,j) 的最大不相交子集为MNS(i,j)MNS(i,j)，Size(i,j)=∣MNS(i,j)∣Size(i,j) = |MNS(i,j)|。


    

  • 当i=1i = 1 时，有MNS(i,j)=N(1,j)={∅j<π(1){1,π(1)}j≥π(1)MNS(i,j) = N(1, j) = \begin{cases}\varnothing & j < \pi(1)\\ \{1, \pi(1)\} & j \geq \pi(1)\end{cases}
    • 

  • 当i>1i > 1 时，有

      

    • 若j<π(i)j < \pi(i)。此时(i,π(i))∉N(i,j)(i, \pi(i)) \notin N(i,j)，所以N(i,j)=N(i−1,j)N(i,j) = N(i-1,j)，Size(i,j)=Size(i−1,j)Size(i,j) = Size(i-1,j)
      • 

    • 若j≥π(i)j \geq \pi(i)。若(i,π(i))∈MNS(i,j)(i, \pi(i)) \in MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)(t, \pi(t)) \in MNS(i,j)，有t<it < i，π(t)<π(i)\pi(t) < \pi(i)，否则(t,π(t))(t, \pi(t)) 和(i,π(i))(i, \pi(i)) 相交。所以MNS(i,j)−{(i,π(i))}MNS(i,j) - \{(i, \pi(i))\} 是N(i−1,π(i)−1)N(i-1, \pi(i)-1) 的最大不相交子集，否则MNS(i−1,π(i)−1)∪{(i,π(i))}⊆N(i,j)MNS(i-1, \pi(i)-1)\cup\{(i, \pi(i))\} \subseteq N(i,j) 是比MNS(i,j)MNS(i,j) 更大的不相交子集，这与MNS(i,j)MNS(i,j) 的定义矛盾。若(i,π(i))∉MNS(i,j)(i, \pi(i)) \notin MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)(t, \pi(t)) \in MNS(i,j)，有t<it < i，从而MNS(i,j)/subseteqN(i−1,j)MNS(i,j)/subseteq N(i-1,j)，因此Size(i,j)/leqSize(i−1,j)Size(i,j) /leq Size(i-1,j)。另一方面，MNS(i−1,j)⊆N(i,j)MNS(i-1,j) \subseteq N(i,j)，所以Size(i,j)≥Size(i−1,j)Size(i,j) \geq Size(i-1,j)，则Size(i,j)=Size(i−1,j)Size(i,j) = Size(i-1,j)。
      • 

    

    • 



# 递归计算最优值


    

  • 当i=1i = 1 时，Size(1,j)={0j<π(1)1j≥π(1)Size(1,j) = \begin{cases}0 & j < \pi(1)\\ 1 & j \geq \pi(1)\end{cases}
    • 

  • 当i>1i > 1 时，Size(i,j)={Size(i−1,j)j<π(i)max⁡{Size(i−1,j),Size(i−1,π(i)−1)+1}j≥π(i)Size(i,j) = \begin{cases}Size(i-1,j) & j < \pi(i)\\ \max\{Size(i-1,j), Size(i-1, \pi(i)-1)+1\} & j \geq \pi(i)\end{cases}
    • 



// C[0:n]
void MNS(const vector<int> &C, vector<vector<int>> &size) {
  const int n = C.size();
  for (int j = 0; j < n; j++) {
    size[0][j] = j < C[0] ? 0 : 1;
  }
  for (int i = 1; i < n - 1; i++) {
    for (int j = 0; j < n; j++) {
      if (j < C[i]) {
        size[i][j] = size[i - 1][j];
      } else {
        size[i][j] = max(size[i - 1][j], size[i - 1][C[i] - 1] + 1);
      }
    }
  }
  size[n - 1][n - 1] = max(size[n - 2][n - 1], size[n - 2][C[n - 1] - 1] + 1);
}
# 构造最优解


auto Traceback(const vector<vector<int>> &size, const vector<int> &C) {
  vector<int> Net;
  int j = C.size() - 1;
  int m = 0;
  for (int i = C.size() - 1; i > 0; i--) {
    if (size[i][j] != size[i - 1][j]) {
      Net[m++] = i;
      j = C[i] - 1;
    }
  }if (j >= C[0]) {
      Net[m++] = 0;
    }
  return Net;
}
# 流水线作业调度


nn 个作业{1,2,⋯ ,n}\{1,2,\cdots,n\} 要在 2 台相同的流水线上加工，每个作业加工顺序为先在M1M_1 上加工，再在M2M_2 上加工。第ii 个作业在M1M_1 上加工时间为aia_i，在M2M_2 上加工时间为bib_i。


最优调度方案是使得M1M_1 没有空闲时间，M2M_2 的空闲时间最小。


设全部作业集合为N={1,2,⋯ ,n}N = \{1,2,\cdots,n\}，S⊆NS \subseteq N 是一个作业子集。在一般情况下，机器M1M_1 开始加工SS 中作业时，机器M2M_2 还在加工其他作业，要等时间tt 后才可利用。这种情况下完成SS 中作业所需的最短时间记为T(S,t)T(S, t)。

流水作业调度问题的最优值为T(N,0)T(N, 0)。


# 流水线作业调度的最优子结构


设π\pi 是所给nn 个作业的一个最优调度方案，所需加工时间为aπ(1)+T′a_{\pi(1)} + T'。其中T′T' 是在机器M2M_2 的等待时间为bπ(1)b_{\pi(1)} 时，安排作业π(2),π(3),⋯ ,π(n)\pi(2),\pi(3),\cdots,\pi(n) 所需的时间。记S=N−{π(1)}S=N-\{\pi(1)\}，则T′=T(S,bπ(1))T' = T(S, b_{\pi(1)})。


# 流水线作业调度的递归计算最优值


T(N,0)=min⁡1≤i≤n{ai+T(N−{i},bi)}T(N, 0) = \min\limits_{1\leq i\leq n}\{a_i + T(N-\{i\}, b_i)\}，推广到一般情况有：


T(S,t)=min⁡i∈S{ai+T(S−{i},bi+max{t−ai,0})}T(S,t) = \min \limits_{i \in S} \{a_i+T(S-\{i\}, b_i+max\{t-a_i,0\})\}



式中， max⁡{t−ai,0}\max\{t-a_i, 0\} 项是由于在机器M2M_2 上，作业 i 必须在max⁡{t,ai}\max\{t,a_i\} 时间之后才能开工。因此在机器M1M_1 上完成作业 i 之后在机器上还需要bi+max⁡{t,ai}−ai=bi+max⁡{t−ai,0}b_i+\max\{t,a_i\} - a_i = b_i + \max\{t-a_i, 0\} 时间才能完成对作业 i 的加工。


# 流水线作业调度的 Johnson 法则


如果作业ii 和作业jj 满足min⁡{bi,aj}≥min⁡{bj,ai}\min\{b_i, a_j\} \geq \min\{b_j, a_i\}，则作业ii 应该在作业jj 之前加工。




nn 个任务的 Johnson 法则


    

  1. 令N1={i∣ai<bi}N_1 = \{i|a_i < b_i\}，N2={i∣ai≥bi}N_2 = \{i|a_i \geq b_i\}；
    2. 

  2. 按照aia_i 的非降序排列N1N_1 中的任务，按照bib_i 的非升序排列N2N_2 中的任务；
    3. 

  3. N1N_1 中的任务在N2N_2 中的任务之前加工。
    4. 





vector<int> flowShop(const vector<int> &a, const vector<int> &b) {
  const int n = a.size();
  vector<int> C(n);
  vector<pair<int, int>> tasks(n);
  for (int i = 0; i < n; i++) {
    tasks[i] = {a[i], b[i]};
  }
  vector<int> N1, N2;
  for (int i = 0; i < n; i++) {
    if (tasks[i].first < tasks[i].second) {
      N1.push_back(i);
    } else {
      N2.push_back(i);
    }
  }
  sort(N1.begin(), N1.end(),
       [&](int i, int j) { return tasks[i].first < tasks[j].first; });
  sort(N2.begin(), N2.end(),
       [&](int i, int j) { return tasks[i].second > tasks[j].second; });
  move(N1.begin(), N1.end(), C.begin());
  move(N2.begin(), N2.end(), C.begin() + N1.size());
  return C;
}
# 流水线作业调度的总时间


int calculateTime(vector<int> C, const vector<int> &a, const vector<int> &b) {
    const int n = C.size();
    vector<int> f(n);
    vector<int> g(n);
    f[0] = a[C[0]];
    g[0] = f[0] + b[C[0]];
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + a[C[i]];
        g[i] = max(g[i - 1], f[i]) + b[C[i]];
    }
    return g[n - 1];
}
# 0-1 背包问题


给定nn 个物品，每个物品的重量为wiw_i，价值为viv_i，背包的容量为cc，求如何装入背包使得背包中物品的总价值最大。


形式化描述为：给定c>0,wi>0,vi>0,i=1,2,⋯ ,nc>0, w_i>0, v_i>0, i=1,2,\cdots,n，求一个向量x=(x1,x2,⋯ ,xn)x=(x_1,x_2,\cdots,x_n)，其中xi∈{0,1}x_i\in\{0,1\}，使得∑i=1nwixi≤c\sum\limits_{i=1}^{n}w_ix_i\leq c 且∑i=1nvixi\sum\limits_{i=1}^{n}v_ix_i 最大，即


{max⁡∑i=1nvixis.t.∑i=1nwixi≤cxi∈{0,1}i=1,2,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=1}^{n}v_ix_i\\
  s.t. & \sum\limits_{i=1}^{n}w_ix_i\leq c\\
  & x_i\in\{0,1\} & i=1,2,\cdots,n
\end{cases}



# 0-1 背包问题的最优子结构


设(y1,y2,⋯ ,yn)(y_1,y_2,\cdots,y_n) 是一个最优解，则(y2,y3,⋯ ,yn)(y_2,y_3,\cdots,y_n) 是下面相应子问题的一个最优解：


{max⁡∑i=2nvixis.t.∑i=2nwixi≤c−wiy1xi∈{0,1}i=2,3,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=2}^{n}v_ix_i\\
  s.t. & \sum\limits_{i=2}^{n}w_ix_i\leq c-w_iy_1\\
  & x_i\in\{0,1\} & i=2,3,\cdots,n
\end{cases}



否则，设(z2,z3,⋯ ,zn)(z_2,z_3,\cdots,z_n) 是上述子问题的一个最优解，则(y2,y3,⋯ ,yn)(y_2,y_3,\cdots,y_n) 不是它的一个最优解。由此可知，∑i=2nvizi>∑i=2nviyi\sum\limits_{i=2}^{n}v_iz_i > \sum\limits_{i=2}^{n}v_iy_i，且w1y1+∑i=2nwizi≤cw_1y_1 + \sum\limits_{i=2}^{n}w_iz_i \leq c。因此


v1y1+∑i=2nvizi>∑i=1nviyiw1y1+∑i=2nwizi≤c\begin{align*}
  v_1y_1 + \sum\limits_{i=2}^{n}v_iz_i &> \sum\limits_{i=1}^{n}v_iy_i \\
w_1y_1 + \sum\limits_{i=2}^{n}w_iz_i &\leq c
\end{align*}



这说明(y1,z2,z3,⋯ ,zn)(y_1,z_2,z_3,\cdots,z_n) 是原问题的一个最优解。从而(y1,y2,⋯ ,yn)(y_1,y_2,\cdots,y_n) 不是原问题的一个最优解，这与假设矛盾。


# 0-1 背包问题的递归计算最优值


设所给 0-1 背包的子问题的最优值为m(i,j)m(i, j)，即可选择物品为{i,i+1,⋯ ,n}\{i, i+1,\cdots,n\}，背包容量为jj 时的最优值。则有


m(i,j)={max{m(i+1,j),m(i+1,j−wi)+vi}j≥wim(i+1,j)j<wim(i, j) = \begin{cases}
  max\{m(i+1, j), m(i+1, j-w_i)+v_i\} & j\geq w_i\\
  m(i+1, j) & j < w_i
\end{cases}



// 下标从 1 开始
void knapsack(const vector<int> &w, const vector<int> &v, int c,
              vector<vector<int>> &m) {
  const int n = w.size();
  for (int j = 0; j <= min(c, w[n - 1]); j++) {
    m[n][j] = 0;
  }
  for (int j = w[n]; j <= c; j++) {
    m[n][j] = v[n];
  }
  for (int i = n - 1; i > 1; i--) {
    for (int j = 0; j <= min(c, w[i - 1]); j++) {
      m[i][j] = m[i + 1][j];
    }
    for (int j = w[i]; j <= c; j++) {
      m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
    }
  }
  if (c >= w[1]) {
    m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
  }
  else {
    m[1][c] = m[2][c];
  }
}
void Traceback(const vector<vector<int>> &m, const vector<int> &w,
               const vector<int> &v, int c, vector<int> &x) {
  const int n = w.size();
  for (int i = 1; i < n; i++) {
    if (m[i][c] == m[i + 1][c]) {
      x[i] = 0;
    } else {
      x[i] = 1;
      c -= w[i];
    }
  }
  x[n] = m[n][c] > 0 ? 1 : 0;
}
# 0-1 背包问题的跳跃点解法


p[i]={(j,m(i,j))∣0≤j≤c}p[i] = \{(j, m(i, j))|0\leq j\leq c\}，p[i]p[i] 是一个有序对的集合，其中jj 是背包容量，m(i,j)m(i, j) 是选择物品{i,i+1,⋯ ,n}\{i, i+1,\cdots,n\}，背包容量为jj 时的最优值。


m(i,j)m(i,j) 的全部跳跃点p[i]p[i] 包含于​m(i+1,j)m(i+1,j) 的跳跃点集p[i+1]p[i+1] 与m(i+1,j−wi)+vim(i+1,j-w_i)+v_i 的跳跃点集q[i+1]q[i+1] 的并集中​


p[i]⊆p[i+1]∪q[i+1]q[i+1]=p[i+1]⊕(wi,vi)={(j+wi,m(i,j)+vi)∣(j,m(i,j))∈p[i+1]}\begin{align*}
p[i] &\subseteq p[i+1] \cup q[i+1]\\
q[i+1] &= p[i+1] \oplus  (w_i, v_i) \\
       &= \{(j+w_i, m(i, j)+v_i) \mid (j, m(i, j)) \in p[i+1]\}
\end{align*}



设(a,b)(a,b) 和(c,d)(c,d) 是p[i+1]∪q[i+1]p[i+1] \cup q[i+1] 中的两个跳跃点，当c≥ac \geq a 且d<bd < b 时，(c,d)(c, d) 是(a,b)(a, b) 的一个受控点，需要删掉。


图 5


图中(5,4)(5,4) 是(4,6)(4,6) 的一个受控点，需要删掉。


# 贪心算法


# 活动安排问题


设有nn 个活动的集合E={1,2,⋯ ,n}E=\{1,2,\cdots,n\}，每个活动ii 都有一个使用该资源的起始时间sis_i 和一个结束时间fif_i，且0≤si<fi<∞0\leq s_i < f_i < \infty。如果选择活动ii，则活动ii 发生在半开时间区间[si,fi)[s_i, f_i) 内。若区间[si,fi)[s_i, f_i) 与[sj,fj)[s_j, f_j) 不相交，则称活动ii 与活动jj 是相容的。目标：找出最大相容活动集。


思路：选择最早结束的活动，然后删除与该活动相容的活动，重复此过程。


class Activity {
public:
  int id;
  int start;
  int finish;
  Activity(int s, int f) : start(s), finish(f) {
    static int count = 0;
    id = count++;
  }
};
void GreedyActivitySelector(vector<shared_ptr<Activity>> &activities,
                            vector<shared_ptr<Activity>> &selected) {
  ranges::sort(activities, [](const shared_ptr<Activity> &a,
                              const shared_ptr<Activity> &b) {
    return a->finish < b->finish;
  });
  selected.clear();
  selected.emplace_back(activities[0]);
  auto last = activities[0];
  for (int i = 1; i < activities.size(); i++) {
    if (activities[i]->start >= last->finish) {
      selected.emplace_back(activities[i]);
      last = activities[i];
    }
  }
}
# 证明活动安排问题的贪心选择性质


# 证明活动安排问题有一个最优解以贪心选择开始


设AA 是最优解，且AA 中活动也按fif_i 非减序排列，AA 中第一个活动是kk。


若k=1k=1，则AA 就是一个以贪心选择开始的最优解；


否则，构造B=A−{k}∪{1}B=A-\{k\}\cup \{1\}


# 证明每一步贪心选择→问题的整体最优解 ​


若AA 是EE 的最优解，则A′=A−{1}A' = A - \{1\} 是E′={i∈E∣si≥f1}E' = \{i\in E|s_i \geq f_1\} 的最优解。


如果能找到一个E′E' 的解B′B'，它包含比A′A' 更多的活动，则B=B′∪{1}B = B' \cup \{1\} 优于AA，这与AA 是最优解矛盾。


# 贪心算法基本要素


贪心算法通过一系列的选择来得到问题的解。​它所做的每一个选择都是当前状态下局部的​最好选择，即贪心选择。​


    

  • 最优子结构性质
    • 

  • 贪心选择性质
    • 



# 贪心与动态规划的区别


    

  • 动态规划算法通常以自底向上的方式解决问题，每步所作的选择依赖于相关子问题的解。​
    • 

  • 贪心算法通常以自顶向下的方式解决问题，贪心选择依赖于以往作出的选择，不依赖于子问题的解。 ​
    • 



# 贪心选择思路


证明每一步贪心选择→问题的整体最优解


    

  1. 假设问题有一个整体最优解，并证明可修改​这个最优解，使其以贪心选择开始。​做了贪心选择后，原问题简化为规模更小的类似子问题。​
    2. 

  2. 运用数学归纳法证明：​每一步贪心选择→问题的整体最优解。​
    3. 



# 背包问题（可选部分）


贪心选择性质：每次选择单位价值最高的物品。可选部分。


class Item {
public:
  int id;
  int weight;
  int value;
  double unitValue;
  Item(int w, int v) : weight(w), value(v) {
    static int count = 0;
    id = count++;
    unitValue = static_cast<double>(v) / w;
  }
};
void FractionalKnapsack(vector<shared_ptr<Item>> &items, int c,
                        vector<shared_ptr<Item>> &selected) {
  ranges::sort(items, [](const shared_ptr<Item> &a, const shared_ptr<Item> &b) {
    return a->unitValue > b->unitValue;
  });
  selected.clear();
  int weight = 0;
  for (int i = 0; i < items.size(); i++) {
    if (weight + items[i]->weight <= c) {
      selected.emplace_back(items[i]);
      weight += items[i]->weight;
    } else {
      auto remain = c - weight;
      auto item = make_shared<Item>(remain, remain * items[i]->unitValue);
      selected.emplace_back(item);
      break;
    }
  }
}
# 最优装载


有一批集装箱要装上一艘载重量为CC 的轮船，其中第ii 个集装箱的重量为wiw_i。装载问题是找出尽可能多的集装箱装上轮船。


形式化描述为


{max⁡∑i=1nxis.t.∑i=1nwixi≤Cxi∈{0,1}i=1,2,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=1}^{n}x_i\\
  s.t. & \sum\limits_{i=1}^{n}w_ix_i \leq C\\
  & x_i\in\{0,1\} & i=1,2,\cdots,n
\end{cases}



贪心选择性质：每次选择重量最小的集装箱。


vector<int> Loading(vector<int> &w, int c) {
  vector<int> x(w.size());
  ranges::sort(w);
  int weight = 0;
  for (int i = 0; i < w.size(); i++) {
    if (weight + w[i] <= c) {
      x.emplace_back(w[i]);
      weight += w[i];
    }
  }
  return x;
}
# 哈夫曼编码


给定编码字符集cc，以及每个字符的频率f(c)f(c)，构造一个无歧义的前缀编码，使得所有字符的编码长度之和最小。

平均码长：B(T)=∑c∈Cf(c)dT(c)B(T) = \sum\limits_{c\in C}f(c)d_T(c)，其中dT(c)d_T(c) 是字符cc 在树TT 中的深度。

找到使B(T)B(T) 最小的前缀码编码方案。


# 哈夫曼编码的思路


优先队列QQ 以f(c)f(c) 为关键字存放二叉树各节点，每次从QQ 中选取两个频率最小的二叉树合并，然后将新树（根节点的频率为两个子树的频率之和）插入QQ。


class Node {
public:
  char ch;
  int freq;
  shared_ptr<Node> left;
  shared_ptr<Node> right;
  Node(char c, int f) : ch(c), freq(f) {}
};
shared_ptr<Node> Huffman(vector<pair<char, int>> &freq) {
  auto cmp = [](const shared_ptr<Node> &a, const shared_ptr<Node> &b) {
    return a->freq > b->freq;
  };
  priority_queue<shared_ptr<Node>, vector<shared_ptr<Node>>, decltype(cmp)> Q(cmp);
  for (const auto &p : freq) {
    Q.emplace(make_shared<Node>(p.first, p.second));
  }
  while (Q.size() > 1) {
    auto left = Q.top();
    Q.pop();
    auto right = Q.top();
    Q.pop();
    auto parent = make_shared<Node>('\0', left->freq + right->freq);
    parent->left = left;
    parent->right = right;
    Q.emplace(parent);
  }
  return Q.top();
}
# 哈夫曼编码的正确性


# 哈夫曼编码的贪心选择性质


设xx 和yy 是字符集CC 中具有最小频率的两个字符，证明存在CC 的最优前缀码使xx 和yy 具有最长、相同的码长且仅最后一位编码不同。​

证明：​设二叉树TT 表示CC 的任意一个最优前缀码方案。只要证明可以对TT 做适当修改后，得到一棵新的二叉树T′T'，新树中，xx 和yy 是最深叶子且为兄弟。​

同时，新树也是CC 的最优前缀码方案。​

picture 6


B(T)−B(T′)=∑c∈Cf(c)dT(c)−∑c∈Cf(c)dT′(c)=f(x)dT(x)+f(b)dT(b)−f(x)dT′(x)−f(b)dT′(b)=f(x)dT(x)+f(b)dT(b)−f(x)dT(b)−f(b)dT(x)=(f(b)−f(x))(dT(b)−dT(x))≥0\begin{align*}
B(T) - B(T') &= \sum\limits_{c\in C}f(c)d_T(c) - \sum\limits_{c\in C}f(c)d_{T'}(c)\\
&= f(x)d_T(x) + f(b)d_T(b) - f(x)d_{T'}(x) - f(b)d_{T'}(b)\\
&= f(x)d_T(x) + f(b)d_T(b) - f(x)d_{T}(b) - f(b)d_{T}(x)\\
&= (f(b) - f(x))(d_T(b) - d_T(x)) \geq 0
\end{align*}



同理，B(T′)−B(T′′)≥0B(T') - B(T'') \geq 0，所以B(T)≥B(T′)≥B(T′′)B(T) \geq B(T') \geq B(T'')，又因为TT 是最优前缀码方案，所以B(T)=B(T′)B(T) = B(T')，所以T′T' 也是最优前缀码方案。


# 哈夫曼编码的最优子结构性质


设TT 表示CC 的一个最优前缀码方案。xx 和yy 是树TT 中的叶子节点且为兄弟。zz 是它们的父亲。


若将zz 看做是具有频率f(z)=f(x)+f(y)f(z)=f(x)+f(y) 的字符，


则证明树T′=T−{x,y}T'=T-\{x,y\} 表示字符集C′=C−{x,y}∪{z}C'=C-\{x,y\} \cup \{z\} 的一个最优前缀码即可。


证明：首先证明TT 的平均码长B(T)B(T) 可用B(T′)B(T') 表示。

对任意字符c∈C−{x,y}c\in C-\{x,y\}，有dT(c)=dT′(c)d_{T}(c) = d_{T'}(c)，故f(c)dT(c)=f(c)dT′(c)f(c)d_{T}(c) = f(c)d_{T'}(c)。

另一方面，dT(x)=dT(y)=dT′(z)+1d_{T}(x) = d_T(y) = d_{T'}(z) + 1，

故


f(x)dT(x)+f(y)dT(y)=(f(x)+f(y))(dT′(z)+1)=f(x)+f(y)f(z)dT′(z)\begin{align*}
  f(x)d_{T}(x) + f(y)d_{T}(y) &= (f(x)+f(y))(d_{T'}(z)+1) \\
  &=f(x) + f(y)f(z)d_{T'}(z)
\end{align*}



若T′T' 不是C′C' 的最优前缀码方案，则存在另一棵树T′′T''，使得B(T′′)<B(T′)B(T'') < B(T')。由于zz 被看作C′C' 中的一个字符，故zz 在T′′T'' 中是一个叶子节点，若将xx 和yy 加入树T′′T''，则得到一个新树T′′′T'''，且有


B(T′′′)=B(T′′)+f(x)+f(y)<B(T′)+f(x)+f(y)=B(T)\begin{align*}
  B(T''') &= B(T'') + f(x) + f(y) \\
  &< B(T') + f(x) + f(y) = B(T)
\end{align*}



这与TT 是最优前缀码方案矛盾，所以T′T' 是C′C' 的最优前缀码方案。


# 回溯法


# 问题的解空间树


解空间树是一个有根树，其每个节点对应于问题的一个解，树的根节点对应于问题的初始状态，叶节点对应于问题的一个解。


picture 7


# 回溯法的基本思想


回溯法从根结点出发，以深度优先的方式搜索解空间树。


    

  • 活结点：自身已生成但其儿子还没有全部生成
    • 

  • 扩展结点：正在产生其儿子的结点
    • 

  • 死结点：不满足约束条件或所有儿子已经产生的，不能向纵深方向移动的结点
    • 



picture 8


# 回溯法的步骤


    

  1. 针对所给问题，定义问题的解空间；​
    2. 

  2. 确定易于搜索的解空间结构；子集树，排列树​
    3. 

  3. 以深度优先方式搜索解空间，并在搜索​过程中用剪枝函数避免无效搜索。
    4. 



# 回溯法的解空间树构造


# 子集树


当所给问题是从nn 个元素的集合SS 中找出满足某种性质的子集时，解空间树是一个有根树，其每个节点对应于SS 的一个子集。


满足所有约束条件的解状态结点称为回答结点。


# 排列树


当所给问题是从nn 个元素的集合SS 中找出满足某种性质的排列时，解空间树是一个有根树，其每个节点对应于SS 的一个排列。


树中从根至叶结点的路径的集合构成解空间。树的每一个叶结点称为一个解状态。


# 解空间树的剪枝策略


    

  • 用约束函数在扩展结点处剪去不满足约束的子树；​
    • 

  • 用限界函数剪去得不到最优解的子树。
    • 



# 回溯法的递归回溯


# 子集树的回溯法


//t 表示当前扩展结点的深度
void Backtrack(int t) {
  if (t > n) {
    Output(x);
  } else {
    //f (n,t),g (n,t) 分别表示在当前扩展结点处未搜索过的
    // 子树的起始编号和终止编号​
    for (int i = f(n, t); i <= g(n, t); i++) {
      //h (i) 表示在当前扩展节点处 x [t] 的第 i 个可选值​
      x[t] = h(i);
      // Constraint (t) 和 Bound (t) 表示当前扩展节点处
      // 的约束函数和限界函数​
      if (Constraint(t) && Bound(t)) {
        Backtrack(t + 1);
      }
    }
  }
}
# 排列树的回溯法


// 调用 Backtrack (1) 开始搜索前，需要初始化 x [1:n]​为 1:n
void Backtrack(int t) {
  if (t > n) {
    Output(x);
  } else {
    for (int i = t; i <= n; i++) {
      swap(x[t], x[i]);
      if (Constraint(t) && Bound(t)) {
        Backtrack(t + 1);
      }
      swap(x[t], x[i]);
    }
  }
}
# 回溯法的迭代回溯


void IterativeBacktrack() {
  int t = 1;
  while (t > 0) {
    if (f(n, t) <= g(n, t)) {
      for (int i = f(n, t); i <= g(n, t); i++) {
        x[t] = h(i);
        if (Constraint(t) && Bound(t)) {
          if (Solution(t)) {
            Output(x);
          } else {
            t++;
          }
        }
      }
    } else {
      t--;
    }
  }
}
# 旅行商问题


某旅行商要访问nn 个城市，从城市11 出发，经过每个城市一次，最后回到城市11。每两个城市之间有一条道路，旅行商要选择一条路径，使得总路程最短。


picture 9


# 旅行商问题的解空间树


旅行商问题的解空间树是一个有根树，从根节点出发到叶节点的路径对应于旅行商的一条路径。


picture 10


# 装载问题


nn 个集装箱要装上 2 艘载重量分别为C1C_1 和C2C_2 的轮船，其中第ii 个集装箱的重量为wiw_i。装载问题是找出尽可能多的集装箱装上轮船。


若装载问题有解，采用如下策略可得一个最优装载方案:​


    

  1. 将第一艘轮船尽可能装满；​
    2. 

  2. 剩余的货箱装到第二艘轮船上。
    3. 



将第一艘船尽可能装满等价于如下 0-l 背包问题:​


{max⁡∑i=1nxis.t.∑i=1nwixi≤C1xi∈{0,1}i=1,2,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=1}^{n}x_i\\
  s.t. & \sum\limits_{i=1}^{n}w_ix_i \leq C_1\\
  & x_i\in\{0,1\} & i=1,2,\cdots,n
\end{cases}



# 装载问题的算法设计


template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {}
};
template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    bestw = max(bestw, cw);
    return;
  }
  // 搜索子树
  if (cw + w[i] <= c) {// 左子树 (装入第 i 个集装箱)
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  // 右子树 (不装入第 i 个集装箱)
  Backtrack(i + 1);
}
template <typename T>
T MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestw;
}
# 上界函数 - 解决右子树剪枝问题​


template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
    T r; // 剩余集装箱重量
  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {
      r = accumulate(w.begin(), w.end(), 0);
    }
};
template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    bestw = cw;
    return;
  }
  // 计算剩余集装箱重量
  r -= w[i];
  if (cw + w[i] <= c && cw + r > bestw) {// 左子树 (装入第 i 个集装箱)
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  if (cw + r > bestw) {// 右子树 (不装入第 i 个集装箱)
    Backtrack(i + 1);
  }
  r += w[i];
}
template <typename T>
T MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestw;
}
# 构造最优解 - 装载问题的回溯算法​


template <typename T>
class Loading {
  private:
    void Backtrack(int i);
    vector<int> x; // 当前解
    vector<int> bestx; // 当前最优解
    vector<T> w; // 集装箱重量
    T c; // 轮船载重量
    T cw; // 当前载重量
    T bestw; // 当前最优载重量
    T r; // 剩余集装箱重量
  public:
    Loading() : cw(0), bestw(0) {}
    Loading(const vector<T> &ww, const T cc) : w(ww), c(cc), cw(0), bestw(0) {
      r = accumulate(w.begin(), w.end(), 0);
      x.resize(w.size() + 1);
      bestx.resize(w.size() + 1);
    }
};
template <typename T>
void Loading<T>::Backtrack(int i) {
  if (i > w.size()) {
    if (cw > bestw) {
      for (int j = 1; j <= w.size(); j++) {
        bestx[j] = x[j];
      }
      bestw = cw;
    }
    return;
  }
  r -= w[i];
  if (cw + w[i] <= c && cw + r > bestw) {
    x[i] = 1;
    cw += w[i];
    Backtrack(i + 1);
    cw -= w[i];
  }
  if (cw + r > bestw) {
    x[i] = 0;
    Backtrack(i + 1);
  }
  r += w[i];
}
template <typename T>
vector<int> MaxLoading(const vector<T> w, const T c) {
  Loading<T> X(w, c);
  X.Backtrack(1);
  return X.bestx;
}
# 0/1 背包问题


给定nn 个物品，每个物品的重量为wiw_i，价值为viv_i，背包的容量为cc，求如何装入背包使得背包中物品的总价值最大。


0-1 背包问题属于找最优解问题，适合于用子集树表示 0-1 背包问题的解空间。在搜索解空间树时​


    

  • 只要左儿子节点是一个可行结点，搜索就进入左子树。(约束剪枝)​∑i=1nwixi≤c\sum\limits_{i=1}^{n}w_ix_i \leq c​
    
​- 在右子树中有可能包含最优解是才进入右子树搜索，否则将右子树剪去（限界剪枝）。​
    • 



# 限界函数


设当前位于状态空间树的结点 XX 处，已考察 kk 个物品。


背包中的当前物品总重量为 cwcw，背包中的当前物品总价值为 cpcp。


背包的载重量为 cc，则剩余载重是 c−cwc - cw。


使用贪心法，计算以剩余载重和剩余物品构成的一般背包问题的最优解值，设该最大收益为 rprp。


bp=cp+rpbp = cp + rp，作为以 XX 为根的子树上所有可能的答案结点的目标函数值的上界。


# 0/1 背包问题的回溯算法


void Backtrack(int i) {
  if (i > n) {
    bestp = cp;
  }
  if (cw + w[i] <= c) { // 左子树
    cw += w[i];
    cp += p[i];
    Backtrack(i + 1);
    cw -= w[i];
    cp -= p[i];
  }
  if (Bound(i + 1) > bestp) { // 右子树
    Backtrack(i + 1);
  }
}
int Bound(int i) {
  int cleft = c - cw;
  int b = cp;
  // 以物品单位价值递减的顺序装入物品（已经排序完成）
  while (i <= n && w[i] <= cleft) {
    cleft -= w[i];
    b += p[i];
    i++;
  }
  if (i <= n) { // 装入部分物品
    b += p[i] / w[i] * cleft;
  }
  return b;
}
# 最大团问题


给定无向图 G=(V,E)G=(V,E)，如果 U⊆VU \subseteq V，且对任意 u,v∈Uu,v \in U，(u,v)∈E(u,v) \in E，则称 UU 是图 GG 的完全子图。GG 的完全子图 UU 是 GG 的一个团当且仅当 UU 不包含在 GG 的更大的完全子图中。GG 的最大团是指 GG 中所含顶点数最多的团。


picture 11


在图中的无向图 GG 中，子集 {1,2}\{1,2\} 是 GG 的大小为 2 的完全子图。这个完全子图不是团，因为它被 GG 的更大的完全子图 {1,2,5}\{1,2,5\} 包含。{1,2,5}\{1,2,5\} 是 GG 的最大团。{1,4,5}\{1,4,5\} 和 {2,3,5}\{2,3,5\} 也是 GG 的最大团。


如果 U⊆VU \subseteq V，且对任意 u,v∈Uu,v \in U，(u,v)∉E(u,v) \notin E，则称 UU 是图 GG 的空子图。GG 的空子图 UU 是 GG 的一个独立集当且仅当 UU 不包含在 GG 的更大的空子图中。GG 的最大独立集是指 GG 中所含顶点数最多的独立集。


对于任意无向图 GG，其补图 G‾=(V1,E1)\overline{G} = (V_1, E_1) 定义为 V1=VV_1 = V，E1={(u,v)∣u,v∈V,(u,v)∉E}E_1 = \{(u,v) | u,v \in V, (u,v) \notin E\}。GG 的最大独立集是 G‾\overline{G} 的最大团。


# 最大团问题的算法设计


可以用子集树表示问题的解空间。解最大团问题的回溯法与解装载问题的回溯法十分相似。设当前扩展结点 Z  位于解空间树的第 i  层。在进入左子树前，必须确认从顶点 i  到已选入的顶点集中每个顶点都有边相连。在进入右子树前，必须确认还有足够多的可选择顶点，使得算法有可能在右子树中找到更大的团。

整型数组 v  返回所找到的最大团。 v[i]=1  当且仅当顶点 i  属于找到的最大团。


class Clique {
  private:
    vector<vector<int>> a; // 图的邻接矩阵
    vector<int> x; // 当前解
    int cn; // 当前团的顶点数
    int bestn; // 当前最优团的顶点数
    int n; // 图的顶点数
  public:
    void Backtrack(int i);
    Clique() : cn(0), bestn(0) {}
    Clique(const vector<vector<int>> &aa) : a(aa), n(aa.size()) {
      x.resize(n + 1);
      bestx.resize(n + 1);
    }
    vector<int> bestx; // 当前最优解
};
void Clique::Backtrack(int i) {
  if (i > n) {
    for (int j = 1; j <= n; j++) {
      bestx[j] = x[j];
    }
    bestn = cn;
    return;
  }
  bool ok = true;
  for (int j = 1; j < i; j++) {
    if (x[j] && !a[i][j]) {
      ok = false;
      break;
    }
  }
  if (ok) {
    x[i] = 1;
    cn++;
    Backtrack(i + 1);
    x[i] = 0;
    cn--;
  }
  if (cn + n - i > bestn) {
    x[i] = 0;
    Backtrack(i + 1);
  }
}
vector<int> MaxClique(const vector<vector<int>> &a) {
  Clique X(a);
  X.Backtrack(1);
  return X.bestx;
}
# 图的着色


给定无向连通图 GG 和 mm 种不同的颜色。用这些颜色为图 GG 的各顶点着色，每个顶点着一种颜色。是否有一种着色法，使 GG 中每条边的 22 个顶点着有不同颜色？这个问题是图的 mm 可着色判定问题。若一个图最少需要 mm 种颜色才能使图中每条边连接的 22 个顶点着不同颜色，则称这个数 mm 为该图的色数。求一个图的色数 mm 的问题称为图的 mm 可着色优化问题。


如果一个图的所有顶点和边都能用某种方式画在平面上且没有任何两边相交，则称这个图是可平面图。著名的平面图的四色猜想是图的 mm 可着色性判定问题的特殊情形。


# 图的着色问题的算法设计


采用 nn - 元组 (x0,x1,…,xn−1)(x_0, x_1, \dots, x_{n-1}) 表示图 GG 的 mm - 着色判定问题的解，并采用邻接矩阵表示无向图 G=(V,E)G=(V,E)。​


a[i][j]={1如果(i,j)∈E0其他a[i][j] = \begin{cases}
  1 & \text{如果} (i,j) \in E\\
  0 & \text{其他}
\end{cases}



    

  • 显式约束：nn - 元组 (x0,x1,…,xn−1)(x_0, x_1, \dots, x_{n-1})，xi∈{1，…，m}x_i \in \{1，\dots，m\}，0≤i<n0 \leq i < n，表示结点 ii 的颜色。xi=0x_i=0 表示没有可用的颜色。因此解空间的大小为 mnm^n。​
    • 

  • 隐式约束：如果边 (i,j)∈E(i,j) \in E，则 xi≠xjx_i \ne x_j。​
    • 



约束函数：对所有ii 和jj，0≤i,j<k0 \leq i,j < k，i≠ji \neq j，若a[i][j]=1a[i][j]=1，则xi≠xjx_i \neq x_j。（1≤xi,xj≤m1 \leq x_i,x_j \leq m）

​

限界函数：对于当前解(x0,x1,…,xn−1)(x_0, x_1, \dots, x_{n-1})，如果已经着色的顶点数为kk，则剩余未着色的顶点数为n−kn-k，则最多需要m−km-k 种颜色。如果m−k=0m-k=0，则当前解是可行解，否则当前解是一个可行解的上界。


class Color {
private:
    bool Ok(int k);
    vector<vector<int>> a; // 图的邻接矩阵
    vector<int> x; // 当前解
    int n; // 图的顶点数
    int m; // 颜色数
    long long sum; // 当前已找到的可 m 着色方案数
public:
    void Backtrack(int i);
    Color() : sum(0) {}
    Color(vector<vector<int>> &&aa, int mm) : a(aa), m(mm), n(aa.size()), sum(0) { x.resize(n); }
    long long GetSum() { return sum; }
};
bool Color::Ok(int k) {
    for (int i = 0; i < k; i++) {
        if (a[k][i] && x[i] == x[k]) {
            return false;
        }
    }
    return true;
}
void Color::Backtrack(int i) {
    if (i > n) {
        sum++;
        for (int j = 0; j < n; j++) {
            cout << x[j] << " ";
        }
        cout << endl;
    } else {
        for (int j = 1; j <= m; j++) {
            x[i] = j;
            if (Ok(i)) {
                Backtrack(i + 1);
            }
            //x[i] = 0;
        }
    }
}
int mColoring(vector<vector<int>> &&a, int m) {
    Color X(std::move(a), m);
    X.Backtrack(0);
    return X.GetSum();
}
# n 皇后问题


在 n×nn \times n 的棋盘上放置 nn 个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。求所有可能的放置方案。


    

  • 确定问题状态：问题的状态即棋盘的布局状态。​
    • 

  • 构造状态空间树：状态空间树的根为空棋盘，每个布局的下一步可能布局是该布局结点的子结点。​
    • 



由于可以预知，在每行中有且只有一个皇后，因此可采用逐行布局的方式，即每个布局有 n 个子结点。​


picture 12


# n 皇后问题的算法设计


将棋盘从左至右，从上到下编号为1,…,n1,\dots,n，皇后编号为1,…,n1,\dots,n。 ​

设解为(x1,…,xn)(x_1, \dots, x_n)，xix_i 为皇后ii 的列号，且xix_i 位于第ii 行。

解空间：E={(x1,...,xn)∣xi∈Si,i=1,...,n}E=\{(x_1,..., x_n) \mid x_i \in S_i, i=1,...,n\}，Si={1,...,n}S_i=\{1, ..., n\}，1≤i≤n1 \leq i \leq n

 解空间为排列树。

其约束集合DD 为


    

  1. xi≠xjx_i \neq x_j
    2. 

  2. xi−i≠xj−jx_i - i \neq x_j - j
    3. 

  3. xi+i≠xj+jx_i + i \neq x_j + j
    4. 



class Queen {
private:
    vector<int> x; // 当前解
    int n; // 皇后个数
    long long sum; // 当前已找到的可行方案数
    bool place(int k);
public:
    void Backtrack(int t);
    Queen() : sum(0) {}
    Queen(int nn) : n(nn), sum(0) { x.resize(n + 1); }
    long long GetSum() { return sum; }
};
bool Queen::place(int k) {
    for (int j = 1; j < k; j++) {
        if (abs(k - j) == abs(x[j] - x[k]) || x[j] == x[k]) {
            return false;
        }
    }
    return true;
}
void Queen::Backtrack(int t) {
    if (t > n) {
        sum++;
        for (int i = 1; i <= n; i++) {
            cout << x[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = 1; i <= n; i++) {
            x[t] = i;
            if (place(t)) {
                Backtrack(t + 1);
            }
        }
    }
}
int nQueen(int n) {
    Queen X(n);
    X.Backtrack(1);
    return X.GetSum();
}
# 分支限界法


# 分支限界法的基本思想


分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法的主要区别在于它们对当前扩展结点所采用的扩展方式不同。在分支限界法中，每个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。最常见的有以下两

种方式。


# 队列式分支限界法


队列式分支限界法将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点为当前扩展结点。




叶子结点不能加入队列，因为叶子结点没有儿子结点。叶子结点是问题的一个解，应该直接输出。




# 优先队列式分支限界法


优先队列式的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。

优先队列中规定的结点优先级常用一个与该结点相关的数值 p  来表示。结点优先级的高低与 p  值的大小相关。

最大优先队列规定 p  值较大的结点优先级较高。在算法实现时，通常用最大堆来实现最大优先队列，用最大堆的  Deletemax  运算抽取堆中下一个结点成当前扩展结点，体现最大效益优先的原则。

类似地，最小优先队列规定 p  值较小的结点优先级较高。在算法实现时，通常用最小堆来实现最小优先队列，用最小堆的  Deletemin  运算抽取堆中下一个结点成为当前扩展结点，体现最小费用优先的原则。


# 活结点表


每个活结点只有一次机会成为扩展结点，一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。