专注人工智能在金融领域的应用

最短哈密顿回路Hamilton的分片算法——可以运行几千个顶点的完全图

       在之前的文章中介绍了最短哈密顿回路的分支限界算法:http://blog.xy2hand.com/post/e69c80e79fade59388e5af86e9a1bfe59b9ee8b7afHamiltone79a84e58886e694afe99990e7958ce7ae97e6b395e28094e28094C2b2be7a88be5ba8f.aspx
但是使用分支限界算法程序可以运行的节点数不超过30个,为了求大规模(例如:几千个顶点)完全图的最短哈密顿回路可以使用分片算法,即将顶点等分成N个区域,每个区域内的节点数最好不要超过20个,然后对每个区域使用分支限界算法求得最短哈密顿回路,然后将N个区域的最短哈密顿回路进行最优合并。
注意:此分片算法求的的并不是最短哈密顿回路,只是一个近似解。
C++程序源码如下:


//////////////////////////Hamilton.h文件//////////////////////////

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define MAXNODE 6000

 

#define MAX    999999999   /////定义最大值

 

int g_nodecount;/////总顶点数

 

const int g_piecescale=10;/////20个顶点为一片

 

int g_piececount;/////分片数量

 

int g_piecenow;////记录当前的分片标号

 

double g_weight=0;

 

double g_minweight=MAX;

 

int map[MAXNODE][MAXNODE];

 

int visited[MAXNODE];

 

int pathnow[g_piecescale+1];

 

int pathbest[MAXNODE+1];

 

int pathofpiece[MAXNODE/g_piecescale+1][g_piecescale+1];

 

int scaleofpiece[MAXNODE/g_piecescale+1];

 

int pathindex=0;

 

void ReadFromFile();

 

void WriteToFile();

 

void DFS(int start,int end,int nodej,int count);

 

void WritePieceToFile(int pieceindex,int piecescale);

 

void MergePiece();

 

///////////////////////////Hamilton.cpp///////////////////////////////////

#include"Hamilton.h"

 

void main()

{

         ReadFromFile();

 

         g_piececount=ceil((double)g_nodecount/g_piecescale);

 

         g_piecenow=1;

 

         while(g_piecenow<=g_piececount)

         {

                   //////分别对每片进行处理

                   int i,j;

                   int start=(g_piecenow-1)*g_piecescale;

                   int end=g_piecenow*g_piecescale;

                  

                   if(end>g_nodecount)

                            end=g_nodecount;

 

                   for(i=start;i<end;i++)

                   {

                            visited[i]=0;//////初始化

                   }

 

                   int count=0;////记录已经遍历的顶点个数  

 

                 pathnow[0]=start;

 

                   g_minweight=MAX;

 

                   DFS(start,end,start,count+1);

                  

                   for(i=0;i<end;i++)

                   {

                            pathofpiece[g_piecenow-1][i]=pathbest[i];

                   }

                   pathofpiece[g_piecenow-1][end-start]=start;

 

                   scaleofpiece[g_piecenow-1]=end-start;

 

         //      WritePieceToFile(g_piecenow-1,end-start);

 

                   g_piecenow++;

 

         }

 

         MergePiece();

 

         WriteToFile();

}

 

void MergePiece()

