C言語で貪欲法を実装について教えてほしいです

Question

実現したいこと

C言語でGreedy法を修正してほしいです。以下のような実行結果が出力されるようにしたいです。

以下は理想の実行結果です。

1-3: 165.4
0-3: 185.3
0-1: 449.1
1-4: 617.7
0-2: 750.4
2-3: 855.6
3-4: 871.2
1-2: 1015.1
0-4: 1055.9
2-4: 1592.3
//1-3を追加後の次数
点0の次数:0
点1の次数:1
点2の次数:0
点3の次数:1
点4の次数:0

//0-3を追加後の次数
点0の次数:1
点1の次数:1
点2の次数:0
点3の次数:2
点4の次数:0

//0-1を追加後の次数
点0の次数:1
点1の次数:1
点2の次数:0
点3の次数:2
点4の次数:0

//1-4を追加後の次数
点0の次数:1
点1の次数:2
点2の次数:0
点3の次数:2
点4の次数:1

//0-2を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//2-3を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//3-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//1-2を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//0-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//1-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:2
点3の次数:2
点4の次数:2

Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 1
Total Distance: 3311.1

前提

Greedy法でグラフの最短経路を見つけるプログラムを書いています。

アルゴリズムは、
①すべての辺の重みを昇順に並べる
②からの閉路からはじめ、辺の重みが小さい順に調べ、その辺が以下の2つの条件を満たすならば閉路を付け加える。
条件１．点の次数が3をこえない
条件２．すべての点を回らないような閉路はつくらない
です。

条件1まではできたのですが、条件2の閉路を見つけるのに苦労しています。もしよろしければ、以下のコードをもとに修正案を具体的に下さると助かります。もし、不明点がありましたら、コメント下さい。よろしくお願いします。

以下のプログラムのdfs関数やvalid関数がおかしいのは分かってはいるのですが、何度修正してもできませんでした。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CITIES 20 //最大都市数
#define INF 10000

int path[MAX_CITIES]; //現在の経路
int min_path[MAX_CITIES]; //最短距離の経路
int **circuit; //閉路
double dist[100]; //すべての辺の距離
int n; //点の総数
int m; //辺の数
double min_dist = INF; //最短距離
double total_dist = 0;
int visited[MAX_CITIES]; //訪問済みの点
int count = 0;

typedef struct {
  int u; //点1
  int v; //点2
  double dist; //点間の距離
} Adjacent;

// 比較関数
int compare(const void *a, const void *b) {
  if (((Adjacent *)a)->dist > ((Adjacent *)b)->dist) {
    return 1; //昇順
  } else if (((Adjacent *)a)->dist < ((Adjacent *)b)->dist) {
    return -1;
  } else {
    return 0;
  }
}

//すべて点の次数を計算する関数
int *degree(void) {
  int i, j;
  int *degree = (int *)malloc(sizeof(int) * n); //各点の次数

  // すべての点の次数を求める
  for (i = 0; i < n; i++) {
    degree[i] = 0;
    for (j = 0; j < n; j++) {
      degree[i] += circuit[i][j];
    }
    printf("点%dの次数:%d\n", i, degree[i]);
  }
	printf("\n");

  return degree;
}

//dfs(今いるノード, 一つ前にいたノード)
int dfs(const int current, const int before) {
  visited[current] = 1;
  for (int i = 0; i < n; i++) {
    if (circuit[current][i] == before) {
			printf("operate!1\n");
      // 前のノードに戻る場合
      continue;
    }
		
    if (visited[i]) {
      // 次に行くノードが過去に通ったことがある場合
			printf("operate!2\n");
      return 1;
    }
		
		printf("current:%d, i:%d\n", current, i);
    dfs(i, current);
		
  }
  return 0;
}

//閉路が条件を満たしているかを確かめる関数
int valid(int start) {
  int i;
  int *deg;

  //条件1:都市の次数が3を越えない
  deg = degree();
  for (i = 0; i < n; i++) {
    if (deg[i] > 2) {
      return 0; // 条件1を満たさない場合は0を返す
    }
  }

  // 条件2: すべての都市を回る閉路があるかチェック
  for (i = 0; i < n; i++) {
    visited[i] = 0; // 訪問済みのフラグをリセット
  }
  if (dfs(start, -1)) {
    return 1; // 条件2を満たす閉路が存在する場合は1を返す
  }
	
	return 0;
}

