The Backbone of the Travelling Salesperson
The Backbone of the Travelling Salesperson
复制标题
DOI：
--
复制
发表时间：
2005-07
期刊：
影响因子：
--
通讯作者：
P. Kilby;J. Slaney;T. Walsh
中科院分区：
文献类型：
--
作者：
P. Kilby;J. Slaney;T. Walsh
我们研究了旅游销售人员优化问题的主干。我们证明了在任何性能保证的情况下，假设P≠NP且错误返回的边的数量有限制，难以近似主干。然而，在实践中，似乎大部分主干都以接近最优解的形式存在。因此，我们经常可以使用基于良好启发式的近似方法找到大部分骨干。我们证明，这些骨干信息可以用来指导搜索最优解。然而，当使用骨干引导启发式时，运行时的差异很大。这表明我们可能需要将这种启发式与随机化和重启结合起来。此外，尽管骨干引导启发式方法对于寻找最优解很有用，但它们在证明最优性方面帮助不大。
We study the backbone of the travelling salesperson optimization problem. We prove that it is intractable to approximate the backbone with any performance guarantee, assuming that P≠NP and there is a limit on the number of edges falsely returned. Nevertheless, in practice, it appears that much of the backbone is present in close to optimal solutions. We can therefore often find much of the backbone using approximation methods based on good heuristics. We demonstrate that such backbone information can be used to guide the search for an optimal solution. However, the variance in runtimes when using a backbone guided heuristic is large. This suggests that we may need to combine such heuristics with randomization and restarts. In addition, though backbone guided heuristics are useful for finding optimal solutions, they are less help in proving optimality.