鉴于x和y坐标所限定的点集合。

Given a point collection defined by x and y coordinates.

在此集合，我得到的起点，终点和所有其他正2分。

In this collection I get the start point, the end point and all the other n-2 points.

我一定要找到起点和终点之间的最短路径一路过关斩将所有其他点。最短的方式是由它的价值，如果可能的交叉点顺序定义。

I have to find the shortest way between the start point and end point by going through all the other points. The shortest way is defined by its value and if possible the crossing point order.

在第一次看这似乎是一个图的问题，但我不那么肯定，现在，任何方式我试图找到这个最短的路只用几何关系，因为目前所有的信息，我已经是仅在x和点y坐标，并且其点是起点并且其终点。

At a first look this seems to be a graph problem, but i am not so sure about that right now, any way i am trying to find this shortest way by using only geometric relations since currently all the information that i have is only the x and y coordinates of the points, and which point is the start point and which is the end point.

我的问题是，这种方式只用几何关系发现？

My question is, can this way be found by using only geometric relations?

我想在C＃中实现这一点，因此，如果一些有用的软件包可以请让我知道。

I am trying to implement this in C#, so if some helpful packages are available please let me know.

推荐答案

最简单的启发与合理的性能是2-OPT。放点的数组，与开始点的第一和结束点最后，并多次试图改善该溶液如下。选择一个开始索引我和结束索引j，并从我扭转子阵到j。如果总成本是更小，则保持这个变化，否则撤消它。需要注意的是总费用会少，当且仅当d（对[I - 1]，第[I]）+ D（P []]，第[J + 1]）> D（P [I - 1] ，P [J]）+ D（P [I]，P [] + 1]），这样就可以避免进行交换，除非它是一个进步。

The simplest heuristic with reasonable performance is 2-opt. Put the points in an array, with the start point first and the end point last, and repeatedly attempt to improve the solution as follows. Choose a starting index i and an ending index j and reverse the subarray from i to j. If the total cost is less, then keep this change, otherwise undo it. Note that the total cost will be less if and only if d(p[i - 1], p[i]) + d(p[j], p[j + 1]) > d(p[i - 1], p[j]) + d(p[i], p[j + 1]), so you can avoid performing the swap unless it's an improvement.

有改进该方法一个可能的数目。 3-opt和K-OPT考虑更多的可能的行动，从而更好的解决方案的质量。数据结构的几何搜索，KD树，例如，减少时间找到改进动作。据我所知，在本领域中的TSP局部搜索算法的状态是Keld Helsgaun的的 LKH 。

There are a possible number of improvements to this method. 3-opt and k-opt consider more possible moves, resulting in better solution quality. Data structures for geometric search, kd-trees for example, decrease the time to find improving moves. As far as I know, the state of the art in local search algorithms for TSP is Keld Helsgaun's LKH.

算法的另一个家庭是分支定界。这些回报的最佳解决方案。 协和（据我所知）是最先进的国家在这里。

Another family of algorithms is branch and bound. These return optimal solutions. Concorde (as far as I know) is the state of the art here.

下面是一个Java实现的O（N ^ 2 ^ 2 n）的DP的尼克拉斯描述。有许多可能的改进，例如，缓存点之间的距离，切换到花车（也许），重组循环，使子集枚举递增的顺序大小（以允许 minTable的只是最近的层来予以保留，导致显著节省空间）。

Here's a Java implementation of the O(n^2 2^n) DP that Niklas described. There are many possible improvements, e.g., cache the distances between points, switch to floats (maybe), reorganize the iteration so that subsets are enumerating in increasing order of size (to allow only the most recent layer of minTable to be retained, resulting in a significant space saving).

class Point {
    private final double x, y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    double distanceTo(Point that) {
        return Math.hypot(x - that.x, y - that.y);
    }

    public String toString() {
        return x + " " + y;
    }
}

public class TSP {
    public static int[] minLengthPath(Point[] points) {
        if (points.length < 2) {
            throw new IllegalArgumentException();
        }
        int n = points.length - 2;
        if ((1 << n) <= 0) {
            throw new IllegalArgumentException();
        }
        byte[][] argMinTable = new byte[1 << n][n];
        double[][] minTable = new double[1 << n][n];
        for (int s = 0; s < (1 << n); s++) {
            for (int i = 0; i < n; i++) {
                int sMinusI = s & ~(1 << i);
                if (sMinusI == s) {
                    continue;
                }
                int argMin = -1;
                double min = points[0].distanceTo(points[1 + i]);
                for (int j = 0; j < n; j++) {
                    if ((sMinusI & (1 << j)) == 0) {
                        continue;
                    }
                    double cost =
                        minTable[sMinusI][j] +
                        points[1 + j].distanceTo(points[1 + i]);
                    if (argMin < 0 || cost < min) {
                        argMin = j;
                        min = cost;
                    }
                }
                argMinTable[s][i] = (byte)argMin;
                minTable[s][i] = min;
            }
        }
        int s = (1 << n) - 1;
        int argMin = -1;
        double min = points[0].distanceTo(points[1 + n]);
        for (int i = 0; i < n; i++) {
            double cost =
                minTable[s][i] +
                points[1 + i].distanceTo(points[1 + n]);
            if (argMin < 0 || cost < min) {
                argMin = i;
                min = cost;
            }
        }
        int[] path = new int[1 + n + 1];
        path[1 + n] = 1 + n;
        int k = n;
        while (argMin >= 0) {
            path[k] = 1 + argMin;
            k--;
            int temp = s;
            s &= ~(1 << argMin);
            argMin = argMinTable[temp][argMin];
        }
        path[0] = 0;
        return path;
    }

    public static void main(String[] args) {
        Point[] points = new Point[20];
        for (int i = 0; i < points.length; i++) {
            points[i] = new Point(Math.random(), Math.random());
        }
        int[] path = minLengthPath(points);
        for (int i = 0; i < points.length; i++) {
            System.out.println(points[path[i]]);
            System.err.println(points[i]);
        }
    }
}