[アルゴリズム] データ構造における貨郎担パス問題の一般的な解法、境界パス問題は、高度なアルゴリズムデータ構造を学んだ友人たちには「貨郎担問題」が非常に古典的なグラフアルゴリズムの問題であることは確かです。貨郎担問題は、主にバックトラッキング、貪欲法、動的計画法の 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;
/* スタック呼び出し */
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*/
/*
* アルゴリズムの主検索関数、分岐限定アルゴリズム検索
* 入力：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 である場合、選択されていない 2 つの辺があり、これらの辺は必ず 1 つの組み合わせしか持たないため、全体のループを構成することができるので、実際にはすべてのルートが確定しています。 */
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*/
/* 回路辺を計算する関数
* 新しい辺を追加する以外に、現在のノードのルート集合にはすでに選定された辺が含まれている可能性があり、これらの辺は 1 つまたは複数のパスを構成します。回路を構成しないためには、新しい辺を含むパスの頭と尾が接続されないようにする必要があります。この関数は、回路辺の長さを無限に設定するために、この頭と尾が接続されている辺を返します。
*/
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*/