[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;
}
```