// greedy法
void greedy(Adjacent *adjacent) {
  int i;
  int n1, n2;
  int path_idx = 0; // 経路のインデックスを初期化

  for (i = 0; i < m; i++) {
    n1 = adjacent[i].u;
    n2 = adjacent[i].v;
    circuit[n1][n2] = 1;
    circuit[n2][n1] = 1;

    if (valid(n1) == 0) {
      // 条件を満たさない閉路を作った場合は辺を削除
      circuit[n1][n2] = 0;
      circuit[n2][n1] = 0;
    } else {
      total_dist += adjacent[i].dist; // 距離を加算
      path[path_idx++] = n1; // 経路に点n1を追加
    }
  }

  // 最後に始点を追加して閉路を完成させる
  path[path_idx] = 0;
  total_dist += adjacent[0].dist; // 始点から始点への距離を加算
}

int main(void) {
  FILE *fp;
  int i, j;
  Adjacent adjacent[100];

  printf("operate!\n");

  if ((fp = fopen("network.txt", "r")) == NULL) {
    fprintf(stderr, "File open error.\n");
    exit(1);
  }

  // 点の数を取得
  fscanf(fp, "%d", &n);

  // 閉路を格納する2次元ポインタの隣接行列を作る
  circuit = (int **)malloc(sizeof(int *) * MAX_CITIES);
  for (i = 0; i < n; i++) {
    circuit[i] = malloc(sizeof(int) * MAX_CITIES);
    for (j = 0; j < n; j++) {
      circuit[i][j] = 0;
    }
  }

  // 隣接する辺を生成
  while (fscanf(fp, "%d %d %lf", &adjacent[m].u, &adjacent[m].v, &adjacent[m].dist) != EOF) {
    m++;
  }

  fclose(fp);

  // アークを長さの昇順でソートする
  qsort(adjacent, m, sizeof(Adjacent), compare);

  for (i = 0; i < m; i++) {
    printf("%d-%d: %.1lf\n", adjacent[i].u, adjacent[i].v, adjacent[i].dist);
  }

  greedy(adjacent);

  // 最終的な経路を表示
  printf("Final Path: ");
  for (i = 0; i < n; i++) {
    printf("%d", path[i]);
    if (i < n - 1) {
      printf(" -> ");
    }
  }
  printf("\n");

  printf("Total Distance: %.1lf\n", total_dist);

  return 0;
}

実行結果です。点0、点1、点3で0のときに閉路になっているので、greedy関数内の辺を追加を取り消すプログラムが動かずに、そのごもそのまま計算されてしまいます。

operate!
1-3: 165.4
0-3: 185.3
0-1: 449.1
1-4: 617.7
0-2: 750.4
2-3: 855.6
3-4: 871.2
1-2: 1015.1
0-4: 1055.9
2-4: 1592.3
点0の次数:0
点1の次数:1
点2の次数:0
点3の次数:1
点4の次数:0

current:1, i:0
operate!2
operate!2
点0の次数:1
点1の次数:1
点2の次数:0
点3の次数:2
点4の次数:0

operate!2
点0の次数:2
点1の次数:2
点2の次数:0
点3の次数:2
点4の次数:0

operate!2
点0の次数:2
点1の次数:3
点2の次数:0
点3の次数:2
点4の次数:1

点0の次数:3
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:0

点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:3
点4の次数:0

点0の次数:2
点1の次数:2
点2の次数:0
点3の次数:3
点4の次数:1

点0の次数:2
点1の次数:3
点2の次数:1
点3の次数:2
点4の次数:0

点0の次数:3
点1の次数:2
点2の次数:0
点3の次数:2
点4の次数:1

点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

current:2, i:0
operate!2
current:2, i:1
operate!2
operate!2
Final Path: 1 -> 0 -> 0 -> 2 -> 0
Total Distance: 2557.5

network.txt

5
0 1 449.1
0 2 750.4
0 3 185.3
0 4 1055.9
1 2 1015.1
1 3 165.4
1 4 617.7
2 3 855.6
2 4 1592.3
3 4 871.2

