实例探索TSP路线--周游美国48州

posted at 2021.6.26 15:36 by administrator

这道难题流行于20世纪40年代,题目是给一名旅行商设计路线。让他以华盛顿特区为起点,周游美国本土的48个州。Julia Robinson建议把各州首府指定为旅行商的目的地,从而限制了路线的范围。求出最优路线。

那么,解决这道题目的算法有哪些呢?

一、最近邻算法

在从头开始构建路线的时候,最容易想到的方法就是每次都在没有到过的城市中选择最近的一个。这种算法称为最近邻算法(nearest-neighbor algorithm),看起来合情合理,然而得到的路线通常不是最短的。

二、贪心算法greedy algoruthm

贪心算法就是同时生成许多段子路线,每一步都把最短的可用路线片段加入解集中。

如果测试范例很大,若城市在正方形内随机分布,以直线距离作为每段路程,则贪心算法通常不会超过最优解的1.15倍,而最近邻算法通常不超过最优解的1.25倍。

三、插入算法insertion algorithm

这种算法的思路是从一条周游几个城市的子路线出发,逐个增加新的城市,让路线像橡皮筋一样扩展,从而包围更多城市。

插入算法可分为几种,分别为最小插入法(cheapest)、最近插入法(nearest)、最远插入法(farthest)、随机插入法(random)。无论是哪一种插入算法,在插入新城市时,都会选择路线上最合适的位点,使插入后的路线长度最短。

研究表明,在满足三角不等式的条件下,最小插入法和最近插入法都相当好,得到的路线长度不会超过最优路线长度的2倍。虽然在实际应用中,最远插入法往往效果最好,但在理论上,其路线长度只能保证不超过最优路线的log(n)倍。

四、深度优先搜索算法depth-first search algorithm

对于路线选择问题,最优解是一棵树,但树并不是环形路线,但是可以给出周游城市的方式。下面给出一种做法:在一棵树中,到达一座新城市后,如果有一条边从这座城市出发,尚未经过搜索,便沿这条边继续前进,到达另一座新城市;否则,如果从这座城市出发的所有边都已搜索过,则逐个回溯之前访问的城市,直到发现某座城市连接的某条边未经搜索为止。重复上述过程,最终会到达所有城市,并回到出发点。这样的路线称为按照深度优先搜索遍历一棵树。

五、Christofides算法

算法可以描述如下:

构造图上的最小的生成树T

O为原图顶点集中在T上度数为奇数的顶点集。根据握手定理,O中有偶数个顶点

构造点集O在原完全图上的最小完全匹配M

M T 的边集取并,构造重图H ,满足其每个顶点都是偶数度的

H可以形成一个欧拉回路

将前一步得到的图改造为一个哈密尔顿回路:只需要跳过前一步欧拉回路中重复的顶点即可(这个步骤又称作选取近道,"short-cutting")。

1976年,Nicos Christofides首次完整提出这一算法,将欧拉和Edmonds的结论结合在一起,Christofides算法保证路线长度不超过最优解的1.5倍。

六、边交换算法

TSP领域,最基本的定理可能要数这一条:如果题目数据使用欧几里德距离,那么最优路线必定不会相交,用一步2-交换就可以证明这个事实。如果我们反复使用2-交换改进路线,就会大大改善差劲的最近邻路线。

七、Lin-Kernighan算法

20世纪60年代中期,Shen Lin发表了结果,证明3-交换可以成功地改进路线。但是,如果k远远大于23 ,搜寻改进路线的k-交换就需要巨大的计算量,因此完全不可行。尽管如此,Lin和计算机科学先驱Brian Kernighan还是成功实现了这种方法。他们巧妙地构建了一种新算法,取得了TSP研究中最伟大有成就之一。

Lin-Kernighan算法精巧复杂,但图一足以概述其中心思想。该图将初始路线表现为一个环,降低了理解算法流程的难度。需要提醒读者注意,各边在图中的长度并不代表实际路程。

Lin-Kernighan算法使用随机路线作为初始路线,结果同样得到了环游美国问题的短路线。这为过去几十年中大多数优秀TSP解法奠定了基础,在此期间,规模大得多的题目也得以解决。

八、Lin-Kernighan-Helsgaun算法

Lin-Kernighan算法在实际计算领域长期占据统治地位。1998年。计算机科学家Keld Helsgaun带来了一枚重磅炸弹,他的主要贡献是重写了算法的核心搜索程序。Lin-Kernighan标准算法可以视为搜寻2-交换操作序列的方法,Helsgaun的新方法却以5-交换操作序列为搜寻对象,以愚公移山的努力,在性能方面实现了惊人的飞跃。

Helsgaun后来对LKH程序进行了有力的升级,允许用户具体指定每次交换操作包含连续几步。2003年,他以周游瑞典24978座城市的问题为例,计算了10-交换操作,所得TSP路线的最优性于次年得到证明。

九、借鉴物理和生物思想的算法

事实证明,把TSP视为一类搜索问题的特例,从全局着眼看待寻找路线过程,会大有裨益。思路意图产生元启发式算法(metaheuristic)。

(一)局部搜索与爬山算法

想象路线所处环境具有一定的地形变化,每条路线的高程对应于它的好坏程度,这样一来,启发式算法就可以想象成四处移动搜寻高地的过程。若搜寻全面彻底,则最终算法将在山峰上终止。

(二)模拟退火(simulated annealing)算法

该方法的动力源于统计力学与TSP的关联,在统计力学中,退火表示先加热再缓慢冷却材料以改善其结构的工艺过程。

(三)链式Lin-Kernighan算法

这种算法基本上垄断了20世纪90年代的路线搜寻领域。

(四)遗传算法(geneyic algorithm

也有人从生物角度出发,把路线当成能够逐渐变异和进化的生命有机体。首先形成路线的初始“种群”,可以通过反复从随机城市出发使用最近邻算法获取路线。然后是一般的循环步骤,在种群中选取若干对路线,让它们“交配”(即交叉配对)得到子代路线,再从父子两代路线中选出一个新的种群。反复多次进行这一步骤,最优秀的路线最终将脱颖而出,成为唯一的生存赢家。

(五)蚁群优化算法(ant-colony optimization,ACO

此类算法的工作原理是令一小群蚂蚁沿着图和各边移动,每只蚂蚁探寻一条路线,每次到达新顶点时都选择一条通向未访问的顶点的边。选择规则是算法的核心。

(六)其他

还有许多算法,如神经网络算法(neural network)、禁忌搜索算法(tabu search)和人工蜂群算法(honey bee)。

不知不觉,我们已经走了很远。毫无疑问,在研究TSP领域,丹麦人Keld Helsgaun和日本人永田裕一双双荣登世界冠军的宝座。对破记录的85900座城市TSPHelsgaun的路线是绝对最优的。永田裕一也实现了一种TSP遗传算法,并以此求出了《蒙娜丽莎》TSP挑战的已知最佳路线,也给出了National TSP Collection中规模最大的两道题目的最佳答案。

我们并不宣称该程序万无一失,只是说它能在可行的计算时间内给出较好的结果。

                                                —— Robert Karg Gerald Thompson,1964

Tags: , , , , , , ,

IT技术 | 生活艺术

Add comment

  Country flag

biuquote
微笑得意调皮害羞酷大笑惊讶发呆喜欢可怜尴尬闭嘴噘嘴皱眉伤心抓狂呕吐坏笑漫骂发怒
Loading