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

西安电子科技大学
(2018年度)
算法分析

实
验
报
告

实验名称： 渗透实验
班 级： 1603012
姓 名： 朱 斌
学 号： 16030120032

实验一：渗透问题（Percolation）
一、实验题目
使用合并-查找（union-find）数据结构，编写程序通过蒙特卡罗模拟（Monte Carlo simulation）来估计渗透阈值的值。
给定由随机分布的绝缘材料和金属材料构成的组合系统：金属材料占多大比例才能使组合系统成为电导体？ 给定一个表面有水的多孔渗水地形（或下面有油），水将在什么条件下能够通过底部排出（或油渗透到表面）？ 科学家们已经定义了一个称为渗透（percolation）的抽象过程来模拟这种情况。
模型： 我们使用N×N网格点来模型一个渗透系统。 每个格点或是open格点或是blocked格点。 一个full site是一个open格点，它可以通过一连串的邻近（左，右，上，下）open格点连通到顶行的一个open格点。如果在底行中有一个full site格点，则称系统是渗透的。（对于绝缘/金属材料的例子，open格点对应于金属材料，渗透系统有一条从顶行到底行的金属路径，且full sites格点导电。对于多孔物质示例，open格点对应于空格，水可能流过，从而渗透系统使水充满open格点，自顶向下流动。）

问题： 在一个著名的科学问题中，研究人员对以下问题感兴趣：如果将格点以空置概率p独立地设置为open格点（因此以概率1-p被设置为blocked格点），系统渗透的概率是多少？ 当p = 0时，系统不会渗出; 当p=1时，系统渗透。 下图显示了20×20随机网格和100×100随机网格的格点空置概率p与渗滤概率。

当N足够大时，存在阈值p*，使得当p <p*，随机N´ N网格几乎不会渗透，并且当p> p*时，随机N´ N网格几乎总是渗透。 尚未得出用于确定渗滤阈值p*的数学解。你的任务是编写一个计算机程序来估计p*。
Percolation数据类型：模型化一个Percolation系统，创建含有以下API的数据类型Percolation。
public class Percolation {
public Percolation(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 percolates() // 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(), connected(), and count()。

蒙特卡洛模拟（Monte Carlo simulation）. 要估计渗透阈值，考虑以下计算实验：
· 初始化所有格点为blocked。
· 重复以下操作直到系统渗出：
o 在所有blocked的格点之间随机均匀选择一个格点 (row i, column j)。
o 设置这个格点(row i, column j)为open格点。
· open格点的比例提供了系统渗透时渗透阈值的一个估计。
例如，如果在20×20的网格中，根据以下快照的open格点数，那么对渗滤阈值的估计是204/400 = 0.51，因为当第204个格点被open时系统渗透。

50 open sites

100 open sites

150 open sites

204 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 {
public 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% 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，在N×N网格上进行T次独立的计算实验（上面讨论），并打印出均值m、标准差s和95％ 渗透阈值的置信区间。 使用标准库中的标准随机数生成随机数； 使用标准统计库来计算样本均值和标准差。
Example values after creating PercolationStats(200, 100)
mean() = 0.5929934999999997
stddev() = 0.00876990421552567
confidenceLow() = 0.5912745987737567
confidenceHigh() = 0.5947124012262428

Example values after creating PercolationStats(200, 100)
mean() = 0.592877
stddev() = 0.009990523717073799
confidenceLow() = 0.5909188573514536
confidenceHigh() = 0.5948351426485464

Example values after creating PercolationStats(2, 100000)
mean() = 0.6669475
stddev() = 0.11775205263262094
confidenceLow() = 0.666217665216461
confidenceHigh() = 0.6676773347835391

运行时间和内存占用分析。
使用quick-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算法和加权quick-union算法来实现，因为算法中的数组是一维的，所以首要解决的问题就是将NxN矩阵中的点经过变换转换到一维数组中对应的位置来完成之后的算法求解。
将它们在连通分量数组中的编号依次设置为0~NxN-1。为了之后检验连通性的问题，有一个非常巧妙的方法。抽象出在矩阵的顶部有一个单独的注水口，它和第一行的所有点都是连通的，在矩阵的底部有一个出水口，它和最后一行的所有点是连通的，并分别将注水口和出水口在连通分量数组中的编号设为NxN和NxN+1。按照题目的要求每次随机打开矩阵中的一个点，然后判断与它邻近的点（上下左右）是否已经被打开，若已经打开就将它们连接起来。那么每次打开一个新的结点之后检验连通性,只需要检验注水口和出水口是否连通即可。
具体设计：
设计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 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 boolean[N * N];
qu = new QuickFindUF(N * N + 2);
}

//检查边界
private void checkValidIndex(int row,int col){
if(row <= 0 || row >matrixLength){
throw new IndexOutOfBoundsException("row index out of bounds");
}
if(col <= 0 || col >matrixLength){
throw new IndexOutOfBoundsException("col index out of bounds");
}
}

//计算点(row 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 (matrix[real]) {
return; //如果已经是打开的，就直接返回
}
matrix[real] = true;

if (row == 1) { //如果是第一行的情况，那么让他连接top的虚拟点
qu.union(real, virtualTop);
}

if (row == matrixLength) { //如果是最后一行的情况，那么让他连接bottom的虚拟点
qu.union(real, virtualbottom);
}
int neighbor; //记录相邻点的坐标
//判断周围的四个点是否是打开的，如果是的话就连接
if (row > 1) { // up
neighbor = rowCol_to_real(row - 1, col);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}

if (row < matrixLength) { // down
neighbor = rowCol_to_real(row + 1, col);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}

if (col > 1) { // left
neighbor = rowCol_to_real(row, col - 1);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}

if (col < matrixLength) { // right
neighbor = rowCol_to_real(row, col + 1);
if (matrix[neighbor]) {
qu.union(real, neighbor);
}
}
}

public boolean isOpen(int row,int col){ //判断这个点是不是已打开的
checkValidIndex(row, col);
return matrix[rowCol_to_real(row, col)];
}

public boolean isPercolated(){ //判断网格是否渗透
return qu.isConnect(virtualTop, virtualbottom);
}
}
QuickFindUF算法核心：每个点所在连通分量记录在以该点为下标的数组中，find方法的复杂度低，但合并时要遍历数组中的所有点，将其中一个连通分量中所有点的连通分量记录改为另一个连通分量，union方法的复杂度高。
public int find(int p) { //由标号找该点所在连通分量
return id[p];
}

public void union(int p,int q){ //合并两个连通分量
int pID=find(p);
int qID=find(q);
if(pID==qID){
return;
}
for(int i=0;i<id.length;i++) //遍历所有点，将与p点在同一连通分量的点合并到q所在的连通分量
if(id[i]==pID) id[i]=qID;
count--;
}
WeightedQuickUnionUF算法核心：以每个点为下标的数组中记录该点的父亲节点，由父亲节点找到根节点，根节点为该连通分量的标记；增加size数组记录每个连通分量的大小，在union时比较两个连通分量的size的大小，将小连通分量连接到大连通分量上，以此来减小树的高度减少查找根节点的时间。
public int find(int p) {//复杂度为两倍的树的高度h 即2h
while(p!=id[p]){
p=id[p];
}
return p;
}
public void union(int p,int q){//不计算find的情况下union的算法复杂度为1
int i=find(p);
int j=find(q);
if(i==j){
return;
}
if(sz[i]<sz[j]){
id[i]=j;
sz[j]+=sz[i];
}
else{
id[j]=i;
sz[i]+=sz[j];
}
count--;
}

三、实验结果及分析
1. QuickFindUF合并查找：

通过以上数据分析：
N一定时，运行时间与T成正比；T一定时，运行时间与N^4成正比；所以用quick-find方法解决渗透问题的时间成长量级为：~N^4T

2. WeightedQuickUnionUF算法：

N一定时，运行时间与T成正比；T一定时，运行时间与lgN2成正比；所以用quick-find方法解决渗透问题的时间成长量级为：~lgN2T
两种算法均得出渗透问题的阈值约为0.59。

（二）几种排序算法的实验性能比较
一、实验题目
实现插入排序（Insertion Sort，IS），自顶向下归并排序（Top-down Mergesort，TDM），自底向上归并排序（Bottom-up Mergesort，BUM），随机快速排序（Random Quicksort，RQ），Dijkstra 3-路划分快速排序（Quicksort with Dijkstra 3-way Partition，QD3P）。在你的计算机上针对不同输入规模数据进行实验，对比上述排序算法的时间及空间占用性能。要求对于每次输入运行10次，记录每次时间，取平均值。

