banner
李大仁博客

李大仁博客

天地虽大,但有一念向善,心存良知,虽凡夫俗子,皆可为圣贤。

[算法]数据结构中关于货郎担路径问题的常用解法,边界路径问题

[算法] 数据结构中关于货郎担路径问题的常用解法,边界路径问题相信诸位学习过高级算法数据结构的朋友肯定是知道 “货郎担问题” 是很经典的图算法问题货郎担问题可以总结出 4 种不同的解法,主要有回溯、贪心、动态规划以下提供的算法是使用的动态规划方法,结合边界路径问题提出的算法 C 语言实现,调试 TC 平台,动规算法

代码:

/* 货郎担路径问题 边界路径,贪心算法
* author YCTC CG
* code 12 10
* last modify 12 13
*/
#include #include #include #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*/

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。