TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，即假设有一个旅行商人要拜访n个城市，从某个城市出发，每个城市只能访问一次且最后回到出发城市，问该推销员应如何选择路线，才能使总的行程最短？

使用动态规划解决该问题的策略为：

易知从哪个城市出发其最短路径都是一样的，故假设从城市1出发。假设已经经过了几个城市，我们需要记录此时位于的城市，以及未访问的城市的集合。
以dp[{V}][init]表示从init点开始，要经过集合V中所有点的距离。dis[init][i]表示城市init到城市i的距离。
其状态转移方程为dp[{V}][init]=min(dp[{V}][init], dp[{V-i}][i]+dis[init][i])。即假设处于城市init，欲前往下一个城市i，如果在城市i的状态dp[{V-i}][i]加上城市init到城市i的距离小于当前最小值，则前往城市i。
我们怎么存储未访问的城市的集合？一个方法是以二进制01表示该城市是否被访问过，如s=111110，城市1对应的位为0，其他城市对应的位为1，则表示城市6到城市2都还未访问，城市1已访问过。例如在出发点1时，要判断城市2是否访问过，若s&(1<<1)为1则表示城市2未被访问过，若去城市2，则集合V变为s&(~(1<<1))。
以数组path[s][init]记录在城市init，未访问城市集合为s时，下一个城市的最优选择，以存储最优路径。

%遗传算法
%D是距离矩阵，n为种群个数
%参数city是中国31个城市的坐标
%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适配值淘汰加速指数,最好取为1,2,3,4,不宜太大
%交叉概率Pc，变异概率Pm 
%R为最短路径,Rlength为路径长度
function GA
clear
tic
%初始化
city=[1304 2312;   3639 1315;   4177 2244;   3712 1399;   3488 1535;   3326 1556;   3238 1229;
   4196 1044;   4312  790;   4386  570;   3007 970;    2562 1756;   2788 1491;   2381 1676;
   1332  695;   3715 1678;   3918 2179;   4061 2370;   3780 2212;   3676 2578;   4029 2838;   
   4263 2931;   3429 1908;   3507 2376;   3394 2643;   3439 3201;   2935 3240;   3140 3550;
   2545 2357;   2778 2826;   2370 2975];
n=100;
C=2000;
m=2;
Pc=0.9;
Pm=0.2;
D=juli(city);%生成距离矩阵
[R,Rlength]=geneticTSP(D,city,n,C,m,Pc,Pm);%运算返回最优路径R和其总距离Rlength
toc