java - 旅行商和最短路径

Question

我目前正在从事一个混合了旅行推销员和最短路径的项目。它是这样的:

我给定了一组 9 个顶点，它们在 2 空间 (x,y) 中都具有正坐标，其中 x 和 y 是正实数。然后我被要求计算旅行推销员可以走的最短路径，并遍历所有点。本质上，该图只是具有坐标的节点的集合，我必须排列边，以便从节点 1 到节点 9 有一条连接，这是最短的连接。假设我已经访问过最开始的节点1(x1,y1)，并且每个节点只需要访问一次。我将在由 (x9,y9) 指定的节点 9 结束。

我正在用Java写程序，虽然教授说程序可以用任何语言写。

我首先编写了一个节点类，它表示每个节点，并具有分别表示 x 和 y 坐标的字段 x,y。但是，我完全不知道如何执行优化。

如果您能就此问题提供任何帮助，我将不胜感激。

非常感谢，我很高兴成为这个社区的一员!

Answer 1

欧几里德 TSP 仍然是 NP-hard，所以只要为您想要的一般 TSP 使用任何算法即可；对于 9 个顶点，蛮力解决方案比较 7! = 5040 7 个中间顶点的排列(因为根据问题描述，您从 1 开始并以 9 结束)，所以您需要做的就是为此生成 {2,...,8} 的所有排列，然后检查这些路径的长度。

如果您想要一些稍微花哨的东西，请选择 Held、Karp 和 Bellman 的动态规划方法，您可以在 lots of places online 中继续阅读，所以我不会发布它是如何工作的。