西安电子科技大学算法上机报告

1、爰氯西安电子科技大学（2018年度）算法分析实验报告实验名称：渗透实验班级：1603012姓名：朱斌学号：16030120032实验一：渗透问题（Percolation ）一、实验题目使用合并-查找（union-find ）数据结构，编写程序通过蒙特卡罗模拟（ Monte Carlo simulation）来估计渗透阈值的值。给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组合系统成为电导体？给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下能够通过底部排出（或油渗透到表面）？科学家们已经定义了一个称为渗透（percolation的抽象过程来模拟这种情况。

2、模型：我们使用N x N网格点来模型一个渗透系统。每个格点或是openly点或是blocked格点。 一个full site是一个opern点，它可以通过一连串的邻近（左，右，上，下）oper点连通到顶行的一个 opern点。如果在底行中有一个 full site格点，则称系统是渗透的。（对 于绝缘/金属材料白例子，oper点对应于金属材料，渗透系统有一条从顶行到底行的金属 路径，且full sites格点导电。对于多孔物质示例，opern点对应于空格，水可能流过，从而渗透系统使水充满 opern点，自顶向下流动。）BEdo画 nci percolateopen s加 connected to

3、 topno open H能 conneaed to mp问题： 在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率p独立地设置为opern点（因此以概率 1-p被设置为blocke略点），系统渗透的概率是多少?当p= 0时，系统不会渗出；当p=1时，系统渗透。 下图显示了 20X20随机网格和100X100随机网格的格点空置概率 p与渗滤概率。percohuionprobabilitysite vacancy probability psite vacancy probability p当N足够大时，存在阈值 p*,使得当p 炉，随机N x N网格几乎不会渗透，并且当 p

4、p*时，随机NMN网格几乎总是渗透。尚未得出用于确定渗滤阈值p*的数学解。你的任务是编写一个计算机程序来估计p*opublic Percolation(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)Percolation数据类型：模型化一个Percolation系统，创建含有以下 API的数据类型Perc

5、olation。 public class Percolation / 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) open?/ is site (row i, column j) full?/ does the system percolate?/ test client, optional 约定行i列j下标在1和N之间,其中(1, 1)为左上格点位置：如果open(), isOpen(), or

6、isFull() 不在这个规定的范围，则抛出IndexOutOfBoundsException例外。如果N 0构造函数应该抛出川egalArgumentException例外。构造函数应该与N2成正比。所有方法应该为常量时间加上常量次调用合并 -查找方法union(), find(), connected(), and count()。蒙特卡洛模拟(Monte Carlo simulation ).要估计渗透阈值，考虑以下计算实验：初始化所有格点为 blocke d重复以下操作直到系统渗出：o 在所有blocked勺格点之间随机均匀选择一个格点(row i, column j)。o 设置这个格

7、点(row i, column j)为 oper点。 opern点的比例提供了系统渗透时渗透阈值的一个估计。例如，如果在20X20的网格中，根据以下快照的opern点数，那么对渗滤阈值的估计是204/400 = 0.51 ,因为当第204个格点被ope的系统渗透。50 open sites100 open sites150 open sites204 open sites通过重复该计算实验 T次并对结果求平均值，我们获得了更准确的渗滤阈值估计。令xt是第t次计算实验中ope格点所占比例。样本均值任提供渗滤阈值的一个估计值；样本标准差;测量阈值的灵敏性。假设T足够大(仞如至少 30),以下为渗滤

8、阈值提供 95%置信区间:N -PercolationStats 来执行我们创建数据类型public 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()public static void main(String口 args)crcr-R系列计算实验，包含以下 API。/ perform T in

9、dependent 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 95% confidence interval/ test client, described below在 NW 0或 T 0时，构造函数应该抛出java.lang.IllegalArg

10、umentException 例外。此外，还包括一个 main()方法，它取两个命令行参数 N和T,在N x N网格上进行T次独 立的计算实验(上面讨论)，并打印出均值 N、标准差仃和95%渗透阈值的置信区间。使用标准库中的标准随机数生成随机数；使用标准统计库来计算样本均值和标准差。Example values after creating PercolationStats(200, 100)mean()stddev()confidenceLow() confidenceHigh()=0.5929934999999997=0.00876990421552567=0.59127459877375

11、67=0.5947124012262428Example values after creating PercolationStats(200, 100)mean() stddev() confidenceLow() confidenceHigh()=0.592877=0.009990523717073799=0.5909188573514536=0.5948351426485464Example values after creating PercolationStats(2, 100000)mean()=0.6669475stddev()=0.11775205263262094confid

