旅行商问题

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;
import java.util.Random;


public class Test {

    public static void main(String[] args) throws IOException {
        List<String> data = Files.readAllLines(Paths.get(
            "test.file"));
        Node[] nodes = new Node[102];
        for (int i = 0; i < 102; i++) {
            nodes[i] = new Node();
        }
        nodes[0].x = nodes[0].y = nodes[101].x = nodes[101].y = 0;
        for (int i = 0; i < 100; i++) {
            String point = data.get(i);
            String[] xy = point.split(",");
            nodes[i + 1].x = Integer.valueOf(xy[0]);
            nodes[i + 1].y = Integer.valueOf(xy[1]);
        }

        //for (int i = 0; i < 101; i++) {
        //    int index = i + 1;
        //    int dist = 10000;
        //    for (int j = i + 1; j < 101; j++) {
        //        int d = countDist(nodes[i], nodes[j]);
        //        if (d < dist) {
        //            dist = d;
        //            index = j;
        //        }
        //    }
        //    Node k = nodes[index];
        //    nodes[index] = nodes[i + 1];
        //    nodes[i + 1] = k;
        //}

        System.out.println(getAnserString(nodes));
        System.out.println("最优解:" + countCost(nodes, 1, 102));

        int bestAnser = countCost(nodes, 1, 102);
        long startTime = System.currentTimeMillis();
        Random random = new Random();
        while (true) {
            if (System.currentTimeMillis() - startTime > 3 * 1000) {
                break;
            }
            int p1 = random.nextInt(100);
            int p2 = random.nextInt(100);
            if (p1 == p2) {
                continue;
            }
            Node k = nodes[p1 + 1];
            Node h = nodes[p2 + 1];
            nodes[p1 + 1] = h;
            nodes[p2 + 1] = k;
            int newAnser = countCost(nodes, 1, 102);
            if (newAnser < bestAnser) {
                System.out.println(getAnserString(nodes));
                System.out.println("最优解:" + countCost(nodes, 1, 102));
                bestAnser = newAnser;
            } else {
                nodes[p1 + 1] = k;
                nodes[p2 + 1] = h;
            }
        }
        System.out.println("--------------------------------------");
        int minDist = countCost(nodes, 1, 102);
        while (true) {
            boolean flag = true;
            for (int f = 10; f > 0; f--) {
                System.out.println("--------------------继续----------------"+f);

                for (int i = 1; i + maxDept <= 101; i += f) {
                    maxDist = 10000;
                    for (int j = 0; j < maxDept + 2; j++) {
                        indexNode[j] = position[j] = nodes[i + j - 1];
                        used[j] = false;
                    }
                    dfs(0, 0);
                    if(maxDist != 10000) {
                        for (int j = 0; j < maxDept; j++) {
                            nodes[j + i] = bestPosition[j];
                        }
                    }
                    if (minDist > countCost(nodes, 1, 102)) {
                        if (minDist > countCost(nodes, 1, 102)) {
                            System.out.println(getAnserString(nodes));
                            System.out.println("最优解:" + countCost(nodes, 1, 102));
                            minDist = countCost(nodes, 1, 102);
                        }
                        flag = false;
                    }
                }
            }
            if (flag) {
                break;
            } else {
                System.out.println("--------------------继续----------------");
            }
        }
    }

    final static int maxDept = 30;

    public static Node[] bestPosition = new Node[maxDept + 2];
    public static Node[] position = new Node[maxDept + 2];
    public static Node[] indexNode = new Node[maxDept + 2];
    public static boolean[] used = new boolean[maxDept + 2];
    public static int maxDist = 100000;

    public static void dfs(int depth, int countCost) {
        if (depth == maxDept) {
            int dist = countCost(position, 1, maxDept + 1);
            if (dist < maxDist) {
                maxDist = dist;
                for (int i = 0; i < maxDept; i++) {
                    bestPosition[i] = position[i + 1];
                }
            }
            return;
        }
        for (int i = 0; i < maxDept; i++) {
            if (used[i]) {
                continue;
            }
            int newCost = countCost + countDist(position[depth], indexNode[i + 1]);
            if (newCost >= maxDist) {
                continue;
            }
            used[i] = true;
            position[depth + 1] = indexNode[i + 1];
            dfs(depth + 1, newCost);
            used[i] = false;
        }
    }

    public static int countDist(Node a, Node b) {
        return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
    }

    public static int countCost(Node[] nodes, int begin, int end) {
        int anser = 0;
        for (int i = begin; i < end; i++) {
            anser += Math.abs(nodes[i].x - nodes[i - 1].x) + Math.abs(nodes[i].y - nodes[i - 1].y);
        }
        return anser;
    }

    public static String getAnserString(Node[] nodes) {
        StringBuilder sb = new StringBuilder("0,0\n");
        for (int i = 1; i <= 100; i++) {
            sb.append(nodes[i].x).append(",").append(nodes[i].y).append("\n");
        }
        sb.append("0,0");
        return sb.toString();
    }

    public static class Node {
        public int x;
        public int y;
    }

}

0,8
1,9
14,8
24,6
35,2
36,7
37,8
38,6
47,4
60,4
67,0
67,10
66,13
82,14
82,17
83,18
90,19
94,13
94,21
98,25
88,28
81,29
84,36
71,36
66,49
53,55
54,68
53,69
49,71
43,75
36,78
36,87
40,88
40,93
50,98
38,97
32,90
27,87
25,88
23,92
17,89
10,91
8,94
13,82
2,76
5,73
9,65
8,62
10,60
14,57
25,56
24,53
19,50
13,47
11,41
4,42
8,38
20,31
29,25
29,24
36,23
33,19
33,15
40,15
48,33
49,37
43,41
42,43
34,44
26,44
19,64
22,71
30,72
38,73
55,82
58,78
60,79
69,81
69,69
77,69
77,65
80,57
94,48
95,48
96,50
98,53
98,61
98,62
94,62
96,77
95,97
92,95
90,94
91,91
83,87
83,86
73,98
69,97
64,91
41,51

旅行商问题

题目：起始点0，0，终止点0，0中间必须经过所有的点。求最短路径。

解法：

贪心求初始解，每次找最近的点走。

然后局部枚举所有路径求最优路径

 

 

 

本文地址：https://blog.csdn.net/firenet1/article/details/109236532