我的函数创建从下到上的路径的渗透阈值是 0.1 太高了

Question

我的目标是计算包含黑色和白色单元格的矩阵中从上到下路径的渗透阈值的近似值。为此，我随机将单元格涂黑，并且在每个步骤之后，我检测是否有一条由黑色单元格组成的路径，从矩阵的任何顶部单元格（第一行）到底部（最后一行）的任何单元格（没有对角线）跳跃）。如果是这样，就达到了渗透。渗透阈值是概率上需要变黑才能达到渗透的黑色单元的比例。对于任何不太小的矩阵，这个阈值都是相同的。

为了表示大小为 N 的方阵 M，我使用大小为 NxN 的一维数组 T：M 中第 i 行第 j 列的单元格（i 和 j 在 0 到 N-1 之间）对应于该元素T 中的索引 i.N + j。

我的问题是我的渗透阈值在 0.7 左右，而正常情况下应该是 0.6。我试图找出代码中的错误，但一切似乎都很好，但我找不到我的错误。这是我创建的代码：

public class Percolation {
    public static final int size = 10;
    public static final int length = size * size;
    public static boolean[] grid = new boolean[length];

    public static void init() {
        for (int i = 0; i < length; i++) {
            grid[i] = false;
        }
    }

    public static void print() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int index = i * size + j;
                if (grid[index]) {
                    System.out.print("*");
                } else {
                    System.out.print("-");
                }
            }
            System.out.println();
        }
    }

    public static int randomShadow() {
        int index;
        do {
            index = (int) (Math.random() * length);
        } while (grid[index]);
        grid[index] = true; 
        return index;
    }


    public static boolean isNaivePercolation(int n) {
        boolean[] seen = new boolean[length];
        
        
        boolean pathToTop = detectPath(seen, n, true);
        
        boolean pathToBottom = detectPath(seen, n, false);
        
        // Percolation occurs if there's a path to both top and bottom rows
        return pathToTop && pathToBottom;
    }

    private static boolean detectPath(boolean[] seen, int n, boolean up) {
        if (n < 0 || n >= length || seen[n] || !grid[n]) {
            return false; // Out of bounds, already visited cell, or white cell
        }
        if ((up && n < size) || (!up && n >= length - size)) {
            return true; // Reached top or bottom row
        }
        seen[n] = true; // Mark cell as visited
        int row = n / size;
        int col = n % size;
        // Check neighboring cells (up, down, left, right)
        return detectPath(seen, n - size, up) ||
               detectPath(seen, n + size, up) ||
               (col > 0 && detectPath(seen, n - 1, up)) ||
               (col < size - 1 && detectPath(seen, n + 1, up));
    }

    public static boolean isPercolation(int n) {
        return isNaivePercolation(n);
    }

    public static double percolation() {
        init(); // Initialize the matrix
        int blackenedCells = 0;
        int index;
        boolean percolationDetected = false;
        while (!percolationDetected) {
            index = randomShadow(); // Blacken a random white cell
            blackenedCells++;
            percolationDetected = isPercolation(index);
        }
        print();
        return (double) blackenedCells / length; // Return the proportion of blackened cells
    }
    

    public static void main(String[] args) {
        init();
        System.out.println("Matrix after initializing:");
        print();
        System.out.println();

        int blackenedIndex = randomShadow();
        System.out.println("Matrix after blackening a random cell:");
        print();
        System.out.println("Index of blackened cell: " + blackenedIndex);
        System.out.println();

        System.out.println("Testing percolation:");
        double percolationThreshold = percolation();
        System.out.println("Percolation threshold: " + percolationThreshold);
    }
}

我已经尝试过多次调试，手动做示例，副驾驶。

Answer 1

您的代码实现了 isNaivePercolation(int n) 方法，以便指示渗透的发生。 然而，在渗流模拟中，重要的是可以从顶角一直向下移动。 如果存在通向顶行和底行的路径，则会发生渗透。 解决此问题的一种方法如下：

public static boolean isNaivePercolation(int n) {
    boolean[] seen = new boolean[length];
    
    boolean pathToTop = detectPath(seen, n, true);
    boolean pathToBottom = detectPath(seen, n, false);
    
    return pathToTop && pathToBottom;
}

并且还可以在不带索引参数的情况下调用 isPercolation。

public static double percolation() {
        init(); // Initialize the matrix
        int blackenedCells = 0;
        int index;
        boolean percolationDetected = false;
        while (!percolationDetected) {
            index = randomShadow(); // Blacken a random white cell
            blackenedCells++;
            percolationDetected = isPercolation(); // <---
        }
        print();
        return (double) blackenedCells / length; // Return the proportion of blackened cells
}