高级算法课程

1、、程序运行指南1、程序介绍本程序为高级算法课程的实验程序，共完成了二分图的最大匹配算法、最大 网络流的Dinic算法和欧几里德TSP问题的ESTPAPPROX近似算法三个题目。经 过测试，程序可以编译运行通过。程序的编码语言为JAVA,开发工具为Eclipse。2、运行方法该程序为Applet应用程序，目前已经将其嵌入到网页中进行显示，可以直接 点击Algorithm.html页面运行。如果提示有阻止的内容，请选择“允许”。打开 成功后，即可看到实验程序的运行界面。用户可以在相应的算法演示区域输入想 要测试的数据，如果信息无误，在底部的结果区域会显示运行结果。如图所示:HungaryHHung

2、aryH法演示话输入节点个数：|话输入边的个数二|话输入边的信息（包括起点和终点）:Dinic算法演示 TOC o 1-5 h z 话输入节点个数：|话输入边的个数二|话输入边的信息（包括起点.终点和权值）:EtsapapproxS 法演示话输入节点个数：II话输入边的个数：II话输入边的信息（包括起点、终点和权值）:匹配个数为:二、Dinic 算法1、实验名称利用JAVA语言实现最大网络流的Dinic算法2、实验目的在一个给定的网络（G,s,t,c）中找到一个从s到t的最大网络流问题被称为最大 流问题。Dinic算法就是一个找到最大流的算法，并且可以将时间复杂度减少到 O（mn2）。在算法M

3、PLA中，在计算层次图后，增广路径逐条找出。相反，Dinic 算法将更有效地找出所有这些增广路径，这也正是改进了运行时间的原因。3、算法基本思想Dinic算法是基于“层次图”的时间效率优先的最大流算法。层次是指从源点 走到终点的最短路径长度。因此，从源点开始，在层次图中沿着边不管怎么走， 经过的路径一定是终点在剩余图中的最短路径。在Dinic算法中，我们首先要判断有没有能到达终点的路径（即判断是否存 在增广路径)，在这个过程中我们就可以把层次图计算出来，然后沿着层次图一 层一层地寻找增广路径。如果找到一条增广路径就进行增广(注意在沿着层次图 寻找增广路径的时候使用栈的结构，把路径压进栈中)。增

4、广完成后就继续寻找， 如果找不到则退栈，并继续寻找下一层节点是否有与这个节点相连的，知道栈为 空。如在算法MPLA中那样，Dinic方法被分成之多n个阶段，每一个阶段由寻找 出层次图和关于此层次图的阻塞流以及用阻塞流来增加当前流这样几部分组成。 中间的while循环基本上是一个深度优先搜索，在那里找到增广路径用来增加流 量。这里，p=s,是一条至此为止找到的当前路径。在内层的while循环中有两 个基本的运算，如果在当前路径的一端是u而不是七并且u至少有一条边自u 引出，比如说(u,v)，则向前运算就开始了。这个运算包括添加v到p，并让它成 为p的当前端点。另一方面，假如u不是七并且没有边从u

5、引出，此时进行后 退运算。这个运算只是相当于把u从p的一端拿掉，并在当前层次图L中移去所 有和u邻接的边，因为不可能有任何增广路径经过u。如果t已到达，或者搜索 后退到s点并且从s出来的所有邻接边都已探究，则内层的while循环结束。如 果到达t，这也就说明一条增广路径被找到了，跟随在内while循环后的步骤将 根据这一路径执行增值。另一方面，如果已经到达s，并且所有从它引出的边已 被删除，那么就没有增值发生，并且对当前层次图的处理已完成。4、算法伪代码算法1实现最大流的Dinic算法输入：网络(G,s,t,c)输出：G中的最大流for 每条边(u,v)EEf(u,v) 0end for初始化