{

         int count=0;

         int besti,bestj;/////记录最优连通弧

         int i,j,index=1;

         for(i=0;i<scaleofpiece[0];i++)

         {

                    pathbest[i]=pathofpiece[0][i];

         }

         count=scaleofpiece[0];

 

         while(count<g_nodecount)

         {

                   int minweight=MAX;

                   int weight;

 

                   int nodei,nodej,nodem,noden;

 

                   for(i=0;i<count;i++)

                   {

                            //////找出已经合并的圈中任意一条弧

                            nodei=pathbest[i];

                            nodej=pathbest[i+1];

                   //      weight=map[nodei][nodej];

 

                            for(j=0;j<scaleofpiece[index];j++)

                            {

                                     nodem=pathofpiece[index][j];

                                     noden=pathofpiece[index][j+1];

 

                                     //////判断当前选出的两条弧是否是最优组合

                                     weight=map[nodei][nodem]+map[nodej][noden]-map[nodei][nodej]-map[nodem][noden];

                                     if(weight<minweight)

                                     {

                                               minweight=weight;

                                               besti=i;

                                               bestj=j;

                                     }

                                    

                                     weight=map[nodei][noden]+map[nodej][nodem]-map[nodei][nodej]-map[nodem][noden];

                                     if(weight<minweight)

                                     {

                                               minweight=weight;

                                               besti=i;

                                               bestj=j+1;

                                     }

                            }///end for

                   }////end for

                  

                   ///////根据besti,bestj合并两个圈

                   for(i=count;i>=besti+1;i–)

                   {

                            /////pathbest中的<besti,besti+1>弧断开

                            ///////后面的数据移动scaleofpiece[index],形成空白插入圈index

                            int temp=scaleofpiece[index];

                            pathbest[i+temp]=pathbest[i];

                   }

                  

                  

                  

                  

                   printf("besti:%d       bestj:%d  \n",besti,bestj);

                  

                   i=1;

                   for(j=bestj;j>=0;j–)

                   {

                            pathbest[besti+i]=pathofpiece[index][j];

                            i++;

                   }

 

                   for(j=scaleofpiece[index]-1;j>=bestj+1;j–)

                   {

                            pathbest[besti+i]=pathofpiece[index][j];

                            i++;

                   }

 

 

                   count+=scaleofpiece[index];

                  index++;

                  

         }///end while

 

}

 

void ReadFromFile()

{

         FILE *myfile;

         myfile=fopen("data.txt","r");

         fscanf(myfile,"%d",&g_nodecount);////////图的顶点数

        

         for(int i=0;i<g_nodecount;i++)

         {

                   for(int j=0;j<g_nodecount;j++)

                   {

                            fscanf(myfile,"%d",&map[i][j]);/////边权值

                   }

         }

 

         fclose(myfile);

}

 

void WritePieceToFile(int pieceindex,int piecescale)

{

         FILE *myfile;

         myfile=fopen("result.txt","w");

        

         fprintf(myfile,"%d片:\n",pieceindex+1);/////最优哈密顿回路

         for(int i=0;i<piecescale;i++)

         {

                   fprintf(myfile,"%d    ",pathofpiece[pieceindex][i]);/////最优哈密顿回路

         }

         fprintf(myfile,"\n");

         fprintf(myfile,"\n");

         fprintf(myfile,"最小值:%f",g_minweight);

         fprintf(myfile,"\n");

         fclose(myfile);

}

 

 

 

void WriteToFile()

{

         FILE *myfile;

         int i,j;

         myfile=fopen("result.txt","w");

        

         for(j=0;j<g_piececount;j++)

         {

                   fprintf(myfile,"%d片:\n",j+1);/////最优哈密顿回路

                   for( i=0;i<=scaleofpiece[j];i++)

                   {

                            fprintf(myfile,"%d    ",pathofpiece[j][i]);/////最优哈密顿回路

                   }

                   fprintf(myfile,"\n");

                   fprintf(myfile,"\n");

         }

 

         for( i=0;i<=g_nodecount;i++)

         {

                   fprintf(myfile,"%d    ",pathbest[i]);/////最优哈密顿回路

         }

         fprintf(myfile,"\n");

         fprintf(myfile,"最小值:%f",g_minweight);

         fprintf(myfile,"\n");

         fclose(myfile);

}

 

 

void DFS(int start,int end,int nodej,int count)

{

         int i;

         if(nodej>=end)

         {

                   return;

         }

        

         if(count==end-start)////找到哈密顿回路,更新最小权值和路径

         {

                   if(g_weight+map[start][nodej]<g_minweight)

                   {

                            for(i=0;i<end;i++)

                            {

                                     pathbest[i]=pathnow[i];

                            }

                           

                            g_minweight=g_weight+map[start][nodej];

                   }

 

                   return;

         }

 

         visited[nodej]=1;

 

         for(i=start;i<end;i++)

         {

                   if(visited[i]!=1&&i!=nodej)

                   {

                            if(g_weight+map[nodej][i]<g_minweight)

                            {

                                     visited[i]=1;

                                    

                                     g_weight+=map[nodej][i];

                                    

                                     pathnow[count]=i;

                                    

                                     DFS(start,end,i,count+1);

                                    

                                     visited[i]=0;

                                    

                                     g_weight-=map[nodej][i];

                            }

                   }

         }

}


点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>