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

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
/* 货郎担路径问题 边界路径,贪心算法
* 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*/
  1. December 18th, 2008 at 09:47 | #1
  2. December 18th, 2008 at 12:02 | #2

    呵呵,可能是自动评论

  3. December 18th, 2008 at 14:02 | #3

    一楼的评论被我给删了~~~

  4. December 18th, 2008 at 14:15 | #4

    删除错了,垃圾评论已经被我删除了

  5. December 18th, 2008 at 14:32 | #5

    没有错啊~~~你搞错了~~~

  6. May 12th, 2009 at 00:06 | #6

    OK

  1. No trackbacks yet.