旅⾏售货员问题旅⾏售货员问题【题⽬】某售货员要到4个城市去推销商品，已知各城市之间的路程，如右图所⽰。
请问他应该如何选定⼀条从城市1出发，经过每个城市⼀遍，最后回到城市1的路线，使得总的周游路程最⼩？并分析所设计算法的计算时间复杂度。
【分析】该题利⽤回溯法求解，此时需要确定解空间的类型：我们可以知道该解空间为⼀棵排列树。
我们假设初始的⼀条路线为x，x中的值为 1，2，3，……，n，表⽰该路线为由城市1依次经过城市2、3……到n后再回到城市1（当然是假设该路线存在）。
如果不存在的话，我们只需改变⼀下这个排列的排列⽅式，再进⾏判断，所以可想⽽知，我们可以知道该解空间是⼀棵排列树。
当然上述的说法，只是单纯的穷举，这并不是我们想要的回溯法，我们通过递归实现，在递归的过程中适当地“剪枝”即除去那些不可能形成最优解的解。
现在我们来确定⼀下可⾏的约束条件，当我们进⾏递归搜索，搜索到第t层时，我们需要判断⼀下x[t]所代表的城市是否与上⼀层x[t-1]所代表的城市有“路”，如果没有的话，需要改变x[t]的值，然后继续上述判断，当出现⼀个满⾜条件的x[t]后还要判断当前从1到t-1所⾛的路程cc加上x[t]与x[t-1]的距离是否⼩于当前已经记录的最优解（最优解的初始值是⼀个⾜够⼤的数），如果到t的距离⽐当前最优解还要⼤的话，那么再以这条路线搜索下去的话回到城市1的路程⼀定⽐当前最优解还⼤，所以我们没有必要对这条路线进⾏下⼀步的搜索。
最后我们来确定当搜索到叶⼦结点的时候我们该如何处理？已知搜索到t层时，若t = n，说明已经搜索到了叶⼦结点，这个时候我们还需做上述所说的两个判断，如果两个判断都通过的话，说明该解⽐当前最优解还优，那么我们需要将该解记录下来，并记录该解的最优值。
【伪代码】void travel(int t) {if(t到达第n层即搜索到叶⼦结点) {if(城市x[t-1]可以到达城市x[t]，并且城市x[t]可以回到城市1，且此时所⾛的路程cc加上x[t-1]与x[t]的距离和x[t]与1的距离⼩于当前最优值bestc) {将最优解记录下来;将最优值记录下来;}return;}for(int i = t; i < n; i++) {if(城市x[t-1]能达到城市x[i]即这两个城市间有边，并当前所⾛的路程cc加上这两个城市的距离没有⽐当前最优值bestc⼤) {swap(x[i], x[t]);修改此时所⾛的路程cc;进⼊下⼀层递归;恢复原来cc的值;swap(x[i], x[t]);}}}【程序】⽤C++语⾔编写程序，代码如下：#include<iostream>using namespace std;const int INF = 10000000;int n, cc = 0, bestc = INF;int **g;int *x, *bestx;void travel(int t) {if (t == n) {if (g[x[t - 1]][x[t]] != INF && g[x[t]][1] != INF &&(cc + g[x[t - 1]][x[t]] + g[x[t]][1] < bestc || bestc == INF)) { for (int i = 0; i < n + 1; i++)bestx[i] = x[i];bestc = cc + g[x[t - 1]][x[t]] + g[x[t]][1];}return;}for (int i = t; i < n; i++) {if (g[x[t - 1]][x[i]] != INF && (cc + g[x[t - 1]][x[i]] < bestc|| bestc == INF)) {swap(x[i], x[t]);cc += g[x[t - 1]][x[t]];travel(t + 1);cc -= g[x[t - 1]][x[t]];swap(x[i], x[t]);}}}void output() {cout << bestc << endl;cout << bestx[1];for (int i = 2; i < n + 1; i++)cout << " " << bestx[i];cout << " " << bestx[1] << endl;}int main() {n = 4;g = new int*[n + 1];x = new int[n + 1];bestx = new int[n + 1];for (int i = 0; i < n + 1; i++) {g[i] = new int[n + 1];x[i] = i;for (int j = 0; j < n + 1; j++)g[i][j] = INF;}}g[1][2] = g[2][1] = 30;g[1][3] = g[3][1] = 6;g[1][4] = g[4][1] = 4;g[2][3] = g[3][2] = 5;g[2][4] = g[4][2] = 10;g[3][4] = g[4][3] = 20;travel(2);output();return 0;}【结果】先设置好城市间的距离，调⽤回溯⽅法，输出最优值（最⼩路程）和最优解（路线）：该算法的时间复杂度为O(n!)。
TSP 问题及LINGO 求解技巧巡回旅行商问题(Traveling Salesman Problem ，TSP)，也称为货郎担问题。
最早可以追溯到1759年Euler 提出的骑士旅行问题。
1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。
它已经被证明属于NP 难题。
用图论描述TSP ，给出一个图(,)G V E =，每边e E ∈上有非负权值()w e ,寻找G 的Hamilton 圈C ，使得C 的总权()()()W C w e e E C =∑∈最小. 几十年来，出现了很多近似优化算法。
如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。
这里我们介绍利用LINGO 软件进行求解的方法。
问题1设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。
10个城市相互距离如下表。
要求每个城市到达一次仅一次后，回到原出发城市。
问他应如何选择旅行路线，使总路程最短。
我们采用线性规划的方法求解设城市之间距离用矩阵d 来表示，ij d 表示城市i 与城市j 之间的距离。
设0--1矩阵X 用来表示经过的各城市之间的路线。
设01,ij i j x i j i j ⎧=⎨⎩若城市不到城市若城市到城市且在前考虑每个城市后只有一个城市，则：11,nij j j ix =≠=∑1,,i n =… 考虑每个城市前只有一个城市，则：11,nij i i jx =≠=∑1,,j n =…； 但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。
为此我们引入额外变量i u (1,,i n =…），附加以下充分约束条件：1,i j ij u u nx n -+≤-1i j n <≠≤；该约束的解释：如i 与j 不会构成回路，若构成回路，有：1ij x =，1ji x =，则：1i j u u -≤-，1j i u u -≤-，从而有：02≤-，导致矛盾。