二、算法设计
1.每种排序算法均实现下列模板中的各个方法：
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=a[i];a[i]=a[j];a[j]=t;
}
private static void show(Comparable[] a) {
for(int i=0;i<a.length;i++)
System.out.println(a[i]+" ");
System.out.println();
}
public static boolean isSorted(Comparable[] a) {
for(int i=0;i<a.length;i++)
if(less(a[i],a[i-1])) return false;
return true;
}
}
参与排序的数据均实现Comparable接口。

2.插入排序算法：
public static void sort(Comparable[] a) {
int N=a.length;
for(int i=1;i<N;i++) {
for(int j=i;j>0&&less(a[j],a[j-1]);j--)
exch(a,j,j-1);
}
}
从i=0开始依次取i，将a[i]插入到已经部分有序的a[0]~a[i-1]的合适的位置。

3.自顶向下排序算法：
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,int lo,int mid,int hi) {
int i=lo,j=mid+1;

for(int k=lo;k<=hi;k++)
aux[k]=a[k];
for(int k=lo;k<=hi;k++)
if(i>mid) a[k]=aux[j++];
else if(j>hi) a[k]=aux[i++];
else if(less(aux[j],aux[i])) a[k]=aux[j++];
else a[k]=aux[i++];
}
merge方法不断从两个数组中取出数据进行比较，较小的数据插入到辅助数组中并取该较小数据所在数组的下一个数据继续比较，当有某个数组中的数据取完时则将另一个数组中剩下的数据全部放到辅助数组中，完成两个有序数组合为一个有序数组的排序。

4.自底向上排序算法：
public static void sort(Comparable[] a) {
int N=a.length;
aux=new Comparable[N];
for(int sz=1;sz<N;sz=sz*2)
for(int lo=0;lo<N-sz;lo+=sz*2)
merge(a,lo,lo+sz-1,Math.min(lo+sz*2-1, N-1));
}
从数组大小size为1开始将相邻的大小为size的两个数组用merge方法归并排序，直至辅助数组中的数排完，辅助数组成为每2*size部分有序的数组；增大数组大小size为上一次归并的两个数组大小size的两倍，继续用merge方法将相邻的大小为size的数组排序；增大size重复上一步直至将整个辅助数组排成有序的。merge方法同上。

