设为主页 加入收藏 繁體中文

量子计算中经典的旅行商(TSP)问题

旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:

       给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。

       最早的旅行商问题的数学规划是由Dantzig(1959)等人提出,并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难,但已经有了大量的启发式算法和精确方法来求解数量上万的实例,并且能将误差控制在1%内。

从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

量子计算可以加速某些算法来解决着名的旅行推销员问题。

      英国布里斯托尔大学Dominic Moylett及其同事展示了量子计算如何有潜力加快TSP算法。

      有几种方法可以帮助旅行推销员挑选他的旅行路线。暴力法是最基本也是最容易想到的算法。计算每个可能的行程的距离,对于n个城市来说,这相当于n!计算,计算量随着n增长而变得非常大,天文数字一样的计算量让经典的暴力算法无能为力了。

      量子计算机可以通过将计算次数减少为√n 来提供二次加速。 

      经典算法与量子计算有所不同吗?莫利特和他的同事们认为采用一种有效的特殊类型的方法:回溯。在经典情况下,一个迭代地选择城市之间的道路,给它分配一个“旅行”或“不行驶”的值,然后检查这个分配是否与形成通过每个城市的完整路线一致,对于量子回溯,团队对每条道路进行“行驶”和“不行驶”的叠加,然后传统的措施,结果表明,道路数量可以获得近似二次加速度。

 

以上文章转自微信公众号“量子纠缠”


TAG: