寻找 TSP 问题的哈密顿电路的问题
你好呀 我正在做一个需要解决 TSP 问题的项目。我在这里需要的是如何在图中找到哈密顿电路。事实上，我知道如何在现实世界中做到这一点。但在实现和源代码中我不知道如何做到这一点。我在互联网上读过一些文章，其中使用了一些嵌套循环，但我不知道每个 for 的作用以及整个故事是如何进行的。如果有人能在这方面帮助我，我将不胜感激。并举一个简单的例子来说明如何实现这一点。我不需要工作模型。假设我们有一个顶点数组和一个路径数组（路径是指路径的起始和结束顶点）。我们如何解决这个问题。
Hi there
Im working on a project which needs to solve the TSP problem. The thing i need here is that how i can find the Hamiltonian circuits in the graph. In fact I know how to do this in the real world. But in the implementation and on the source code I do not know how this can be done. I have read articles on the internet which use some nested loops but i did not get what each for does and how the whole story goes on. I would be appreciating if someone can help me on this. And give me a simple example on how to implement this. I do not need a working model. Just assume that we have an array of vertices and an array of paths (by path I mean the start and end vertices of the path). How we can solve this problem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
找到 TSP 精确解的更有效方法之一是使用运行时间为 O(n^2*2^n) 的动态规划算法。与一些线性规划替代方案相比，它相当简单。搜索“TSP动态规划”，你一定会找到很多例子。
还有更简单的方法，例如以 O(n!) 运行的蛮力。如果您看到很多 for 循环（即：两个以上），这可能是您以前见过的算法类型。这些将完成工作（也许不会在这一生中完成，具体取决于图表的大小）。
One of the more efficient ways to find an exact solution to TSP is using a dynamic programming algorithm which runs in O(n^2*2^n). It is rather simple in comparison to some of the linear programming alternatives. Search "TSP dynamic programming" and you'll surely find a lot of examples.
There are more naive approaches, such as brute force which run in O(n!). If you saw a lot of for loops (ie: more than two) this is likely the type of algorithm that you have seen before. These will get the job done (maybe not in this lifetime, depending on the size of your graph).