五、贪心算法

1.基本原理

(1)基本概念

  • 分步骤实施，它在每一步仅作出当时看起来最佳的选择，即局部最优的选择，并寄希望这样的选择最终能导致全局最优解。
  • 实例：最小生成树问题的$ Prim $算法、$ Kruskal $算法，单源最短路径$ Dijkstra $算法，分数背包。
  • 贪心算法不总能对所有问题能求解，只是对一些问题确实有效，可以求出最优解或近似最优解。

(2)贪心算法的步骤

  • 提出贪心策略：观察问题特征，构造贪心选择；

  • 证明策略正确：假设最优方案，通过替换证明。

    对应每个贪心算法，都有一个动态规划算法，但动态规划算法要繁琐的多。

(3)贪心选择性质

可以通过做出局部最优（贪心）选择来构造全局最优解的性质。

贪心选择性使得我们进行选择时， 只需做出当前看起来最优的选择，而不用考虑子问题的解。

2.活动选择问题

(1)问题描述

  • 假定有一个活动的集合$ S $​含有$ n $​个活动$ {a_1,a_2,\dots,a_n} $​，每个活动$ a_i $​都有一个开始时间$ s_i $​和结束时间$ f_i $​且$ 0\leq s_i\lt f_i\lt\infty $。同时，这些活动都要使用同一资源(如演讲会场)，而这个资源在任何时刻只能供一个活动使用。

  • 活动的兼容性：如果选择了活动$ a_i $，则它在半开时间区间 $ [s_i, f_i) $内占用资源。若两个活动$ a_i $和$ a_j $满足$ [s_i, f_i) $与区间$ [s_j, f_j) $不重叠，则称它们是兼容的。

  • 活动选择问题：假设活动按照结束时间单调递增排序，对给定的包含$ n $个活动的集合$ S $，在已知每个活动开始时间和结束时间的条件下，从中选出最多可兼容活动的子集合，称为最大兼容活动集合。

    考虑下列活动集合$ S $：

(2)问题分析

  • 设$ S_{ij} $表示在$ a_i $结束之后开始且在$ a_j $开始之前结束的活动集合，$ A_{ij} $表示$ S_{ij} $的一个最大兼容活动子集，设$ A_{ij} $包括活动$ a_k $，则得到两个子问题——寻找$ S_{ik} $和$ S_{kj} $的最大兼容活动集合。

    图解如下：

  • 必有：$ A_{ik} $是$ S_{ik} $一个最大兼容活动子集，$ A_{kj} $是$ S_{kj} $一个最大兼容活动子集。

    $ A_{ij}=A_{ik}∪{a_k}∪A_{kj} $

  • 令$ c[i,j] $表示集合$ S_{ij} $的最优解大小，可使用动态规划方法解决

(3)贪心算法

  • 每次总选择具有最早结束时间的兼容活动加入到集合$ A $中——使剩余的可安排时间段最大化，以便安排尽可能多的兼容活动。

  • 当输入的活动已按结束时间的递增顺序排列，贪心算法只需$ O(n) $的时间即可选择出来$ n $个活动的最大兼容活动集合。

    考虑任意非空子问题$ S_k $，令$ a_m $是$ S_k $中结束时间最早的活动，则$ a_m $必在$ S_k $的某个最大兼容活动子集中。

  • 自顶向下的递归方法

    首先做出一个选择，然后求解剩下的子问题。每次选择将问题转化成一个规模更小的问题。

    伪代码如下：

    第$ 2\thicksim 3 $行查找$ S_k $中最早结束的活动，循环检查$ a_{k+1},a_{k+2},\dots,a_n $，直至找到第一个与$ a_k $兼容的活动$ a_m $，也即满足$ s_m\geq f_k $。

    如果成功找到$ m $（也即$ m\leq n $），则返回$ {a_m} $与$ RECURSIVE-ACTIVITY-SELECTOR(s,f,m,n) $返回的$ S_m $的最大子集的并集。

    如果未成功找到$ m $，则说明未找到与$ a_k $兼容的活动，则返回$ \Phi $。

  • 迭代实现的贪心算法

    伪代码如下：

    $ k $对应最后一个加入$ A $的活动，$ f_k $是$ A $中活动的最大结束时间，若$ m $的开始时间大于$ f_k $，则$ m $就是下一个被选中的活动。

    算法的运行时间是$ O(n) $。

3.带权活动选择问题

(1)问题描述

  • 在活动选择问题中，如果每个活动都具有权重$ w $，现寻找活动子集$ S' $，使得权重和最大

