第12讲 旅行售货商问题和斯坦纳最小树问题

旅⾏售货员问题旅⾏售货员问题【题⽬】某售货员要到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!)。

旅行商问题本页仅作为文档页封面，使用时可以删除This document is for reference only-rar21year.March旅行商问题旅行商问题（Traveling Saleman Problem，TSP）又译为、，简称为，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。

最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。

目录1简介“旅行商问题”常被称为“”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。

规则虽然简单，但在地点数目增多后求解却极为复杂。

以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。

多年来全球数学家绞尽脑汁，试图找到一个高效的TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。

如何确定最短路线。

TSP问题最简单的求解方法是。

它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。

可以形象地把看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。

求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

2研究历史旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。

TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

TSP由RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。

3问题解法旅行推销员的问题，我们称之为巡行（Tour），此种问题属于的问题，1、途程建构法（Tour Construction Procedures）从中产生一个近似最佳解的途径，有以下几种解法：2、途程改善法（Tour Improvement Procedure）先给定一个可行途程，然后进行改善，一直到不能改善为止。

一问题的重述售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。

他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

路线是一个带权图。

图中各边的费用（权）为正数。

图的一条周游路线是包括V中的每个顶点在内的一条回路。

周游路线的费用是这条路线上所有边的费用之和。

旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。

旅行售货员问题要在图G中找出费用最小的周游路线。

设有p个城市，假设每两个城市之间都有直通通道，两个城市之间的路程已知，一个售货员要到每个城市推销产品，然后返回原出发地，问这个售货员应该如何选择路线，能使每个城市都经过一次且仅一次，并且行程最短，这就是著名的旅行售货员问题，也即货郎担问题。

用图论的术语来描述旅行售货员问题：即在一个正权完全图中寻找一个具有最小权的哈密顿回路，对于此问题，由于完全图中必然存在哈密顿回路，那么目前可以用于求解的方法有枚举法，分枝限界法，这两种算法可以求得此问题的精确解，但到目前为止，还没有求解这一问题的有效算法，我们可以利用分支限界法，回溯法求解此问题的近似解，以求得与最优解最为接近的解。

