?? a.c
字號:
/*
* File: tsp.c
* Description: 求解貨郎擔問題的分枝限界算法
* Branch-and-bound algorithm to solve
* the travelling salesman problem.
* Created: 2001/11/29
* Author: Justin Hou [mailto:justin_hou@hotmail.com]
* C.S.Department of Tongji University
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TRUE (1)
#define FALSE (0)
#define MAX_CITIES (10)
#define INFINITY (999)
#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;
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.bound += Simplify(&root.matrix);
/* 進入搜索循環 */
path = BABA(root);
ShowPath(path, root.matrix);
return 0;
}
/*
* 算法主搜索函數，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:%d\n", 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);
}
}
/* 根據左下界盡量大的原則選分枝邊 */
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");
}
/* 如果右結點下界小于當前最佳答案，繼續分枝搜索 */
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 %d\n", 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 (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 (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);
}
/* 搜索所有花費為零的邊中最合適的，使左枝下界更大 */
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;
}
}
}
return (best);
}
/* 計算如果選 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];
}
}
dCol = INFINITY;
for (row = 0; row < n; row++) {
if (dCol < c.distance[row][edge.tail] && row != edge.head) {
dCol = c.distance[row][edge.tail];
}
}
return (dRow + dCol);
}
/* 刪掉所選分枝邊 */
MATRIX LeftNode(MATRIX c, EDGE edge)
{
c.distance[edge.head][edge.tail] = INFINITY;
return c;
}
/* 刪除行列和回路邊后的矩陣 */
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);
}
/* 計算回路邊的函數
* 除了加入的新邊， 當前結點路線集合中還可能包含一些已經選定的邊， 這些邊構成一條或
* 幾條路徑， 為了不構成回路， 必須使其中包含新邊的路徑頭尾不能相連，本函數返回這個
* 頭尾相連的邊，以便把這個回路邊的長度設成無窮。
*/
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;
}
}
}
/* 尋找回路邊的尾端點，即包含新邊的路徑的頭端點 */
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;
}
}
}
return (loopEdge);
}
/* 將新邊加入到路徑中 */
PATH AddEdge(EDGE edge, PATH path)
{
path.edge[path.edgesNumber++] = edge;
return path;
}
/* 計算花費矩陣當前階數 */
int MatrixSize(MATRIX c, PATH path)
{
return (c.citiesNumber - path.edgesNumber);
}
/* 顯示路徑 */
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); */
}
/* 顯示花費矩陣 */
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(" -");
}
}
putchar('\n');
}
getch();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -