货郎担分枝限界算法图形.rar_Branch and bound_分枝_分枝限界_货郎担_货郎担问题

/* * File: tsp.c * Description: 求解货郎担问题的分枝限界算法图形演示 * Branch-and-bound algorithm to solve the * travelling salesman problem. CG demo. * Use: tcc tsp graphics.lib * Created: 2001/11/29 - 2001/12/01 * Author: Justin Hou [mailto:justin_hou@hotmail.com] */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <graphics.h> #define MAX_CITIES 15 /* 城市的数目 */ #define INFINITY 9999 /* 表示无穷大 */ #define I INFINITY /* 表示无穷大 */ typedef struct _POINT { /* 定义点的结构 */ int x; int y; } POINT; typedef struct _EDGE { /* 定义边的结构 */ int head; int tail; } EDGE; typedef struct _PATH { /* 定义路径结构 */ EDGE edge[MAX_CITIES]; int edgesNumber; } PATH; typedef struct _MATRIX { /* 定义花费矩阵结构 */ int distance[MAX_CITIES][MAX_CITIES]; int citiesNumber; } MATRIX; typedef struct _NODE { /* 定义树结点 */ int bound; /* 结点的花费下界 */ MATRIX matrix; /* 当前花费矩阵 */ PATH path; /* 已经选定的边 */ } NODE; int minDist = INFINITY; int GraphDriver; int GraphMode; int ErrorCode; POINT city[MAX_CITIES] = { {459, 333}, {345, 234}, {362, 245}, {332, 183}, {323, 343}, {630, 345}, {154, 263}, {213, 112}, {432, 254}, {534, 223}, {334, 333}, {432, 234}, { 23, 442}, {600, 400}, {500, 300} }; int Simplify(MATRIX *); /* 归约矩阵并返回归约常数 */ int MatrixSize(MATRIX, PATH); /* 计算矩阵阶数 */ EDGE SelectBestEdge(MATRIX); /* 返回最合适的分枝边 */ MATRIX InitMatrix(void); /* 初始化费用矩阵数据 */ MATRIX LeftNode(MATRIX, EDGE); /* 计算左枝结点费用矩阵 */ MATRIX RightNode(MATRIX, EDGE, PATH); /* 计算右枝结点费用矩阵 */ PATH AddEdge(EDGE, PATH); /* 将边添加到路径数组中 */ PATH BABA(NODE *); /* 分枝回溯函数 B-and-B Ar. */ PATH MendPath(PATH, MATRIX); /* 修补没有完成的路径 */ void ShowMatrix(MATRIX); /* 文本显示费用矩阵 调试用 */ void ShowPath(PATH); /* 文本显示路径 */ void DrawPath(PATH); /* 图形显示路径 */ void main() { PATH path; NODE root; GraphDriver = DETECT; initgraph( &GraphDriver, &GraphMode, "" ); ErrorCode = graphresult(); if( ErrorCode != grOk ) { printf(" Graphics System Error: %s\n", grapherrormsg(ErrorCode)); exit(1); } /* 初始化数据，归约，建立根结点 */ root.matrix = InitMatrix(); root.bound = Simplify(&(root.matrix)); (root.path).edgesNumber = 0; /* 进入搜索循环，最终返回最佳路线 */ path = BABA(&root); /* 显示结果 */ DrawPath(path); ShowPath(path); printf("\nminDist:%d\n", minDist); getch(); closegraph(); } /* 初始化数据 */ MATRIX InitMatrix() { int row, col, n; double dx, dy; MATRIX c; n = MAX_CITIES; /* 有待完善数据读取方式 */ c.citiesNumber = n; for (row = 0; row < n; row++) { putpixel(city[row].x, city[row].y, 5); for (col = 0; col < n; col++) { dx = (double)(city[row].x - city[col].x); dy = (double)(city[row].y - city[col].y); /* 求两点间距离 */ c.distance[row][col] = (int)sqrt(dx * dx + dy * dy); if (row == col) c.distance[row][col] = INFINITY; } } return c; } /* * 算法主搜索函数，Branch-And-Bound Algorithm Search * root 是当前的根结点，已归约，数据完善 */ PATH BABA(NODE* root) { static PATH minPath; EDGE selectedEdge; NODE *left, *right; /* 如果当前矩阵大小为2，说明还有两条边没有选，而这两条边必定只能有一 * 种组合，才能构成整体回路，所以事实上所有路线已经确定。 */ if (MatrixSize(root->matrix, root->path) == 2) { if (root->bound < minDist) { minDist = root->bound; minPath = MendPath(root->path, root->matrix); free(root); return (minPath); } } /* 根据左下界尽量大的原则选分枝边 */ setcolor(7); selectedEdge = SelectBestEdge(root->matrix); line(city[selectedEdge.head].x, city[selectedEdge.head].y, city[selectedEdge.tail].x, city[selectedEdge.tail].y); putpixel(city[selectedEdge.head].x, city[selectedEdge.head].y, MAGENTA); putpixel(city[selectedEdge.tail].x, city[selectedEdge.tail].y, MAGENTA); /* * 建立左右分枝结点 */ right = (NODE *)malloc(sizeof(NODE)); if (right == NULL) { fprintf(stderr,"Error malloc branch.\n"); exit(-1); } /* 使左枝结点站局原根结点位置，节省空间 */ left = root; /* 初始化左右分枝结点 */ right->matrix = RightNode(root->matrix, selectedEdge, root->path); right->bound = root->bound + Simplify(&(right->matrix)); right->path = AddEdge(selectedEdge, root->path); left->matrix = LeftNode(left->matrix, selectedEdge); left->bound = left->bound + Simplify(&(left->matrix)); /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */ if (right->bound < minDist) { BABA(right); } /* 否则删除这条不可能产生更佳路线的死枝 */ else { free(right); } setcolor(BLACK);; line(city[selectedEdge.head].x, city[selectedEdge.head].y, city[selectedEdge.tail].x, city[selectedEdge.tail].y); putpixel(city[selectedEdge.head].x, city[selectedEdge.head].y, MAGENTA); putpixel(city[selectedEdge.tail].x, city[selectedEdge.tail].y, MAGENTA); /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */ if (left->bound < minDist) { BABA(left); } /* * 如果不是最初根结点才删除，避免'Null pointer assignment'问题 * ‘Null pointer assingnment'问题指如果手动删除主函数里面的数据 * 当main()执行完毕后释放空间时找不到数据的指针。 */ else if ((left->path).edgesNumber != 0){ free(left); } gotoxy(1, 1); printf("Current minDist: %d ", minDist); return (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 < n; col++) { edge.tail = col; if (c.distance[row][col] == 0) { path = AddEdge(edge, path); } } } return path; } /* 归约费用矩阵，返回费用矩阵的归约常数 */ int Simplify(MATRIX* c) { int row, col, min_dist, h; int n = c->citiesNumber; h = 0; /* 行归约 */ for