算法导论整理

问题求解3算法导论整理

动态规划

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们成这样的解为问题的一个最优解，而不是最优解。

最优子结构：

问题的最优解由相关子问题的最优解构成，而这些子问题可以独立求解。

实现：

• 自顶向下的备忘算法（递归）
• 自底向上的动态规划算法（循环）

重构解

每一次记录下子问题的最优解的结构

解题思考过程

• 状态的表示
• 状态间的转移（转移方程）
• 解的表达
• 边界条件
• 计算顺序

例：

• 钢材切割问题（左边第一刀和右边剩下的）
• 矩阵链乘法
• 最长公共子序列问题（LCS）（考虑X和Y对后一个是否相等）
• 最优二叉搜索树（伪关键字）
• 最长递增子列（LIS）（LCS（A，SORT（A））；或者dp计算以A[i]结尾的子列的最大长度）

贪心

贪心算法每一步都作出当时看起来最佳的最优解，希望这样的选择能得到全局最优解。

最优子结构（同上）

贪心选择性质

我们可以通过做出局部最优（贪心）选择来构造全局最优。即进行选择的时候，我们直接作出在当前问题汇总看来最优的选择，而不必考虑子问题的解。

算法设计步骤

• 将最优化问题转化为这样的形式：对齐作出一次选择之后，只剩下一个子问题需要求解。
• 证明作出贪心选择后，原问题总是存在最优解，即贪心选择是安全的。（替换法）
• 证明作出贪心选择后，剩余的子问题满足性质：其最优解和贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

例：

• 活动选择问题（总是选择最早结束的）
• 分数背包问题（01背包问题不行）
• 赫夫曼编码（找当前频率最低的两个合成一个新的结点）

并查集

三个基本操作

• MAKE-SET(x)：建立一个新的集合，唯一成员（因而是代表）是x；
• UNION(x, y)：将包含x和y的两个动态几何合并为一个新的集合；
• FIND-SET(x)：返回一个指针，指向包含x的唯一集合的代表。

链表表示

每个链表有head和tail；

链表中每个成员有key，prev（指向head），next

时间复杂度：

• MAKE-SET O(1)
• FIND-SET O(1)
• UNION（简单实现） O(n)

简单加权合并启发式策略

• 将较小的链表挂到较大的链表上

不相交集合森林

使用有根树来表示集合。
每棵树表示一个集合，树的根结点是该集合的代表元。
执行UNION操作时将两棵树的树根合并。
实现时可以用到两种改进运行时间的启发式策略。

（一）按秩合并

类似链表的加权合并启发式策略。为了易于分析，对于每个结点，维护一个秩，表示该结点高度的一个上界。

UNION操作

• 如果根的秩不同，则让较大秩的根成为较小秩的根的父结点，但秩本身保持不变；
• 如果根的秩相同，则任意选择两个中的一个作为父结点，并使它的秩+1

（二）路径压缩

• 在FIND-SET操作中是查找路径中的每个结点直接指向根，不改变任何结点的秩。

伪代码：

    MAKE-SET(x)
    x.p = x
    x.rank = 0

    //摊还代价O(\alpha(n))
    FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

    UNION(x, y)
    LINK(FIND-SET(x), FIND-SET(y))

    //摊还代价O(\alpha(n))
    LINK(x, y)
    if(x.rank > y.rank)
        y.p = x
    else x.p = y
    if(x.rank == y.rank)
        y.rank ++

例：

• 确定无向图的连通分量

树

最小生成树问题

• 每个连通图都含有一个生成树。

• Kruskal算法：对于一个连通赋权图$G$，$G$的生成树$T$按下述方法构造：对于$T$的第一条边$e_1$，选择$G$的任一权值最小的边；对于$T$的第二条边$e_2$，在G剩下的边中选择权值最小的边；对于T的第三条边$e_3$，在$G$剩下的边中选择权值最小的边，且不与前面所选的边构成圈。继续这种做法，直至产生一个生成树。

    MST-KRUSKAL(G, w)
    A = empty set
    for each vertex v in G.V
        MAKE-SET(v)
    sort the edges of G.E into  nondecreasing order by weight w
    for each edge (u, v) in G.E, taken in nondecreasing order by weight
        if FIND-SET(v) != FIND-SET(u)
            A = A \cup {(u, v)}
            UNION(u, v)
    return A
  