6、剩余图，设R=G查找R中的层次图Lwhile t为L中的顶点uspuwhileoutdegree(s)0开始阶段while u#t and outdegree(s)0if outdegree(u)0 then 前进设(u,v)为L中的一条边pp,vuvelse exit删除u和L中所有的邻接边从p的末尾删除u将u设置为p中最后一个顶点end ifend whileif u=t then设为p中的瓶颈容量，用增值p中的当前流。在剩余图中 和层次图中调整p的容量，删除饱和边。设u是p中从s可到达的最后 顶点，注意u可能是s。end ifend while从当前剩余图R中重新计算层次图Lend wh

7、ile5、算法核心代码深度优先遍历算法private static int myDFS(int tempV, int myFlow)(int myD = myFlow;if(tempV = nodeNum)return myFlow;for(int i = 1; i 0 & data tempV+1 = data i)( int flow = myDFS(i, myMIN(myD, temptempVi); temptempVi -= flow; temp itempV += flow;myD -= flow;return myFlow - myD;(2)广度优先遍历算法private sta

8、tic boolean myBFS()(for(int i = 0; i NUM; i+)data i = -1;data 1 = 0;Queue queue = new LinkedList(); queue.add(l);while (! queue.isEmpty()int tempV = queue.poll();for(int j = 1; j = nodeNum; j+)if(dataj= -1 & temptempVj != 0) data j = datatempV+1; queue.add(j);return data nodeNum!= -1;6、实验结果在文本框中输入图中

9、节点的个数，如图所示:在文本框中输入图中边的个数，如图所示:请输入边的个数：10在文本域中输入边的信息，包括起点、终点和边上的权值。每一组数据之 间以空格分隔，组与组之间请回车，如下图所示：话输入边的信息(包括起点、终点和权值):2 1 3 TOC o 1-5 h z 3 423 22 1 04 93 25 S4516 76 y|(4)点击“执行算法”按钮，如果输入信息合法，则在结果文本框中将会显示 出最大网络流的值，如图所示：DinicS法演示 TOC o 1-5 h z 诺输入节点个数二|e|诺输入边的个数二|何|诺输入边的信息(包括起点、终点和权值)2 1 33 43 22 1U4 93

10、 25 85 16 76 9执行耸法 活晦数据最大网雄流的值为：|估|(5)再次进行实验时可以点击“清除数据”按钮，这样已经输入的信息将会自 动清空。三、ESTPAPPROX近似算法1、实验名称利用JAVA语言实现欧几里德TSP问题的ESTPAPPROX近似算法2、实验目的有很多困难的组合最优化问题不能用回溯法和随机化算法有效地解决，在这 种情况下，对于其中的一些问题代之以设计近似算法，我们要保证它是近似于最 优解的一个“合理”的解。欧几里德旅行商问题的一个特殊情况是，给出一个平 面上n点的集合S，找出一个在这些点上的最短长度的游程t，这里，一个游程 是恰好访问每点一次的一条回路。这个问题通常

11、被称为EUCLIDEAN MINIMUM SPANNING TREE(EMST)。ESTPAPPROX近似算法可以找出一个最小权重匹配。3、算法基本思想组合最优化问题不是最小化问题，就是最大化问题。它由三部分组成：一个实例集合D；对于每个实例Il D，存在I的一个候选解的有限集S(I)；D中的一个实例I的每个解6 I S(I)，存在一个值f(6 )，称为6的解值。旅行商问题是著名的组合优化问题，该问题的具体描述是：某售货员要到若 十城市去推销商品，已知各城市间的路程(或旅费)，要求选定一条从驻地出发， 经过每个城市恰好一次，最后回到驻地的路线，使总的路程(或旅费)最小。MST(最小生成树)启发

12、式法：首先，构造一个最小耗费生成树T，接着通过将 T的每边复制成两份从T构造出多重图T，接下来，找出一个欧拉游程t (欧拉 游程是一条回路，它恰好访问每条边一次)。一旦找到了 t,就可以通过跟踪欧拉 游程t和删除那些已经访问过的顶点很容易地把它转换成要求的哈密顿游程t。ESTPAPPROX近似算法对MST近似算法背后的思想进行了改进，以得到这个 问题的更好的近似度。为了把T变成欧拉图，不把它的边加倍，而是首先识别出 那些度数为奇数的顶点集合X，X的奇数总是偶数。接着在X的成员上找出权重最小的匹配M，最后，令T=T M。显然，T中的每个顶点度数为偶数，于是T 是欧拉图。这种方法就称为最小匹配(M

13、M)启发式法。4、算法伪代码算法2欧几里德TSP问题的ESTPAPPROX近似算法输入：欧几里得TSP问题的一个实例I输出：实例I的一个游程t找出S的一个最小生成树识别T中度数为奇数的集合X在X中查找最小权重匹配M在TUM中查找欧拉游程t按边跟踪t，删除那些已访问过的顶点，设t为结果游程5、算法核心代码递归实现深度优先遍历private static void myDFS(int nodeid)(if (flag nodeid = true) return;result += String. valueOf(nodeid) + flagnodeid = true;for(int i=0;i n

14、odeNum;i+)(if(graphMatrix nodeidi = -1) myDFS(i);主程序boolean flag = new boolean nodeNum ;int numOfU = 0;for(int i=0;i nodeNum;i+)flagi = false;flag0 = true;numOfU = 1;while (true)(if(numOfU = nodeNum) break;int nodel = -100;int node2 = -100;int nowMinWeight = MaxNum + 1;for(int i=0;i nodeNum;i+)( if(

15、flagi = true)(for(int j=0;jnodeNum;j+)(if(graphMatrix ij!=-1 & graphMatrix ijr，则M1M2至少包含k=s-r条顶点不相交的关于M1的增广路径。设G=(XY,E)是一个二分图，有|X| + |Y|=n和|E|=m。设M是G中的匹配，我 们把X中的顶点称为x顶点，同样把Y中顶点称为y顶点。首先找一个自由的x 顶点，比如说r，把它标记为外部的。从r开始，我们逐步生成一棵交替路径树， 即每一条从根节点r到叶子的路径均为交替路径。这棵树称为T，其构造过程如 下。从r开始，加上每一条连接r和y顶点y的未匹配边(r,y)，并标记为

16、y为 内部的。对于和r邻接的y顶点y,如果有匹配边(y,z)存在，就把它加入丁，并 标记z为外部的。重复上述过程扩大这棵树直到遇到一个自由的y顶点，比如说 v，那么从根r到v的交替路径即为一条增广路径。另一方面，若树被阻塞，则 这棵树称为匈牙利树。接下来，我们从另一个自由x顶点开始，重复上述步骤。如果T是匈牙利树，那么它就不能再扩大了，每一条从根出发的交替路径在 某个外部顶点停止。T中惟一的自由顶点为它的根。注意到如果(x,y)是一条边， 使得x在T中而y不在T中，那么x肯定是标记为内部的，否则x 一定连接到一 个自由顶点或者T从x处可扩大。这样在匈牙利树中没有顶点能在增广路径还只 能出现。假

17、定p是一条交替路径，它至少有一个T中的顶点，如果p “进入” T， 那么它必然穿过一个标记为内部的顶点；如果p “离开” T，那么它也必然穿过 一个标记为内部的顶点。但是这是p不是交替路径了，这是一个矛盾。这也蕴含 着下面重要的观察结论。观察结论：在搜索增广路径的过程中，如果找到一棵匈牙利树，那么它可被 永久地移去而不影响搜索过程。4、算法伪代码算法3二分图的匈牙利树算法输入：二分图G=(X U Y,E)输出：G中的最大匹配M初始化M为任意匹配while存在一个自由的x顶点和一个自由的y顶点设r为一个自由的x顶点，采用广度优先搜索，生成一个以r为根的 交替路径树Tif如果T为匈牙利树then

18、GG-T 删除Telse在T中找到一条增广路径p，并设M= Mpelse while5、算法核心代码private static boolean myDFS(int temp)(for(int i=1; i = nodeNum; i+)(if (hashMap tempi & ! viNode i)( viNodei = true;if(testi = 0 | myDFS( testi)( test i = temp;return true;return false;6、实验结果在文本框中输入图中节点的个数，如图所示：诺输入节点个觐：g在文本框中输入图中边的个数，如图所示：话输入边的个数：g在文本域中输入