(2)问题分析

  • 存在重叠子问题，可以使用动态规划求解
  • 设$ p[i] $表示在$ a_i $开始前最后结束的活动编号
  • 设$ Rec[i] $表示是否选择问题$ i $
  • 设$ D[i] $表示集合$ \{a_1,a_2,a_3,\dots,a_i\} $中兼容活动最大权重和
  • 将活动按照结束时间升序进行排序，则可得到$ D[i]=max\{D[p[i]]+w_i,D[i-1]\} $；其中不选择$ a_i $时，其最大权重和即为$ D[i-1] $，选择$ a[i] $时，其最大权重和应为在$ a_i $开始前最后结束的活动编号对应的最大权重和加上$ w_i $，即$ D[p[i]]+w_i $。

(3)动态规划

  • 伪代码如下

  • 时间复杂度为$ O(n\log n) $

4.$ Huffman $编码

(1)基本概念

  • 码字：每个字符用唯一的二进制串表示，称为码字。

  • 定长编码：每个字符的编码长度一样。

    对于$ a\thicksim f $六个字符，应采用3位码字编码，则10万个字符需用30万个二进制位编码。

  • 变长编码：每个字符赋予不同长度的码字。

    赋予高频字符短码字，低频字符长码字，字符的码字互不为前缀，这样才能唯一解码，同时能够提高编码效率。如$ a $用1位的串0表示，$ b $用3位的串101表示，$ f $用4位的串1100表示等。

  • 前缀码$ (Prefix code) $：任何码字都不是其它码字的前缀。

    前缀码可以简化解码过程，由于没有码字是其它码字的前缀，所以编码文件的开始部分是没有歧义的，可以唯一地转换回原字符。

  • 编码树：一种为表示字符二进制编码而构造的二叉树。

    叶子结点：对应给定的字符，每个字符对应一个叶子结点。

    编码构造：字符的二进制码字由根结点到该字符叶子结点的简单路径

    路径表示：0代表转向左孩子，1代表转向右孩子

  • 最优字符编码方案总对应一棵满二叉树， 即每个非叶子结点都有两个孩子结点。

(2)最优字符编码方案

  • 符号表示

    • 设$ C $为字母表

      对字母表$ C $中的任意字符$ c $，令属性$ c.freq $表示字符$ c $在文件中出现的频率

      最优前缀码对应的树中恰好有$ \vert C\vert $个叶子结点，每个叶子结点对应字母表中的一个字符，且恰有$ \vert C\vert-1 $个内部结点。

    • 设$ T $表示一棵前缀编码树

    • 设$ d_T(c) $表示c的叶子结点在树T中的深度（根到叶子结点的路径长度）

      $ d_T(c) $也表示字符$ c $的码字长度

    • 设$ B(T) $表示采用$ T $编码时的文件编码长度，即$ B(T)=\sum\limits_{c\in C}c.freq\cdot d_T(c) $，称$ B(T) $为T的代价。

      使得$ B(T) $最小的编码称为最优编码。

      对给定的字符集和文件，$ Huffman $编码是一种最优编码。

(3)$ Huffman $编码

  • 算法$ HUFFMAN $从$ \vert C\vert $个叶子结点开始，每次选择频率最低的两个结点合并，将得到的新结点加入集合继续合并，这样执行$ \vert C\vert-1 $次合并后即可构造出一棵编码树——$ Huffman $树。

    伪代码如下：

    第2行用$ C $中字符初始化最小优先队列$ Q $；

    第$ 3\thicksim 8 $行的循环反复从队列中合并频率最低的结点$ x $和$ y $，合并为新结点$ z $并替代之；

    经过$ n-1 $次合并后，最后返回剩下的唯一结点——编码树的根结点

    示例如下：

  • 时间复杂度的分析

    • 假设$ Q $使用最小二叉堆实现，则其初始化花费$ O(n) $的时间

    • 循环的总代价是$ O(n\lg n) $

      $ for $循环共执行了$ n-1 $次，每次从堆中找出当前频率最小的两个结 点及把合并得到的新结点插入到堆中均花费$ O(\lg n) $，所以循环的总代价是$ O(n\lg n) $。

    • 因此，$ HUFFMAN $的总运行时间$ O(n\lg n) $

  • ※$ Huffman $算法的正确性

    • 证明贪心选择性
    • 证明最优子结构性

5.分数背包问题

