Gharan等人提出的新算法的近似解,先利用随机过程创建树,然后再将它转换成完整的往返旅程。
这种方法似乎很有前景,他们相信这是一种更好的算法,但严谨地证明出这种优越性并非易事。
2011年,Gharan等人成功证明,他们的新算法在“图形化”TSP上比克里斯托菲德斯算法更优。“图形化”TSP可以理解成TSP的一类特例,也就是城市之间的距离由一个网络(不一定包括所有连接)表示,每边长度相同。但他们一直没能将结果推广到一般性TSP中。
几年来,Gharan仍然在一直思考这个问题。他认为,数学中的多项式几何(geometry of polynomials)领域可能是解决问题的关键工具,但理论计算机界对这一数学领域知之甚少。Gharan在与Karlin共同指导研究生Klein时,他们决定共同推进对这个问题的研究。
在第一年里,他们先从一种简化版本入手。尽管困难重重,但他们开始对所用的工具有了感觉,尤其是多项式几何。
多项式是由常数和变量的幂运算等组合而成的表达式,比如x²y+2yz⁵。在TSP中,研究人员将一张城市地图提炼成一个多项式,其中每座城市之间的连接是一个变量,可以连接所有城市的每个树是一项。数值因数随后为这些项加权,反映出旅行售货员问题的分段解中每条边的值。
他们发现,这个多项式有一种迷人的性质,也就是“实稳定性”(real stability),也就是说,让多项式为零的复数永远不在复平面的上半部分。实稳定性带来的优势是,即使对多项式做出许多改变,它仍然有效。例如,当研究人员操控一些更简化的多项式时,他们操控的结果仍然具有实稳定性,这就为各种各样的技巧打开了大门。
这使得研究人员能够更好地处理一些问题。终于,在一份80多页的论文中,Karlin、Klein和Gharan证明出,10年前设计出的算法确实比克里斯托菲德斯算法要更好。新算法在克里斯托菲德斯算法(3/2近似比)的基础上,将近似比提高到了3/2 - 10⁻³⁶。
虽然这一微小的数字看似不足为道,但许多理论计算机学家相信,它突破了理论和心理上的僵局。研究人员希望,这能为进一步的提高开辟道路。
喜欢数学心请大家收藏:(www.qicaizw.com)数学心七彩中文更新速度全网最快。