• 大小: 7KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-06-19
  • 语言: C/C++
  • 标签:

资源简介

对基于动态规划的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)
{
 

评论

共有 条评论

相关资源