trave.c

关于旅行商问题的动态规划算法 在vc环境下编译通过

//---------------第j个顶点对应数值为j，。
// 集合采用2进制形式来进行一一映射,共有2^(n-1)个映射关系
// TSP函数：int TSP(int i,int Bit_Num_Value) 
// 从第i个顶点出发，经过Bit_Num_Value值对应的集合中的顶点一次且仅一次的最短路径

#include<stdio.h>
#include<stdlib.h>
#include <math.h>
#define MAXSIZE 30
#define MAXLENG 999999
#include "draw.h"

typedef struct graph
{
    int node[MAXSIZE];//顶点  
    int vertex[MAXSIZE][MAXSIZE];//存放权值
    int num;//个数
}graph;

graph G;
int TSP_Value[MAXSIZE][MAXLENG];
int New_Bit_Value;//新的集合值
int path[MAXSIZE][MAXLENG];
/*-----------------------------------子函数---------------------------------*/
int TSP(int i,int Bit_Num_Value)
{
   int Min_charge =1000;
   int Value;
   int j,bit_selected = 0;
   if (Bit_Num_Value == 0)//集合为空
   {  
	   return G.vertex[i][1];
   }//if
   else if(TSP_Value[i][Bit_Num_Value] != 0)
	   return TSP_Value[i][Bit_Num_Value]; //已经求过，则直接返回
   else
   {
	   for (j = 1;j <= G.num ; j++)
	   {
          bit_selected =(int)pow(2,j-1);//标记第j个顶点是否有在集合中
	      if(( bit_selected & Bit_Num_Value) == bit_selected && j!=i)
			  //如果在，且不为i值
		  {
             New_Bit_Value = Bit_Num_Value ^ bit_selected;
			 //屏蔽当前位为0，即去掉当前顶点成为新集合	 
		     Value = G.vertex[i][j] + TSP(j,New_Bit_Value);
			  {
		       if(Value < Min_charge) 
			   {
					Min_charge=Value;
				    path[i][Bit_Num_Value] = j;
			   }//if
			  } //if  
		  }//if 	  
	   }//for
		  TSP_Value[i][Bit_Num_Value] = Min_charge;//保存当前tsp值	  
   }//else
  return Min_charge;
}
/*----------------------------主函数----------------------------------*/
void main()
{ 
	FILE *fp;
	int i,j,result,bit_selected;
	int Bit_Num_Value = 0;
	char filename[80];
    printf("please input the name of the file to test:");
	scanf("%s",filename);
	if((fp=fopen(filename,"r"))==NULL)
	{
		printf("the file does not exist\n");
		return;
	}
	fscanf(fp,"%d\n",&G.num);
	for(i=1; i <= G.num; i++)
	{
	   G.node[i] = i;
	   for (j=1;j<= G.num ;j++ )
	    {
	    fscanf(fp,"%d ",&G.vertex[i][j]);
		}
	}/*读取文件数据*/

	fclose(fp);

	//第一次进入时的其余顶点集合值，去掉顶点1
	for(i=1;i<= G.num;i++)
		for(j=0;j<Bit_Num_Value; j++)
		{
		   path[i][j]=0;
           TSP_Value[i][j]=0;
		}
		//初始化存储数组
  	Bit_Num_Value = (int) pow(2,G.num) - 2; 
	result = TSP(G.node[1],Bit_Num_Value);
	printf("The minimum charge is %d\n",result);
	printf("The path of this directory is:\n");
	printf("1  ");
	j = path[1][Bit_Num_Value];
	for(i=1;i<=G.num - 1;i++)
	{
		printf("%d  ",j);
        bit_selected =(int)pow(2,j-1);
        Bit_Num_Value = Bit_Num_Value ^ bit_selected;//选取合适分支
		j = path[j][Bit_Num_Value];
	}//for
    printf("1  ");//打印路径

}