寻找哈密顿电路TSP问题的问题

您好我正在开发一个需要解决TSP问题的项目。我需要的是我如何在图中找到哈密顿电路。事实上，我知道如何在现实世界中做到这一点。但是在实现和源代码中，我不知道如何做到这一点。我已经在互联网上阅读过使用一些嵌套循环的文章，但是我没有得到什么，以及整个故事如何进行。如果有人能够帮助我，我会很感激。给我一个关于如何实现这个的简单例子。我不需要一个工作模型。假设我们有一个顶点数组和一个路径数组（通过路径来表示路径的开始和结束顶点）。我们如何解决这个问题。寻找哈密顿电路TSP问题的问题

来源

2010-12-16 user435245

我不知道你想要什么，但要以最快的方式解决TSP，你需要结合不同的算法，如：最近邻居，2-opt，3-opt，蚂蚁算法......问题是以最好的方式将它们结合起来，而不仅仅是编程。 – Pietro 2010-12-16 13:21:32

没有我的问题没有找到快速的方法，它只是关于它的实现。我的意思是通过哪些步骤可以在图表中找到一个循环？然后我想比较这些周期并查看哪一个访问了所有节点，然后我想要找到最小巡视路线。我知道这不是一个好的算法，但我想实现这一点。我不知道如何在图中查找循环的编程算法。 – user435245 2010-12-16 13:25:45

您可能会发现一个图形库使事情变得更容易，所以您不必自己乱搞原始顶点/边界/子图/路径表示。我使用http://jgrapht.org/ – andersoj 2010-12-16 14:29:30

找到TSP的确切解决方案的一种更有效的方法是使用运行于O（n^2 * 2^n）的动态编程算法。与一些线性编程方案相比，它相当简单。搜索“TSP动态编程”，你一定会找到很多例子。

还有更天真的方法，比如在O（n！）中运行的强力操作。如果你看到很多for循环（即：多于两个），这可能是你以前见过的算法的类型。这些将完成工作（可能不会在这一生中，取决于图的大小）。

来源

2010-12-16 14:06:34

我认为一些有用的东西不应该超过O（n³） – Pietro 2010-12-16 14:52:14

@Pietro他正试图解决（可能是最着名的）计算机科学中的NP难题。我对你如何认为它应该运行在不超过O（n^3）的情况感兴趣。 – 2010-12-16 16:18:23

@Ian Bishop。 DP可能是解决TSP（NP困难问题）的一种方法。我怀疑是否有任何研究已经完成，以确立其“最佳（最有效率）” - 超越其他方法......我相当确定分支和限制/削减一代消除子级可能是有竞争力的。 – Tryer 2010-12-16 17:42:24

寻找哈密顿电路TSP问题的问题

回答

相关问题