先以小规模城市数量开始，假设为 4 个，如图：
从 0 出发，经过[1,2,3]这几个城市，然后回到 0，使得花费最少。要实现这个要求，需要从下面三个实现方案中选择花费最少的方案。
1、 从 0 出发，到 1，然后再从 1 出发，经过[2,3]这几个城市，然后回到 0，使得花费最少。
2、 从 0 出发，到 2，然后再从 2 出发，经过[1,3]这几个城市，然后回到 0，使得花费最少。
3、 从 0 出发，到 3，然后再从 3 出发，经过[1,2]这几个城市，然后回到 0，使得花费最少。
可以发现，三个小的解决方案的最优解，构成了大的解决方案，所以这个问题具有最优子结构，可以用动态规划来实现。
设置一个二维的动态规划表 dp,定义符号{1,2,3}表示经过[1,2,3]这几个城市，然后回到 0。
那么题目就是求 dp[0][{1,2,3}]。将{1,2,3}表示成二进制，就是 111，对应 10 进制的7，所以题目是在求 dp[0][7];
要求三个方案的最小值意味：
dp[0][{1,2,3}] = min{ C01+dp[1][{2,3}] ，C02+dp[2][{1,3}] ，C03+dp[3][{1,2}]}
其中 C01 表示从 0 出发到 1 的距离。
dp[1][{2,3}] = min{ C12+dp[2][{3}] ，C13+dp[3][{1}]}，dp[2][{3}] = C23+dp[3][{}]
dp[3][{}]就是从 3 出发，不经过任何城市，回到 0 的花费，所以 dp[3][{}] =C30。
==============================================================================================
根据此种思路写出城市稍多一点的TSP解法，代码如图：
#include <stdio.h>
#include<math.h>
const double INF=1000000000;
int T,n,cnt;
double a[25][25],dp[25][1100000];
struct city{ //定义结构体
int x,y;
}pt[25];
int i,j;
double d(struct city a,struct city b){ //结点间距离
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)*1.0);}
double min(double a,double b){
if(a<b)return a;
else return b;}
int main(){
cnt=1;
scanf("%d",&n);//数据有n行
for(int i=2;i<n;i++) cnt<<=1; //组合数（除起点终点外）
for(int i=0;i<n;i++) //输入
scanf("%d %d",&pt[i].x,&pt[i].y);
for(int i=0;i<n;i++) //建边
for(int j=0;j<n;j++)
a[i][j]=d(pt[i],pt[j]);
for(int i=0;i<n;i++) //初始化
for(int j=0;j<cnt;j++)
dp[i][j]=INF;
for(int i=0;i<n;i++) //起点确定，定下初始条件
dp[i][0]=a[i][0];
for(int i=1;i<cnt;i++) //从有元素考虑起
for(int j=1;j<n-1;j++){
for(int k=1;k<n-1;k++){
if((1<<k-1)&i)
dp[j][i]=min(dp[j][i],a[j][k]+dp[k][i-(1<<k-1)]);
}}//状态转移方程
double ans=INF;
for(int i=1;i<n;i++)
ans=min(ans,dp[i][cnt-1]+a[i][n-1]);
printf("%.2lf\n",ans);
return 0;
}旅行商问题是 np 问题，要保存的数都是不重复的比较小的整数，所以这里用二进制串表示集合。比如集合{1,3,5,6,7}表示成二进制串用 1110101，其中集合里面有的对应的位数写成 1，没有的写成 0。要判断第 3 位是不是 1，就把 1110101 右移(3-1)位，得到11101，然后结果和 00001 进行 & 运算，如果结果是 1 说明第 3 位是 1，否则说明第 3位是 0。推广一下，对于数字 x，要看它的第 i 位是不是 1，那么可以通过判断布尔表达式 ((x >> (i - 1)) & 1)== 1 的真值来实现，就是这个式子if((1<<k-1)&i)。
但这种算法也存在局限性，
for(int i=2;i<n;i++) cnt<<=1;
这句代码当n稍大的时候就会使得变量cnt越界。