西安电子科技大学算法上机报告.doc
《西安电子科技大学算法上机报告.doc》由会员分享,可在线阅读,更多相关《西安电子科技大学算法上机报告.doc(24页珍藏版)》请在咨信网上搜索。
1、西安电子科技大学(2018年度)算法分析实验报告实验名称: 渗透实验 班 级: 1603012 姓 名: 朱 斌 学 号: 16030120032 实验一:渗透问题(Percolation)一、实验题目使用合并-查找(union-find)数据结构,编写程序通过蒙特卡罗模拟(Monte Carlo simulation)来估计渗透阈值的值。给定由随机分布的绝缘材料和金属材料构成的组合系统:金属材料占多大比例才能使组合系统成为电导体? 给定一个表面有水的多孔渗水地形(或下面有油),水将在什么条件下能够通过底部排出(或油渗透到表面)? 科学家们已经定义了一个称为渗透(percolation)的抽象
2、过程来模拟这种情况。模型: 我们使用NN网格点来模型一个渗透系统。 每个格点或是open格点或是blocked格点。 一个full site是一个open格点,它可以通过一连串的邻近(左,右,上,下)open格点连通到顶行的一个open格点。如果在底行中有一个full site格点,则称系统是渗透的。(对于绝缘/金属材料的例子,open格点对应于金属材料,渗透系统有一条从顶行到底行的金属路径,且full sites格点导电。对于多孔物质示例,open格点对应于空格,水可能流过,从而渗透系统使水充满open格点,自顶向下流动。)问题: 在一个著名的科学问题中,研究人员对以下问题感兴趣:如果将格点
3、以空置概率p独立地设置为open格点(因此以概率1-p被设置为blocked格点),系统渗透的概率是多少? 当p = 0时,系统不会渗出; 当p=1时,系统渗透。 下图显示了2020随机网格和100100随机网格的格点空置概率p与渗滤概率。 当N足够大时,存在阈值p*,使得当p p*时,随机N N网格几乎总是渗透。 尚未得出用于确定渗滤阈值p*的数学解。你的任务是编写一个计算机程序来估计p*。Percolation数据类型:模型化一个Percolation系统,创建含有以下API的数据类型Percolation。public class Percolation public Percolati
4、on(int N) / create N-by-N grid, with all sites blocked public void open(int i, int j) / open site (row i, column j) if it is not already public boolean isOpen(int i, int j) / is site (row i, column j) open? public boolean isFull(int i, int j) / is site (row i, column j) full? public boolean percolat
5、es() / does the system percolate? public static void main(String args) / test client, optional约定行i列j下标在1和N之间,其中(1, 1)为左上格点位置:如果open(), isOpen(), or isFull()不在这个规定的范围,则抛出IndexOutOfBoundsException例外。如果N 0,构造函数应该抛出IllegalArgumentException例外。构造函数应该与N2成正比。所有方法应该为常量时间加上常量次调用合并-查找方法union(), find(), connect
6、ed(), and count()。蒙特卡洛模拟(Monte Carlo simulation). 要估计渗透阈值,考虑以下计算实验: 初始化所有格点为blocked。 重复以下操作直到系统渗出:o 在所有blocked的格点之间随机均匀选择一个格点 (row i, column j)。o 设置这个格点(row i, column j)为open格点。 open格点的比例提供了系统渗透时渗透阈值的一个估计。例如,如果在2020的网格中,根据以下快照的open格点数,那么对渗滤阈值的估计是204/400 = 0.51,因为当第204个格点被open时系统渗透。 50 open sites100
7、open sites150 open sites204 open sites通过重复该计算实验T次并对结果求平均值,我们获得了更准确的渗滤阈值估计。 令xt是第t次计算实验中open格点所占比例。 样本均值m提供渗滤阈值的一个估计值; 样本标准差s测量阈值的灵敏性。m=x1+x2+xTT, s2=(x1-m)2+(x2-m)2+(xT-m)2T-1假设T足够大(例如至少30),以下为渗滤阈值提供95置信区间:m-1.96sT, m+1.96sT我们创建数据类型PercolationStats来执行一系列计算实验,包含以下API。public class PercolationStats pub
8、lic PercolationStats(int N, int T) / perform T independent computational experiments on an N-by-N grid public double mean() / sample mean of percolation threshold public double stddev() / sample standard deviation of percolation threshold public double confidenceLo() / returns lower bound of the 95%
9、 confidence interval public double confidenceHi() / returns upper bound of the 95% confidence interval public static void main(String args) / test client, described below在N 0或T 0时,构造函数应该抛出java.lang.IllegalArgumentException例外。此外,还包括一个main( )方法,它取两个命令行参数N和T,在NN网格上进行T次独立的计算实验(上面讨论),并打印出均值m、标准差s和95 渗透阈值
10、的置信区间。 使用标准库中的标准随机数生成随机数; 使用标准统计库来计算样本均值和标准差。Example values after creating PercolationStats(200, 100)mean() = 0.5929934999999997stddev() = 0.00876990421552567confidenceLow() = 0.5912745987737567confidenceHigh() = 0.5947124012262428Example values after creating PercolationStats(200, 100)mean() = 0.59
11、2877stddev() = 0.009990523717073799confidenceLow() = 0.5909188573514536confidenceHigh() = 0.5948351426485464Example values after creating PercolationStats(2, 100000)mean() = 0.6669475stddev() = 0.11775205263262094confidenceLow() = 0.666217665216461confidenceHigh() = 0.6676773347835391运行时间和内存占用分析。使用q
12、uick-find算法(QuickFindUF.java from algs4.jar)实现Percolation数据类型。进行实验表明当N加倍时对运行时间的影响;使用近似表示法,给出在计算机上的总时间,它是输入N和T的函数表达式。使用weighted quick-union算法(WeightedQuickUnionUF.java from algs4.jar)实现Percolation数据类型。进行实验表明当N加倍时对运行时间的影响;使用近似表示法,给出在计算机上的总时间,它是输入N和T的函数表达式。二、算法设计程序要求实现对一个NxN矩阵的连通性判断问题,则可以使用quick-find算法
13、和加权quick-union算法来实现,因为算法中的数组是一维的,所以首要解决的问题就是将NxN矩阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。将它们在连通分量数组中的编号依次设置为0NxN-1。为了之后检验连通性的问题,有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口,它和第一行的所有点都是连通的,在矩阵的底部有一个出水口,它和最后一行的所有点是连通的,并分别将注水口和出水口在连通分量数组中的编号设为NxN和NxN+1。按照题目的要求每次随机打开矩阵中的一个点,然后判断与它邻近的点(上下左右)是否已经被打开,若已经打开就将它们连接起来。那么每次打开一个新的结点之后
14、检验连通性,只需要检验注水口和出水口是否连通即可。具体设计:设计Percolation类,分别使用quick-find和weight quick-union算法进行合并。Percolation类中设计open方法打开一个点,并将该点与其它相邻的点合并。public class Percolation private int matrixLength; /网格大小 private boolean matrix; /记录方格是否打开数组private QuickFindUF qu; /合并查找类变量/或者:private WeightedQuickUnionUF wqu; private int
15、virtualTop; /注水口 private int virtualbottom; /出水口public Percolation(int N)if (N = 0) throw new IllegalArgumentException(length must be positive); matrixLength = N; virtualTop = matrixLength * matrixLength; virtualbottom = matrixLength * matrixLength + 1; matrix = new booleanN * N; qu = new QuickFindU
16、F(N * N + 2);/检查边界 private void checkValidIndex(int row,int col) if(row matrixLength) throw new IndexOutOfBoundsException(row index out of bounds); if(col matrixLength) throw new IndexOutOfBoundsException(col index out of bounds); /计算点(row i, col j)的一维坐标 private int rowCol_to_real(int row,int col) r
17、eturn (row - 1) * matrixLength + col - 1; /打开一个点 public void open(int row,int col) checkValidIndex(row, col); /检查边界 int real = rowCol_to_real(row, col); /转换成一维坐标 if (matrixreal) return; /如果已经是打开的,就直接返回 matrixreal = true; if (row = 1) /如果是第一行的情况,那么让他连接top的虚拟点 qu.union(real, virtualTop); if (row = mat
18、rixLength) /如果是最后一行的情况,那么让他连接bottom的虚拟点 qu.union(real, virtualbottom); int neighbor; /记录相邻点的坐标 /判断周围的四个点是否是打开的,如果是的话就连接 if (row 1) / up neighbor = rowCol_to_real(row - 1, col); if (matrixneighbor) qu.union(real, neighbor); if (row 1) / left neighbor = rowCol_to_real(row, col - 1); if (matrixneighbor
19、) qu.union(real, neighbor); if (col matrixLength) / right neighbor = rowCol_to_real(row, col + 1); if (matrixneighbor) qu.union(real, neighbor); public boolean isOpen(int row,int col) /判断这个点是不是已打开的 checkValidIndex(row, col); return matrixrowCol_to_real(row, col); public boolean isPercolated() /判断网格是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 西安电子科技大学 算法 上机 报告
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。