中财网少年中国说的全文:算法设计与分析 5.9 旅行售货员问题
来源：百度文库 编辑：中财网 时间：2024/05/02 23:22:24
/***************************************************************
* 5.9 旅行售货员问题
* 旅行售货员问题的解空间是一棵排列树。对于排列树的回溯搜索与生成 1, 2, 3, .., n
* 的所有排列的递归算法 perm 类似。开始时 x = [1, 2, .., n], 相应的排列
* 树由 x[1 .. n] 的所有排列构成。
*/
public class TravelSeller {
static int n; // 图G的顶点数
static int[] x; // 当前解
static int[] bestx; // 当前最优解
static int bestc; // 当前最优值
static int cc; // 当前费用
static int[][] a; // 图G的邻接矩阵
public static int travelSeller(int[][] matrix, int[] v) {
n = matrix.length;
a = matrix;
//置 x 为单位排列
x = new int[n];
bestx = v;
bestc = Integer.MAX_VALUE;
cc = 0;
trackback(1); //由于起点固定
return 0;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void trackback(int i) {
if (i == n - 1) {
if (a[x[i - 1]][i] < Integer.MAX_VALUE
&& a[x[i]][0] < Integer.MAX_VALUE
&& (bestc == Integer.MAX_VALUE || cc + a[x[i - 1]][x[i]]
+ a[x[i]][0] < bestc)) {
for (int j = 0; j < n; j++) {
bestx[j] = x[j];
}
bestc = cc + a[x[i - 1]][x[i]] + a[x[i]][0];
}
} else {
for (int j = i; j < n; j++) {
//是否可以进入 x[j] 子树
if (a[x[i - 1]][x[j]] < Integer.MAX_VALUE && (bestc == Integer.MAX_VALUE || cc + a[x[i - 1]][x[j]] < bestc)) {
//搜索子树
swap(x, i, j);
cc += a[x[i - 1]][x[i]];
trackback(i + 1);
cc -= a[x[i - 1]][x[i]];
swap(x, i, j);
}
}
}
}
}