12、enceLow()=0.666217665216461confidenceHigh()=0.6676773347835391运行时间和内存占用分析。使用 quick-fine法(QuickFindUF.java from algs4.jar)实现 Percolation 数据类型。进行实 验表明当N加倍时对运行时间的影响；使用近似表示法，给出在计算机上的总时间，它是 输入N和T的函数表达式。使用 weighted quick-un辑该(WeightedQuickUnionUF.java from algs4.jar)实现 Percolation数据类型。进行实验表明当N加倍时对运行时间的影响；

13、使用近似表示法，给出在计算机上的总时间，它是输入 N和T的函数表达式。二、算法设计程序要求实现对一个 NxN矩阵的连通性判断问题，则可以使用quick-find算法和加权 quick-union算法来实现，因为算法中的数组是一维的，所以首要解决的问题就是将NxN矩阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。将它们在连通分量数组中的编号依次设置为0NxN-1。为了之后检验连通性的问题，有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口，它和第一行的所有点都是连通的，在矩阵的底部有一个出水口，它和最后一行的所有点是连通的，并分别将注水口和出水口在连通分量数组中的编号设为

14、NxN和NxN+1。按照题目的要求每次随机打开矩阵中的一个点，然后判断与它邻近的点(上下左右)是否已经被打开，若已经打开就将它们连 接起来。那么每次打开一个新的结点之后检验连通性只需要检验注水口和出水口是否连通即可。具体设计:Percolation设计Percolation类，分别使用 quick-find和weight quick-union算法进行合并。类中设计open方法打开一个点，并将该点与其它相邻的点合并。classprivate int matrixLength;/网格大小private boolean matrix;/记录方格是否打开数组private QuickFindUF q

15、u; /合并查找类变量/ 或者：private WeightedQuickUnionUF wqu;private int 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 * matri

16、xLength + 1;matrix = new booleanN * N;qu = new QuickFindUF(N * N + 2);/检查边界private void checkValidIndex(int row,int col)if(row = 0 | row matrixLength)thrownew IndexOutOfBoundsException(row index out of bounds);if(col matrixLength)thrownew IndexOutOfBoundsException(col index out of bounds);)/计算点(row

17、i, col j)的一维坐标 private int rowCol to real(int row,int col)return (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;/如果已经是打开的，就直接返回if (row = 1) /如果是第一行的情况，那么让他连接top的虚拟点qu.union(

18、real, virtualTop);if (row = matrixLength) /如果是最后一行的情况，那么让他连接bottom的虚拟点qu.union(real, virtualbottom);int neighbor; /记录相邻点的坐标-6 -/判断周围的四个点是否是打开的，如果是的话就连接if (row 1) / upneighbor = rowCol to real(row - 1, col);if (matrixneighbor) qu.union(real, neighbor);if (row 1) / leftneighbor = rowCol to real(row, c

19、ol - 1);if (matrixneighbor) qu.union(real, neighbor);if (col matrixLength) / rightneighbor = 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 is

20、Percolated()/判断网格是否渗透return qu.isConnect(virtualTop, virtualbottom);QuickFindUF算法核心：每个点所在连通分量记录在以该点为下标的数组中，And方法的复杂度低，但合并时要遍历数组中的所有点，将其中一个连通分量中所有点的连通分量记由标号找该点所在连通分量录改为另一个连通分量，union方法的复杂度高。public int find(int p) /return idp;public void union(int p,int q) /合并两个连通分量int pID=find(p);int qID=find(q);if(pI

21、D=qID)return;)for(int i=0;iid.length;i+) /遍历所有点，将与p点在同一连通分量的点合并到q所在的连通分量if(idi=pID) idi=qID;count-;WeightedQuickUnionUF算法核心：以每个点为下标的数组中记录该点的父亲节点，由父亲节点找到根节点，根节点为该连通分量的标记；增加size数组记录每个连通分量的大小，在union时比较两个连通分量的size的大小，将小连通分量连接到大连通分量上，以此来减小树的高度减少查找根节点的时间。public int find(int p) /复杂度为两倍的树的高度h即2hwhile(p!=idp

22、)p=idp;)return p;public void union(int p,int q)/不计算find的情况下union的算法复杂度为1int i=find(p);int j=find(q);if(i=j)return;if(sziszj) idi=j;)三、实验结果及分析QuickFindUF 合并查找:Pl哒dse ertr N nd T : 100 50The incon of percolationStats is 0,591978The stddev of percolationStats is 0.616905627650075382Th，匚口ndidgne interva

23、ls of p*rcolationSt is 0.5B726982A?201 0.596686175779896 Thg tiifiQ of the prog rami is IJWriis通过以上数据分析：N 一定时，运行时间与T成正比；T 一定时，运行时间与N”成正比；所以用quick-find 方法解决渗透问题的时间成长量级为：44 TWeightedQuickUnionUF 算法： wnter N jnd T :rh hi#an of p#rcolftliDnStatf it 白一%74砧时的密）0001The stddflv of percolsticnStflts 狂 O,6163

24、67267066475The ccndidcnca inUnvuli of parcel at icn Sti e. 5929156753399d5S , 3.60195632666&056JTFw time of tbv prugrjrr it iidni*PJ.wds例 vntiat1 N nd r :100 1 的The of percolatioHStots is57263 1*999999999The Etddeu of porcoLutionStJt 工5 e.ei617l6032350ei54Th curdidncff intrvdl V 哼F式4七1ksiit 我 5&融电35

25、657659397 , 0.595%则M2M箕心 Th* tim* nf th* prcgr*rn if J05hswnlr N dnd I : 2 翻Th* of p4rcaldtiuStdt ii &.S93103999599997TM 廿.曰1日211902358123335TM tondidentc intcrvdii. of pureLdion&htE i& 色 5州“8g754优3期,6.593293922593669 The tig of th电 pgrjim is h/ismsN 一定时，运行时间与T成正比；T 一定时，运行时间与lgN2成正比；所以用quick-find 方法

26、解决渗透问题的时间成长量级为：lgN 2t两种算法均得出渗透问题的阈值约为0.59。-10 -(二)几种排序算法的实验性能比较一、实验题目实现插入排序(Insertion Sort, IS),自顶向下归并排序 (Top-down Mergesort,TDM ), 自底向上归并排序 (Bottom-up Mergesort, BUM),随机快速排序 (Random Quicksort, RQ), Dijkstra 3-路划分快速排序(Quicksort with Dijkstra 3-way Partition , QD3P )。在你的计算机上 针对不同输入规模数据进行实验，对比上述排序算法的时

27、间及空间占用性能。要求对于每次输入运行10次，记录每次时间，取平均值。二、算法设计.每种排序算法均实现下列模板中的各个方法:public class Example public static void sort(Comparable a) private static boolean less(Comparable v,Comparable w) return pareTo(w)0;private static void exch(Comparable口 a,int i,int j) Comparable t=ai;ai=aj;aj=t;private static void show(Co

28、mparable口 a) for(int i=0;ia.length;i+)System.out.println(ai+);System.out.println();public static boolean isSorted(Comparable口 a) for(int i=0;ia.length;i+)if(less(ai,ai-1) return false;return true;参与排序的数据均实现Comparable接口。.插入排序算法:static voidint N=a.length;for(int i=1;i0&exch (a,j,j-1);)从i=0开始依次取i,将ai插入

29、到已经部分有序的a0ai-1的合适的位置。.自顶向下排序算法：private static void sort(Comparable口 a,int lo,int hi) if(hi=lo) return;int mid=lo+(hi-lo)/2;sort (a,lo,mid);sort (a,mid+1,hi);merge (a,lo,mid,hi);)在sort方法中递归地调用sort方法将大数组二分为两个小数组直至两个小数组大小为1 ,再在递归返回时调用merge方法将已经有序的两个小数组合并成一个较大的有序数组。public static void merge(Comparable口 a

30、,int lo,int mid,int hi) int i=lo,j=mid+1;for(int k=lo;k=hi;k+)aux k=ak;for(int k=lo;kmid)ak=aux j+;else if(jhi)ak=aux i+;else if( less (aux j, aux i) ak= aux j+;elseak=aux i+;merge方法不断从两个数组中取出数据进行比较，较小的数据插入到辅助数组中并取该较小数据所在数组的下一个数据继续比较，当有某个数组中的数据取完时则将另一个数组中剩下的数据全部放到辅助数组中，完成两个有序数组合为一个有序数组的排序。4.自底向上排序算法

31、:public static void sort(Comparable a) int N=a.length;aux =new ComparableN;for(int sz=1;szN;sz=sz*2)min (lo+sz*2-1, N-1);for(int lo=0;loN-sz;lo+=sz*2)merge (a,lo,lo+sz-1,Math.-12 -）从数组大小size为1开始将相邻的大小为 size的两个数组用 merge方法归并排序， 直至辅助数组中的数排完，辅助数组成为每2*size 部分有序的数组；增大数组大小size为上一次归并的两个数组大小size的两倍，继续用merge方

32、法将相邻的大小为 size的数组排序；增大size重复上一步直至将整个辅助数组排成有序的。merge方法同上。5,随机快速排序算法：private static void sort(Comparable a,int lo,int hi) if(hi=j)break;exch (a,i,j);exch (a,lo,j);return j;Partition方法以传入的数组的第一个数据为切分数据，比切分数据小的数据全部移动到切分数据左边，比切分数据大的全部移动到切分数据右边，将切分数据移动到正确的位置并返回1位置j。sort方法调用Partition方法得到切分数据aj,再递归地对aj左右两边的数

33、组调用sort方法直至传入sort方法的数组大小为1 （大小为1的数组恒有序），整个数组排序完 成。-13 -1 91 b i nj avaw. exe (201 9 目三、实验结果及分析 SortCorn pare -Java Application G :JAVAjre 1.S.0_1000工S已排序15执行时间:13.053sTDM已排序TDM执行时间:0.037sBUM已排序BUM执行时间：0.062sRQ已排序RQ执行日寸间士 0.042sQD3P已排序QD3P执行时间：0.054s-termi n a ted &ortCompare Jsws Application G:JAVAj

34、 rel .8.0=191 binjavaw.eKe-120195600IS已排序工S执行时fib 12.908sTDM已排序TDM执行时间：0.0345BUM已排序BUM执行时间:0.031sRQ已排序RQ执行时间:0.046sQD3P已排序QD3P执行时间：0.041s SortCompare Java Application G:JAVAjre1.8,0_1 9IXbiinSjavaw.exe (201 91000015已排序15执行E寸间：13.313sTDM已排序TDM执行时间：0.042sBUM已排序BUM执行时间:0.04sRQ已排序RQ执行时间：0.952sQD3P已排序3P执

35、行时间;0.053s由以上实验结果可以看出插入排序花的时间最多，其他四种排序算法时间开销相差不大,比插入排序快很多，随机快排排序最快。-14 -（三）地图路由（Map Routing）一、实验题目实现经典的 Dijkstra最短路径算法，并对其进行优化。这种算法广泛应用于地理信息系统（GIS）,包括MapQuest和基于GPS的汽车导航系统。地图：本次实验对象是图 map或graphs其中顶点为平面上的点，这些点由权值为欧氏 距离的边相连成图。可将顶点视为城市，将边视为相连的道路。为了在文件中表示地图，我们列出了顶点数和边数，然后列出顶点（索引后跟其x和y坐标），然后列出边（顶点对）， 最后列

36、出源点和汇点。 例如，如下左图信息表示右图：6 9 ） 0 1000 Z4QQ TOC o 1-5 h z 2800 3QQ02400 250Q40000一4500 380D6000 1500II AXDijkstra算法：Dijkstra算法是最短路径问题的经典解决方案。它在教科书第21章中有描述。基本思路不难理解。对于图中的每个顶点，我们维护从源点到该顶点的最短已知的路径长度，并且将这些长度保持在优先队列（priority queu（PQ）中。 初始时，我们把所有的顶点放在这个队列中，并设置高优先级，然后将源点的优先级设为0.0。算法通过从PQ中取出最低优先级的顶点，然后检查可从该顶点经由

37、一条边可达的所有顶点，以查看这条边是否提供了从源点到那个顶点较之之前已知的最短路径的更短路径。如果是这样，它会降低优先级来反映这种新的信息。这里给出了 Dijkstra算法计算从0至U 5的最短路径0-1-2-5的详细过程。process 0 （0.0）lower 3 to 3841.9lower 1 to 1897.4process 1 （1897.4）lower 4 to 3776.2lower 2 to 2537.7process 2 （2537.7）lower 5 to 6274.0 process 4 (3776.2)process 3(3841.9)process 5 (6274.

38、0)-15 -该方法计算最短路径的长度。为了记录路径，我们还保持每个顶点的源点到该顶点最短路径上的前驱。文件 Euclidean Graph.java, Point.java, IndexPQ.java, Intlterator.java 和Dijkstra.java提供了针对 map的Dijkstra算法的基本框架实现，你应该以此作为起点。客户端程序ShortestPath.java求解一个单源点最短路径问题，并使用图形绘制了结果。客户端程序Paths.java求解了许多最短路径问题，并将最短路径打印到标准输出。客户端程序Distances.java求解了许多最短路径问题，仅将距离打印到标准

39、输出。目标：优化Dijkstra算法，使其可以处理给定图的数千条最短路径查询。一旦你读取图（并可选地预处理），你的程序应该在亚线性时间内解决最短路径问题。一种方法是预先计算出所有顶点对的最短路径；然而，你无法承受存储所有这些信息所需的二次空间。你的目标是减少每次最短路径计算所涉及的工作量，而不会占用过多的空间。建议你选择下面的一些潜在想法来实现，或者你可以开发和实现自己的想法。想法1: Dijkstra算法的朴素实现检查图中的所有V个顶点。减少检查的顶点数量的一种策略是一旦发现目的地的最短路径就停止搜索。通过这种方法，可以使每个最短路径查询的运行时间与 E log V成比例，其中E和V是Dij

40、kstra算法检查的边和顶点数。然而，这需要一些小心，因为只是重新初始化所有距离为8就需要与V成正比的时间。由于你在不断执行查询，因而只需重新初始化在先前查询中改变的那些值来大大加速查询。想法2：你可以利用问题的欧式几何来进一步减少搜索时间，这在算法书的第21.5节描述过。对于一般图，Dijkstra通过将dw更新为dv +从v到w的距离来松弛边 v-w。对于 地图，则将dw更新为dv +从v到w的距离+从w到d的欧式距离 一从v到d的欧式 距离。 这种方法称之为 A*算法。这种启发式方法会有性能上的影响，但不会影响正确性。想法3:使用更快的优先队列。在提供的优先队列中有一些优化空间。你也可以

41、考虑使用Sedgewick程序20.10中的多路堆。测试：美国大陆文件usa.txt包含87,575个交叉口和121,961条道路。图形非常稀疏-平 均的度为2.8。你的主要目标应该是快速回答这个网络上的顶点对的最短路径查询。你的算法可能会有不同执行时间，这取决于两个顶点是否在附近或相距较远。我们提供测试这两种情况的输入文件。你可以假设所有的 x和y坐标都是0到10,000之间的整数。二、算法设计因为要实现地图路由，地图是一个加权无向图，图中所用的边为加权无向边，实现一个 加权无向图的数据结构，初始化地图后，利用 Dijkstra算法来找出最短路径。经典的Dijkstra算法是初始化时就把所有

42、节点的最短路径找出来了，程序优化则可以重用代码（想法 1）,多次查询两节点间最短路径用同一对象，并且每次查询当找到目标节点 后便停止，不再遍历其他的节点。然后将上一次查询改变的成员变量部分还原，以供下一次的查询使用，这样便大大的优化了传统的Dijkstra算法。优化方法采用的想法 1减少检查的顶点数量，一旦发现目的地的最短路径就停止搜索。通过这种方法使每个最短路径查询的运行时间与Hog V成比例，在不断执行查询，每次重新初始化在先前查询中改变的那些值来大大加速查询。-16 -public class DijkstraUndirectedSP private double distTo;priv

43、ate Edge edgeTo;private IndexMinPQ pq;private EdgeWeightedGraph mGraph;private int from;public DijkstraUndirectedSP(EdgeWeightedGraph G) 设置算法的起点public void setFrom(int from) 更新到节点的最短路径private void relax(Edge e, int v) 获取到某一节点的最短距离public double distTo(intv) 在这里才执行相关的路径初始化public boolean hasPathTo(intv

44、) 还原上一次查询被修改的部分public void itijkstra() 遍历到一个节点所经过的边public Iterable pathTo(int v) 想法1实现：调用setFrom函数设置算法的起点，每次设置新的起点后，调用initDijkstra方法还原上次 查询操作被修改的数据。/设置算法的起点public void setFrom(int from) / /开始新的-次查询后把上一次修改过的部分还原初始化initDijkstra();=from;distTofrom = 0.0;pq. insert(from, distTofrom);-17 -/还原上一次查询被修改的部分public void initDijkstra()for (int i = 0; i mGraph.v(); i+) if (pq. contains(i) pq.delete(i);if (edgeToil=nul1) edgeToi=null;if (!Double. isInfinite(distTo(i) distToi=Double. POSITIVE. INFINITY;当执行查询源点到目的地的最短路径时调用 hasPathTo方法来查询，不断的从优先队列