【介绍】TSP旅行商-问题介绍

好了，我们开始学习智能优化算法，在学智能优化算法之前，先来说说TSP旅行商问题，因为它是智能优化算法用来解决的一个经典问题，我们先看看TSP问题是什么，之后再学智能优化算法，看看它们是如何解决TSP问题的。

一、TSP旅行商问题是什么

1.1. TSP问题-描述

TSP问题，全称为Traveling Salesman Problem，也就是旅行销售商问题。它是怎么回事呢，如下：

如图所示，有N个城市 ，旅行销售商要穿过所有城市去卖东西，最终回到自己的城市。那么，旅行商问题就是：如何寻找一条路径，使旅行总距离最小。

1.2. TSP问题-数学表述

好了，上面我们是文字语言来描述TSP旅行商问题，如果将TSP问题，抽象为数学语言，那要如何来描述呢？

设矩阵是城市之间的距离，其中，代表第i个城市到第j个城市的距离。而我们所要求的路径X，则可以用序列形式来表示，例如5个城市的时候， 就代表先到城市1，再到城市5，再到3.....最后由4回到1，而总距离就是按这顺序行走的总距离。

使用以上表示 ，则旅行商TSP问题可以理解为：求一 个包含1到N的序列X，使总距离F最小。

1.3. TSP问题的经典特点

TSP问题有两个特有的经典特点，如下：

1. 不能穷举

它的解空间是非常大的，这就不能用一般的穷举法来寻找最优解，如果有N个城市，那么就会有(N-1)！个解，N=15时，(15-1)!就约等于871亿。

2. 描述性优化目标

 它的目标函数   和解  而更倾向于一系列描述性计算，而不是一个具体的连续函数，这导致它不能用梯度下降一类的算法来求解。

结束语

好了，这节我们简单的说了一下TSP问题是什么问题，知道它是怎么一回事就可以了。TSP问题一般可以用智能算法来求解，例如模拟退火、遗传算法等等，之后我们学习智能优化算法时，就拿它来试刀。