二问题的求解方法1枚举法枚举法就是一一列出问题的所有解，然后进行比较，取权值最小的解为最优解，这种方法虽然可以求取问题的最优解，但是我们知道旅行售货员问题是对完全图而言的，对有N个结点的完全图，存在2)!1(N个不同的哈密顿回路，如果采用枚举法求解，则要对上述数目的不同的哈密顿回路一一进行运算且需要相互之间比较，当N取值较小时，此种求解方法没有任何问题，但若N值较大时，计算量则以级数级别递增，况且没有有效的算法，所以在计算机中也较难实现，故枚举法在大多数的实际应用中是不可取的。

2回溯法旅行售货员问题的解空间是一棵排列树。

对于排列树的回溯搜索与生成1，2，…，n的所有排列的递归算法perm类似。

回溯法之旅⾏售货员问题问题描述:某售货员要到若⼲城市去推销商品，已知各城市之间的路程，他要选定⼀条从驻地出发，经过每个城市⼀遍，最后回到住地的路线，使总的路程最短。

算法描述：回溯法，序列树，假设起点为 1。

算法开始时 x = [1, 2, 3, ..., n]x[1 : n]有两重含义 x[1 : i]代表前 i 步按顺序⾛过的城市， x[i + 1 : n]代表还未经过的城市。

利⽤Swap函数进⾏交换位置。

若当前搜索的层次i = n 时，处在排列树的叶节点的⽗节点上，此时算法检查图G是否存在⼀条从顶点x[n-1] 到顶点x[n] 有⼀条边，和从顶点x[n] 到顶点x[1] 也有⼀条边。

若这两条边都存在，则发现了⼀个旅⾏售货员的回路即：新旅⾏路线），算法判断这条回路的费⽤是否优于已经找到的当前最优回路的费⽤bestcost，若是，则更新当前最优值bestcost和当前最优解bestx。

若i < n 时，检查x[i - 1]⾄x[i]之间是否存在⼀条边, 若存在，则x [1 : i ] 构成了图G的⼀条路径，若路径x[1: i] 的耗费⼩于当前最优解的耗费，则算法进⼊排列树下⼀层，否则剪掉相应的⼦树。

代码实现：#include <bits/stdc++.h>using namespace std;const int max_ = 0x3f3f3f;const int NoEdge = -1;int citynum;int edgenum;int currentcost;int bestcost;int Graph[100][100];int x[100];int bestx[100];void InPut(){int pos1, pos2, len;scanf("%d %d", &citynum, &edgenum);memset(Graph, NoEdge, sizeof(Graph));for(int i = 1; i <= edgenum; ++i){scanf("%d %d %d", &pos1, &pos2, &len);Graph[pos1][pos2] = Graph[pos2][pos1] = len;}}void Initilize(){currentcost = 0;bestcost = max_;for(int i = 1; i <= citynum; ++i){x[i] = i;}}void Swap(int &a, int &b){int temp;temp = a;a = b;b = temp;}void BackTrack(int i) //这⾥的i代表第i步去的城市⽽不是代号为i的城市{if(i == citynum){if(Graph[x[i - 1]][x[i]] != NoEdge && Graph[x[i]][x[1]] != NoEdge && (currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]] < bestcost || bestcost == max_)){bestcost = currentcost + Graph[x[i - 1]][x[i]] + Graph[x[i]][x[1]];for(int j = 1; j <= citynum; ++j)bestx[j] = x[j];}}else{for(int j = i; j <= citynum; ++j){if(Graph[x[i - 1]][x[j]] != NoEdge && (currentcost + Graph[x[i - 1]][x[j]] < bestcost || bestcost == max_)){Swap(x[i], x[j]); //这⾥i 和 j的位置交换了, 所以下⾯的是currentcost += Graph[x[i - 1]][x[i]]; currentcost += Graph[x[i - 1]][x[i]];BackTrack(i + 1);currentcost -= Graph[x[i - 1]][x[i]];Swap(x[i], x[j]);}}}}void OutPut(){cout << "路线为:" << endl;for(int i = 1; i <= citynum; ++i)cout << bestx[i] << "";cout << "1" << endl;}int main(){InPut();Initilize();BackTrack(2);OutPut();}View Code测试样例：实现结果：参考：王晓东《算法设计与分析》。

旅行商问题
TSP,Travelling salesman problem
问题描述：
给定一系列点，以及各点之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

问题实质：
哈密尔顿回路问题
NP完全问题
解决方法：
早期方法：分支定界法，线性规划法，动态规划法
近代方法：遗传算法，模拟退火法，蚁群算法，禁忌搜索算法，贪心算法，神经网络算法
空间数结构术语：
问题状态：在解空间树中的每一个结点确定所求问题的一个问题状态
状态空间：由根结点到其它结点的所有路径则确定了这个问题的状态空间解状态：表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组
答案状态：表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解
问题求解：
1.暴力求解：
运用枚举的思想，复杂度为O(n！)。

旅行售货员问题问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短该问题是一个NP完全问题，有(n-1)!条可选路线最优解(1,3,2,4,1)，最优值25问题具体描述：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。

他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。

路线是一个带权图。

图中各边的费用（权）为正数。

图的一条周游路线是包括V 中的每个顶点在内的一条回路。

周游路线的费用是这条路线上所有边的费用之和。

旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。

旅行售货员问题要在图G中找出费用最小的周游路线。

https:///retype/zoom/ae9a5b75f46527d3240ce072?pn=1&x=0&y= 0&raww=489&rawh=175&o=png_6_0_0_135_635_550_196_892.979_1262.879&type =pic&aimh=171.77914110429447&md5sum=4ced18926fc1df50fb21611e730b7292&s ign=9f67dccda7&zoom=&png=0-6122&jpg=0-0算法描述：旅行售货员问题的解空间是一棵排列树x=[1 2 3…..n]——>相应的排列树由x[1:n]的所有排列构成①在递归算法Backtrack中②当i=n时，当前扩展结点是排列树的叶节点的父结点③此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边………算法：template<class Type>void Traveling<Type>::Backtrack(int i){if (i == n) {if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {for (int j = 1; j <= n; j++) bestx[j] = x[j];bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}}else {for (int j = i; j <= n; j++)// 是否可进入x[j]子树?if (a[x[i-1]][x[j]] != NoEdge &&(cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) { // 搜索子树Swap(x[i], x[j]);cc += a[x[i-1]][x[i]];Backtrack(i+1);cc -= a[x[i-1]][x[i]];Swap(x[i], x[j]);}}}复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。

旅行售货员问题传统的旅行售货员问题可以概述如下：设有n个城市，以V1 ，V2 ，…V n表示之，用d ij表示城市V i到城市V j之间的距离，一个推销员从某城市(不妨假设从城市V1)出发到其他城市去一次而且仅一次，然后回到原来的城市(城市V1)，问其应该选择什么样的行走路线才能使得总的旅行路程最短。

把这个问题抽象成图论问题就是给定一个连通无向图G(V,E)，其中V＝{V1 ,V2,…V n}是顶点(城市)的集合，E是顶点间边的集合，表示相应城市间的旅行路线，即E={e=(V i,V j)；顶点V i与V j间有边e},每个边e∈E上有非负权重w(e)=w(V i,V j)=d ij，表示顶点V i即城市V i到顶点V i(即城市V j)的距离，问题就是要确定图G的一个圈，它过每个顶点一次且仅一次，而且使得该圈的总权(即圈上所有边的权之和)最小。

这个圈在图论里称为Hamilton圈，简称H圈。

由于G(V,E)的边是无向的，相邻的边和顶点可以通过边进入顶点，也可以通过顶点进入边。

这样，寻找售货员最优旅行路线的问题就可以归结为如下的图论问题：给定连通图G(V,E)，对每条边e= (V i,V j)∈E对应的顶点V i与V j间添加反向边e'=(V j,V i)，得到双倍于G的另外一个连通图G'=(V,E')，求E1⊆E'使得G1(V,E1)为H圈且总权为∑w(e)最∈E1e小。

为叙述方便，若e= (V i ,V j )，则记为e i ,j ∈E,而相应的添加边为e j ,i 。

与边e i ,j ∈E '相对应，设定一个0-1整数变量x i ,j 。

若e i ,j ∈E '，即称边是从V i 到V j 的，或称为弧。

这样，我们就可以把无向图理解为有向图D (V,E)。

每一个E 1⊆E '唯一对应一组x i ,j 的值，反之亦然。

我们称x i ,j 为E 1的值系。

摘要旅行售货员问题是一个古老而典型的NP组合优化问题。

对该问题合理而有效的解法不但有重要的理论和学术意义，同时对众多工程实际中的应用提供了重要的指导意义。

这篇论文首先对TSP问题进行了大体的陈述，对其进行了数学描述。

在此基础上,本文对TSP问题进行了进一步的定义。

论文介绍了五种算法的基本概念、原理、意义及发展现状。

这五种算法包括动态规划法、分支界限法、回溯法、遗传算法和微粒子算法。

并展示了部分算法的部分数学过程。

关键词：旅行售货员问题；遗传算法；微粒子算法；回溯法Several Solutions to Traveling Salesman ProblemAbstractTraveling salesman problem is an old and typicalNP hard combinatorial optimization problem, its valid and effective solutions not only has important theoretical and academic values, but also has important guiding significance for many practical engineering applications.The essay starts with the general account of TSP, explains the mathematical description of TSP. On the original basis, the essay made through classification of TSP; The essay introduced the basic concept, principle, procedure and significance of five types of algorithm, including dynamic programming, branch bounding method, backtracking method, Genetic algorithm, Particle Swarm Optimization. It also displayed some major process in mathematic ways..Key Words：Traveling Salesman Problem; Genetic Algorithm; Backtracking Algorithm目录摘要 (I)Abstract (II)引言 (1)1 旅行售货员问题的研究现状 (2)1.1旅行售货员问题概述 (2)1.2 旅行售货员问题的数学描述 (3)1.3 旅行售货员问题的分类 (4)1.4 前人的工作 (5)1.4.1 精确算法 (5)1.4.2 启发式算法 (5)1.5 本章小结 (5)2 精确算法求解策略及优化算法 (6)2.1动态规划法解旅行售货员问题 (6)2.1.1 动态规划思想简介 (6)2.1.2 动态规划求解旅行售货员问题 (6)2.2分支限界法解问题 (6)2.3回溯法解旅行售货员问题 (8)2.3.1 回溯法思想简介 (8)2.3.2 回溯法求解履行商问题 (8)2.3.3 回溯法的不足 (9)2.3.4 回溯算法的改进 (9)2.4 三种精确算法的比较 (10)2.4.1 动态规划法和回溯法的比较 (10)2.4.2分支限界法和回朔法的比较 (11)3 遗传算法解决旅行售货员问题 (12)3.1启发式算法简介 (12)3.2 遗传算法介绍 (12)3.2.1遗传算法发展 (12)3.2.2遗传算法自身特点 (13)3.2.3遗传算法总结 (13)3.3 基本遗传算法求解旅行售货员问题 (14)4 微粒子算法简介 (15)4.1 微粒子算法历史 (15)4.3 微粒子算法结合旅行售货员问题 (15)5 旅行售货员问题的应用 (16)结论 (17)参考文献 (18)附录Ａ旅行售货员问题的最小耗费分枝定界算法 (19)附录Ｂ旅行售货员问题的回溯法 (22)致谢................................................. 错误！未定义书签。