(1)问题描述

  • 已知$ n $个物品组成的集合O，每个物品有两个属性$ v_i $和$ p_i $，分别表示体积和价格；
  • 背包容量为$ C $；
  • 试求解$ S=\{x_i|1\leq i\leq n,0\leq x_i\leq 1\} $，使得$ max\sum\limits_{x_i\in S}x_ip_i $且$ \sum\limits_{x_i\in S}x_iv_i\leq C $。

(2)问题分析

  • 采用贪心算法，每次选择最高性价比($ p_i/v_i $)的物品，证明可得贪心解不劣于最优解

  • 伪代码如下

    $ FractionalKnapsack(n,p,v,C) $

    当背包未装满且商品未装完时填入商品，商品体积不大于容量则全部装入，否则装入部分商品填满背包

  • 算法复杂度为$ O(n\log n) $

六、基本图算法

1.基本概念

  • 图的定义

    图可以表示为一个二元组$ G=\langle V,E\rangle $

    相关术语：

    $ V $表示非空顶点集，其元素称为顶点(Vertex) ，$ \vert V\vert $表示顶点数； $ E $表示边集，其元素称为边(Edge)，$ \vert E $表示顶点数 ； $ e=(u,v) $表示一条边，其中$ u\in V,v\in V,e\in E $；

    相邻$ (Adjacent) $：边$ (u,v) $连接的顶点$ u $和$ v $相邻；

    关联$ (Incident) $：边$ (u,v) $和其连接的顶点$ u(or\,\,v) $相互关联。

  • 相关数据结构

    • 子图：如果$ V'\subseteq V,E'\subseteq E $，则称图$ G'=\langle V',E'\rangle $为G的一个子图
    • 生成子图：如果$ V'=V,E'\subseteq E $，则称图$ G'=\langle V',E'\rangle $为G的一个生成子图
    • 树：连通、无环图$ T=\langle V_T,E_T\rangle $，树有$ \vert V_T\vert-1 $条边
    • 森林：一至多棵树组成的无环图

  • 图的表示

    • 邻接表
      • 邻接表是一个包含$ \vert V\vert $条链表的数组$ Adj $；
      • 在$ Adj $中，每个结点$ u\in V $有一条链表$ Adj[u] $，包含所有与结点$ u $之间有边相连的结点$ v $；
      • 用$ G.Adj[u] $表示结点$ u $在邻接表$ Adj $中的邻接链表；
      • 稀疏图一般用邻接表表示；
      • 可用于表示有向图也可用于表示无向图，空间需求均为$ O(V+E) $。
    • 邻接矩阵
      • 将图$ G $中的结点编号为$ 1,2,\dots,\vert V\vert $，则图$ G $的邻接矩阵是一个$ \vert V\vert\times\vert V\vert $的矩阵$ A=(a_{ij}) $；
      • 当$ (i,j)\in E $，$ a_{ij}=1 $；否则$ a_{ij}=0 $；
      • 稠密图更倾向于用邻接矩阵表示；
      • 可以快速判断任意两个结点之间是否有边相连，空间需求为$ O(V^2) $。
    • 权重图
      • 权重值通常以权重函数$ \omega:E\to R $给出；
      • 用邻接表表示权重图：
        • 将边$ (u,v)\in E $的权重值$ ω(u,v) $存放在$ u $的邻接链表结点中, 作为其属性。
      • 用邻接矩阵表示权重图：
        • 对于边$ (u,v)\in E $，令邻接矩阵$ A[u][v]=ω(u,v) $；
        • 若$ (u,v) $不是$ E $中的边，则令$ A[u][v]=NIL $，或$ \infty $、0。

2.图的搜索与周游

(1)宽度优先搜索与周游

①宽度优先搜索

  • 算法过程描述

    • 从结点$ v $开始，首先访问结点$ v $，给$ v $标上已访问标记；
    • 访问邻接于$ v $且目前尚未被访问的所有结点，此时结点$ v $被检测，而$ v $的邻接结点是新的未被检测结点。将这些结点依次放置到一个称为未检测结点表的队列(Q)中；
    • 若未检测结点表为空，则算法终止；
    • 否则取Q的表头作为下一个检测结点，重复上述过程。直到$ Q $为空，算法终止。

  • 算法伪代码

  • 复杂度分析

    • 空间复杂度：$ s(V,E)=\Theta(n) $
    • 采用邻接表的时间复杂度：$ t(V,E)=O(n+e) $
    • 采用邻接矩阵的时间复杂度：$ t(V,E)=O(n^2) $
②宽度优先周游

  • 若$ G $是无向连通图或强连通有向图，则一次调用$ BFS $即可完成对$ G $的周游。否则，需要多次调用$ BFS $

  • 算法伪代码

