[TOC]
# 问题描述
> 已给一个n个点的完全图，每条边都有一个权值。求总权值最小的经过每个顶点正好一次的封闭回路。
假设有如下TSP问题：
计算从顶点1出发，依次经过剩下所有的顶点，最后回到顶点1的最小权值。
* 穷举法：
所有构成环路的情况如下：
1-2-3-4
1-2-4-3
1-3-2-4
1-3-4-2
1-4-2-3
1-4-3-2
我们可以将这个解空间组织成一棵树，从树的根节点到任一结点的路径定义了图的一条回路。如图，从A到L的路径上边的标号组成了一条路线，即1,2,3,4。图中的每一条路线对应这个解空间中的一个解，所以解空间树的结点个数为**(n-1)!**
注意：
1. 该树是一棵排列树。
2. 最后到达叶子结点时，需要加上由叶子结点回到根节点的权值。
遍历：
使用回溯法时，从解空间树的根节点A出发，搜索至B,C,F,L。在叶子结点L处记录找到的路线1,2,3，4,1.该路线的花费为59。从叶子结点返回到F处。由于F处没有可扩展的结点，算法又返回到结点C处。结点C称为新扩展结点，由新扩展结点，算法再移至结点G后又移至结点M,得到路线1,2,4,3,1。得到的费用为66，比之前费用大，故删除该结点。
依次方法算法继续搜索遍整个解空间，最终得到最小权值路线。
# 算法设计
#代码实现-1
```
#include <stdio.h>
int a[4][4] = {
{0,30,6,4},
{30,0,5,10},
{6,5,0,20},
{4,10,20,0}
};
int x[3] = {1,2,3}; //顺序
int cc; //临时值
int n = 4;
void
swap(int *a,int *b) {
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
backtrack(int i) {
int j;
if(i == n) {
//printf("%d-",cc+a[x[n-1]][x[n]]+a[x[n]][1]);
}else
{
for(j=i;j<n;j++) {
swap(&x[i],&x[j]);
cc += a[x[i-1]][x[i]];
printf("%d--",cc);
backtrack(i+1);
cc -= a[x[i-1]][x[i]];
swap(&x[i],&x[j]);
}
}
}
int
main(void) {
backtrack(1);
return 0;
}
```
