作业|学习资料|算法|题解

Percolation

凝神长老 · 11月7日 · 2017年 · · · · · 878次已读

本文写于 2017年11月07日,距今已超过 1 年,距 2020年03月30日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


Princeton Alhorithms Percolation

普林斯顿大学算法课第 1 次作业“渗透模型 ”。

题目描述: https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php

这是一道并查集的问题。

按照题目要求逐步定义 isFullisOpen 是没有难度的,然后只需要在 open 操作中,设置一个 openStatustrue 并将它与它周围的四个格子连通即可。

注意 isFull 必须首先满足 isOpen

这题想要通过,80 分,非常简单,难点在于得高分,因为需要优化的地方非常多,也细节。

首先一个技巧,是 ACM 竞赛中常用的,虚拟起点与虚拟终点,这样可以加速是否连通的判断,不需要遍历整个最后一行,只需要直接看虚拟点是否连接。

由此,我们可以轻松得到 95 分。

但是这样还有 3 个 backwash,分别是 Test Case 16 – 18。

比如一个 3×3 的网格,我们先打开 (1, 1), (1, 2), (1, 3), (2, 3), (3, 3) 和 (3, 1),由于我们打开到 (3, 3) 的时候,事实上它已经渗透,所以虚拟起点和虚拟终点已经连接,此时我们打开 (3, 1) 之后,它会通过虚拟终点连接到 (3, 3),并逐步向上直到第一层,最终与虚拟起点连通。这会导致在判断 (3, 1) 的 isFull() 出错。

为此,我们维护另一个并查集,该并查集只有虚拟起点,没有虚拟终点。

以下代码获得 100 分。


import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

    private final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 虚拟起点,减少 UnionFind 的调用
    private static final int TOP = 0;
    private boolean[][] openStatus;
    private final int n;
    private final WeightedQuickUnionUF disjointSet;
    // 为了解决 backwash,这里只用于 TOP 连接
    private final WeightedQuickUnionUF disjointSetBackwash;
    // 虚拟终点,减少 UnionFind 的调用
    private final int bottom;
    // 直接计入 counter,避免 isOpen() 去遍历
    private int counter;

    public Percolation(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException();
        }
        this.n = n;
        openStatus = new boolean[n + 1][n + 1];
        bottom = n * n + 1;
        disjointSet = new WeightedQuickUnionUF(bottom + 1);
        disjointSetBackwash = new WeightedQuickUnionUF(bottom + 1);
    }

    public void open(int row, int col) {
        if (isValid(row, col)) {
            if (!openStatus[row][col]) {
                // 没有打开过才能加 1
                counter++;
                openStatus[row][col] = true;
                // 将第一层与虚拟起点连接,最后一层与虚拟终点连接
                int unionIndex = (row - 1) * n + col;
                if (row == 1) {
                    disjointSet.union(TOP, unionIndex);
                    disjointSetBackwash.union(TOP, unionIndex);
                }
                // 这里不是 else if 因为 n = 1 的时候,头尾都要连通
                if (row == n) {
                    disjointSet.union(bottom, unionIndex);
                    // 不在 backwash 中记录
                }
            }
            for (int[] ints : directions) {
                int newRow = row + ints[0];
                int newCol = col + ints[1];
                if (isValid(newRow, newCol) && isOpen(newRow, newCol)) {
                    int unionIndexP = (row - 1) * n + col;
                    int unionIndexQ = (newRow - 1) * n + newCol;
                    disjointSet.union(unionIndexP, unionIndexQ);
                    disjointSetBackwash.union(unionIndexP, unionIndexQ);
                }
            }
        } else {
            throw new IllegalArgumentException();
        }
    }

    private boolean connectedWithTop(int row, int col) {
        int unionIndex = (row - 1) * n + col;
        return disjointSetBackwash.connected(TOP, unionIndex);
    }

    private boolean isValid(int row, int col) {
        return row >= 1 && row <= n && col >= 1 && col <= n;
    }

    public boolean isOpen(int row, int col) {
        if (isValid(row, col)) {
            return openStatus[row][col];
        } else {
            throw new IllegalArgumentException();
        }
    }

    public boolean isFull(int row, int col) {
        if (isValid(row, col)) {
            // A full site is an open site that can ....
            // 所以 isFull 必须要先满足 isOpen
            return isOpen(row, col) && connectedWithTop(row, col);
        } else {
            throw new IllegalArgumentException();
        }
    }

    public int numberOfOpenSites() {
        return counter;
    }

    public boolean percolates() {
        return disjointSet.connected(TOP, bottom);
    }

    public static void main(String[] args) {
        Percolation p;
        p= new Percolation(2);
        p.open(2, 1);
        p.open(2, 2);
        p.open(1, 2);
        assert p.percolates();

        // Backwash
        // (3, 1) 通过虚拟终点与起点连接,但它其实不是 full 的
        p = new Percolation(3);
        p.open(1, 1);
        p.open(1, 2);
        p.open(1, 3);
        p.open(2, 3);
        p.open(2, 2);
        p.open(3, 3);
        p.open(3, 1);
        assert !p.isFull(3, 1);
        assert p.percolates();
    }

}
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
    private static final double CONFIDENCE = 1.96;
    private final double[] thresholds;
    // 缓存,以减少 Stats 的调用,否则会扣分
    private final double mean;
    private final double stddev;

    public PercolationStats(int n, int trials) {
        if (!isValid(n, trials)) {
            throw new IllegalArgumentException();
        }
        thresholds = new double[trials];
        for (int i = 0; i < trials; ++i) {
          Percolation p = new Percolation(n);
            while (!p.percolates()) {
                int possibleRow = StdRandom.uniform(1, n + 1);
                int possibleCol = StdRandom.uniform(1, n + 1);
                p.open(possibleRow, possibleCol);
            }
            thresholds[i] = (double) (p.numberOfOpenSites()) / (double) (n * n);
        }
        mean = StdStats.mean(thresholds);
        stddev = StdStats.stddev(thresholds);
    }

    private boolean isValid(int n, int trials) {
        return n > 0 && trials > 0;
    }

    public double mean() {
        return mean;
    }

    public double stddev() {
        return stddev;
    }

    public double confidenceLo() {
        return mean - CONFIDENCE * stddev / Math.sqrt(thresholds.length);
    }

    public double confidenceHi() {
        return mean + CONFIDENCE * stddev / Math.sqrt(thresholds.length);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int trials = Integer.parseInt(args[1]);
        PercolationStats ps = new PercolationStats(n, trials);
        System.out.println("mean=" + ps.mean());
        System.out.println("stddev=" + ps.stddev());
        System.out.println("95% confidence interval=[" + ps.confidenceLo() + "," + ps.confidenceHi() + "]");
    }
}
0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论