③宽度优先生成树

  • 向前边：$ BFS $中由$ u $到达未访问结点$ w $的边$ (u,w) $称为向前边。

  • 宽度优先生成树： 记$ T $是$ BFS $中处理的所有向前边集合。若$ G $是连通图，则$ BFS $终止时，$ T $构成一棵生成树，称为图$ G $的宽度优先生成树。

  • 对于图$ G=(V,E) $和源结点$ s $，定义图$ G $的前驱子图为$ G_\pi=(V_\pi,E_\pi) $，其中$ V_\pi=\{v\in V:v.\pi\ne NIL\}\cup\{s\} $，$ E_\pi=\{(v.\pi,v):v\in V_\pi-\{s\}\} $。该前驱子图构成一棵广度优先树。

(2)深度优先搜索与周游

①深度优先搜索

  • 算法过程描述

    • 从结点$ v $开始，首先访问$ v $， 给$ v $标上已访问标记；
    • 然后中止对$ v $的检测，并从邻接于$ v $且尚未被访问的结点的中找出一个结点$ w $开始新的检测；
    • 在$ w $被检测后，再恢复对$ v $的检测。当所有可到达的结点全部被检测完毕后，算法终止

  • 算法伪代码

  • 复杂度分析

    • 运行时间为$ \Theta(V+E) $
②深度优先周游

  • 算法伪代码

(3)深度检索

  • 改造$ BFS $算法，用栈来保存未被检测的结点

3.回溯法

(1)$ n $-皇后问题

(2)子集和问题

4.分支-限界法

(1)$ n $-皇后问题

(2)子集和问题

七、最小生成树

1.问题背景

  • 生成树(Spanning Tree)
    • 图$ T’=\langle V’,E’\rangle $是无向图$ G\langle V,E,W\rangle $的一个生成子图，并且是连通、无环路的(树)
    • 权重最小的生成树可能不唯一

2.通用框架

  • 新建一个空边集$ A $，边集$ A $可逐步扩展为最小生成树

  • 每次向边集$ A $中新增加一条边，需保证边集$ A $仍是一个无环图，且仍是最小生成树的子集

    $ A $是某棵最小生成树$ T $边的子集，$ A\subseteq T $； $ A\cup\{(u,v)\} $仍是$ T $边的一个子集，则称$ (u,v) $是$ A $的安全边。

    若每次向边集$ A $中新增安全边，可保证边集$ A $是最小生成树的子集

  • $ Generic-MST(G) $

  • 为了有效辨识安全边，给出以下定义

    割：对于连通无向图$ G=\langle V,E\rangle $，割$ (S,V-S) $将顶点集$ V $划分为两部分

    给定割$ (S,V-S) $和边$ (u,v) $，$ u\in S,v\in V-S $，称边$ (u,v) $横跨割$ (S,V-S) $

    轻边：横跨割的所有边中，权重最小的称为横跨这个割的一条轻边

    如果一个边集$ A $中没有边横跨某割，则称该割不妨害边集$ A $

  • 安全边辨识定理

    给定图$ G=\langle V,E\rangle $是一个带权的连通无向图，令$ A $为边集$ E $的一个子集，且$ A $包含在图$ G $的某棵最小生成树中。若割$ (S,V-S) $是图$ G $中不妨害边集$ A $的任意割，且$ (u,v) $是横跨该割的轻边，则对于边集$ A $，边$ (u,v) $是其安全边。

  • 在算法推进的过程中，集合$ A $始终保持无环状态；算法执行的任意时刻，图$ G_A=(V,A) $是一个森林。对于安全边$ (u,v) $，由于$ A\cup\{(u,v)\} $必须无环，所以 $ (u,v) $连接的是$ G_A $中的两个不同连通分量。

3.$ Prim $算法

