回溯法解决旅行商问题（Java实现）

旅行商问题（Traveling Salesman Problem，TSP）又称为旅行推销员问题、货郎担问题，是数学领域的著名问题之一。

问题描述：一个旅行商从 n 个城市中的某一城市出发，不重复地走完其余 n-1 个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第 1 个城市出发。

问题分析

为了方便描述该问题，可采用带权图表示 n 个城市之间的关系，顶点表示城市，顶点之间的权值表示城市之间的距离。例如，n=4 时的旅行商问题可用下图表示。


图中的回路有 (1,2,3,4,1)、(1,2,4,3,1)、(1,3,2,4,1)、(1,4,2,3,1)、(1,3,4,2,1) 等，其中 (1,3,4,2,1) 的路径长度最短，其路径长度为 29。

旅行商人所走过的可能路线其实是所有路径的排列组合，这些方案可绘制成一棵排列树，也是该问题的解空间树，如下图所示。该树的深度为 5，两个结点之间的路径表示旅行商经过的城市。


根据图 2 构造的解空间树，其实是一棵排列树，从根结点出发对每个分支进行搜索遍历，直到叶子结点，得到一系列问题的解，其中代价最小的那个解就是所求问题的解。其步骤如下：

1) 从根结点 A 出发，按照深度优先搜索，依次经过 B、C、F、L，周游路线为 1，2，3，4，1，其费用为 56。

2) 从叶子结点 L 处返回上一层，即 F，由于 F 没有可扩展结点，因此继续向上一层返回，到结点 C 处。

3) 结点 C 成为新的扩展结点，对其他还未走过的分支搜索，走到结点 G，直至结点 M，周游路线为 1，2，4，3，1，其费用为 29。

4) 从叶子结点 M 处返回 G，由于没有可扩展结点，因此继续向上一层返回，到结点 C，同样没有新的可扩展结点，继续返回上一层，到结点 B。

5) 继续对结点 B 进行扩展，走到结点 D，结点 D 成为当前扩展结点，沿着结点 H 走到结点 N，周游路线为 1，3，2，4，1，其费用为 53。

6) 从叶子结点 N 处返回结点 H，由于 H 没有可扩展结点，因此继续向上一层返回，到结点 D。

7) 继续对结点 D 的其他未搜索路径进行扩展，沿着结点 I 走到结点 O，周游路线为 1，3，4，2，1，其费用为 29。

以此类推，对其他未搜索的路径重复执行以上过程，直到所有的路径都走过一遍，最终得到一条长度最小的周游路线 1，3，4，2，1，其费用为 29。

回溯法解决旅行商问题

算法实现如下：

import java.util.Scanner;

public class MyTSP {
    static int INFINITY = 65535;
    int c, bestc;

    MyTSP() {
        c = 0;
        bestc = INFINITY;
    }

    int GetCurrentCost() {
        return c;
    }

    void SetBestCost(int bestc) {
        this.bestc = bestc;
    }

    int GetBestCost() {
        return bestc;
    }

    void SetCurrentCost(int c) {
        this.c = c;
    }

    void Backtrack(int t, int n, int m, int a[][], int bestx[], int x[]) {
        if (t == n) {
            if (a[x[n - 1]][x[n]] != INFINITY && a[x[n]][1] != INFINITY &&
                    (c + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == INFINITY)) {
                for (int i = 1; i <= n; i++) {
                    bestx[i] = x[i];
                }
                bestc = c + a[x[n - 1]][x[n]] + a[x[n]][1];
            }
            return;
        } else {
            for (int i = t; i <= n; i++) {
                if (a[x[t - 1]][x[i]] != INFINITY && (c + a[x[t - 1]][x[i]] < bestc || bestc == INFINITY)) {
                    Swap(x, t, i);
                    c += a[x[t - 1]][x[t]];
                    Backtrack(t + 1, n, m, a, bestx, x);
                    c -= a[x[t - 1]][x[t]];
                    Swap(x, t, i);
                }
            }
        }
    }

    void Swap(int x[], int a, int b) {
        int t;
        t = x[a];
        x[a] = x[b];
        x[b] = t;
    }

    public static void main(String args[]) {
        final int NUM = 100;
        int i, j, m, n;
        int s, t, w;
        int a[][];
        int x[];
        int bestx[];
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入城市数和直接路径数: ");
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n + 1][n + 1];
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                a[i][j] = INFINITY;
            }
        }
        for (i = 1; i <= m; i++) {
            s = sc.nextInt();
            t = sc.nextInt();
            w = sc.nextInt();
            a[s][t] = w;
            a[t][s] = w;
        }
        x = new int[n + 1];
        for (i = 1; i <= n; i++) {
            x[i] = i;
        }
        MyTSP TSP = new MyTSP();
        bestx = new int[n + 1];
        TSP.Backtrack(2, n, m, a, bestx, x);
        System.out.printf("最优路径: ");
        for (j = 1; j <= n; j++) {
            System.out.printf("%d ", bestx[j]);
        }
        System.out.printf("\n最优路径长度: %d\n", TSP.GetBestCost());
    }
}

程序运行结果如下：

请输入城市数和直接路径数：
4 6
1 2 10
1 3 8
1 4 25
2 3 15
2 4 5
3 4 6
最优路径：1 2 4 3
最优路径长度：29

对于旅行商问题，就是从出发顶点出发对所有的路径进行搜索，经过顶点的顺序不同，其路径也就不一样，因此，其解空间是一棵排列树。代码如下：

TSP.Backtrack(2,n,m,a,bestx,x);

其中的参数 2 表示排列树中结点所在的层次，树中的分支构成一个顶点。

当 t==n 时，到达叶子结点，表示完成一个周游路线，将此次周游路线所经过的顶点保存到 best[] 数组中，同时将路径长度也保存到 bestc 中。

当 t<n 时，说明还未完成一个周游路线，若从当前顶点出发到下一个顶点存在路径，则继续搜索，即递归调用 Backtrack(t+1,n,m,a,bestx,x)。