0

为学校做一个项目，我们实现最近邻启发式（我已经做过），以及我们进行详尽搜索的旅行销售员问题（然后我们分析算法，它们的时间复杂度等）。我们的老师说要四处寻找用于详尽搜索部分的代码（或修改），而不是像在最近邻部分中那样对整个事物进行编程。我环顾四周，只找到了与我们被指示如何执行程序无关的内容。与使用整数的典型问题相反，我们使用点 (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];

任何帮助是极大的赞赏。

4

2 回答 2

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 方法，其中您有一个循环遍历所有组合，就像一个数字时钟，每个数字代表数组中的 1 个索引。

于 2012-09-06T06:42:09.203 回答
0

您不需要（额外的）内存来为给定实例生成所有排列/解决方案。你可以把它们写在屏幕上...

看看这个实现https://github.com/stardog-union/pellet/blob/master/core/src/main/java/org/mindswap/pellet/utils/PermutationGenerator.java。
它在每次调用getNext()新解决方案时生成。

public void PermGen() {
    int[] tour;
    PermutationGenerator x = new PermutationGenerator(N);
    System.out.println(x.getTotal());
    while (x.hasMore()) {
        tour = x.getNext();
        System.out.println(Arrays.toString(tour));
    }
}

上面的 Java 代码打印了所有 TSP 实例解决方案……
但是您当然可以保存它们（例如在文件中），但是您需要数百 TB 才能做到这一点。

于 2017-08-12T16:53:43.850 回答