贪心策略：集合$ A $始终是一棵树，每次加入到$ A $中的安全边是连接$ A $和$ A $之外某个结点的边中权重最小的边。

  • 采用的数据结构：最小优先队列。

  • 步骤1：选择任意一个顶点，作为生成树的起始顶点

  • 步骤2：保持边集$ A $始终为一棵树，选择割$ (V_A,V-V_A) $

  • 步骤3：选择横跨割$ (V_A,V-V_A) $的轻边，添加到边集$ A $中

  • 步骤4：重复步骤2和步骤3，直至覆盖所有顶点

  • 伪代码：

    第$ 1\thicksim 5 $行将每个结点的$ key $值设为$ \infty $（除了根节点$ r $的$ key $值为0，以便其为第一个被处理的结点），将每个结点的父节点设为$ NIL $，并对最小优先队列$ Q $进行初始化；

    在每遍$ while $循环前，有

    • $ A=\{(v,v.\pi):v\in V-\{r\}-Q\} $
    • 已经加入到最小生成树的结点为集合$ V-Q $
    • 对于所有结点$ v\in Q $，如果$ v.\pi\ne NIL $，则$ v.key\lt \infty $且$ v.key $是连接结点$ v $和最小生成树中某个结点的轻边$ (v,v.\pi) $的权重。

    第7行找出结点$ u\in Q $，该结点是某条横跨割$ (V-Q,Q) $的轻边的一个端点，将$ u $从$ Q $中删除并将$ (u,u.\pi) $加入集合$ A $中；

    $ for $循环对与$ u $相邻却不在树中的结点$ v $的属性进行更新。

  • 优先队列

    • 采用二叉堆实现

    • 队列中每个元素有一个关键字，依据关键字大小离开队列

算法 说明 时间复杂度
$ INSERT() $ 向优先队列中插入元素 $ O(\log n) $
$ EXTRACT-MIN(Q) $ 移除优先队列中的最小元素 $ O(\log n) $
$ DECREASE-KEY(u,u.d) $ 更新距离数组，调整优先队列 $ O(\log n) $

  • 算法复杂度

    • 算法运行时间取决于$ Q $的实现方式，如果实现为二叉最小优先队列，则可以使用$ BUILD-MIN-HEAP $执行第$ 1\thicksim 5 $行，时间成本为$ O(V) $；
    • $ while $循环一共执行$ \vert V\vert $次，$ EXTRACT-MIN $需要时间成本为$ O(\lg V) $，$ for $循环执行次数为$ O(E) $，第11行隐藏$ DECREASE-KEY $操作，在二叉最小堆上执行时间成本为$ O(\lg V) $；
    • 总成本为$ O(E\lg V) $。

4.$ Kruskal $算法

贪心策略：集合$ A $始终是一个森林，开始时，其结点集就是$ G $的结点集，并且$ A $是所有单节点树构成的森林。之后每次加入到集合$ A $中的安全边是$ G $中连接$ A $的两个不同分量的权重最小的边。

  • 采用的数据结构：不相交集合。

  • 伪代码：

    第$ 1\thicksim 3 $行将$ A $初始化为空集，并创建$ \vert V\vert $棵树，每棵树只包含一个结点；

    第$ 5\thicksim 8 $行的$ for $循环按照权重从低到高的次序对每条边进行检查，如果不在同一棵树中，则加入到集合$ A $中，并将两棵树的结点进行合并。

    证明算法保证选择的边为安全边：

  • 不相交集合

    • $ MAKE-SET(v) $

      • 初始化集合：创建根结点，并设置一条指向自身的边

      • 时间复杂度为$ O(1) $

        1
        2
        x.parent=x
        return x
    • $ FIND-SET(v) $

      • 判定顶点是否在同一集合：回溯查找树根，检查树根是否相同

      • 时间复杂度为$ O(h) $，且$ \vert V\vert\geq 2^h $，则为$ O(\log\vert V\vert) $

        1
        2
        3
        4
        while x.parent ≠ x do
        	x=x.parent
        end
        return x
    • $ UNION(u,v) $

      • 合并两棵树

      • 时间复杂度为$ O(h) $，且$ \vert V\vert\geq 2^h $，则为$ O(\log\vert V\vert) $

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        a=FIND-SET(x)
        b=FIND-SET(y)
        if a.height ≤ b.height then
        	if a.height = b.height then
        		b.height=b.height+1
        	end
        	a.parent=b
        end
        else
        	b.parent=a
        end

  • 算法复杂度

    • 将边按照权重升序排序的时间成本为$ O(E\log E) $；
    • 建立不相交集合的时间成本为$ O(V) $；
    • $ while $循环进行了$ \vert E\vert $次，内部时间复杂度为$ O(\log V) $，也即$ while $循环总时间复杂度为$ O(E\log V) $；
    • 假设$ E=O(V^2) $，则总成本为$ O(E\lg V) $。

5.算法对比

Prim算法 Kruskal算法
核心思想 保持一颗树，不断扩展 子树森林，合并为一棵树
数据结构 优先队列 不相交集合
求解视角 微观视角，基于当前点选边 宏观视角，基于全局顺序选边
算法策略 采用贪心策略的图算法 采用贪心策略的图算法