基于动态规划的TSP问题求解源码

#include
#include
#include

typedef struct tf* cnode;

struct tf{
 int currentNode;//当前的节点
 int set;   //当前的状态集合用二进制表示
 int pathLength;//当前的路径值
 cnode last;//记录上一个节点以保存上一个的信息
 cnode next;//记录下一个节点
};

struct tsp
{
	int count;//当前的城市的个数
	cnode* ltf;//记录struct tf数组
};


void output1（int *aint n）
{
  int i;
  for（i = 0;i < n;i++）
	  printf（“%d  “a[i]）;
  printf（“\n“）;
}

void output2（int **aint n）
{
	int ij;
	for（i = 0;i < n;i++）
	{
		for（j = 0;j < n;j++）
		{
		  printf（“%d “a[i][j]）;
		}
		printf（“\n“）;
	}
}


//自定义的幂函数<用于之后的集合的表示>
int mypow（int xint y）
{
	return （int）pow（（double）x（double）y）;
}

//判断元素i是否在set集合中
int inSet（int setint i）
{
	if（（set&mypow（2i-1）） > 0）
		return 1;
	else
		return 0;
}

//将元素i插入集合set中
void insertSet（int &setint i）
{
   int p = mypow（2i-1）;
   set = set|p;
}

//删除set中的i
void deleteSet（int &setint i）
{
	set = ~（mypow（2i-1））&set;
}

//读权矩阵
int** readWeight（int &nchar* filename）
{
 FILE *fp;
 fp = fopen（filename“r“）;
 if（fp == NULL）
 {
   printf（“文件%s打开时出错\n“filename）;
   exit（1）;
 }

  int ij**w;
  fscanf（fp“%d“&n）;
  w = （int**）calloc（nsizeof（int*））;
  for（i = 0;i < n;i++）
  {
    w[i] = （int*）calloc（nsizeof（int））;
  }

  for（i = 0;i < n;i++）
  {
	  for（j = 0;j < n;j++）
	  {
	    fscanf（fp“%d“&w[i][j]）;
	  }
  }
  fclose（fp）;
  return w;
}

//返回组合数C（nr）值
int ZuHeShu（int nint r）
{
	int ick*a;
	a = （int*）calloc（nsizeof（int））;
	for（i = 0;i < n;i++）
	{
		a[i] = i+1;
	}

	c = 0;
  do{
		i = -1;
		for（k = 0;k < r;k++）
		if（a[k] < n-r+k+1）
			i = k;
		if（i != -1）
		{
		  a[i]++;
		  for（k = i+1;k < r;k++）
	    	a[k] = a[k-1]+1;
		
	      c++;
		}
  }while（i != -1）;
  free（a）;
  return c+1;
}


//指定组合c（nr）中所有可能组合，返回其转化后的01格式的int数组
int* ZuHeArray（int *a0int nint rint sn）
{ 
	int ick*set*a;
	c = 0;
	set = （int*）calloc（snsizeof（int））;
	for（i = 0;i < sn;i++）
	{
	  set[i] = 0;
	}
    
	a = （int*）calloc（nsizeof（int））;
	for（i = 0;i < n;i++）
	{
		a[i] = i+1;
	}

	int t;
	
	for（i = 0;i < r;i++）
	{
	   t = a[i]-1;
	   insertSet（set[c]a0[t]）;
	}

  do{
	i = -1;
	for（k = 0;k < r;k++）
	if（a[k] < n-r+k+1）
		i = k;
    if（i != -1）
	{
     a[i]++;
	for（k = i+1;k < r;k++）
	a[k] = a[k-1]+1;
	
    c++;
	for（k = 0;k < r;k++）
	{
	   t = a[k]-1;
	   insertSet（set[c]a0[t]）;
	}
   }
	}while（i != -1）;

  free（a）;
  return set;

}

//设置最后一个集合
int setLastSet（int n）
{
  int iset;
  set = 0;
  for（i = 0;i < n;i++）
  {
    set = set|mypow（2i）;
  }
  return set;
}

//获得第row行的set中所有元素集合 ，总元素的个数为n<非set集合中的元素个数>
int* getSetNum（int setint rowint n）
{
  int ij*a;
  a = （int*）calloc（rowsizeof（int））;
  j = 0;

  for（i = 1;i < n;i++）
  {
    if（inSet（seti） == 1）
	{
		a[j] = i;
		j++;
	}
	if（j == row）
	{
		break;
	}
  }
  return a;
}

//将集合a转为二进制的数
int setNumSet（int *aint n）
{