• Prim算法：对于一个连通赋权图$G$，$G$的一个生成树$T$由下述方法构造：对于$G$的任一顶点$u$，选择与$u$关联的且权值最小的边作为$T$的第一条边$e_1$。对于接下来的边$e_2$, $e_3$, …, $e_{n-1}$，在与一条已选边只有一个公共顶点的所有边中选择权值最小的边。

    MST-PRIM(G, w, r)
    for each u in G.V
        u.key = $\infty$
        u.p = NIL
    r.key = 0
    Q = G.V
    while Q != $\emptyset$
        u = EXTRACT-MIN(Q)
        for each v in G.Adj[u]
            if v in Q and w(u, v) < v.key
                v.p = u
                v.key = w(u, v)
  

• 两种算法都是贪心算法，Kruskal时间复杂度为$O(E\lg E)$, Prim时间复杂度用二叉最小堆为$O(E\lg V)$，用斐波那契堆为$O(E + V\lg V)$.

图的表示和遍历

图的表示

• 邻接链表 和 邻接矩阵

  图的遍历

  广度优先 bfs

• 从一个源结点s开始，每次从已发现的结点向未发现的结点扩展
• 算法需要在发现所有距离源结点s为k的所有结点之后，才会发现距离源结点s为k+1的其他结点
• 用三种颜色标记结点的访问状态：
  白色：未被发现
  黑色：本身被发现且所有与之相连的结点都已经被发现
  灰色：本身被发现且与之相连的结点中存在未被发现的
• 总时间复杂度： O(V+E)

• 伪代码

    BFS(G, s)
    for each vertex u in G.V - {s}
        u.color = WHITE
        u.d = \infty
        u.p = NIL
    s.color = GRAY
    s.d = 0
    s.p = NIL
    Q = \emptyset
    ENQUEUE(Q, s)
    while Q isn't empty
        u = DEQUEUE(Q)
        for each v in G.Adj[u]
            if v.color == WHITE
                v.color = GREY
                v.d = u.d + 1
                v.p = u
                ENQUEUE(Q, v)
            u.color = BLACK
  

  深度优先 dfs

• 时间戳： 每个结点v有两个时间戳

  • 第一个时间戳v.d记录结点v第一次被发现的时间（染上灰色的时候）
  • 第二个时间戳v.f记录搜索完成对v的邻接链表扫描的时间（图上黑色的时候）
    时间戳都是处于1和2|V|之间的整数
    u.d < u.f

• 代码

    DFS(G)
    for each vertex u in G.V
         u.color = WHITE
         u.p = NIL
    time = 0
    for each vertex u in G.V
        if u.color == WHITE
            DFS-VISIT(G, u)
  
    DFS-VISIT(G, u)
    time ++
    u.d = time
    u.color = GRAY
    for each v in G.Adj[u] 
        if v.color == WHITE
            v.p = u
            DFS-VISIT(G, v)
    u.color = BLACK
    time ++
    u.f = time
  

• 括号化定理，后代区间嵌套，白色路径定理

• 边的分类
  • 树边：深度优先森林中的边
  • 前向边F：从祖先指向后代
  • 后向边B：从后代指向祖先（包括有向图中的自循环）
  • 横向边C：两端点无血缘关系
• dfs中每条边要么是树边，要么是后向边

拓扑排序

• 有向无环图
• 如果图$G$包含边$(u, v)$，则结点$u$在拓扑排序中处于结点$v$的前面。

• 伪代码

    TOPOLOGICAL-SORT
    1 call DFS(G) to compute finishing times v.f for each vertex v
    2 as each vertex is finished, insert it onto the front of a linked list
    3 return the linked list
  

• 引理22.11 一个有向图$G$是无环的当且仅当对齐进行深度优先搜索不产生后向边。

强连通分量

• 有向图$G$的强连通分量是一个最大结点集合 $C\subset V$，对于该集合中任意一对结点u和v来说，路径u->v和路径v->u同时存在，也就是说，结点u和结点v可以互相到达。

• 算法伪代码：

    STRONGLY-CONNECTED-COMPONENTS(G)
    1 call DFS(G) to compute finishing times u.f for each vertex u
    2 compute G^T
    3 call DFS(G^T), but in the main loop of DFS, consider the verteces
      in order of decreasing u.f
    4 output the verteces of each tree in the depth-first forest 
      in line 3 as a seperate strongly connected component
  

• 时间复杂度：$\theta(V+E)$
• 分量图的关键性质：是一个有向无环图
• 半连通：u->v 或 v->u

