Java TSP 排列点

Question

为学校做一个项目，我们实现最近邻启发式算法(我已经完成了)，以及旅行推销员问题，我们进行详尽的搜索(然后我们分析算法、它们的时间复杂度等)。我们的老师说要四处寻找用于穷举搜索部分的代码(或修改)，而不是像最近邻部分那样对整个事情进行编程。我环顾四周，只发现了与我们被指示如何执行程序无关的内容。 与使用整数的典型问题相反，我们使用点 (x, y)。 我的目标是计算最短的排列并能够知道该排列是什么。所以我想拥有一个数组的数组(其中包含排列)。

如果有人可以帮助我进行详尽的搜索，那就太好了。

以下是我的代码的一些摘录(成员变量、计算两点之间距离的函数以及所有点的存储位置):

private int x;
private int y;
private boolean visited;

public double dist( point pt ){
    int xdist = this.getX() - pt.getX();
    int ydist = this.getY() - pt.getY();
    double xsr = xdist*xdist;
    double ysr = ydist*ydist;
    return Math.sqrt( xsr + ysr );
}

point[] points = new point[n];

非常感谢任何帮助。

Answer 1

单个 TSP 可能的解决方案本质上只是一系列城市，代表访问它们的顺序，没有起始城市。

因此，假设 n(城市数量)= 5。然后将一个可能的解决方案表示为长度为 4 的数组。现在，您可以用多少种方式对城市 [B、C、D、E] 进行排序？ BCDE、BCED、BDCE、BDEC...这是 4! 或 24 种组合。因此，对于 n 个城市，您将获得 (n-1)! 组合。对于 10 个城市，可产生 362880 个组合。对于 20 个城市或 10^17 种组合，如果您想将它们全部保存到内存中，您将耗尽内存。

另一个问题是您需要 n 个嵌套的 for 循环，但不可能只编写这些 for 循环，因为有 n 个。 (您可以开始编写 for() for() for() ...。 因此，您的实现可能需要某种 walker approach ，其中有一个循环遍历所有组合，就像一个数字时钟，每个数字代表数组中的 1 个索引。