李大仁博客

/* 货郎担路径问题 边界路径，贪心算法
* author YCTC CG
* code 12 10
* last modify 12 13
*/
#include <stdio.H>
#include <stdlib.H>
#include <math.H>
#define TRUE 1
#define FALSE 0
#define MAX_CITIES 10
#define INFINITY  9999
#define I INFINITY
 
typedef int bool;
/* 定义边结构 */
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;  /* 已经选定的边 */
    struct _NODE* left; /* 左枝 */
    struct _NODE* right;    /* 右枝 */
} NODE;
/*stack called*/
int Simplify(MATRIX*);
EDGE 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}, /* 自定义花费矩阵 */
          {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*/
    /* 归约，建立根结点 */
    clrscr();
    root.bound += Simplify(&root.matrix);
    /* 进入搜索循环 */
    path = BABA(root);
    ShowPath(path, root.matrix);
return 0;
}/*main*/
/*
 * 算法主搜索函数，Branch-And-Bound Algorithm Search
 * 输入：root 是当前的根结点
 */
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 (MatrixSize(root.matrix, root.path) == 2) {
        if (root.bound < minDist) {
            minDist = root.bound;
            minPath = MendPath(root.path, root.matrix);
            getch();
            return (minPath);
        }/*if*/
    }/*if*/
    /* 根据左下界尽量大的原则选分枝边 */
    selectedEdge = SelectBestEdge(root.matrix);
    printf("Selected Edge:(%d, %d)n", selectedEdge.head + 1, selectedEdge.tail + 1);
    /* 建立左右分枝结点 */
    left = (NODE *)malloc(sizeof(NODE));
    right = (NODE *)malloc(sizeof(NODE));
    if (left == NULL || right == NULL) {
        fprintf(stderr,"Error malloc.n");
        exit(-1);
    }
    /* 初始化左右分枝结点 */
    left->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, selectedEdge, 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 Branch:n------------");
    ShowMatrix(right->matrix);
    puts("Left Branch:n-----------");
    ShowMatrix(left->matrix);
    /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */
    if (right->bound < minDist) {
        BABA(*right);
    }
    /* 否则不搜索，因为这条枝已经不可能产生更佳路线 */
    else {
        printf("Current minDist is %d, ", minDist);
        printf("Right Branch's Bound(= %d).n", right->bound);
        printf("This branch is dead.n");
    }/*else*/
 
    /* 如果右结点下界小于当前最佳答案，继续分枝搜索 */
    if (left->bound < minDist) {
        BABA(*left);
    }
    /* 否则不搜索，因为这条枝已经不可能产生更佳路线 */
    else {
        printf("Current minDist is %d, ", minDist);
        printf("Left Branch's Bound(= %d).n", left->bound);
        printf("This branch is dead.n");
    }
 
    printf("The best answer now is %dn", minDist);
    return (minPath);
}/*BABA*/
/* mendpath修补路径
*输入 PATH path  路径
MATRIX C 矩阵
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 (row = 0; row < n; row++) {
        /* 找出本行最小的元素 */
        min_dist = INFINITY;
        for (col = 0; col < n; col++) {
            if (c->distance[row][col] < min_dist) {
                min_dist = c->distance[row][col];
            }
        }
        /* 如果本行元素都是无穷，说明本行已经被删除 */
        if (min_dist == INFINITY) continue;
        /* 本行每元素减去最小元素 */
        for (col = 0; col < n; col++) {
            if (c->distance[row][col] != INFINITY) {
                c->distance[row][col] -= min_dist;
            }
        }
        /* 计算归约常数 */
        h += min_dist;
    }/*for*/
    /* 列归约 */
    for (col = 0; col < n; col++) {
        /* 找出本列最小的元素 */
        min_dist = INFINITY;
        for (row = 0; row < n; row++) {
            if (c->distance[row][col] < min_dist) {
                min_dist = c->distance[row][col];
            }
        }
        /* 如果本列元素都是无穷，说明本列已经被删除 */
        if (min_dist == INFINITY) continue;
        /* 本列元素减去最小元素 */
        for (row = 0; row < n; row++) {
            if (c->distance[row][col] != INFINITY) {
                c->distance[row][col] -= min_dist;
            }
        }
        /* 计算归约常数 */
        h += min_dist;
    }
    return (h);
}/*mendpath*/
 
 
 
 
/* selectbestedge花费为零的边中最合适的，使左枝下界更大
*输入MATRIX c
*/
EDGE SelectBestEdge(MATRIX c)
{
    int row, col;
    int n = c.citiesNumber;
    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.distance[row][col] && maxD < D(c, edge)) {
                maxD = D(c, edge);
                best = edge;
            } /*if*/
        }/*for*/
    }/*for*/
    return (best);
}/*selectbestedge*/
/* 计算如果选 edge 作为分枝边，左枝（不含 edge）下界的增量
*输入 MATRIX c 路径矩阵 EDGE edge 边 */
int D(MATRIX c, EDGE edge)
{
    int row, col, dRow, dCol;
    int n = c.citiesNumber;
    dRow = INFINITY;
    for (col = 0; col < n; col++) {
        if (dRow < c.distance[edge.head][col] && col != edge.tail) {
            dRow = c.distance[edge.head][col];
        }/*if*/
    }/*for*/
    dCol = INFINITY;
    for (row = 0; row < n; row++) {
        if (dCol < c.distance[row][edge.tail] && row != edge.head) {
            dCol = c.distance[row][edge.tail];
        }
    }/*for*/
    return (dRow + dCol);
}/*D*/
 /* leftNode删掉所选分枝边
*输入 MATRIX c 图矩阵
*  EDGE edge要删除的边节点连接边*/
MATRIX LeftNode(MATRIX c, EDGE edge)
{
    c.distance[edge.head][edge.tail] = INFINITY;
    return c;
}/*leftnode*/
/*rightnode 删除行列和回路边后的矩阵
* 输入 MATRIX c 图矩阵
*  EDGE edge 边
* PATH path 路径
*/
MATRIX  RightNode(MATRIX c, EDGE edge, PATH path)
{
    int row, col;
    int n = c.citiesNumber;
    EDGE loopEdge;
 
    /* 声明所需要的求回路边函数 */
    EDGE LoopEdge(PATH, EDGE);
 
    for (col = 0; col < n; col++)
        c.distance[edge.head][col] = INFINITY;
    for (row = 0; row < n; row++)
        c.distance[row][edge.tail] = INFINITY;
 
    loopEdge = LoopEdge(path, edge);
    c.distance[loopEdge.head][loopEdge.tail] = INFINITY;
 
    return (c);
} /*right node*/
 