单源最短路径算法

    INITIALIZE-SINGLE-SOURCE(G, s)
    1 for each vertex v in G.V
    2     v.d = \infty
    3     v.p = NIL
    4 s.d = 0

    RELAX(u, v, w)
    1 if v.d > u.d + w(u, v)
    2     v.d = u.d + w(u, v)
    3     v.p = u

• 最短路径和松弛操作的性质
  • 三角不等式性质：对任何边$(u, v) \in E$, 有$\delta (s, v)\le \delta (s, u) + w(u, v)$.
  • 上界性质：
    对所有点v，有$v.d\ge \delta(s, v)$, 一旦$v.d$取值达到$\delta(s, v)$，就不会再变化。
  • 非路径性质：如果s和v之间不存在路径，则总是有$v.d = \delta(s, v) = \infty$.
  • 收敛性质：对于结点$v$，若有s~>u->v是图$G$中的一条最短路径，并且在对边$(u, v)$进行松弛前的任意时间有$u.d=\delta (s, u)$，则在之后的所有时间有$u.d = \delta(s, v)$.
  • 路径松弛性质：如果$p=$是从源结点$s=v_0$到结点$v_k$的一条最短路径，并且我们队p中的边所进行的松弛的次序为$(v_0, v_1)$, $(v_1, v_2)$, …, $(v_{k-1}, v_k)$，则$v_k.d =\delta(s,v_k)$.
  • 前驱子图性质：对于所有节点$v\in V$, 一旦$v.d = \delta(s, v)$，则前驱子图为一颗根结点为$s$的最短路径树。

    BELLMAN-FORD算法

• 代码

    BELLMAN-FORD(G, w, s)
    1 INITIALIZE-SINGLE-SOURCE(G, s)
    2 for i = 1 to |G.V| - 1
    3     for each edge (u, v) in G.E
    4         RELAX(u, v, w)
    5 for each edge (u, v) in G.E
    6     if v.d > u.d + w(u, v)
    7         return false
    8 return true
  

• 时间复杂度$O(VE)$

有向无环图中的单源最短路径

• 代码

    DAG-SHORTEST-PATH(G, w, s)
    1 topologically sort the vertices of G
    2 INITIALIZE-SINGLE-SOURCE(G, s)
    3 for each vertex u, taken in topologically sorted order
        for each vertex v in G.Adj[u]
            RELAX(u, v, w)
  

• 时间复杂度 $O(V+E)$
• 找最长路径，则将所有权重变成负的，或者初始化为负无穷，RELAX过程 > 变为 <

Dijkstra算法

• 有向图中单源最短路径问题，要求所有边的权重非负

• 代码

    DIJKSTRA(G, w, s)
    1 INITIALIZE-SINGLE-SOURCE(G, s)
    2 S = \emptyset
    3 Q = G.V
    4 while Q != \emptyset
    5    u = EXTRACT-MIN(Q)
    6    S = S \cup {u}
    7    for each vertex v in G.Adj[u]
    8        RELAX(u, v, w)
  

• 时间复杂度：$O((V+E)\lg V)$; 若源结点可达所有点，则为$O(E\lg V)$. 用斐波那契堆可以达到$O(VlgV + E)$.

• 实际用C++实现的时候，因为优先队列不能直接decrease_key，不需要一次性push所有的点，到达之后再push，同时记录每个点有没有遍历过。

多源最短路径算法

“矩阵乘法”

• 每次将最短路径拓展了一条边！

• 代码

    EXTEND-SHORTEST-PATHES(L, W)
    n = L.rows
    for i = 1 to n
        for j = 1 to n 
            l'_{ij} = \infty
            for k = 1 to n
                l'_{ij} = min(l'_{ij}, l_{ik} + w_{kj})
    return L'
  

• 类似于矩阵乘法
• 每一步拓展时间复杂度$O(n^3)$
• 用类似快速幂计算，时间复杂度$\Theta(n^3\lg n)$
• 垃圾算法基本不用

Floyd-Warshall算法

• 递归定义$d_{ij}^k$如下： $$d_{ij}^k = \begin{cases} w_{ij}, &\text{k = 0}\\\\ min(d_{ij}^{k-1}, d_{ik}^{k-1} + d_{kj}^{k-1}), &\text{k > 0} \end{cases}$$

• 代码

    FLOYD-WARSHALL(W)
    n = W.rows
    for k = 1 to n
        for i = 1 to n
            for j = 1 to n
                d_{ij} = min(d_{ij}, d_{ik} + d_{kj})
  

• 注：书上初始代码是用n个矩阵来记录的，但是实际上没必要。

