[算法]数据结构中关于货郎担路径问题的常用解法，边界路径问题相信诸位学习过高级算法数据结构的朋友肯定是知道“货郎担问题”是很经典的图算法问题货郎担问题可以总结出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 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 bound);
printf("This branch is dead.n");
}/*else*/
/* 如果右结点下界小于当前最佳答案，继续分枝搜索 */
if (left->bound 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 citiesNumber;
h = 0;
/* 行归约 */
for (row = 0; row distance[row][col] distance[row][col];
}
}
/* 如果本行元素都是无穷，说明本行已经被删除 */
if (min_dist == INFINITY) continue;
/* 本行每元素减去最小元素 */
for (col = 0; col distance[row][col] != INFINITY) {
c->distance[row][col] -= min_dist;
}
}
/* 计算归约常数 */
h += min_dist;
}/*for*/
/* 列归约 */
for (col = 0; col distance[row][col] distance[row][col];
}
}
/* 如果本列元素都是无穷，说明本列已经被删除 */
if (min_dist == INFINITY) continue;
/* 本列元素减去最小元素 */
for (row = 0; row 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