算法设计与分析 5.9 旅行售货员问题w

来源：百度文库 编辑：神马文学网 时间：2024/05/23 11:31:33
/***************************************************************
*                  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);
}
}
}
}
}
算法设计与分析 5.9 旅行售货员问题w 算法设计与分析 5.9 旅行售货员问题9090 回溯法旅行售货员问题 算法设计与分析　冒泡排序 算法设计与分析 2.81 快速排序 算法设计与分析 2.2 分治法基本思想 算法分析与设计之五大常用算法_算法_C/C++频道_中国IT实验室技术专题 算法：设计与择优1 算法——设计与择优1 数据结构与算法分析 学习笔记 算法分析 楼宇自动化系统设计问题分析1 常用算法设计方法 计算名次与按名次排序问题的算法优化 文革时与售货员的吵架 Rijndael算法分析 面向服务的分析与设计原理 WebQuest设计与应用调查分析 办学swot分析与战略设计 面向服务的分析与设计原理 新课程小学英语教学设计与案例分析 ｎＰＶＲ业务的分析与设计(1) ｎＰＶＲ业务的分析与设计(2) 算法设计(回溯法1)