高级算法课程实验报告文档格式.docx
- 文档编号:787290
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:14
- 大小:69.61KB
高级算法课程实验报告文档格式.docx
《高级算法课程实验报告文档格式.docx》由会员分享,可在线阅读,更多相关《高级算法课程实验报告文档格式.docx(14页珍藏版)》请在冰点文库上搜索。
增广完成后就继续寻找,如果找不到则退栈,并继续寻找下一层节点是否有与这个节点相连的,知道栈为空。
如在算法MPLA中那样,Dinic方法被分成之多n个阶段,每一个阶段由寻找出层次图和关于此层次图的阻塞流以及用阻塞流来增加当前流这样几部分组成。
中间的while循环基本上是一个深度优先搜索,在那里找到增广路径用来增加流量。
这里,p=s,…,u是一条至此为止找到的当前路径。
在内层的while循环中有两个基本的运算,如果在当前路径的一端是u而不是t,并且u至少有一条边自u引出,比如说(u,v),则向前运算就开始了。
这个运算包括添加v到p,并让它成为p的当前端点。
另一方面,假如u不是t,并且没有边从u引出,此时进行后退运算。
这个运算只是相当于把u从p的一端拿掉,并在当前层次图L中移去所有和u邻接的边,因为不可能有任何增广路径经过u。
如果t已到达,或者搜索后退到s点并且从s出来的所有邻接边都已探究,则内层的while循环结束。
如果到达t,这也就说明一条增广路径被找到了,跟随在内while循环后的步骤将根据这一路径执行增值。
另一方面,如果已经到达s,并且所有从它引出的边已被删除,那么就没有增值发生,并且对当前层次图的处理已完成。
4、算法伪代码
算法1实现最大流的Dinic算法
输入:
网络(G,s,t,c)
输出:
G中的最大流
1.for每条边(u,v)∈E
2.f(u,v)←0
3.endfor
4.初始化剩余图,设R=G
5.查找R中的层次图L
6.whilet为L中的顶点
7.u←s
8.p←u
9.whileoutdegree(s)>
0{开始阶段}
10.whileu≠tandoutdegree(s)>
11.ifoutdegree(u)>
0then{前进}
12.设(u,v)为L中的一条边
13.p←p,v
14.u←v
15.else{exit}
16.删除u和L中所有的邻接边
17.从p的末尾删除u
18.将u设置为p中最后一个顶点
19.endif
20.endwhile
21.ifu=tthen
22.设△为p中的瓶颈容量,用△增值p中的当前流。
在剩余图中和层次图中调整p的容量,删除饱和边。
设u是p中从s可到达的最后顶点,注意u可能是s。
23.endif
24.endwhile
25.从当前剩余图R中重新计算层次图L
26.endwhile
5、算法核心代码
(1)深度优先遍历算法
privatestaticintmyDFS(inttempV,intmyFlow){
intmyD=myFlow;
if(tempV==nodeNum)
returnmyFlow;
for(inti=1;
i<
=nodeNum;
i++){
if(temp[tempV][i]>
0&
&
data[tempV]+1==data[i]){
intflow=myDFS(i,myMIN(myD,temp[tempV][i]));
temp[tempV][i]-=flow;
temp[i][tempV]+=flow;
myD-=flow;
}
}
returnmyFlow-myD;
(2)广度优先遍历算法
privatestaticbooleanmyBFS(){
for(inti=0;
NUM;
i++)
data[i]=-1;
data[1]=0;
Queue<
Integer>
queue=newLinkedList<
();
queue.add
(1);
while(!
queue.isEmpty()){
inttempV=queue.poll();
for(intj=1;
j<
j++){
if(data[j]==-1&
temp[tempV][j]!
=0){
data[j]=data[tempV]+1;
queue.add(j);
}
}
returndata[nodeNum]!
=-1;
6、实验结果
(1)在文本框中输入图中节点的个数,如图所示:
(2)在文本框中输入图中边的个数,如图所示:
(3)在文本域中输入边的信息,包括起点、终点和边上的权值。
每一组数据之间以空格分隔,组与组之间请回车,如下图所示:
(4)点击“执行算法”按钮,如果输入信息合法,则在结果文本框中将会显示出最大网络流的值,如图所示:
(5)再次进行实验时可以点击“清除数据”按钮,这样已经输入的信息将会自动清空。
三、ESTPAPPROX近似算法
利用JAVA语言实现欧几里德TSP问题的ESTPAPPROX近似算法
有很多困难的组合最优化问题不能用回溯法和随机化算法有效地解决,在这种情况下,对于其中的一些问题代之以设计近似算法,我们要保证它是近似于最优解的一个“合理”的解。
欧几里德旅行商问题的一个特殊情况是,给出一个平面上n点的集合S,找出一个在这些点上的最短长度的游程t,这里,一个游程是恰好访问每点一次的一条回路。
这个问题通常被称为EUCLIDEANMINIMUMSPANNINGTREE(EMST)。
ESTPAPPROX近似算法可以找出一个最小权重匹配。
组合最优化问题不是最小化问题,就是最大化问题。
它由三部分组成:
(1)一个实例集合D;
(2)对于每个实例I
D,存在I的一个候选解的有限集S(I);
(3)D中的一个实例I的每个解б
S(I),存在一个值f(б),称为б的解值。
旅行商问题是著名的组合优化问题,该问题的具体描述是:
某售货员要到若干城市去推销商品,已知各城市间的路程(或旅费),要求选定一条从驻地出发,经过每个城市恰好一次,最后回到驻地的路线,使总的路程(或旅费)最小。
MST(最小生成树)启发式法:
首先,构造一个最小耗费生成树T,接着通过将T的每边复制成两份从T构造出多重图T’,接下来,找出一个欧拉游程t(欧拉游程是一条回路,它恰好访问每条边一次)。
一旦找到了t,就可以通过跟踪欧拉游程t和删除那些已经访问过的顶点很容易地把它转换成要求的哈密顿游程t。
ESTPAPPROX近似算法对MST近似算法背后的思想进行了改进,以得到这个问题的更好的近似度。
为了把T变成欧拉图,不把它的边加倍,而是首先识别出那些度数为奇数的顶点集合X,X的奇数总是偶数。
接着在X的成员上找出权重最小的匹配M,最后,令T’=T
M。
显然,T’中的每个顶点度数为偶数,于是T’是欧拉图。
这种方法就称为最小匹配(MM)启发式法。
算法2欧几里德TSP问题的ESTPAPPROX近似算法
欧几里得TSP问题的一个实例I
实例I的一个游程t
1.找出S的一个最小生成树
2.识别T中度数为奇数的集合X
3.在X中查找最小权重匹配M
4.在T∪M中查找欧拉游程t
5.按边跟踪t,删除那些已访问过的顶点,设t为结果游程
(1)递归实现深度优先遍历
privatestaticvoidmyDFS(intnodeid)
{
if(flag[nodeid]==true)
return;
result+=String.valueOf(nodeid)+"
"
;
flag[nodeid]=true;
for(inti=0;
i<
nodeNum;
i++)
{
if(graphMatrix[nodeid][i]==-1)
myDFS(i);
}
(2)主程序
boolean[]flag=newboolean[nodeNum];
intnumOfU=0;
for(inti=0;
flag[i]=false;
flag[0]=true;
numOfU=1;
while(true){
if(numOfU==nodeNum)break;
intnode1=-100;
intnode2=-100;
intnowMinWeight=MaxNum+1;
i++){
if(flag[i]==true){
for(intj=0;
j<
j++)
{
if(graphMatrix[i][j]!
=-1&
graphMatrix[i][j]<
nowMinWeight){
node1=i;
node2=j;
nowMinWeight=graphMatrix[i][j];
}
}
flag[node2]=true;
numOfU++;
graphMatrix[node1][node2]=-1;
graphMatrix[node2][node1]=-1;
myDFS(0);
(4)点击“执行算法”按钮,如果输入信息合法,则在结果文本框中将会显示出最终的结果,如图所示:
(5)再次进行实验时可以点击“清除数据”按钮,这样已经输入的信息将会自动清空。
四、二分图的最大匹配算法
利用JAVA语言实现二分图的最大匹配算法
给定一个无向图G=(V,E),最大匹配问题是要找出一个E的子集M属于E,它具有最大数量的不变迭边,即在M中任何两条边没有一个共同顶点。
寻找一个最大匹配的问题,往往在许多实用算法的实现中作为一个子例程。
二分图的匈牙利树方法就是一个寻找二分图的最大匹配算法。
定理1:
设M是一个匹配,p是关于M的一条增广路径,则M⊕p是一个规模为|M⊕p|=|M|+1的匹配。
定理2:
无向图G中一个匹配M是最大的当且仅当G不包含关于M的一个增广路径。
定理3:
设M1和M2是无向图G中的两个匹配,是的使得|M1|=r,|M2|=s,s>
r,则M1⊕M2至少包含k=s-r条顶点不相交的关于M1的增广路径。
设G=(X
Y,E)是一个二分图,有|X|+|Y|=n和|E|=m。
设M是G中的匹配,我们把X中的顶点称为x顶点,同样把Y中顶点称为y顶点。
首先找一个自由的x顶点,比如说r,把它标记为外部的。
从r开始,我们逐步生成一棵交替路径树,即每一条从根节点r到叶子的路径均为交替路径。
这棵树称为T,其构造过程如下。
从r开始,加上每一条连接r和y顶点y的未匹配边(r,y),并标记为y为内部的。
对于和r邻接的y顶点y,如果有匹配边(y,z)存在,就把它加入T,并标记z为外部的。
重复上述过程扩大这棵树直到遇到一个自由的y顶点,比如说v,那么从根r到v的交替路径即为一条增广路径。
另一方面,若树被阻塞,则这棵树称为匈牙利树。
接下来,我们从另一个自由x顶点开始,重复上述步骤。
如果T是匈牙利树,那么它就不能再扩大了,每一条从根出发的交替路径在某个外部顶点停止。
T中惟一的自由顶点为它的根。
注意到如果(x,y)是一条边,使得x在T中而y不在T中,那么x肯定是标记为内部的,否则x一定连接到一个自由顶点或者T从x处可扩大。
这样在匈牙利树中没有顶点能在增广路径还只能出现。
假定p是一条交替路径,它至少有一个T中的顶点,如果p“进入”T,那么它必然穿过一个标记为内部的顶点;
如果p“离开”T,那么它也必然穿过一个标记为内部的顶点。
但是这是p不是交替路径了,这是一个矛盾。
这也蕴含着下面重要的观察结论。
观察结论:
在搜索增广路径的过程中,如果找到一棵匈牙利树,那么它可被永久地移去而不影响搜索过程。
算法3二分图的匈牙利树算法
二分图G=(X∪Y,E)
G中的最大匹配M
1.初始化M为任意匹配
2.while存在一个自由的x顶点和一个自由的y顶点
3.设r为一个自由的x顶点,采用广度优先搜索,生成一个以r为根的交替路径树T
4.if如果T为匈牙利树thenG←G-T{删除T}
5.else在T中找到一条增广路径p,并设M=M⊕p
6.elsewhile
privatestaticbooleanmyDFS(inttemp){
for(inti=1;
if(hashMap[temp][i]&
!
viNode[i]){
viNode[i]=true;
if(test[i]==0||myDFS(test[i])){
test[i]=temp;
returntrue;
returnfalse;
(3)在文本域中输入边的信息(即两个有边的端点编号)。
(4)点击“执行算法”按钮,如果输入信息合法,则在结果文本框中将会显示出计算出的匹配个数,如图所示:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高级 算法 课程 实验 报告