CS61B 课程笔记（Lecture 31 Dynamic Programming)

1. 引言

在这一章节中，我们回顾了大量的内容，包括编程实践、使用 IDE、设计数据结构、渐近分析、实现多种不同的抽象数据类型（例如，使用 BST、Trie 或 HashTable 实现映射，使用堆实现优先队列），以及图算法。课程强调，CS 61B 教授的知识在技术公司面试中是非常重要的，因为许多实际问题可以通过我们学习的数据结构和算法来解决。

2. 拓扑排序和 DAGs

假设我们有一系列任务或活动，其中一些任务必须在其他任务之前完成。我们可以将这些任务视为一个图，其中每个节点表示一个任务，边 \(v \to w\) 表示任务 \(v\) 必须在任务 \(w\) 之前完成。

拓扑排序

拓扑排序是一个图的顶点的线性排序，使得对于每条有向边 \(u \to v\)，顶点 \(u\) 在排序中出现在顶点 \(v\) 之前。拓扑排序仅适用于有向无环图（\(DAGs\)）。

  • 源节点（Sources）：拓扑排序的起点，不能有任何边指向它们的节点。
  • 汇节点（Sinks）：拓扑排序的终点，不能指向其他节点的节点。

算法回顾

  • 拓扑排序：可以使用深度优先搜索（DFS）或广度优先搜索（BFS）在 \(O(V + E)\) 时间内找到任何 DAG 的拓扑排序。

下面是三种实现拓扑排序的 Java 代码示例：深度优先搜索（DFS）、广度优先搜索（BFS，使用 Kahn 算法）和按度数（入度）排序的方法。

1. 深度优先搜索（DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;

public class TopologicalSortDFS {
    private int vertices;
    private List<List<Integer>> adjList;

    public TopologicalSortDFS(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

    public List<Integer> topologicalSort() {
        boolean[] visited = new boolean[vertices];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                dfs(i, visited, stack);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private void dfs(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int neighbor : adjList.get(v)) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited, stack);
            }
        }
        stack.push(v);
    }

    public static void main(String[] args) {
        TopologicalSortDFS graph = new TopologicalSortDFS(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        List<Integer> topoSortResult = graph.topologicalSort();
        System.out.println("拓扑排序结果 (DFS): " + topoSortResult);
    }
}

2. 广度优先搜索（BFS，Kahn 算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.*;

public class TopologicalSortBFS {
    private int vertices;
    private List<List<Integer>> adjList;

    public TopologicalSortBFS(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

    public List<Integer> topologicalSort() {
        int[] inDegree = new int[vertices]; // 入度数组
        for (int i = 0; i < vertices; i++) {
            for (int neighbor : adjList.get(i)) {
                inDegree[neighbor]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.add(i); // 将入度为 0 的顶点入队
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);
            for (int neighbor : adjList.get(u)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TopologicalSortBFS graph = new TopologicalSortBFS(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        List<Integer> topoSortResult = graph.topologicalSort();
        System.out.println("拓扑排序结果 (BFS): " + topoSortResult);
    }
}

3. 按度数（入度）排序

以下代码使用了类似于 Kahn 算法的方式，但可以更直接地按顶点的入度进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;

public class TopologicalSortByDegree {
    private int vertices;
    private List<List<Integer>> adjList;

    public TopologicalSortByDegree(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
    }

    public List<Integer> topologicalSort() {
        int[] inDegree = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            for (int neighbor : adjList.get(i)) {
                inDegree[neighbor]++;
            }
        }

        List<Integer> result = new ArrayList<>();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 将入度为 0 的顶点放入优先队列
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                minHeap.add(i);
            }
        }

        while (!minHeap.isEmpty()) {
            int u = minHeap.poll();
            result.add(u);
            for (int neighbor : adjList.get(u)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    minHeap.add(neighbor);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        TopologicalSortByDegree graph = new TopologicalSortByDegree(6);
        graph.addEdge(5, 2);
        graph.addEdge(5, 0);
        graph.addEdge(4, 0);
        graph.addEdge(4, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);

        List<Integer> topoSortResult = graph.topologicalSort();
        System.out.println("拓扑排序结果 (按度数): " + topoSortResult);
    }
}

代码总结

  1. 深度优先搜索（DFS）：使用栈来保存顶点的排序。
  2. 广度优先搜索（BFS，Kahn 算法）：使用入度数组和队列来处理节点。
  3. 按度数排序：类似于 Kahn 算法，但使用优先队列处理入度为零的节点，以确保按最小入度排序。

3. DAG 上的最短路径

在 DAG 中寻找最短路径的简单算法可以处理负边权。Dijkstra 算法在负边权存在时可能失败，因为它依赖于每次访问边时我们已经找到了到该边的最短路径。

最短路径算法

在 DAG 上，我们可以使用拓扑排序的顺序访问顶点，并在每次访问时松弛所有出边。

  • 松弛边的定义：对于边 \(u \to v\) 和权重 \(w\)：

    1
    2
    3
    4
    if (distTo[u] + w < distTo[v]) {
        distTo[v] = distTo[u] + w;
        edgeTo[v] = u;
    }

  • 时间复杂度：整体运行时间为 O(V + E)。

4. DAG 上的最长路径

寻找从起始顶点到每个其他顶点的最长路径问题是 NP 困难的，然而在 DAG 上我们可以使用以下方法找到最长路径：

  1. 形成一个新图 \(G'\)，将所有边权取负。
  2. 在 \(G'\) 上运行最短路径算法。
  3. 反转结果中的边权。

5. 减少和分解

减少是一种解决问题的方法，它可以将一个问题转化为另一个更易处理的问题。例如，通过将 DAG 上的最长路径问题（DAG-LPT）减少到 DAG 上的最短路径问题（DAG-SPT），我们可以用后者的算法来解决前者。

6. 示例：独立集问题与 3SAT 问题的减少

  • 独立集问题：在一个图中，寻找一个顶点集合，使得集合中没有两个顶点相邻。
  • 3SAT 问题：给定一个布尔公式，判断是否存在一种真值使公式为真。

减少过程

  1. 将 3SAT 的实例转化为图 G。
    • 为每个子句创建三个顶点并连接成三角形。
    • 为每个文字和其否定之间添加边。
  2. 在图 G 上找到大小为子句数量的独立集。
  3. 将独立集中的元素视为“真”，外部元素视为“假”，从而解决 3SAT 问题。