C++算法源码 旅行者问题浅析
时间：2010-06-23 来源：jeanlove
旅行者问题(汉密尔顿回路问题) [Jean.Love]
Travelling Salesman Problem，以下简称TSP。某售货员要到若干个城市推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线(或总的旅费最小)。 由于售货员的每条路线可以用一个以1开始的排列来表示，因此所有可能的路线有(n-1)!/2条，穷举显然不现实。
这类问题就是哈密尔顿图中求最佳哈密尔顿圈的问题。这是个NP-hard问题，没有多项式时间算法。一个可行的办法是先找到一个有效解，再对这个有效解进行优化，对于"圈"不断的做改进，也就是利用2-相邻的关系，求2-最优解---不断的替换两条边，直到不能改进为止。需要的计算量是n*n*(n-1)/2。但是这种穷举"修改"的办法仍然太复杂了。TSP问题简化成数学模型的话仍然是矩阵表示，不同的是问题变成了：
由矩阵中每列取一个元素所组成的集合为TSP的一个方案。如果所取元素都是各列的最小值，则称之为最小方案。显然，任一方案所含n个元素的列指标均不相同。一个方案若满足以下两个条件，则称之为可行方案。很多教程都给出了这样的解释：
1)n个元素的行指标均不相同。
2)从任一元素的行指标i1出发，先到其列指标j1，接着从以j1为行指标的元素出发，再到其列指标，如此进行下去，最后到以i1为列指标的元素为止。其间所经历的元素恰为n个(若所经历的元素为k(k<n)个，则称之为该方案的正阶子循环)。
该算法实现参考了循环子阶相关的论文，描述如下:
(l)从对称矩阵的下三角中(或上三角中)依次取最小值，选出n个元素为止。
(2)检验其中是否含有i行，i列中的元素总共恰有两个。若满足，它便是一个不含二阶子循环的方案；若不满足，仍以增值最小为原则实行替换。设i行i列选出元素之和多于2，j行j列选出元素之和小于2，那么就把i行i列保留两个元素，其余的调出，逐步调到i行j列，最后得出含有i行，i列中的元素总共恰有两个的方案。
(3)检验由(2)得到的方案是否含有三阶子循环。若没有转到(4)；若有以增值最小的原则，把三阶子循环破坏掉，转到(2)。
(4)检验由(3)得到的方案是否含有四阶子循环。若没有转下步；若有以增值最小为原则，把四阶子循环破坏掉，转到(2)。
直到得出可行方案为止。当然，最近邻法和便宜算法也可以求近似解，便宜算法的过程就是从小圈逐渐构造到大圈的办法，不考虑全局最优，起始点随意。
但是，上面的解释都太复杂了。直接用分支定界法DFS就可以求最优解----去掉了全部回路当中那些不构成解的组合。首先排序，然后选取n条边，看是否构成回路：(如果有顶点出现3次则显然不是回路)。如果不是，依次删除最长边，代之以剩余集合中的最短边，再次深探。如果第n条边深探完毕，没有解，继续深探第n-1条边，如此循环。因为深探的过程是非简的，所以得到的解必然是最优解。注意尾端的替换方法需要递归，不能用顺序循环的办法得到。用一个堆栈来模拟递归的过程，穷举该情况下的路径组合。
|0,6,4,5,8|
|6,0,3,2,7|
|4,3,0,3,1|
|5,2,3,0,2|
|8,7,1,2,0|
例程: 如上矩阵所示的5个顶点的图，代码如下，replace函数是整个算法的核心部分。由于算法的期望复杂度不是O(n^2)而是O(n!)，所以不能直接用简单的多重循环，而是必须在排序后路径集合的尾部不断递归。在GCC上运行通过。
>cat tsp.cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define min(a,b) (a)<(b)?(a):(b)
#define V 5
int Length[V]={0};
int D[V][V]={
{0,6,4,5,8},
{6,0,3,2,7},
{4,3,0,3,1},
{5,2,3,0,2},
{8,7,1,2,0}
};
struct edge{
int fromV;
int toV;
int dist;
void set(int f,int t,int d){
fromV=f; toV=t; dist=d;
}
void operator=(const edge& e){
set(e.fromV,e.toV,e.dist);
}
};
static int comp(const void*e1,const void*e2){
if (((edge*)e1)->dist< ((edge*)e2)->dist)return -1;
else if(((edge*)e1)->dist==((edge*)e2)->dist)return 0;
else return 1;
}
const int len=16;
int Asum=0;
edge Path[V];
edge ArrE[len];
void printArrE(){
for(int p=0;p<len;++p){
printf("[%d,%d]=%d,",ArrE[p].fromV,ArrE[p].toV,ArrE[p].dist);
}
printf("\n");
}
void printPath(){
for(int p=0;p<V;++p){//printPath();
printf("[%d,%d]=%d,",Path[p].fromV,Path[p].toV,Path[p].dist);
}
printf("\n");
}
void checkResult(){
printPath();
for(int i=0;i<V;++i){
for(int j=i+1;j<V;++j){
if(Path[i].fromV==Path[j].toV && Path[i].toV==Path[j].fromV)return;
}
}
int sum[V]={0};
for(int s=0;s<V;++s){
sum[ Path[s].fromV ]++;
sum[ Path[s].toV ]++;
}
if(sum[0]==2 && sum[1]==2 && sum[2]==2 && sum[3]==2 && sum[4]==2){
printf("The best path is: ");
printPath();
exit(0);
}
}
#define x 1000
bool checkDuplicate(int c){
int F[V]={x,x,x,x,x};
int T[V]={x,x,x,x,x};
for(int i=0;i<V-c;++i){
int j=0;
do{
if(Path[i].fromV==F[j] || Path[i].toV==T[j]){
return true;
}
else{
F[j]=Path[i].fromV;
T[j]=Path[i].toV;
break;
}
++j;
}while(j<=i);
}
return false;
}
void replace(int c){//replace "count" elements at Path's tail
printPath();
if(checkDuplicate(c))return;
for(int k=V-c;k<V;++k)Path[k]=ArrE[k];//restore tail information
if(c==0){
checkResult();
return;
}
int start=V-c;
for(int i=start+1;i<len;++i){//i is the position in ArrE
Path[start]=ArrE[i];
replace(c-1);
}
}
int main(){
int tmp=V-1;
while(tmp){
Asum+=tmp;
--tmp;
}//For a solution, from/to vertex summary should be Asum
printf("Asum=%d\n",Asum);
int idx=0;
for(int r=0;r<V;++r){
for(int c=0;c<V;++c){
if(r==c)continue;
ArrE[idx++].set(r,c,D[r][c]);
}
}
qsort(ArrE,len,sizeof(edge),comp);
printArrE();
for(int i=0;i<V;++i){
memcpy(Path,ArrE,sizeof(edge)*V);
replace(i);
}
printf("No circle found\n");
return 0;
}
算法的输出是:
Asum=10
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,[2,3]=3,[1,2]=3,[2,1]=3,[2,0]=4,[0,2]=4,[3,0]=5,[0,3]=5,[1,0]=6,[0,1]=6,[1,4]=7,[0,4]=8,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,3]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,3]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,4]=7,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[3,2]=3,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[3,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,3]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,3]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
The best path is: [2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
Travelling Salesman Problem，以下简称TSP。某售货员要到若干个城市推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线(或总的旅费最小)。 由于售货员的每条路线可以用一个以1开始的排列来表示，因此所有可能的路线有(n-1)!/2条，穷举显然不现实。
这类问题就是哈密尔顿图中求最佳哈密尔顿圈的问题。这是个NP-hard问题，没有多项式时间算法。一个可行的办法是先找到一个有效解，再对这个有效解进行优化，对于"圈"不断的做改进，也就是利用2-相邻的关系，求2-最优解---不断的替换两条边，直到不能改进为止。需要的计算量是n*n*(n-1)/2。但是这种穷举"修改"的办法仍然太复杂了。TSP问题简化成数学模型的话仍然是矩阵表示，不同的是问题变成了：
由矩阵中每列取一个元素所组成的集合为TSP的一个方案。如果所取元素都是各列的最小值，则称之为最小方案。显然，任一方案所含n个元素的列指标均不相同。一个方案若满足以下两个条件，则称之为可行方案。很多教程都给出了这样的解释：
1)n个元素的行指标均不相同。
2)从任一元素的行指标i1出发，先到其列指标j1，接着从以j1为行指标的元素出发，再到其列指标，如此进行下去，最后到以i1为列指标的元素为止。其间所经历的元素恰为n个(若所经历的元素为k(k<n)个，则称之为该方案的正阶子循环)。
该算法实现参考了循环子阶相关的论文，描述如下:
(l)从对称矩阵的下三角中(或上三角中)依次取最小值，选出n个元素为止。
(2)检验其中是否含有i行，i列中的元素总共恰有两个。若满足，它便是一个不含二阶子循环的方案；若不满足，仍以增值最小为原则实行替换。设i行i列选出元素之和多于2，j行j列选出元素之和小于2，那么就把i行i列保留两个元素，其余的调出，逐步调到i行j列，最后得出含有i行，i列中的元素总共恰有两个的方案。
(3)检验由(2)得到的方案是否含有三阶子循环。若没有转到(4)；若有以增值最小的原则，把三阶子循环破坏掉，转到(2)。
(4)检验由(3)得到的方案是否含有四阶子循环。若没有转下步；若有以增值最小为原则，把四阶子循环破坏掉，转到(2)。
直到得出可行方案为止。当然，最近邻法和便宜算法也可以求近似解，便宜算法的过程就是从小圈逐渐构造到大圈的办法，不考虑全局最优，起始点随意。
但是，上面的解释都太复杂了。直接用分支定界法DFS就可以求最优解----去掉了全部回路当中那些不构成解的组合。首先排序，然后选取n条边，看是否构成回路：(如果有顶点出现3次则显然不是回路)。如果不是，依次删除最长边，代之以剩余集合中的最短边，再次深探。如果第n条边深探完毕，没有解，继续深探第n-1条边，如此循环。因为深探的过程是非简的，所以得到的解必然是最优解。注意尾端的替换方法需要递归，不能用顺序循环的办法得到。用一个堆栈来模拟递归的过程，穷举该情况下的路径组合。
|0,6,4,5,8|
|6,0,3,2,7|
|4,3,0,3,1|
|5,2,3,0,2|
|8,7,1,2,0|
例程: 如上矩阵所示的5个顶点的图，代码如下，replace函数是整个算法的核心部分。由于算法的期望复杂度不是O(n^2)而是O(n!)，所以不能直接用简单的多重循环，而是必须在排序后路径集合的尾部不断递归。在GCC上运行通过。
>cat tsp.cpp
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define min(a,b) (a)<(b)?(a):(b)
#define V 5
int Length[V]={0};
int D[V][V]={
{0,6,4,5,8},
{6,0,3,2,7},
{4,3,0,3,1},
{5,2,3,0,2},
{8,7,1,2,0}
};
struct edge{
int fromV;
int toV;
int dist;
void set(int f,int t,int d){
fromV=f; toV=t; dist=d;
}
void operator=(const edge& e){
set(e.fromV,e.toV,e.dist);
}
};
static int comp(const void*e1,const void*e2){
if (((edge*)e1)->dist< ((edge*)e2)->dist)return -1;
else if(((edge*)e1)->dist==((edge*)e2)->dist)return 0;
else return 1;
}
const int len=16;
int Asum=0;
edge Path[V];
edge ArrE[len];
void printArrE(){
for(int p=0;p<len;++p){
printf("[%d,%d]=%d,",ArrE[p].fromV,ArrE[p].toV,ArrE[p].dist);
}
printf("\n");
}
void printPath(){
for(int p=0;p<V;++p){//printPath();
printf("[%d,%d]=%d,",Path[p].fromV,Path[p].toV,Path[p].dist);
}
printf("\n");
}
void checkResult(){
printPath();
for(int i=0;i<V;++i){
for(int j=i+1;j<V;++j){
if(Path[i].fromV==Path[j].toV && Path[i].toV==Path[j].fromV)return;
}
}
int sum[V]={0};
for(int s=0;s<V;++s){
sum[ Path[s].fromV ]++;
sum[ Path[s].toV ]++;
}
if(sum[0]==2 && sum[1]==2 && sum[2]==2 && sum[3]==2 && sum[4]==2){
printf("The best path is: ");
printPath();
exit(0);
}
}
#define x 1000
bool checkDuplicate(int c){
int F[V]={x,x,x,x,x};
int T[V]={x,x,x,x,x};
for(int i=0;i<V-c;++i){
int j=0;
do{
if(Path[i].fromV==F[j] || Path[i].toV==T[j]){
return true;
}
else{
F[j]=Path[i].fromV;
T[j]=Path[i].toV;
break;
}
++j;
}while(j<=i);
}
return false;
}
void replace(int c){//replace "count" elements at Path's tail
printPath();
if(checkDuplicate(c))return;
for(int k=V-c;k<V;++k)Path[k]=ArrE[k];//restore tail information
if(c==0){
checkResult();
return;
}
int start=V-c;
for(int i=start+1;i<len;++i){//i is the position in ArrE
Path[start]=ArrE[i];
replace(c-1);
}
}
int main(){
int tmp=V-1;
while(tmp){
Asum+=tmp;
--tmp;
}//For a solution, from/to vertex summary should be Asum
printf("Asum=%d\n",Asum);
int idx=0;
for(int r=0;r<V;++r){
for(int c=0;c<V;++c){
if(r==c)continue;
ArrE[idx++].set(r,c,D[r][c]);
}
}
qsort(ArrE,len,sizeof(edge),comp);
printArrE();
for(int i=0;i<V;++i){
memcpy(Path,ArrE,sizeof(edge)*V);
replace(i);
}
printf("No circle found\n");
return 0;
}
算法的输出是:
Asum=10
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,[2,3]=3,[1,2]=3,[2,1]=3,[2,0]=4,[0,2]=4,[3,0]=5,[0,3]=5,[1,0]=6,[0,1]=6,[1,4]=7,[0,4]=8,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[3,4]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[1,3]=2,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[3,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,3]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,3]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,1]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[1,4]=7,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,3]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,2]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,1]=3,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[2,0]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,2]=4,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[3,0]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,3]=5,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,0]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,1]=6,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[1,4]=7,
[2,4]=1,[3,1]=2,[1,3]=2,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[3,2]=3,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,4]=8,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[3,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,3]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,2]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,1]=3,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[2,0]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[0,2]=4,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[3,0]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[0,3]=5,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,3]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,2]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,1]=3,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[2,0]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,2]=4,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[3,0]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,3]=5,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,0]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,1]=6,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[1,4]=7,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
[2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
The best path is: [2,4]=1,[3,1]=2,[2,3]=3,[1,0]=6,[0,4]=8,
相关阅读 更多 +
