TSP回溯法实现从武汉出发，进行34个省会的遍历，最后回到武汉，要求输出遍历路径和最后总里程

（TSP中的回溯算法） 算法描述 旅行售货员问题的解空间是一棵排列树。在递归算法中，当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路，此时，算法还需判断这条回路的费用是否优于当前已找到的最优回路的距离V。如果是，则必须更新当前最优值bestV和当前最优解bestx。

#include “setting.h“

int x[34];
int v; 
int bestV; 
int bestX[34];
int n = 34;

int** dist;


void backtrack （int tint** dist） {
	void swap（int a[] int i int j）;
		if （t > n - 1） {
			v += dist[0][x[n - 1]];
			if （v < bestV） {
				bestV = v;
				for （int i = 0; i < n; i++）
					bestX[i] = x[i];
			}
			printf（“%d\n“v）;
			v -= dist[0][x[n - 1]];
			return;
		}
	
	for （int i = t; i < n; i++） {
		
		swap（x i t）;
		v += dist[x[t - 1]][x[t]];
		// 剪枝函数
		if （v < bestV）
			backtrack（t + 1dist）;
		v -= dist[x[t - 1]][x[t]];
		swap（x i t）;
	}
}

void swap（int a[] int i int j） {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}


void getdist（int** dist）{
	int i; 
	for （ i = 0;i		x[i] = i;
		bestX[i] = i;
	}
	v = 0;
	bestV = 99999;
		backtrack （1dist）;
	printf（“%d\n“bestV）;
	for （i = 0; i < n; i++）
		printf（“%d\n“bestX[i]）;

}

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

     文件       5022  2009-09-09 23:36  TSP回溯法\Debug\getdist.obj

     文件       1933  2009-09-09 23:37  TSP回溯法\Debug\main.obj

     文件       9162  2009-09-09 23:14  TSP回溯法\Debug\operation.cpp.obj

     文件       9154  2009-09-09 23:36  TSP回溯法\Debug\operation.obj

     文件     184381  2009-09-09 23:37  TSP回溯法\Debug\TSP回溯法.exe

     文件     190948  2009-09-09 23:37  TSP回溯法\Debug\TSP回溯法.ilk

     文件      43520  2009-09-09 23:34  TSP回溯法\Debug\TSP回溯法.opt

     文件     226128  2009-09-09 23:36  TSP回溯法\Debug\TSP回溯法.pch

     文件     467968  2009-09-09 23:37  TSP回溯法\Debug\TSP回溯法.pdb

     文件      41984  2002-05-22 08:25  TSP回溯法\Debug\vc60.idb

     文件      53248  2009-09-09 23:37  TSP回溯法\Debug\vc60.pdb

     文件       5844  2009-09-05 15:17  TSP回溯法\distance.txt

     文件        916  2009-09-09 23:36  TSP回溯法\getdist.cpp

     文件        116  2009-09-09 23:37  TSP回溯法\main.cpp

     文件       1933  2009-09-09 23:33  TSP回溯法\operation.cpp

     文件        106  2009-09-09 23:36  TSP回溯法\setting.h

     文件       4501  2009-09-09 23:24  TSP回溯法\TSP回溯法.dsp

     文件        526  2009-09-09 23:07  TSP回溯法\TSP回溯法.dsw

     文件      58368  2002-05-22 08:36  TSP回溯法\TSP回溯法.ncb

     文件      49664  2002-05-22 08:36  TSP回溯法\TSP回溯法.opt

     文件        252  2002-05-22 08:24  TSP回溯法\TSP回溯法.plg

     目录          0  2002-05-22 08:15  TSP回溯法\Debug

     目录          0  2002-05-22 08:36  TSP回溯法

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

              1355674                    23