試したこと

一応自分なりに考えた閉路を求めるアルゴリズムは、
①追加する辺の両端の点を始点と終点し、あらかじめ訪問済みにする。
②始点から行き止まりまで探索し、最後の値を戻り値として返す。
③②と同様に終点から行き止まりまで探索し、最後の値を戻り値として返す。
④もし、始点からの戻り値と終点からの戻り値が一致すれば閉路があるとし、値が一致しなければ閉路はないする。

こんな感じのアルゴリズムを考えてみたのですが実装が上手くいかず困っていたので質問しました。

Comments

[jimbe]

もしプログラムが想定通りに動作した場合、実行結果は(動作中の全ての表示も含めて)どうなるはずなのでしょうか。

[t-xxx5]

コメントありがとうございます。以下の実行結果のようになるつもりです。

1-3: 165.4
0-3: 185.3
0-1: 449.1
1-4: 617.7
0-2: 750.4
2-3: 855.6
3-4: 871.2
1-2: 1015.1
0-4: 1055.9
2-4: 1592.3
//1-3を追加後の次数
点0の次数:0
点1の次数:1
点2の次数:0
点3の次数:1
点4の次数:0

//0-3を追加後の次数
点0の次数:1
点1の次数:1
点2の次数:0
点3の次数:2
点4の次数:0

//0-1を追加後の次数
点0の次数:1
点1の次数:1
点2の次数:0
点3の次数:2
点4の次数:0

//1-4を追加後の次数
点0の次数:1
点1の次数:2
点2の次数:0
点3の次数:2
点4の次数:1

//0-2を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//2-3を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//3-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//1-2を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//0-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:1
点3の次数:2
点4の次数:1

//1-4を追加後の次数
点0の次数:2
点1の次数:2
点2の次数:2
点3の次数:2
点4の次数:2

Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 0
Total Distance: 3311.1

[y_waiwai]

それを質問文に追記しましょう

[fana]

まず，そもそもとして「何を求める問題なのか？」っていうのを，もうちょっと馬鹿にもわかるように説明してほしいのですが．（「まともな知能をもった読み手であればこれで十分に伝わる想定である」みたいな場合であれば，お手数ですがそう明言していただければそれでもよいです）

> Greedy法でグラフの最短経路を見つけるプログラムを書いています

とのことですが，「最短経路」を得たいなら「どこから　どこまで」っていう話があるハズだと思うんですが，そこの話がどうなってるのかが全く見えないのです（データファイルには辺の重みの定義しか書かれていないように見えるし？）．

あるいは求めたいのは「全てのノードを通る閉路のうち重みの総和が最小のもの」なのか？　とも推測できる気がするのですが，それだと

> Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 0

という結果例と合わないように思うのでそれも違う様子と見えます．
（というのは，「閉路」とは「始点と終点が同じループな経路で，同じ場所は２度通らない」みたいなのなんじゃないかと．　…っていう私の認識が誤りなのか？と思ってちょろっとググってみたけどやはりそんな定義なんじゃないかと見えるし…？？）

[fana]

> Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 0

コレ，最後の '0' が誤記で，本当は '1' なんじゃないかな．それなら話としてわかる．

[8524ba23]

例題をみるかぎり、これは巡回セールスマン問題と同じものと考えてよいでしょうか？
（すべての点を一回だけ通る最短経路を求めたい）

[t-xxx5]

コメントありがとございます。巡回セールマン問題と同じと考えて大丈夫です。よろしくお願いします。

[t-xxx5]

最後の '0' は誤りで，本当は '1'です。ご指摘ありがとうございます。

[jimbe]

結果を比較すると 3 つ目の次数の表示("0-1を追加後の次数")が異なるようですが、その時の各処理内容・変数の変化が理想とどう違っているかは確認されましたでしょうか。

Answer 1

既存コードの問題点を指摘しておきます。

1. dfsが隣接リストを前提としたコードになっている
   circuitは隣接行列なので、隣接リストを前提としたdfsにそのまま渡しても、正常に動作しません。隣接行列を前提としたコードに書き換えましょう。
2. valid内で、閉路があったら 1 を、閉路が無かったら 0 を返している
   現状だと、dfsが 1 を返したら、つまり、閉路があったら 1 を返し、逆に閉路が無かったら 0 を返しています。「条件２．すべての点を回らないような閉路はつくらない」なので、0 を返すべきなのは「すべての点を回らない閉路」があった場合のみです。
3. greedy内で、見つかった辺の始点を順番に並べたものを経路として返している
   今回のテストデータだと、1-3, 0-3, 1-4, 0-2, 2-4の順番で辺が見つかるので、辺の始点を並べても 1->0->1->0->2 になってしまいます。0から改めて経路をたどるなどしてください。

これらの問題を修正したところ、正しい経路が表示されるようになりました。

あと、経路の正しさに直接は関係ありませんが、degreeやmain内でmallocを使って確保したメモリをfreeしていないのもNGです。

Answer 2

valid 関数は、最後に追加した辺を用いるかどうかを返します。
最後に追加した辺を用いるかどうかは、以下の点で判断出来ます。

1. 辺の数が全ての点を回るのに不足している場合：閉路が出来たら false, 出来なかったなら true
2. 辺の数が全ての点を回るのに必要な数に達した場合：完全な閉路が出来たら true, 出来なかったら false
3. 辺の数が多くなった場合：false

1 と 2 で閉路の扱いが逆ですので、判断もそのようにする必要があると思います。

閉路の判定は、(実際に辿ってみなくても)各点から出る辺の数によって判断出来るのではないでしょうか。
点から1本だけ辺が出ていれば、開いている部分があります。
点から3本以上辺が出ていれば、完全な閉路は出来なくなりますし、一部が閉路になった可能性があります。
全ての点から2本の辺が出ていれば、完全な閉路が出来たということでしょう。
これらの条件の組み合わせを考えれば判断出来るものと思います。
※ざっくり考えたものですので穴がある可能性があります。

valid 関数を check に名前を変えて、戻り値を DISCARD/CONTINUE/COMPLETE の 3 つとして状況を返すようにしました。

間違いを指摘頂きまして、結局最後に追加された辺から辿ることになりました。
間違ったコードのままよりは良いかなと・・・これが間違っていないとは言い切れませんが。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

//#define CHECK_TEST
#define CHECK_LOG

typedef struct {
  int u; //点1
  int v; //点2
  double dist; //点間の距離
} Adjacent;

int isConnected(Adjacent *a, int p) {
  return p == a->u || p == a->v;
}
int otherPoint(Adjacent *a, int p) {
  return p == a->u ? a->v : a->u;
}

typedef struct {
  int p, c;
} PC;

void setPc(PC *pc, int i, int p, int c) {
  pc[i].p = p;
  pc[i].c = c;
}
int countAndCrossCheck(PC *pc) {
  return ++pc->c > 2;
}

//size バイトのメモリを確保し、各バイトに value をセット
void *allocAndClear(size_t size, int value) {
  return memset(malloc(size), value, size);
}

//判定
#define DISCARD (-1) //(最期に追加した辺を)破棄
#define CONTINUE (0) //継続
#define COMPLETE (1) //完了

