CS61B 课程笔记（HW2 Percolation)

作业概述

  • 课程名称：CS 61B Spring 2018
  • 作业主题：渗透（Percolation）
  • 代码仓库：GitHub - cs61b-sp18

获取骨架文件

  • 使用命令 git pull skeleton master 获取作业的骨架文件。
  • 如果使用 IntelliJ，确保在最外层的 hw2 目录导入项目（不要在 hw2 目录内导入），以避免包错误。

引言

  • 本程序的目的是通过蒙特卡洛模拟来估计渗透阈值。
  • 使用的 不相交集 实现已包含在普林斯顿标准库中，无需自行实现。

相关视频和资料

  • 介绍视频：包括三个部分：介绍、实现提示和优化提示，可以选择忽略提示以增加挑战性。
  • 作业幻灯片：提供作业的方法和思路。

渗透模型

  • 定义：通过一个 N × N 的网格模型化渗透系统。每个网格点要么是开放的，要么是封闭的。
  • 完全开放点：一个可以通过相邻的开放点连接到第一行的开放点。
  • 渗透：如果底行中存在完全开放点，则系统渗透。

渗透问题

  • 问题描述：研究者关注以下问题：如果网格点以概率 p 独立设置为开放，系统的渗透概率是多少？
    • 当 p = 0 时，系统不渗透；
    • 当 p = 1 时，系统完全渗透。

渗透阈值

  • 存在一个阈值 \(p^*\) ：
    • 当 $p < p^* $ 时，几乎不会渗透；
    • 当 \(p > p^*\) 时，几乎总是渗透。
  • 任务是编写程序估计 \(p^*\) 。

Percolation.java

  • 数据类型：在 hw2 包中创建 Percolation 数据类型，包含以下 API：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public class Percolation {
        public Percolation(int N)                // 创建 N×N 网格，所有点初始封闭
        public void open(int row, int col)       // 打开 (row, col) 点
        public boolean isOpen(int row, int col)  // 检查 (row, col) 点是否开放
        public boolean isFull(int row, int col)  // 检查 (row, col) 点是否完全开放
        public int numberOfOpenSites()           // 获取开放点的数量
        public boolean percolates()              // 检查系统是否渗透
        public static void main(String[] args)   // 用于单元测试（非必需）
    }

处理边界情况

  • 行和列的索引范围为 0 到 N - 1 ，超出范围会抛出 java.lang.IndexOutOfBoundsException。
  • 构造函数中如果 \(N \leq 0\) 则抛出 java.lang.IllegalArgumentException。

性能要求

  • 构造函数的时间复杂度为 \(O(N^2)\) ，所有方法应为常数时间，加上常数次数的并查集方法调用。
  • numberOfOpenSites() 方法需为常数时间。
  • 使用 WeightedQuickUnionUF 类，而不是重新实现并查集。

PercolationStats.java

  • 蒙特卡洛模拟：估计渗透阈值的实验设计如下：
    1. 初始化所有点为封闭。
    2. 直到系统渗透，随机选择一个封闭点并打开。
    3. 记录渗透时已打开点的比例作为估计。

计算阈值的统计方法

  • 重复进行 T 次实验，计算样本均值 \(\mu\) 和标准差 $\(：\) = $ $ ^2 = $
  • 95% 置信区间： $ [- 1.96 , + 1.96 ] $

PercolationStats API

  • 在 hw2 包中创建 PercolationStats，包含以下 API：

    1
    2
    3
    4
    5
    6
    7
    public class PercolationStats {
        public PercolationStats(int N, int T, PercolationFactory pf)   // 执行 T 次独立实验
        public double mean()                                           // 渗透阈值的样本均值
        public double stddev()                                         // 渗透阈值的样本标准差
        public double confidenceLow()                                  // 95% 置信区间下限
        public double confidenceHigh()                                 // 95% 置信区间上限
    }

附加说明

  • 构造函数需检查 $ N $ 或 $T $。
  • 使用 PercolationFactory 对象创建新的 Percolation 对象，避免直接调用 new Percolation(N)。

运行时间分析（未评分）

  • 建议使用不同的 N 和 T 值测量 PercolationStats 的总运行时间。
  • 对于 Percolation 数据类型，建议使用加权快速并查集实现。

提供的文件

  • 交互式可视化客户端：InteractivePercolationVisualizer.java 通过鼠标输入动画展示渗透系统的开放点。
  • 基于文件的可视化客户端：PercolationVisualizer.java 从文件读取点并可视化结果，生成相应的图像。

代码实现

包括 Percolation.java 和 PercolationStats.java 的主要部分，以及用于可视化的客户端代码。