/* 计算回路边的函数
 * 除了加入的新边， 当前结点路线集合中还可能包含一些已经选定的边， 这些边构成一条或
 * 几条路径， 为了不构成回路， 必须使其中包含新边的路径头尾不能相连，本函数返回这个
 * 头尾相连的边，以便把这个回路边的长度设成无穷。
 */
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.edge[j].head) {
                /* 扩大回路边 */
                loopEdge.head = path.edge[j].tail;
                break;
            }/*if*/
        }/*for*/
    } /*for*/
    /* 寻找回路边的尾端点，即包含新边的路径的头端点 */
    for (i = 0; i < path.edgesNumber; i++) {
        for (j = 0; j < path.edgesNumber; j++) {
            if (loopEdge.tail == path.edge[j].tail) {
                /* 扩大回路边 */
                loopEdge.tail = path.edge[j].head;
                break;
            }/*if*/
        }/*for*/
    } /*for*/
 
    return (loopEdge);
}/*loopedge*/
/* 将新边加入到路径中
*输入 EDGE edge 要增加的边
*    PATH path 所求路径*/
PATH AddEdge(EDGE edge, PATH path)
{
    path.edge[path.edgesNumber++] = edge;
    return path;
}/*addedge*/
/* 计算花费矩阵当前阶数 */
int MatrixSize(MATRIX c, PATH path)
{
    return (c.citiesNumber - path.edgesNumber);
}/*matrix size*/
 
 
 
/* 显示路径
* 输入 PATH 输出的路径
* MATRIX c 路线矩阵
**/
void ShowPath(PATH path, MATRIX c)
{
    int i, dist;
    EDGE edge;
    int n = path.edgesNumber;
 
    dist = 0;
    printf("nThe path is: ");
    for (i = 0; i < n; i++) {
        edge = path.edge[i];
        printf("(%d, %d) ", edge.head + 1, edge.tail + 1);
        dist += c.distance[edge.head][edge.tail];
    }
    /* printf("[Total Cost: %d]n", dist); */
}/*showpath*/
/* 显示花费矩阵 */
void ShowMatrix(MATRIX c)
{
    int row, col;
    int n =  c.citiesNumber;
     for (row = 0; row < n; row++) {
        for (col = 0; col < n; col++) {
            if (c.distance[row][col] != INFINITY) {
                printf("%3d", c.distance[row][col]);
            }
            else {
                printf("  -");
            }
        }/*for*/
        putchar('n');
    }/*for*/
    getch();
}/*showMatrix*/