《西安电子科技大学算法上机报告》由会员分享，可在线阅读，更多相关《西安电子科技大学算法上机报告（19页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学（2018年度）算法分析实验报告实验名称：渗透实验班 级：1603012名：学 号: 实验一：渗透问题（Percolation）一、实验题目使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo simulation ）来估计渗透阈值的值。给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组 合系统成为电导体？ 给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件 下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透percolation） 的抽象过程来模拟这种情况。模型：我们使用NXN网
2、格点来模型一个渗透系统。每个格点或是open格点或是blocked 格点。 一个 full site 是一个 open 格点，它可以通过一连串的邻近（左，右，上，下） open 格 点连通到顶行的一个 open 格点。如果在底行中有一个 full site 格点，则称系统是渗透的。（对 于绝缘/金属材料的例子， open 格点对应于金属材料，渗透系统有一条从顶行到底行的金属 路径，且 full sites 格点导电。对于多孔物质示例， open 格点对应于空格，水可能流过，从而 渗透系统使水充满open格点，自顶向下流动。）问题：在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空
3、置概率p 独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？ 当p = 0时，系统不会渗出；当p=1时，系统渗透。下图显示了 20X20随机网格和100X100 随机网格的格点空置概率 p 与渗滤概率。当N足够大时，存在阈值p*,使得当p p*时，随机N N网格几乎总是渗透。尚未得出用于确定渗滤阈值p*的数学解。你的任务 是编写一个计算机程序来估计 p*。Percolation数据类型:模型化一个Percolation系统,创建含有以下API的数据类型Percolation。public class Percolation public Percol
4、ation(int N)public void open(int i, int j) public boolean isOpen(int i, int j) public boolean isFull(int i, int j) public boolean percolates() public static void main(String args)/ create N-by-N grid, with all sites blocked/ open site (row i, column j) if it is not already/ is site (row i, column j)
5、 open?/ is site (row i, column j) full?/ does the system percolate?/ test client, optional约定行i列丿下标在1和N之间，其中(1,1)为左上格点位置:如果open。, isOpen。, or isFull。 不在这个规定的范围，则抛出IndexOutOfBoundsException例外。如果N 0，构造函数应该 抛出IllegalArgumentException例外。构造函数应该与N成正比。所有方法应该为常量时间 加上常量次调用合并-查找方法 union(), find(), connected(),
6、 and count()。蒙特卡洛模拟(Monte Carlo simulation).要估计渗透阈值，考虑以下计算实验: 初始化所有格点为 blocked。 重复以下操作直到系统渗出:o 在所有blocked的格点之间随机均匀选择一个格点(row i, columnj)。o 设置这个格点(row i, columnj)为open格点。 open 格点的比例提供了系统渗透时渗透阈值的一个估计。50 open sites100 open sites150 open sites204 open sites通过重复该计算实验T次并对结果求平均值，我们获得了更准确的渗滤阈值估计。令辱是 第t次计算实验
7、中open格点所占比例。样本均值卩提供渗滤阈值的一个估计值；样本标准 差Q测量阈值的灵敏性。卩=兀卫 厂优_ , 卍 = 伐丄口)2伐 2 口“_T T1假设T足够大(例如至少30),以下为渗滤阈值提供95%置信区间:1.96qpublic class PercolationStats public PercolationStats(int N, int T) on an N-by-N gridpublic double mean()public double stddev()public double confidenceLo()public double confidenceHi()pub
8、lic static void main(String args) 我们创建数据类型 PercolationStats 来执行一系列计算实验，包含以下 API。/ perform T independent computational experiments/ sample mean of percolation threshold/ sample standard deviation of percolation threshold/ returns lower bound of the 95% confidence interval/ returns upper bound of the
9、95% confidence interval/ test client, described below在 N 0 或 T 0 时，构造函数应该抛出 java.lang.IllegalArgumentException 例外。此外，还包括一个main()方法，它取两个命令行参数N和T,在NXN网格上进行T次独 立的计算实验(上面讨论)，并打印出均值小 标准差Q和95%渗透阈值的置信区间。使 用标准库中的标准随机数生成随机数； 使用标准统计库来计算样本均值和标准差。Example values after creating PercolationStats(200, 100)mean()= 0
10、.5929934999999997stddev()= 0.00876990421552567confidenceLow()= 0.5912745987737567confidenceHigh()= 0.5947124012262428Example values after creating PercolationStats(200, 100)mean()= 0.592877stddev()= 0.009990523717073799confidenceLow()= 0.5909188573514536confidenceHigh()= 0.5948351426485464Example va
11、lues after creating PercolationStats(2, 100000)mean()stddev() confidenceLow() confidenceHigh()= 0.6669475= 0.11775205263262094= 0.666217665216461= 0.6676773347835391运行时间和内存占用分析。使用 quick-find 算法(QuickFindUF.java from algs4.jar)实现 Percolation 数据类型。进彳丁实 验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机上的总时间，它是 输入 N 和 T
12、的函数表达式。使用 weighted quick-union 算法(WeightedQuickUnionUF.java from algs4.jar)实现 Percolation 数据类型。进行实验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机 上的总时间，它是输入N和T的函数表达式。二、算法设计程序要求实现对一个NxN矩阵的连通性判断问题，则可以使用quick-find算法和加权 quick-union算法来实现，因为算法中的数组是一维的，所以首要解决的问题就是将NxN矩 阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。将它们在连通分量数组中的编号依次设置为0N
13、xN-1。为了之后检验连通性的问题， 有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口，它和第一行的所有点都 是连通的，在矩阵的底部有一个出水口，它和最后一行的所有点是连通的，并分别将注水口 和出水口在连通分量数组中的编号设为NxN和NxN+1。按照题目的要求每次随机打开矩阵 中的一个点，然后判断与它邻近的点(上下左右)是否已经被打开，若已经打开就将它们连 接起来。那么每次打开一个新的结点之后检验连通性,只需要检验注水口和出水口是否连通 即可。具体设计：设计 Percolation 类，分别使用 quick-find 和 weight quick-union 算法进行合并。 Perc
14、olation 类中设计open方法打开一个点，并将该点与其它相邻的点合并。public class Percolation priva te int matr ixLeng th;/ 网格大小priva te boolean ma trix;/记录方格是否打开数组priva te QuickFindUF qu;/ 合并查找类变量/或者：private WeightedQuickUnionUF wqu;priva te int virtu alTop;/注水口priva te int virtu albo ttom;/出 水口public Percolation(int N)if (N = 0
15、) throw new IllegalArgumentException(length must be positive);matrixLength = N;virtualTop = matrixLength * matrixLength;virtualbottom = matrixLength * matrixLength + 1;matrix = new booleanN * N;qu = new QuickFindUF(N * N + 2);/检查边界private void checkValidIndex(int row,int col)if(row matrixLength)throwiew IndexOutOfBoundsException(row index out of bounds);if(col matrixLength)throwiew IndexOutOfBoundsException(col index o
