#include "stdio.h"
#define n 6
#include<iostream.h>
#define MAX 100000000
typedef int DataType;
DataType bestc;
DataType bestx[n+1];
//DataType a[n][n]={{0,30,6,4},{30,0,5,10},{6,5,0,20},{4,10,20,0}};
DataType a[n+1][n+1]={0, 0,0,0,0,0,0 ,
0,0 , 702 , 454 ,842 , 2396 , 1196,
0,702, 0 , 324 , 1093, 2136 , 764,
0,454 ,324 ,0 ,1137 ,2180 , 798,
0,842, 1093 , 1137 , 0 , 1616 , 1857,
0,2396 ,2136 , 2180 ,1616 ,0 ,2900,
0,1196 , 764 , 798 , 1857 , 2900 , 0 };
DataType x[n+1];
DataType cc;
void Swap(int x[],int i,int j)
{
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
void tSP(int i)
{// 旅行商问题的回溯算法
int j;
if (i == n)
{// 位于一个叶子的父节点
// 通过增加两条边来完成旅行
if (a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc ==0))
{// 找到更优的旅行路径
x[i+1];
for(j = 1; j <= n; j++)
bestx[j] = x[j];
bestc=cc+a[x[n-1]][x[n]] + a[x[n]][1];
}
}
else {// 尝试子树
for (j = i; j <= n; j++)
//能移动到子树x [ j ]吗?
if (a[x[i-1]][x[j]] !=0 &&
(cc+a[x[i-1]][x[i]]<bestc||bestc == 0))
{//能搜索该子树
Swap(x,i,j);
cc += a[x[i-1]][x[i]];
tSP(i+1);
cc -= a[x[i-1]][x[i]];
Swap(x,i,j);
}
}
}
DataType TSP()
{// 用回溯算法解决旅行商问题
int i;
// x 是排列
for (i = 0; i <= n; i++)
{
x[i]=i;
// bestc=0;
bestx[i]=x[i];
}
bestc=MAX;
cc = 0;
// 搜索x [ 2 : n ]的各种排列
tSP(2);
return bestc;
}
void main()
{
int i;
//a[4][4]={{0,30,6,4},{30,0,5,10},{6,5,0,20},{4,10,20,0}}；
TSP();
for(i=1;i<=n;i++)
printf("%d",bestx[i]);
printf("\n The lowest cost is %d\n",bestc);
}
[此贴子已经被作者于2007-8-7 20:15:00编辑过]
