1、用分支限界算法解决旅行商问题/求解旅行商问题的分枝限界算法#include #include #include #define TRUE (1)#define FALSE (0)#define MAX_CITIES (10)#define INFINITY(999)#define I INFINITYtypedef int bool;/* 定义边结构 */typedef struct _EDGE int head; int tail; EDGE;/* 定义路径结构 */typedef struct _PATH EDGE edgeMAX_CITIES; intedgesNumber; PATH;
2、/* 定义花费矩阵结构 */typedef struct _MATRIX int distanceMAX_CITIESMAX_CITIES; int citiesNumber; MATRIX;/* 定义树结点 */typedef struct _NODE int bound; /* 相应于本结点的花费下界 */ MATRIX matrix; /* 当前花费矩阵 */ PATH path; /* 已经选定的边 */ struct _NODE* left; /* 左枝 */ struct _NODE* right; /* 右枝 */ NODE;int Simplify(MATRIX*);EDGE
3、SelectBestEdge(MATRIX);MATRIX LeftNode(MATRIX, EDGE);MATRIX RightNode(MATRIX, EDGE, PATH);PATH AddEdge(EDGE, PATH);PATH BABA(NODE);PATH MendPath(PATH, MATRIX);int MatrixSize(MATRIX, PATH);void ShowMatrix(MATRIX);void ShowPath(PATH, MATRIX);main() PATH path; NODE root = 0, /* 花费下界 */ I, 1, 2, 7, 5, /
4、* 花费矩阵 */ 1, I, 4, 4, 3, 2, 4, I, 1, 2, 7, 4, 1, I, 3, 5, 3, 2, 3, I, 5, /* 城市数目 */ 0, 0, /* 经历过的路径 */ NULL, NULL /* 左枝与右枝 */ ; /* 归约，建立根结点 */ root.bound += Simplify(&root.matrix); /* 进入搜索循环 */ path = BABA(root); ShowPath(path, root.matrix);return 0;/* 算法主搜索函数，Branch-And-Bound Algorithm Search* root
5、 是当前的根结点，已归约，数据完善*/PATH BABA(NODE root) int i; static int minDist = INFINITY; static PATH minPath; EDGE selectedEdge; NODE *left, *right; puts(Current Root:n-); ShowMatrix(root.matrix); printf(Root Bound:%dn, root.bound); /* 如果当前矩阵大小为2，说明还有两条边没有选，而这两条边必定只能有一种组合， * 才能构成整体回路，所以事实上所有路线已经确定。 */ if (Matr
6、ixSize(root.matrix, root.path) = 2) if (root.bound bound = root.bound; /* 继承父结点的下界 */ left-matrix = LeftNode(root.matrix, selectedEdge); /* 删掉分枝边 */ left-path = root.path; /* 继承父结点的路径，没有增加新边 */ left-left = NULL; left-right = NULL; right-bound = root.bound; right-matrix = RightNode(root.matrix, selec
7、tedEdge, root.path);/* 删除行列和回路边 */ right-path = AddEdge(selectedEdge, root.path); /* 加入所选边 */ right-left = NULL; right-right = NULL; /* 归约左右分枝结点 */ left-bound += Simplify(&left-matrix); right-bound += Simplify(&right-matrix); /* 链接到根 */ root.left = left; root.right = right; /* 显示到监视器 */ puts(Right B
8、ranch:n-); ShowMatrix(right-matrix); puts(Left Branch:n-); ShowMatrix(left-matrix); /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */ if (right-bound bound); printf(This branch is dead.n); /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */ if (left-bound bound); printf(This branch is dead.n); printf(The best answer now is %dn, minDist); retu
9、rn (minPath);/* 修补路径 */PATH MendPath(PATH path, MATRIX c) int row, col; EDGE edge; int n = c.citiesNumber; for (row = 0; row n; row+) edge.head = row; for (col = 0; col citiesNumber; h = 0; /* 行归约 */ for (row = 0; row n; row+) /* 找出本行最小的元素 */ min_dist = INFINITY; for (col = 0; col distancerowcol dis
10、tancerowcol; /* 如果本行元素都是无穷，说明本行已经被删除 */ if (min_dist = INFINITY) continue; /* 本行每元素减去最小元素 */ for (col = 0; col distancerowcol != INFINITY) c-distancerowcol -= min_dist; /* 计算归约常数 */ h += min_dist; /* 列归约 */ for (col = 0; col n; col+) /* 找出本列最小的元素 */ min_dist = INFINITY; for (row = 0; row distancerow
11、col distancerowcol; /* 如果本列元素都是无穷，说明本列已经被删除 */ if (min_dist = INFINITY) continue; /* 本列元素减去最小元素 */ for (row = 0; row distancerowcol != INFINITY) c-distancerowcol -= min_dist; /* 计算归约常数 */ h += min_dist; return (h);/* 搜索所有花费为零的边中最合适的，使左枝下界更大 */EDGE SelectBestEdge(MATRIX c) int row, col; int n = c.cit
12、iesNumber; int maxD; EDGE best, edge; /* 所用函数声明 */ int D(MATRIX, EDGE); maxD = 0; for (row = 0; row n; row+) for (col = 0; col n; col+) edge.head = row; edge.tail = col; if (!c.distancerowcol & maxD D(c, edge) maxD = D(c, edge); best = edge; return (best);/* 计算如果选 edge 作为分枝边，左枝（不含 edge）下界的增量 */int D
13、(MATRIX c, EDGE edge) int row, col, dRow, dCol; int n = c.citiesNumber; dRow = INFINITY; for (col = 0; col n; col+) if (dRow c.distanceedge.headcol & col != edge.tail) dRow = c.distanceedge.headcol; dCol = INFINITY; for (row = 0; row n; row+) if (dCol c.distancerowedge.tail & row != edge.head) dCol
14、= c.distancerowedge.tail; return (dRow + dCol);/* 删掉所选分枝边 */MATRIX LeftNode(MATRIX c, EDGE edge) c.distanceedge.headedge.tail = INFINITY; return c;/* 删除行列和回路边后的矩阵 */MATRIX RightNode(MATRIX c, EDGE edge, PATH path) int row, col; int n = c.citiesNumber; EDGE loopEdge; /* 声明所需要的求回路边函数 */ EDGE LoopEdge(
15、PATH, EDGE); for (col = 0; col n; col+) c.distanceedge.headcol = INFINITY; for (row = 0; row n; row+) c.distancerowedge.tail = INFINITY; loopEdge = LoopEdge(path, edge); c.distanceloopEdge.headloopEdge.tail = INFINITY; return (c);/* 计算回路边的函数* 除了加入的新边， 当前结点路线集合中还可能包含一些已经选定的边， 这些边构成一条或* 几条路径， 为了不构成回路，
16、 必须使其中包含新边的路径头尾不能相连，本函数返回这个* 头尾相连的边，以便把这个回路边的长度设成无穷。*/EDGE LoopEdge(PATH path, EDGE edge) int i, j; EDGE loopEdge; /* 最小的回路边 */ loopEdge.head = edge.tail; loopEdge.tail = edge.head; /* 寻找回路边的头端点，即包含新边的路径的尾端点 */ for (i = 0; i path.edgesNumber; i+) for (j = 0; j path.edgesNumber; j+) if (loopEdge.head = path.edgej.head) /* 扩大回路边 */ loopEdge.head = path.edgej.tail; break; /* 寻找回路边的尾端点，即包含新边的路径的头端点 */ for (i = 0; i path.edgesNumber; i+) for (j = 0; j path.edgesNumber; j+) if (loopEdge.tail = path.edgej.tail) /* 扩大回路边 */ loopEdge.tail = path.edgej.head;
