TSP问题 用C语言解决

#include<stdio.h>乎禅

#define N 100

void show(int cur,int n)

int a[N]

int main()

{

int cs[N]

int n,i

while(scanf("%d",&n)!=EOF)

{

for(i=0i<ni++)

cs[i]=i+1

show(0,n)

}

return 0

}

void show(int cur,int n)

{

int i,j,ok

if(n==cur)

{

for(i=0i<ni++)

printf("%d",a[i])

printf("\n")

}

else

{

for(i=1i<=ni++)

{

for(j=0j<=curj++)

{

ok=1

if(a[j]==i)

{

ok=0

break

}

}

if(ok)

{

a[cur]=i

show(cur+1,n)

}

}

}

}

。。就是这么个岁链尘唤如全排列问题吗？

#include <bits/stdc++.h>

using namespace std

double graph[25][25]

int vis[25]

double a[25]

double ub

double ans

struct point {

int x

int y

}p[25]

double dis(point a, point b)

{

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))

}

void dfs(int n, int x, double temp, int cnt)

{

//printf("%.2lf\搜局脊n", temp)

if(cnt == n-2)

{

ub = min(ub, temp+graph[x][n-1])

return

}

vis[x]=1

for(int i=0i<n-1i++)

{

if(graph[x][i] &&!vis[i])

{

temp += graph[x][i]

if(temp <ub)

dfs(n, i, temp, cnt+1)

temp -= graph[x][i]

vis[i]=0

}

}

}

int main()

{

int t, n, x, y

scanf("%d", &t)

while(t--)

{

int cnt=0

ub=0x3f3f3f3f

double temp=0

memset(graph, 0, sizeof(graph))

memset(vis, 0, sizeof(vis))

scanf("%d", &n)

for(int i=0i<ni++)

scanf("%d%d", &p[i].x, &p[i].y)

for(int i=0i<ni++)

for(int j=0j<世渗nj++)

graph[i][j] = dis(p[i], p[j])

vis[0]=1

dfs(n,0,temp,0)

printf("腊行%.2lf\n", ub)

}

return 0

}

#include<stdlib.h>

#include<stdio.h>

#include<math.h>

#include<stdafx.h>

#include <time.h>

#define PopSize 50 /*种群类DNA个数 */

#define MaxGens 200/* 最大代数 */

#define N 10 /* 问题规模*/

#define PC 0.8 /* 交叉概率 */

#define PM 0.01 /* 突变概率 */

#define RAND_MAX 10

int city[N]

int begin_city=0 /*出发城市*/

double r[N][N]={

0, 1, 4, 6, 8, 1, 3, 7, 2, 9,

1, 0, 7, 5, 3, 8, 3, 4, 2, 4,

4, 7, 0, 3, 8, 3, 7, 9, 1, 2,

6, 5, 3, 0, 3, 1, 5, 2, 9, 1,

8, 3, 8, 3, 0, 2, 3, 1, 4, 6,

1, 8, 3, 1, 2, 0, 3, 3, 9, 5,

3, 3, 7, 5, 3, 3, 0, 7, 5, 9,

7, 4, 9, 2, 1, 3, 7, 0, 1, 3,

2, 2, 1, 9, 4, 9, 5, 1, 0, 1,

9, 4, 2, 1, 6, 5, 9, 3, 1, 0

}

int generation /*当前代数 */

int CurBest/*最优个体 */

struct GenoType

{

int gene[N]/* 城市序列 */

double fitness /* 当前城市晌没序列对应的适应值 */

double rfitness /* 适应率 */

double cfitness /* 轮盘对应的起始区间值*/

}

struct ResultType

{

double best_val /*最佳适应度前薯 */

double avg/*平均适应度 */

double stddev /*标准差 */

}

GenoType population[PopSize+1] /* 种群 */

GenoType newpopulation[PopSize+1] /*新种群 */

ResultType result[MaxGens]/*种群换代记录*/

/*函数声明 */

void initialize()/*初始化 */

void evaluate()/*评价函数 */

void Find_the_best()/*找出最优 */

void elitist()/*择优函数*/

void select()/*选择 */

void crossover()/*交叉 */

void mutate()/*变异 */

void report()/*报告输出 */

int IntGenerate()/*产生一个城市节点 */

void swap(int *,int *)/*交换两值 */

void swap(int *a,int *b)

{

int temp

temp=*a

*a=*b

*b=temp

}

/* 产生一个0到10的数，作为城市编号*/

int IntGenerate()

{

int RANGE_MIN = 0

int RANGE_MAX = N

int rand_10

rand_10=(((double)rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN)

return rand_10

}

/*初始化种群*/

void initialize()

{

int matrix[N]

int x1,x2

int i,j

/*生成一个定值序列 ，宴悔纳0点为开始点 */

for(i=1i<Ni++)

matrix[i]=i

for(j=0j<PopSizej++)

{

population[i].gene[0]=begin_city /*gene[0]表示出发城市，i表示城市次序 */

for( i=0i<Ni++) /*N次交换足以产生各种结果了*/

{

x1=0x2=0

while(x1==0)

x1=IntGenerate()

while(x2==0)

x2=IntGenerate()

swap(&matrix[x1],&matrix[x2])

}

for(int i=1i<Ni++)

population[j].gene[i]=matrix[i]

}

---