旅行商问题

来自计算思维百科
跳转至: 导航搜索
旅行商问题1.png

旅行商问题(Traveling Salesman Problem,简称TSP),又称为旅行推销员问题、货郎担问题。通常描述是:一位商人去n个城市推销货物,所有城市走一遍后,再回到起点,问如何事先确定好一条最短的路线,使其旅行的费用最少。

解决方案

旅行商问题又称旅行推销员问题、货郎担问题。不妨假设给定4个城市分别为A、B、C、D,各城市之间的交通分布线路及其距离如下图所示:

旅行商问题2.png

方案一:穷举法

旅行商问题3.png

从上图中可以看出,可供选择的路线有6条,每条线路的总距离计算如下:

路径ABCDA的总距离是:4+2+4+2=12;

路径ABDCA的总距离是:4+6+4+6=20;

路径ACBDA的总距离是:6+2+6+2=16;

路径ACDBA的总距离是:6+4+6+4=20;

路径ADCBA的总距离是:2+4+2+4=12;

路径ADBCA的总距离是:2+6+2+6=16;

根据上述计算,我们很容易就可以选出距离最短为12的线路,ABCDA或ADCBA。如果城市有20个,组合的路径数就有19!≈1.216×1017条,如此庞大的组合数,若按计算机以每秒检索1000万条路线的速度计算也需要花上386年的时间,所以我们需要用其他方法来寻找。

方案二:分支界限法

旅行商问题4.png

步骤一:计算任何路线长度的下界。

对于每一个城市,求出该城市到最近两个城市的距离之和,将所有的和相加再除以2向上取整,所以计算下界如下,

对于城市A,离A最近的两个城市是B、D,距离和2+4=6;

对于城市B,离B最近的两个城市是A、C,距离和2+4=6;

对于城市C,离C最近的两个城市是B、D,距离和2+4=6;

对于城市D,离D最近的两个城市是C、A,距离和2+4=6。

下界 =(6+6+6+6)/2=12.

步骤二:运用分支界限法画出的状态空间树如下:

旅行商问题5.png

可以从状态树中清晰地看出线路ABCDA和ADCBA是路程最短的线路。

方案三:最近邻居算法

步骤一:任意选择一个城市作为开始。

步骤二:重复下面的操作直到访问完所有的城市。下一步走距离当前城市最近的未走过的城市。

步骤三:回到开始的城市。

那么,对于下面的例子,假设从城市A开始,路线应该为ADCBA。

旅行商问题6.png

涉及的计算思维

首先我们要把问题抽象出来,建好模型。我们在考虑解决这种问题时,一般最先想到的就是用最原始的方法-穷举法。列出每一条可供选择的路线,计算出每条路线的总里程,最后从中选出一条最短的路线。这就是“机械式”思维方式的体现。但是如果城市数较多,显然,穷举法就难以解决,那我们可以运用计算思维的“优化”的特点找出相对较好的路线以满足需求。