5.随机快速排序算法：
private static void sort(Comparable[] a,int lo,int hi) {
if(hi<=lo) return;
int j=partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(Comparable[] a,int lo,int hi) {
int i=lo,j=hi+1;
Comparable v=a[lo];
while(true) {
while(less(a[++i],v)) if(i==hi)break;
while(less(v,a[--j])) if(j==lo)break;
if(i>=j)break;
exch(a,i,j);
}
exch(a,lo,j);
return j;
}
Partition方法以传入的数组的第一个数据为切分数据，比切分数据小的数据全部移动到切分数据左边，比切分数据大的全部移动到切分数据右边，将切分数据移动到正确的位置并返回该位置j。
sort方法调用Partition方法得到切分数据a[j]，再递归地对a[j]左右两边的数组调用sort方法直至传入sort方法的数组大小为1（大小为1的数组恒有序），整个数组排序完成。

三、实验结果及分析

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

Dijkstra算法： Dijkstra算法是最短路径问题的经典解决方案。 它在教科书第21章中有描述。 基本思路不难理解。 对于图中的每个顶点，我们维护从源点到该顶点的最短已知的路径长度，并且将这些长度保持在优先队列（priority queue, PQ）中。 初始时，我们把所有的顶点放在这个队列中，并设置高优先级，然后将源点的优先级设为0.0。 算法通过从PQ中取出最低优先级的顶点，然后检查可从该顶点经由一条边可达的所有顶点，以查看这条边是否提供了从源点到那个顶点较之之前已知的最短路径的更短路径。 如果是这样，它会降低优先级来反映这种新的信息。
这里给出了Dijkstra算法计算从0到5的最短路径0-1-2-5的详细过程。
process 0 (0.0)
lower 3 to 3841.9
lower 1 to 1897.4
process 1 (1897.4)
lower 4 to 3776.2
lower 2 to 2537.7
process 2 (2537.7)
lower 5 to 6274.0
process 4 (3776.2)
process 3 (3841.9)
process 5 (6274.0)
该方法计算最短路径的长度。 为了记录路径，我们还保持每个顶点的源点到该顶点最短路径上的前驱。 文件Euclidean Graph.java，Point.java，IndexPQ.java，IntIterator.java和Dijkstra.java提供了针对map的Dijkstra算法的基本框架实现，你应该以此作为起点。 客户端程序ShortestPath.java求解一个单源点最短路径问题，并使用图形绘制了结果。 客户端程序Paths.java求解了许多最短路径问题，并将最短路径打印到标准输出。 客户端程序Distances.java求解了许多最短路径问题，仅将距离打印到标准输出。
目标： 优化Dijkstra算法，使其可以处理给定图的数千条最短路径查询。 一旦你读取图（并可选地预处理），你的程序应该在亚线性时间内解决最短路径问题。 一种方法是预先计算出所有顶点对的最短路径；然而，你无法承受存储所有这些信息所需的二次空间。 你的目标是减少每次最短路径计算所涉及的工作量，而不会占用过多的空间。 建议你选择下面的一些潜在想法来实现， 或者你可以开发和实现自己的想法。
想法1：Dijkstra算法的朴素实现检查图中的所有V个顶点。 减少检查的顶点数量的一种策略是一旦发现目的地的最短路径就停止搜索。 通过这种方法，可以使每个最短路径查询的运行时间与E' log V'成比例，其中E'和V'是Dijkstra算法检查的边和顶点数。 然而，这需要一些小心，因为只是重新初始化所有距离为∞就需要与V成正比的时间。由于你在不断执行查询，因而只需重新初始化在先前查询中改变的那些值来大大加速查询。
想法2：你可以利用问题的欧式几何来进一步减少搜索时间，这在算法书的第21.5节描述过。对于一般图，Dijkstra通过将d[w]更新为d[v] + 从v到w的距离来松弛边v-w。 对于地图，则将d[w]更新为d[v] + 从v到w的距离 + 从w到d的欧式距离 - 从v到d的欧式距离。 这种方法称之为A*算法。这种启发式方法会有性能上的影响，但不会影响正确性。
想法3：使用更快的优先队列。 在提供的优先队列中有一些优化空间。 你也可以考虑使用Sedgewick程序20.10中的多路堆。
测试：美国大陆文件usa.txt包含87,575个交叉口和121,961条道路。 图形非常稀疏 - 平均的度为2.8。 你的主要目标应该是快速回答这个网络上的顶点对的最短路径查询。 你的算法可能会有不同执行时间，这取决于两个顶点是否在附近或相距较远。 我们提供测试这两种情况的输入文件。 你可以假设所有的x和y坐标都是0到10,000之间的整数。

二、算法设计
因为要实现地图路由,地图是一个加权无向图，图中所用的边为加权无向边，实现一个加权无向图的数据结构,初始化地图后，利用Dijkstra算法来找出最短路径。

经典的Dijkstra算法是初始化时就把所有节点的最短路径找出来了，程序优化则可以重用代码（想法1），多次查询两节点间最短路径用同一对象，并且每次查询当找到目标节点后便停止，不再遍历其他的节点。然后将上一次查询改变的成员变量部分还原，以供下一次的查询使用，这样便大大的优化了传统的Dijkstra算法。优化方法采用的想法1减少检查的顶点数量,一旦发现目的地的最短路径就停止搜索。

通过这种方法使每个最短路径查询的运行时间与Elog V成比例,在不断执行查询，每次重新初始化在先前查询中改变的那些值来大大加速查询。

public class DijkstraUndirectedSP {

private double[] distTo;
private Edge[] edgeTo;
private IndexMinPQ<Double> 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) {}
//还原上一次查询被修改的部分
public void itijkstra() {}
//遍历到一个节点所经过的边
public Iterable<Edge> pathTo(int v) {}
}

想法1实现：
调用setFrom函数设置算法的起点,每次设置新的起点后,调用initDijkstra方法还原上次查询操作被修改的数据。

//设置算法的起点
public void setFrom(int from) {
/ /开始新的一-次查询后把上一次修改过的部分还原初始化
initDijkstra();
this.from = from;
distTo[from] = 0.0;