1. Percolation.java

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private final int N;
    private final boolean[][] grid;
    private int openSites;
    private final WeightedQuickUnionUF uf;
    private final int virtualTop; // 虚拟顶部
    private final int virtualBottom; // 虚拟底部

    public Percolation(int N) {
        if (N <= 0) throw new IllegalArgumentException("N must be greater than 0");
        this.N = N;
        this.grid = new boolean[N][N];
        this.openSites = 0;
        this.uf = new WeightedQuickUnionUF(N * N + 2); // +2 for virtual top and bottom
        this.virtualTop = N * N; // 虚拟顶部索引
        this.virtualBottom = N * N + 1; // 虚拟底部索引
    }

    public void open(int row, int col) {
        validateIndices(row, col);
        if (!isOpen(row, col)) {
            grid[row][col] = true; // 打开该点
            openSites++;

            // 如果是第一行，连接到虚拟顶部
            if (row == 0) {
                uf.union(virtualTop, xyTo1D(row, col));
            }
            // 如果是最后一行，连接到虚拟底部
            if (row == N - 1) {
                uf.union(virtualBottom, xyTo1D(row, col));
            }

            // 连接到相邻的开放点
            connectAdjacent(row, col);
        }
    }

    public boolean isOpen(int row, int col) {
        validateIndices(row, col);
        return grid[row][col];
    }

    public boolean isFull(int row, int col) {
        validateIndices(row, col);
        return uf.connected(virtualTop, xyTo1D(row, col));
    }

    public int numberOfOpenSites() {
        return openSites;
    }

    public boolean percolates() {
        return uf.connected(virtualTop, virtualBottom);
    }

    private void connectAdjacent(int row, int col) {
        // 连接上下左右的开放点
        if (row > 0 && isOpen(row - 1, col)) {
            uf.union(xyTo1D(row, col), xyTo1D(row - 1, col));
        }
        if (row < N - 1 && isOpen(row + 1, col)) {
            uf.union(xyTo1D(row, col), xyTo1D(row + 1, col));
        }
        if (col > 0 && isOpen(row, col - 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col - 1));
        }
        if (col < N - 1 && isOpen(row, col + 1)) {
            uf.union(xyTo1D(row, col), xyTo1D(row, col + 1));
        }
    }

    private int xyTo1D(int row, int col) {
        return row * N + col;
    }

    private void validateIndices(int row, int col) {
        if (row < 0 || row >= N || col < 0 || col >= N) {
            throw new IndexOutOfBoundsException("row or column index out of bounds");
        }
    }

    public static void main(String[] args) {
        // 单元测试或演示
    }
}

2. PercolationStats.java

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
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.StdRandom;

public class PercolationStats {
    private final double[] thresholds;
    private final int T;

    public PercolationStats(int N, int T, PercolationFactory pf) {
        if (N <= 0 || T <= 0) throw new IllegalArgumentException("N and T must be greater than 0");
        this.T = T;
        this.thresholds = new double[T];

        for (int t = 0; t < T; t++) {
            Percolation percolation = pf.make(N);
            int openCount = 0;

            while (!percolation.percolates()) {
                int row = StdRandom.uniform(N);
                int col = StdRandom.uniform(N);
                if (!percolation.isOpen(row, col)) {
                    percolation.open(row, col);
                    openCount++;
                }
            }
            thresholds[t] = (double) openCount / (N * N);
        }
    }

    public double mean() {
        return StdStats.mean(thresholds);
    }

    public double stddev() {
        return StdStats.stddev(thresholds);
    }

    public double confidenceLow() {
        return mean() - 1.96 * stddev() / Math.sqrt(T);
    }

    public double confidenceHigh() {
        return mean() + 1.96 * stddev() / Math.sqrt(T);
    }

    public static void main(String[] args) {
        // 可选：运行实验并输出结果
    }
}

3. 交互式可视化客户端 (InteractivePercolationVisualizer.java)

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
import edu.princeton.cs.introcs.StdDraw;

public class InteractivePercolationVisualizer {
    public static void main(String[] args) {
        int N = 20; // 网格大小
        Percolation percolation = new Percolation(N);
        StdDraw.setScale(0, N);
        StdDraw.enableDoubleBuffering();

        while (true) {
            if (StdDraw.mousePressed()) {
                int row = (int) StdDraw.mouseY();
                int col = (int) StdDraw.mouseX();
                if (!percolation.isOpen(row, col)) {
                    percolation.open(row, col);
                }
            }

            // 绘制网格
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    if (percolation.isOpen(row, col)) {
                        StdDraw.setPenColor(StdDraw.BLUE);
                        StdDraw.filledSquare(col + 0.5, N - row - 0.5, 0.5);
                    } else {
                        StdDraw.setPenColor(StdDraw.GRAY);
                        StdDraw.filledSquare(col + 0.5, N - row - 0.5, 0.5);
                    }
                }
            }

            StdDraw.setPenColor(StdDraw.BLACK);
            StdDraw.text(N / 2.0, N + 0.5, "Click to open sites");
            StdDraw.show();
        }
    }
}

4. 基于文件的可视化客户端 (PercolationVisualizer.java)

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
import edu.princeton.cs.introcs.StdDraw;

import java.io.File;

public class PercolationVisualizer {
    public static void main(String[] args) {
        In in = new In(new File("input.txt"));
        int N = in.readInt();
        Percolation percolation = new Percolation(N);
        
        while (in.hasNextLine()) {
            String[] parts = in.readLine().split(" ");
            int row = Integer.parseInt(parts[0]);
            int col = Integer.parseInt(parts[1]);
            percolation.open(row, col);
        }

        // 绘制网格
        StdDraw.setScale(0, N);
        for (int row = 0; row < N; row++) {
            for (int col = 0; col < N; col++) {
                if (percolation.isOpen(row, col)) {
                    StdDraw.setPenColor(StdDraw.BLUE);
                    StdDraw.filledSquare(col + 0.5, N - row - 0.5, 0.5);
                } else {
                    StdDraw.setPenColor(StdDraw.GRAY);
                    StdDraw.filledSquare(col + 0.5, N - row - 0.5, 0.5);
                }
            }
        }
        StdDraw.setPenColor(StdDraw.BLACK);
        StdDraw.text(N / 2.0, N + 0.5, "Final state of the percolation system");
        StdDraw.show();
    }
}

说明

  1. Percolation.java：实现了渗透模型，支持打开网格点和检查系统是否渗透。
  2. PercolationStats.java：进行蒙特卡洛模拟，估计渗透阈值，并计算均值和标准差。
  3. InteractivePercolationVisualizer.java：提供交互式的可视化界面，通过鼠标点击打开网格点。
  4. PercolationVisualizer.java：根据输入文件的内容展示渗透系统的最终状态。