旅行售货员问题的C++实现

用枚举法实现的旅行售货员问题 NP问题 可以处理有向图的矩阵

#include 
#include 
#include 
#include 
#include 
#define n 12
using namespace std;
typedef vector VEC;
int array[n+1];
int remeber[n+1];
int c[n][n];
int minvalue（int a[]int ver）//将排列后的路线计算出相应的距离temp
{
	int temp=0;
	int x;
	int y;
	for（int i=0;i	{
		int j;
		j=i+1;
		x=a[i]-1;
		y=a[j]-1;
		temp+=c[x][y];
	}
	return temp;
}

int main（） 
{   
	clock_t startfinish;
	start=clock（）;//开始计算时间
	cout<<“开始计时“<
	int fvalue;
	ifstream   Fin;
	Fin.open（“tsp.txt“）;
	for （int i=0;i	{
		for（int j=0;j		{
			 Fin>>fvalue;
			 c[i][j]=fvalue;
		}
	}
	//输出图的矩阵
	cout<<“路线长度的矩阵表示如下0表示无限大“<       for（int m=0;m	cout<	for（int k=0;k		cout<<“ “<	}
}
cout<    int arr[n-1];
	for（int j=0;j	{
		arr[j]=j+2;
	}
    VEC ivec（arrarr+n-1）;
	VEC::iterator h;
    sort（ivec.begin（）ivec.end（））;
	int mvalue=1000;
	 do
    { 
		int i=1;
		array[0]=1;
		array[n]=1;
		
		for（h=ivec.begin（）;h!=ivec.end（）;h++i++）
		{  
			array[i]=*h;
		}
	    int r;
        r=minvalue（arrayn+1）;
		if（r		{
			mvalue=r;
			for（int k=0;k			{
				remeber[k]=array[k];
			}

		}

    }while（next_permutation（ivec.begin（）ivec.end（）））;//用next_permutation函数实现所有城市之间的全排列，列举出所有可能的路线
    cout<<“用穷举法计算旅行售货员的问题的最短路径是“<	for（int l=0;l	{
		cout<	}
	cout<	finish=clock（）;//结束计算时间
	cout< 
	return 0;
} 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     577591  2011-05-10 23:25  MYTSP\Debug\MYTSP.exe

     文件     827708  2011-05-10 23:25  MYTSP\Debug\MYtsp.ilk

     文件     372509  2011-05-10 23:25  MYTSP\Debug\MYtsp.obj

     文件    2909020  2011-05-10 21:11  MYTSP\Debug\MYtsp.pch

     文件    1156096  2011-05-10 23:25  MYTSP\Debug\MYTSP.pdb

     文件      91136  2011-05-10 23:25  MYTSP\Debug\vc60.idb

     文件     135168  2011-05-10 23:25  MYTSP\Debug\vc60.pdb

     文件       1753  2011-05-10 23:28  MYTSP\MYtsp.cpp

     文件       3389  2011-05-10 13:28  MYTSP\MYtsp.dsp

     文件        516  2011-05-10 13:59  MYTSP\MYtsp.dsw

     文件      41984  2011-05-10 23:28  MYTSP\MYtsp.ncb

     文件      53760  2011-05-10 23:28  MYTSP\MYtsp.opt

     文件        747  2011-05-10 23:25  MYTSP\MYtsp.plg

     文件        128  2011-05-10 21:11  MYTSP\mytsp.txt

     文件        392  2011-05-10 21:18  MYTSP\tsp.txt

     目录          0  2011-05-10 23:25  MYTSP\Debug

     目录          0  2011-05-10 23:28  MYTSP

----------- ---------  ---------- -----  ----

              6171897                    17