你好 我正在做一个需要解决 TSP 问题的项目。我在这里需要的是如何在图中找到哈密顿回路。事实上，我知道如何在现实世界中做到这一点。但是在实现和源代码中我不知道如何做到这一点。我在互联网上阅读过使用一些嵌套循环的文章，但我没有了解每个 for 的作用以及整个故事的进展情况。如果有人可以帮助我，我将不胜感激。并给我一个关于如何实现它的简单示例。我不需要工作模型。假设我们有一个顶点数组和一个路径数组(路径我指的是路径的开始和结束顶点)。我们如何解决这个问题。
最佳答案
找到 TSP 精确解的更有效方法之一是使用在 O(n^2*2^n) 中运行的动态规划算法。与一些线性规划替代方案相比，它相当简单。搜索“TSP 动态规划”，您一定会找到很多示例。
还有更简单的方法，例如在 O(n!) 中运行的蛮力。如果您看到很多 for 循环(即:超过两个)，这很可能是您以前见过的算法类型。这些将完成工作(可能不会在这一生中完成，具体取决于图表的大小)。
关于java - 为 TSP 问题寻找哈密顿回路的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4460965/