• 时间复杂度$\Theta (n^3)$.
• 构建最短路径：
  • 递归公式： $$\pi_{ij}^0 = \begin{cases} NIL, &i = j \; or \; w_{ij} = \infty\\\\ i, &else \end{cases}$$ $$\pi_{ij}^k = \begin{cases} \pi_{ij}^{k-1}, &d_{ij}^{k-1} \le d_{ik}^{k-1} + d_{kj}^{k-1}\\\\ \pi_{kj}^{k-1}, &else \end{cases}$$
• 计算有向图的传递闭包也用类似的算法（略）
• 对于负权环，检查对角线上的值是否为负即可。

用于稀疏图的Johnson算法

• 技术：重新赋予权重使新的图满足
  • 所有权重都为非负值
  • 新图中的最短路径就是旧图中的最短路径
• 赋值方法：

$$\hat{w}(u,v) = w(u,v)+h(u)-h(v)$$ $$h(u) = \delta(s, u)$$

• 解释：
  • 先增加一个新结点 s，该点到原先各结点都有边相连，权重为 0
  • 对新图进行一次Bellman-Ford算法，寻找是否有负权重环路
  • 没有负权重环，就给每条边重新赋值。
  • 然后对每个点进行Dijkstra
  • 最后将最短路径的权重恢复，并存入矩阵D中返回
• 时间复杂度：
  • 二叉最小优先队列实现Dijkstra：$O(VE\lg V)$
  • 斐波那契堆：$O(V^2 \lg V + VE)$
  • 稀疏图中比Floyd好

最大流算法

流网络

• 有向图$G=(V,E)$
• 图中，每条边
  $(u,v)\in E$ 有一个非负的容量值$c(u,v)\ge 0$
• 如果$(u,v) \notin E$，定义 $c(u,v)=0$
• 如果边集合$E$包含一条边$(u,v)$，则图中不存在反方向的边$(v,u)$
• 有源结点s和汇点t
• 流网络图是连通的
• 除源结点外的每个结点都至少有一条进入的边，$|E| \ge |V| - 1$.

流

设$G=(V,E)$ 为一个流网络，其容量函数为c。设$s$为网络的源结点，$t$为汇点。$G$中的流是一个实值函数$f:V×V→R$，满足下面两条性质：

• 流量限制：对于所有节点$u, v \in V$，要求 $0\le f(u, v) \le c(u, v)$.
• 流量守恒：对于所有的结点 $u \in V - \{s, t\}$，要求 $$\sum _{v\in V} f(v, u) = \sum _{v\in V} f(u, v)$$
• 去掉反平行边：将其中一条分为两条，加入一个新的结点。
• 多个源结点和多个汇点：超级源结点和超级汇点。
• 点容量限制：把一个点拆成两个点（入点和出点），其中用一条容量为原来的点容量的边连接。

Ford-Fulkerson方法

    FORD-FULEKERSON-METHOD(G, s, t)
    initialize flow f to 0
    while there exists an augmenting path p in the residual network G_f
        augment flow f along p
    return f

• 残存网络
  • 给定流网络$G$和流量$f$，残存网络$G_f$由那些仍有空间对流量进行调整的边构成。
  • 残存容量定义：

$$c_f(u, v) = \begin{cases} c(u,v) - f(u,v), &(u, v)\in E\\\\ f(v,u), &(v, u)\in E\\\\ 0, &else \end{cases}$$

• 给定一个流网络$G$ 和一个流 $f$，则有$f$ 所诱导的图$G$ 的残存网络为 $G_f = (V, E_f)$，$E_f = \{(u,v)\in V \times V: c_f(u, v) > 0\}$. 有 $|E_f| \le 2|E|$.
  • 递增
  • 抵消操作
  • 增广路径
• 增广路径p：残存网络 $G_f$中一条从源结点 s 到汇点 t 的简单路径。
• 残存容量：在一条增广路径p上能够为每条边增加的流量的最大值。
  • 流网络的切割
• 流网络的切割：
  将结点集合$V$ 划分为 $S$ 和 $T = V- S$，
  • 横跨切割的净流量 $f(S, T) = \sum_{u \in S}\sum _{v \in T}f(u, v) - \sum_{u \in S}\sum _{v \in T}f(v, u)$
  • 切割的容量：$c(S, T) = \sum_{u \in S}\sum _{v \in T}c(u, v)$
  • 最小切割：整个网络中容量最小的切割
  • 整个流网络的流量与横跨某一个切割的流量相等

