trave.cpp

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

// 第j个顶点对应数值为j,集合采用2进制形式来进行一一映射,共有2^(n-1)个映射关系
//
// TSP函数：int TSP(int i,int Bit_Num_Value) 
// 从第i个顶点出发，经过Bit_Num_Value值对应的集合中的顶点一次且仅一次的最短路径
//
//*****************************绘图实现：vc环境下*****************************
#include<stdio.h>
#include<stdlib.h>
#include <math.h>
#include<conio.h>
#include "draw.h"

#define MAXSIZE 30
#define MAXLENG 999999
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);

	for(i=1;i<= G.num;i++)
		for(j=0;j<Bit_Num_Value; j++)
		{
		   path[i][j]=0;
           TSP_Value[i][j]=0;
		}
		//初始化存储数组
//--------------------- 用vc画图第一部分：初始图形--------------------	
int node_x[MAXSIZE];
int node_y[MAXSIZE];
//存储坐标
openWindow();
resizeWindow(0,0,450,450);
for(i=1;i<=G.num;i++)
	{
		node_x[i]=10+i*30;
		node_y[i]=10+rand()%250;
		ezdSetColor(ezdRed);
		ezdDrawCircle(node_x[i],node_y[i],7);
		char buf[100];
		sprintf(buf,"%d",i);
		ezdSetColor(ezdBlue);
		ezdDrawText(buf,node_x[i]-3,node_y[i]-3);
	}//画出全部点
for(i=1;i<=G.num;i++)
  for(j=1;j<=G.num;j++)
  {
	  if(G.vertex[i][j])
	  {
		ezdSetColor(ezdBlack);
     	ezdDrawLine(node_x[i],node_y[i],node_x[j],node_y[j]);
	  }
  }//for
  //画出所有的边
//------------------------行走路线的求解:调用子函数TSP------------------------
  	Bit_Num_Value = (int) pow(2,G.num) - 2; 
	//第一次进入时的其余顶点集合值，去掉顶点1
	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  ");//打印路径
	
//--------------------- 用vc画图第二部分：最终得到的行走路线-----------------
  	char buffer[50];//存储结点
	Bit_Num_Value = (int) pow(2,G.num) - 2; 
    j = path[1][Bit_Num_Value];
	int beg_node=1;
	ezdSetColor(ezdBlue);
	ezdDrawText("最终行走路线为：",0,300);
        sprintf(buffer,"%d",1);
		ezdSetColor(ezdBlue);
		ezdDrawText(buffer,0,350);
  for(i=1;i<=G.num - 1;i++)
	{
        ezdSetColor(ezdBlue);
     	ezdDrawLine(node_x[beg_node],node_y[beg_node],node_x[j],node_y[j]);//画当前找到2个顶点的最短路线
        bit_selected =(int)pow(2,j-1);
        Bit_Num_Value = Bit_Num_Value ^ bit_selected;
		sprintf(buffer,"%d",j);
		ezdSetColor(ezdBlue);
		ezdDrawText(buffer,i*20,350);//显示当前找到的下一个顶点
		beg_node = j;//保存结点
		j = path[j][Bit_Num_Value];
	}//for
	    sprintf(buffer,"%d",1);
		ezdSetColor(ezdBlue);
		ezdDrawText(buffer,G.num*20,350);	
		//显示最后一个顶点1
viewWindow();	//等待一个任意键被按下
getch();	
closeWindow();
}