变形的KRUSKAL法解决巡回售货员问题.doc

变形的KRUSKAL法解决巡回售货员问题软件工程二班莫承长23号一、。。,直至所有的结点都包含在部分解中。关于巡回售货员问题有如下算法。1)选择一条最短的边作为部分解。2)选择一条长度最短,且满足下述条件的边加入到部分解中:将之加入到部分解中去不会形成(i)叉路(如图中绿线),即一个结点最多允许有两个结点与之相连(ii)回路(如图中红线,最后一次则要求形成回路) 3)重复第2步n-1次因为c是稀疏矩阵。为节省空间可用其它形式来表示城市间的距离。例如用下述的二维数组:intARC[M][3];其中M是图所含有的边的数目的最大值,对于每一条边记录(起点城市,终点城市,距离),城市用整数表示。,每条路径只须记载其两个端点,即将一段路径的起点和终点作成一个记录,这些记录用一个链连接起来。当部分解由两段路径ABC,DE组成时,链如图所示。每次选择长度最短的边(X,Y),则须考虑三种可能的情况:(1)所选择的边不和部分解的任何路径段连接成更长的路径段,此时只要将(X,Y)作为一条路径段的记录加到链中去。(2)所选择的边(X,Y)可与部分解中的一条路径段连接得到更长的路径段(如图)。此时要做的事情有三件:BYXA图中带箭头的边为所选择,起点和终点的标记分别为X和Y。段的一端和X相重,另外一端为A。数组ARC中若有边(A,Y)则将之删除,这是为了避免形成回路。将所有与X相关的其它边从数组ARC中删除,这是为了避免形成叉路。链LIST中有一个关于路径段(A,X)的记录将之改为路径段(A,Y)的记录。BYXA^AXlist(3)所选择的边(X,Y)可与部分解中的两条路径段相连接。要做的事有四件。.(i)数组ARC中若有边(A,B),则将之删除,否则会出现回路。(ii)将所有与X相关的边、所有与Y相关的边从数组ARC中删除,否则会出现岔路。iii)链LIST中关于路径段(A,X)的记录,改为路径段(A,B)的记录。(iv)将关于路径段(B,Y)的记录从链LIST中删除。因此选择了一条边(X,Y)之后,要判断这条边属于这三种情况的哪一种。这三种情况,分别对应于1)结点X、Y都不出现在链的记录中2)结点X、Y只有一个出现在链的记录中3)结点X、Y两者都出现在链的记录中二、程序流程A、读入城市数目,存放在N中;读入关于边的信息,存放在数组ARC中。B、将ARC中的边按长度排序。C、初始化COST=0;LIST=NULL;//链头变量为LISTK=0;//数组ARC的下标D、依次选择N条边E、扫描ARC数组,其中长度不为MAXINT或没有被打标记的边有N条,,即为问题的解。#defineMAXINT2989#include""#include""#defineLENsizeof(structchain)structchain*P1,*P2;intstaticX,Y;intstaticARC[13][3],COST=0,r[5];structcha