int check(int n, int c, Adjacent **roads) {
#ifdef CHECK_LOG
  printf("n=%d,c=%d\n", n, c);
  for(int i=0; i<c; i++) printf("%d-%d\n", roads[i]->u, roads[i]->v);
#endif //CHECK_LOG

  if(c > n) return DISCARD; //辺が多くなったなら破棄

  int hasCross = 0; //false
  int hasClosed = 0; //false

  //最期の辺(roads[c-1])の接続先を追う
  int *used = allocAndClear(sizeof(int) * (c-1), 0); //roads に index で対応するフラグ
  PC *q = allocAndClear(sizeof(PC) * n, 0); //点の探索キュー&探索履歴・接続カウント

  int wi = 0, ri = 0;
  setPc(q, wi++, roads[c-1]->u, 1); //最後に追加した辺の両端を追加
  setPc(q, wi++, roads[c-1]->v, 1);
  while(ri < wi) {
    PC *pc = &q[ri++];
    for(int i=0; i<c-1; i++) { //点 pc に繋がっている未使用辺を探し、 pc の逆側の点を (q に無ければ )q に追加
      if(used[i] || !isConnected(roads[i], pc->p)) continue;

      used[i] = 1; //true
      hasCross |= countAndCrossCheck(pc);
      int np = otherPoint(roads[i], pc->p); //p の逆側の点

      int found = 0; //false
      for(int j=0; j<wi; j++) {
        if(q[j].p == np) { //探索済みor探索予定の点に繋がる?
          found = 1; //true
          hasCross |= countAndCrossCheck(&q[j]);
        }
      }
      hasClosed |= found;
      if(!found) setPc(q, wi++, np, 1);
    }
  }

#ifdef CHECK_LOG
  printf("wi=%d\n", wi);
  for(int i=0; i<wi; i++) printf("p=%d,c=%d\n", q[i].p, q[i].c);
  printf("hasCross=%d, hasClosed=%d\n", hasCross, hasClosed);
  printf("\n");
#endif //CHECK_LOG

  free(used);
  free(q);

  if(hasCross || (hasClosed && c < n)) return DISCARD;
  if(hasClosed && c == n) return COMPLETE;
  return CONTINUE;
}

//greedy法
Adjacent **greedy(int n, int m, Adjacent *adjacent) {
  Adjacent **result = malloc(sizeof(Adjacent*) * n);
  for(int i=0, c=0; i<m; i++) {
    result[c++] = &adjacent[i];
    switch(check(n, c, result)) {
    case COMPLETE: return result;
    case DISCARD: c--;
    }
  }
  free(result);
  return NULL;
}

//表示
void print(int n, Adjacent **result) {
  printf("Final Path: ");
  double total = 0;
  int i = 0;
  int p = result[i]->u;
  printf("%d", p);
  for(int j=0, k; j<n; j++) {
    p = otherPoint(result[i], p);
    printf(" -> %d", p);
    total += result[i]->dist;
    for(k=i, i=0; i==k || !isConnected(result[i], p); i++); //次の i
  }
  printf("\n");
  printf("Total Distance: %.1lf\n", total);
}

int main(void) {
#ifdef CHECK_TEST
  Adjacent testdata1[] = { {0,1,100}, {2,3,110}, {3,4,120}, {2,4,130} };
  Adjacent *test1[] = { &testdata1[0], &testdata1[1], &testdata1[2], &testdata1[3] };
  assert(check(5, 4, test1) == DISCARD);

  Adjacent testdata2[4] = { {0,2,100}, {2,3,110}, {3,4,120}, {1,4,130} };
  Adjacent *test2[] = { &testdata2[0], &testdata2[1], &testdata2[2], &testdata2[3] };
  assert(check(5, 4, test2) == CONTINUE);
#else //TEST
  //ファイル読み込み・ソート等を省略
  int n = 5; //点の数
  int m = 10; //辺の数
  Adjacent adjacents[10] = {
      {1,3, 165.4},
      {0,3, 185.3},
      {0,1, 449.1},
      {1,4, 617.7},
      {0,2, 750.4},
      {2,3, 855.6},
      {3,4, 871.2},
      {1,2, 1015.1},
      {0,4, 1055.9},
      {2,4, 1592.3},
  };

  Adjacent **result = greedy(n, m, adjacents);
  if(result) {
    print(n, result); //最終的な経路を表示
    free(result);
  } else {
    printf("Failure\n");
  }
#endif //TEST
  return 0;
}

n=5,c=1
1-3
wi=2
p=1,c=1
p=3,c=1
hasCross=0, hasClosed=0

n=5,c=2
1-3
0-3
wi=3
p=0,c=1
p=3,c=2
p=1,c=1
hasCross=0, hasClosed=0

n=5,c=3
1-3
0-3
0-1
wi=3
p=0,c=2
p=1,c=2
p=3,c=2
hasCross=0, hasClosed=1

n=5,c=3
1-3
0-3
1-4
wi=4
p=1,c=2
p=4,c=1
p=3,c=2
p=0,c=1
hasCross=0, hasClosed=0

n=5,c=4
1-3
0-3
1-4
0-2
wi=5
p=0,c=2
p=2,c=1
p=3,c=2
p=1,c=2
p=4,c=1
hasCross=0, hasClosed=0

n=5,c=5
1-3
0-3
1-4
0-2
2-3
wi=5
p=2,c=2
p=3,c=3
p=0,c=2
p=1,c=2
p=4,c=1
hasCross=1, hasClosed=1

n=5,c=5
1-3
0-3
1-4
0-2
3-4
wi=5
p=3,c=3
p=4,c=2
p=1,c=2
p=0,c=2
p=2,c=1
hasCross=1, hasClosed=1

n=5,c=5
1-3
0-3
1-4
0-2
1-2
wi=5
p=1,c=3
p=2,c=2
p=3,c=2
p=4,c=1
p=0,c=2
hasCross=1, hasClosed=1

n=5,c=5
1-3
0-3
1-4
0-2
0-4
wi=5
p=0,c=3
p=4,c=2
p=3,c=2
p=2,c=1
p=1,c=2
hasCross=1, hasClosed=1

n=5,c=5
1-3
0-3
1-4
0-2
2-4
wi=5
p=2,c=2
p=4,c=2
p=0,c=2
p=1,c=2
p=3,c=2
hasCross=0, hasClosed=1

Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 1
Total Distance: 3311.1

Comments

[actorbug]

残念ながら、その閉路判定だと対応できない場合があります。
「点0,1から辺が1本、点2,3,4から辺が2本出ている」という同じ状況でも、
以下の1.だと閉路あり、2.だと閉路なしになります。
1. 0→1、2→3、3→4、2→4
2. 0→2、2→3、3→4、1→4

[jimbe]

ご指摘有難うございます。助かります。
考え直してみます。

Answer 3

「既存のコードを修正してくれ」という話への回答とはなりません が，
何らかの参考になるかもしれないので，「全てのノードを通る閉路のうち重みの総和が最小のもの」を求める問題なのだとして，私が解いてみた（つもりの）コードを示してみます．
（…とは言え，貪欲法である以上，本当に「最小」が見つかる保証はないわけですが）

• ファイルからデータを読むところと，辺のデータをソートするところは本題ではないので含めていません．（：ソート済みデータを定数として実装しています）
• 貪欲法の部分は再帰関数になっていますが，その処理中に使うデータ（NodeDeg[], EdgeUsed[]）は外部変数にしてあります（その方が読みやすいと思うので）．
• また，コードは C++ になっていますが，「C言語っぽく」書いたつもりですので，そのあたりは大丈夫かと．

#define N_NODE (5)	//ノードの個数
#define N_EDGE (10)	//辺の個数

//１辺のデータ
struct Edge
{
	//両端のノードの番号
	int Node1;
	int Node2;
	//コスト
	double Cost;
};

//辺のデータ（コストでソート済み）
const Edge Edges[N_EDGE] =
{
	{1,3, 165.4},
	{0,3, 185.3},
	{0,1, 449.1},
	{1,4, 617.7},
	{0,2, 750.4},
	{2,3, 855.6},
	{3,4, 871.2},
	{1,2, 1015.1},
	{0,4, 1055.9},
	{2,4, 1592.3}
};

//各ノードの次数
int NodeDeg[N_NODE] = {};	//初期値は全0
//各辺が閉路に採用されているか否かを示すフラグ
bool EdgeUsed[N_EDGE] = {};	//初期値は全false

//閉路が見つかったか否かの判定
bool ClosedPathFound()
{	//「全ノードの次数が2なら閉路」という判定
	for( int iNode=0; iNode<N_NODE; ++iNode )
	{
		if( NodeDeg[iNode] != 2 )return false;
	}
	return true;
}

//コレはただの作業関数．引数に応じた個数のスペースを表示するだけ
void Indent( int IndentLV ){	for( int i=0; i<IndentLV*2; ++i )putchar( ' ' );	}

