蛮力法求旅行商问题

#include
using namespace std;
const int MAX_FLOAT_NUM=65535;
static int count=0;
static int cost=0; //临时存放路径费用
static int min=MAX_FLOAT_NUM; //最下路径的初始值
//
//交换两个数
//
void swap(int &x, int &y)
{
int temp;
temp = x;
x = y;
y = temp;
}
//
//permutation
//求从n取m个数的排列
//a[]为等待求组合的数组，长度为n，同时用来保存结果
//start 每轮挑选的起点
//step 步数
void permutation(int a[],int start,int step,int n,int m,int Num,int *t,int **c)
{
if(n{
m=n;
}
//穷举求最小的路径
//路径存到数组中

if (step==m)
{
cost=0;
count++;
for (int i=0;i{
if(icost=cost+c[a[i]][a[i+1]];
else
cost=cost+c[a[i]][a[0]];
// cout<
}
//如果costif(cost{
min=cost;
for(i=0;i{
t[i]=a[i];
}
t[i]=a[0];
}
//cout<}
if(count==Num)
{
//输出最小的路径及费用
cout<<"最短路径为："<cout<<"旅行路线为：";
for(int i=0;i{

cout<}
cout<}
else
{
for (int j=start; j{
swap(a[step],a[j]);
permutation(a,start+1,step+1,n,m,Num,t,c);//注意实参start的值 start+1
swap(a[j],a[step]);
}
}
}
//实现n的阶乘
//输入n
//输出n的阶乘
int factorial(int n)
{
int temp=1;
for(int i=1;i{
temp=temp*i;
}
return temp;
}
//城市个数n,费用矩阵c[][]
//旅行路线t,最小费用min
void salesman_problem(int n,int **c,int *T)
{
int Max_count=factorial(n); //全排列的数目,算法的时间复杂度
int *Array=new int[n];
for(int i=0;i{
Array[i]=i;
}
permutation(Array,0,0,n,n,Max_count,T,c);
}
void main()
{
int N;
cout<<"输入城市个数:";
cin>>N;
//存贮最优路径
int *T=new int[N+1];
//建立动态的费用矩阵;
int **Graph=new int *[N];
for(int i=0;i{
Graph[i]=new int[N];
}
cout<<"输入费用矩阵"<for(i=0;ifor(int j=0;j{
cin>>Graph[i][j];
}
salesman_problem(N,Graph,T);
}