java - 为 TSP 问题寻找哈密顿电路的问题

Question

嗨，我正在做一个需要解决 TSP 问题的项目。我需要的是如何在图中找到哈密顿电路。事实上，我知道如何在现实世界中做到这一点。但是在实现和源代码上我不知道如何做到这一点。我已经阅读了互联网上使用一些嵌套循环的文章，但我没有得到每个 for 的作用以及整个故事是如何进行的。如果有人可以帮助我，我将不胜感激。并给我一个简单的例子来说明如何实现这一点。我不需要工作模型。假设我们有一个顶点数组和一个路径数组（路径是指路径的开始和结束顶点）。我们如何解决这个问题。

Answer 1

找到 TSP 精确解决方案的更有效方法之一是使用在 O(n^2*2^n) 中运行的动态规划算法。与一些线性规划替代方案相比，它相当简单。搜索“TSP 动态规划”，你肯定会找到很多例子。

还有更幼稚的方法，例如以 O(n!) 运行的蛮力。如果您看到很多 for 循环（即：两个以上），这很可能是您之前见过的算法类型。这些将完成工作（可能不会在此生中完成，具体取决于图表的大小）。