//貪欲法の実装
bool Greedy( int IndentLV )	//この引数は単なる表示用：↑の関数 Indent() の引数として使うだけ
{
	//終了判定
	if( ClosedPathFound() )return true;

	//コストが小さい辺から順に採用してみる（＝貪欲法）
	for( int iTryEdge=0; iTryEdge<N_EDGE; ++iTryEdge )
	{
		if( EdgeUsed[iTryEdge] )continue;
		if( NodeDeg[ Edges[iTryEdge].Node1 ] >= 2 )continue;
		if( NodeDeg[ Edges[iTryEdge].Node2 ] >= 2 )continue;

		//とりえあず 辺Edges[iTryEdge] を採用して処理を進めてみる
		int Node1 = Edges[iTryEdge].Node1;
		int Node2 = Edges[iTryEdge].Node2;
		Indent(IndentLV);
		printf( "Try to adopt Edge %d - %d\n", Node1, Node2 );
		++NodeDeg[ Node1 ];
		++NodeDeg[ Node2 ];
		EdgeUsed[ iTryEdge ] = true;
		if( Greedy( IndentLV + 1 ) )return true;	//再帰．閉路が見つかった時点で処理は終了．

		//処理を進めてみた結果，ダメだったなら 辺Edges[iTryEdge] を非採用状態に戻す
		Indent(IndentLV);
		printf( "Reject Edge %d - %d\n", Node1, Node2 );
		--NodeDeg[ Node1 ];
		--NodeDeg[ Node2 ];
		EdgeUsed[ iTryEdge ] = false;
	}
	return false;
}

//main
int main()
{
	//探索実施
	//	成功したときの処理結果は配列 EdgeUsed[] であり，その要素値は，閉路を構成する辺だけが true になっている．
	if( !Greedy(0) )
	{	printf( "Failed!!\n" );	return 0;	}

	//結果のパスを求めて表示する
	//※ここはかなり雑（非効率）な処理になっている．
	int Path[ N_NODE+1 ];	//結果のパスをここに作る．要素はノード番号．
	double TotalCost = 0;	//総コスト
	{
		int iPath = 0;
		while( iPath < N_NODE )
		{
			for( int iEdge=0; iEdge<N_EDGE; ++iEdge )
			{
				if( !EdgeUsed[iEdge] )continue;

				int Node1 = Edges[iEdge].Node1;
				int Node2 = Edges[iEdge].Node2;
				if( iPath == 0 )
				{
					Path[ 0 ] = Node1;
					Path[ 1 ] = Node2;
					iPath = 1;
				}
				else
				{
					if( Node1 == Path[ iPath ] ){	Path[++iPath] = Node2;	}
					else if( Node2 == Path[ iPath ] ){	Path[++iPath] = Node1;	}
					else {	continue;	}
				}

				EdgeUsed[ iEdge ] = false;
				TotalCost += Edges[ iEdge ].Cost;
			}
		}
	}
	printf( "---Result---\n" );
	printf( "Path : " );
	printf( "%d", Path[0] );
	for( int i=1; i<N_NODE+1; ++i ){	printf( " -> %d", Path[i] );	}
	printf( "\nTotalCost = %f\n", TotalCost );
	return 0;
}

↑のコードを動作させた結果の表示：

Try to adopt Edge 1 - 3
  Try to adopt Edge 0 - 3
    Try to adopt Edge 0 - 1
      Try to adopt Edge 2 - 4
      Reject Edge 2 - 4
    Reject Edge 0 - 1
    Try to adopt Edge 1 - 4
      Try to adopt Edge 0 - 2
        Try to adopt Edge 2 - 4
---Result---
Path : 1 -> 3 -> 0 -> 2 -> 4 -> 1
TotalCost = 3311.100000

Comments

[t-xxx5]

回答ありがとうございます。参考にさせていただきます。

[actorbug]

こちらのコードも jimbe さんと同様の問題を抱えています。
全5ノードだと問題は出ませんが、全6ノードで3ノードずつ閉路になった場合に、「すべての点を回る閉路」があると判定されてしまいます。
(0-1, 0-2, 1-2, 3-4, 3-5, 4-5 の順番に辺を追加した場合など)

[fana]

あー，なるほど，独立した閉路が複数できちゃうパターンが簡素すぎる判定にひっかかっちゃうのですね．
「繋がり」をちゃんと扱わないとダメっていう．

[fana]

とりあえず気が向いたときに直すかもしれませんが，今のところは放置予定です．
（…っていうとき，低評価システムはやっぱ必要だよなぁ，と思うのだが…）