• 最大流最小割定理：下列等价：

  • $f$ 是 $G$ 的一个最大流。
  • 残存网络 $G_f$ 不包含任何增广路径。
  • $|f| = c(S, T)$，其中 $(S, T)$ 是流网络 $G$ 中的某个切割

  • 基本的Ford-Fulkerson算法

    FORD-FULEKERSON(G, s, t)
    for each edge (u, v) in G.E

      (u, v).f = 0
    

    while there exists a path p from s to t in the residual network G_f

      c_f(p) = min{c_f(u, v)|(u, v) is in p}
      for each edge (u, v) in p
          if(u, v) in E
              (u, v).f = (u, v).f + c_f(p)
          else 
              (v, u).f = (v, u).f + c_f(p)
    

Edmonds-Karp算法

• 在Ford-Fulkerson算法的第三行使用广度优先搜索来寻找增广路径。
  每次在残存网络中选择的增广路径是一条从源结点$s$到汇点$t$的最短路径，其中每条边的权重为单位距离。

• 时间复杂度：$O(VE^2)$

• 快的原因：使用Edmonds-Karp算法，对于除源结点和汇点外的所有结点 $v$，残存网络 $G_f$ 中的最短路径距离 $\delta f(s,v)$ 随着每次流量的递增而单调递增。
• Edmonds-Karp算法所执行的流量递增操作的总次数为 $O(VE)$.
• 关键边：在残存网络中，一条路径 $p$ 的残存容量是该条路径上边 $(u,v)$ 的残存容量，即 $c_f(p)=c_f(u,v)$.
• 对于$E$中每条边来说，其成为关键边的次数最多为 $|V|/2$ 次。

dinic算法（oj补充）

• 通过bfs构造层次网络，然后在层次网络中用dfs进行增广，增广的时候加上条件depth[v] == depth[u] + 1
• 弧优化：dfs的for循环不从i = Head[u]开始，而从i = Cur[u]，而通过写&i = Cur[u]来实时更新Cur。注意在dinic的外层主循环中要恢复Cur数组。
• 时间复杂度：$O(V^2E)$

最大二分匹配

• 二分图中，结点划分为不相交的集合 L 和 R，$E$中所有的边都横跨 L 和 R.
• 构造一个流网络 $G = (V’, E’)$，其中 $V’ = V \cup \{s, t\}$，$E’ = \{(s, u): u\in L\} \cup \{(u, v): (u, v)\in E\} \cup \{(v, t): v\in R\}$，$E’$中每条边的容量都是 1.
• 二分图 $G$ 中的一个最大匹配 $M$ 的基数等于其对应的流网络 $G’$ 中某一最大流 $f$ 的值。
• 时间复杂度：$O(VE)$

匈牙利算法（oj补充）

• 求二部图最大匹配或最小覆盖
• 在任何一个二分图中，最大匹配中的边数等于最小顶点覆盖中的顶点数。
• 算法解释：对于每个S中的点，寻找是否有T中的点可以相连；对于T中的点v，如果没有和别的点相连，就连上；如果和S中的u相连，那就看看u能否和别的点相连。
• 时间复杂度：$O(VE)$
• 有向无环图的最小路径覆盖：拆点变为二部图，最小路径覆盖 = 顶点数（拆点前） – 最大二分匹配数
• 无向图的最小路径覆盖=拆点前点的数量-最大匹配数/2

其余oj补充部分

图的连通性

Tarjan算法

• 可以用来求有向图和无向图中的强\双连通分量，割点和割边
• dfn数组记录第一次到达该结点的时间戳
• low数组记录该点可以到达的时间戳最小的祖先结点的时间戳
• 有向图中需要用一个栈保存tarjan遍历的点，一旦dfn[i] = low[i] 就出栈直到点i，这些点就属于同一个强连通分量
• 常用技巧：缩点

  图上的游走

• 无向图含欧拉回路<==>全部顶点在同一个连通分量，且度均为偶数
• 有向图含欧拉迹<==>全部顶点在同一个连通分量，且度均为偶数或有且仅有两个为奇数
• 有向图含欧拉回路<==>全部顶点在同一个强连通分量，且任意顶点入度等于出度
• 有向图含欧拉迹<==>全部顶点在底图的同一个连通分量，且 至多一顶点出度=入度+1，至多一顶点出度=入度-1，其余：出度=入度
• 中国邮递员问题：
  • 欧拉图走欧拉回路
  • 不是欧拉图则走距离最短的重复路，而走重复路相当于在原图上加边，加权值最小的边使原图变为欧拉图即可
  • 求奇度点之间的最小距离
  • 寻找奇度点的最小权完美匹配