TSP经最近邻

Question

我编写了代码来实现最近邻算法，从而为TSP问题提供了一个解决方案。

在我的机器上，代码大约需要10秒。因为这太短了，我尝试过的很多剖析器都没有机会把它正确地记录下来。如何有效地分析这些代码？

当我定义距离矩阵和全局大小时，代码大约需要6秒，是什么导致了这种差异？

“守则”：

import static java.lang.Math.asin;
import static java.lang.Math.cos;
import static java.lang.Math.sin;
import static java.lang.Math.sqrt;
import static java.lang.Math.toRadians;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;

public class TSPNearestNeighbour {
    final static int size = 1000;
    static double[][] distances = new double[size][size]; // cost matrix

    public static void main(String[] args) throws Exception {
        long start = System.nanoTime();
        TSPNearestNeighbour instance = new TSPNearestNeighbour();
        instance.solveMe();
        System.out.println("Total time: " + (System.nanoTime() - start) / 1000000 + "ms");
    }

    public void solveMe() throws Exception {
        String[] inputs = load("src/1000airports.txt"); //Towns are numbered from 1 to n in the file
        double[][] coords = new double[size][size];
        for (int i = 0; i < size; i++) {
            String[] tokens = inputs[i].split(",");
            for (int j = 0; j < tokens.length - 2; j++) {
                coords[i][j] = Double.parseDouble(tokens[j + 2]);
            }
        }

        for (int i = 0; i < size; i++) {
            for (int j = i; j < size; j++) {
                distances[i][j] = haversin(coords[i][0], coords[j][0], coords[i][1], coords[j][1]);
                distances[j][i] = distances[i][j];
            }
        }

        long start = System.nanoTime();
        int[] shortestPath = nearestNeighbour(distances);

        System.out.println("Nearest took: " + (System.nanoTime() - start) / 1000000 + "ms");
        //printPath(shortestPath);

        double bestShort = 0;
        for (int i = 0; i < size - 1; ++i) {
            bestShort += distances[shortestPath[i] - 1][shortestPath[i + 1] - 1];
        }
        bestShort += distances[shortestPath[size - 1]][shortestPath[0]];

        System.out.println("DONE w/ a distance of: " + bestShort);
        printPath(shortestPath);
    }

    /*  for each town in the graph,
            start there, and find the closest town not yet visited.
            set current location to that town, and add the distance
            When all towns have been visited go home.
            If the total distance is shorter than the previous best, update it
        return the path with the shortest distance found
    */
    public int[] nearestNeighbour(double[][] distances) {
        boolean[] copy = new boolean[size];
        int[] shortestPath = new int[size];
        int current = 0;
        double bestDistance = Double.MAX_VALUE;

        // nearest neighbour thingy
        int town = current;
        for (int a = 0; a < size; a++) {
            // reset distance array
            Arrays.fill(copy, true);
            double shortest = 0,  dist = 0;
            int[] temp = new int[size];
            int index = 0;
            temp[index++] = a + 1;
            current = a;

            for (int c = 0; c < size - 1; c++) {
                shortest = Double.MAX_VALUE; // reset closest

                for (int i = 0; i < size; i++) {
                    if(i == current) continue;
                    if (copy[i] && (distances[current][i] < shortest)) {
                        town = i;
                        shortest = distances[current][i];
                    }
                }

                copy[current] = false;
                temp[index++] = town + 1;
                current = town;
                dist += shortest;
            }

            dist += distances[temp[index - 1] - 1][temp[0] - 1];
            if (dist < bestDistance) {
                shortestPath = Arrays.copyOf(temp, temp.length);
                bestDistance = dist;
            }
        }
        return shortestPath;
    }

    public double haversin(double x1, double x2, double y1, double y2) {

        // difference between x and y co-ords
        double differenceInX = toRadians(x2 - x1);
        double differenceInY = toRadians(y2 - y1);

        // convert to radians
        // angle / 180.0 * PI
        x1 = toRadians(x1);
        x2 = toRadians(x2);

        // 2r is a constant, and presuming the radius is 6371lm
        return 12742.0 * asin(sqrt(sin(differenceInX / 2) * sin(differenceInX / 2) + sin(differenceInY / 2) * sin(differenceInY / 2) * cos(x1) * cos(x2)));
    }

    public void printPath(int[] path) {
        for (int i = 0; i < size - 1; ++i) {
            System.out.print(path[i] + ".");
        }
        System.out.println(path[size - 1]);
    }

    public String[] load(String path) throws Exception {
        BufferedReader in = new BufferedReader(new FileReader(path));
        StringBuilder contents = new StringBuilder();
        String line;
        while ((line = in.readLine()) != null) {
            contents.append(line).append(System.getProperty("line.separator"));
        }
        in.close();
        return contents.toString().split(System.getProperty("line.separator"));
    }
}

Answer 1

高级设计

让我看看main

public static void main(String[] args) throws Exception {
    long start = System.nanoTime();
    TSPNearestNeighbour instance = new TSPNearestNeighbour();
    instance.solveMe();
    System.out.println("Total time: " + (System.nanoTime() - start) / 1000000 + "ms");
}

我有很多问题：

• 投入城市是什么？
• 如何更改程序以输入我自己的城市数据集？
• 为什么我不能在我的程序的其他地方使用这个解决方案？换句话说，为什么solveMe要打印解决方案而不返回它？
• 为什么时间代码在TSP类中？为什么不把它移除，然后用time java TSP.java调用它呢？

我更希望看到以下情况：

public static void main(String[] args) throws Exception {
    System.out.println(
        TravellingSalesMan.readFromFile(FILE_INPUT).solveByNearest() );
}

• TravellingSalesMan是一个更好的名字。类名应该描述情况，算法名可以是一个方法。
• 我可以清楚地看到输入来自FILE_INPUT，这是一个在代码上方声明的常量，以便于更改。
• 或者我可能想直接传递一个数组，类似于：

TravellingSalesMan([ (1,2), (4,5) ...]).solveByNearest()

• 该方法返回一个解决方案，这意味着我可以在我的程序的另一部分中重用它，以便对其进行进一步的计算。
• 如果我想用任何其他启发式方法来解决这个问题，我只需更改最后的方法：

....    .solveByBruteForce()

在类名中对解决方案策略进行硬编码，并将解决方案命名为solveMe一般，这样就不可能扩展该类。