編集履歴

回答編集履歴

コード整理

2023/07/26 09:20

投稿

スコア13318

test CHANGED Viewed

@@ -22,8 +22,9 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <assert.h>
-//#define TEST
+//#define CHECK_TEST
 #define CHECK_LOG
 typedef struct {
@@ -32,143 +33,129 @@
   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 **result) {
+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", result[i]->u, result[i]->v);
+  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 rinf = CONTINUE;
+  int hasCross = 0; //false
   int hasClosed = 0; //false
-  //最期の辺(result[c-1])の接続先を追う
+  //最期の辺(roads[c-1])の接続先を追う
-  Adjacent **cpy = memcpy(malloc(sizeof(Adjacent*) * c), result, sizeof(Adjacent*) * c);
+  int *used = allocAndClear(sizeof(int) * (c-1), 0); //roads に index で対応するフラグ
-  PC *q = memset(malloc(sizeof(PC) * n), 0, sizeof(PC) * n);
+  PC *q = allocAndClear(sizeof(PC) * n, 0); //点の探索キュー&探索履歴・接続カウント
   int wi = 0, ri = 0;
-  q[wi].p = cpy[c-1]->u; //最後に追加した辺の両端を追加
+  setPc(q, wi++, roads[c-1]->u, 1); //最後に追加した辺の両端を追加
-  q[wi++].c = 1;
-  q[wi].p = cpy[c-1]->v;
+  setPc(q, wi++, roads[c-1]->v, 1);
-  q[wi++].c = 1;
-  cpy[c-1] = NULL;
   while(ri < wi) {
     PC *pc = &q[ri++];
-    for(int i=0; i<c-1; i++) { //点 p に繋がっている辺を cpy から探し、 p の逆側の点を q に追加、辺を cpy から削除
+    for(int i=0; i<c-1; i++) { //点 pc に繋がっている未使用辺を探し、 pc の逆側の点を (q に無ければ )q に追加
-      if(cpy[i] == NULL || (cpy[i]->u != pc->p && cpy[i]->v != pc->p)) continue;
+      if(used[i] || !isConnected(roads[i], pc->p)) continue;
+      used[i] = 1; //true
-      if(++pc->c > 2) rinf = DISCARD;
+      hasCross |= countAndCrossCheck(pc);
-      int np = pc->p == cpy[i]->u ? cpy[i]->v : cpy[i]->u; //p の逆側の点
+      int np = otherPoint(roads[i], pc->p); //p の逆側の点
-      cpy[i] = NULL;
       int found = 0; //false
-      for(int j=0; j<wi; j++) { //過去の点に戻った?
+      for(int j=0; j<wi; j++) {
-        if(q[j].p == np) {
-          hasClosed = 1; //true
+        if(q[j].p == np) { //探索済みor探索予定の点に繋がる?
           found = 1; //true
-          if(++q[j].c > 2) rinf = DISCARD;
+          hasCross |= countAndCrossCheck(&q[j]);
         }
       }
-      if(!found) {
-        q[wi].p = np;
+      hasClosed |= found;
-        q[wi++].c = 1;
+      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
-  if(hasClosed) {
-    rinf = DISCARD;
-    if(wi == n) {
-      int count = 0;
-      for(int i=0; i<wi; i++) if(q[i].c == 2) count ++;
-      if(count == n) rinf = COMPLETE; //点全部が 2 辺と接続した閉路なら COMPLETE
-    }
-  }
-  free(cpy);
+  free(used);
   free(q);
-#ifdef CHECK_LOG
+  if(hasCross || (hasClosed && c < n)) return DISCARD;
-  printf("rinf=%d\n", rinf);
+  if(hasClosed && c == n) return COMPLETE;
-#endif //CHECK_LOG
-  return rinf;
+  return CONTINUE;
 }
 //greedy法
-int greedy(int n, int m, Adjacent *adjacent, Adjacent **result) {
+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 c;
+    case COMPLETE: return result;
     case DISCARD: c--;
     }
   }
+  free(result);
-  return 0;
+  return NULL;
 }
 //表示
-void print(int c, Adjacent **result) {
+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<c; j++) {
+  for(int j=0, k; j<n; j++) {
-    p = p == result[i]->u ? result[i]->v : result[i]->u;
+    p = otherPoint(result[i], p);
     printf(" -> %d", p);
     total += result[i]->dist;
-    for(k=i, i=0; i==k || (result[i]->u != p && result[i]->v != p); i++); //次の i
+    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 TEST
+#ifdef CHECK_TEST
-  printf("TEST start\n");
-  Adjacent testdata1[] = {
+  Adjacent testdata1[] = { {0,1,100}, {2,3,110}, {3,4,120}, {2,4,130} };
-      {0,1,100},
-      {2,3,110},
-      {3,4,120},
-      {2,4,130},
-  };
-  Adjacent *test1[] = {
+  Adjacent *test1[] = { &testdata1[0], &testdata1[1], &testdata1[2], &testdata1[3] };
-      &testdata1[0],
-      &testdata1[1],
-      &testdata1[2],
-      &testdata1[3],
-  };
-  if(check(5, 4, test1) != DISCARD) printf("%d error\n", __LINE__);
+  assert(check(5, 4, test1) == DISCARD);
-  Adjacent testdata2[4] = {
+  Adjacent testdata2[4] = { {0,2,100}, {2,3,110}, {3,4,120}, {1,4,130} };
-      {0,2,100},
-      {2,3,110},
-      {3,4,120},
-      {1,4,130},
-  };
-  Adjacent *test2[] = {
+  Adjacent *test2[] = { &testdata2[0], &testdata2[1], &testdata2[2], &testdata2[3] };
-      &testdata2[0],
-      &testdata2[1],
-      &testdata2[2],
-      &testdata2[3],
-  };
-  if(check(5, 4, test2) != CONTINUE) printf("%d error\n", __LINE__);
+  assert(check(5, 4, test2) == CONTINUE);
-  printf("end\n");
 #else //TEST
   //ファイル読み込み・ソート等を省略
   int n = 5; //点の数
@@ -185,12 +172,11 @@
       {0,4, 1055.9},
       {2,4, 1592.3},
   };
-  Adjacent *result[10] = {0}; //結果保存領域(adjacents の要素へのポインタ)
-  int c = greedy(n, m, adjacents, result);
+  Adjacent **result = greedy(n, m, adjacents);
-  if(c == n) {
+  if(result) {
-    print(c, result); //最終的な経路を表示
+    print(n, result); //最終的な経路を表示
+    free(result);
   } else {
     printf("Failure\n");
   }
@@ -204,7 +190,8 @@
 wi=2
 p=1,c=1
 p=3,c=1
-rinf=0
+hasCross=0, hasClosed=0
 n=5,c=2
 1-3
 0-3
@@ -212,7 +199,8 @@
 p=0,c=1
 p=3,c=2
 p=1,c=1
-rinf=0
+hasCross=0, hasClosed=0
 n=5,c=3
 1-3
 0-3
@@ -221,7 +209,8 @@
 p=0,c=2
 p=1,c=2
 p=3,c=2
-rinf=-1
+hasCross=0, hasClosed=1
 n=5,c=3
 1-3
 0-3
@@ -231,7 +220,8 @@
 p=4,c=1
 p=3,c=2
 p=0,c=1
-rinf=0
+hasCross=0, hasClosed=0
 n=5,c=4
 1-3
 0-3
@@ -243,7 +233,8 @@
 p=3,c=2
 p=1,c=2
 p=4,c=1
-rinf=0
+hasCross=0, hasClosed=0
 n=5,c=5
 1-3
 0-3
@@ -256,7 +247,8 @@
 p=0,c=2
 p=1,c=2
 p=4,c=1
-rinf=-1
+hasCross=1, hasClosed=1
 n=5,c=5
 1-3
 0-3
@@ -269,7 +261,8 @@
 p=1,c=2
 p=0,c=2
 p=2,c=1
-rinf=-1
+hasCross=1, hasClosed=1
 n=5,c=5
 1-3
 0-3
@@ -282,7 +275,8 @@
 p=3,c=2
 p=4,c=1
 p=0,c=2
-rinf=-1
+hasCross=1, hasClosed=1
 n=5,c=5
 1-3
 0-3
@@ -295,7 +289,8 @@
 p=3,c=2
 p=2,c=1
 p=1,c=2
-rinf=-1
+hasCross=1, hasClosed=1
 n=5,c=5
 1-3
 0-3
@@ -308,7 +303,8 @@
 p=0,c=2
 p=1,c=2
 p=3,c=2
-rinf=1
+hasCross=0, hasClosed=1
 Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 1
 Total Distance: 3311.1
 ```

コード修正

2023/07/25 17:06

投稿

jimbe

スコア13318

test CHANGED Viewed

@@ -1,22 +1,30 @@
 valid 関数は、最後に追加した辺を用いるかどうかを返します。
-最後に追加した辺を用いるかどうかは、以下の点で判断出来ます。
+~~最後に追加した辺を用いるかどうかは、以下の点で判断出来ます。~~
-1. 辺の数が全ての点を回るのに不足している場合：閉路が出来たら false, 出来なかったなら true
+~~1. 辺の数が全ての点を回るのに不足している場合：閉路が出来たら false, 出来なかったなら true
 2. 辺の数が全ての点を回るのに必要な数に達した場合：完全な閉路が出来たら true, 出来なかったら false
-3. 辺の数が多くなった場合：false
+3. 辺の数が多くなった場合：false~~
-1 と 2 で閉路の扱いが逆ですので、判断もそのようにする必要があると思います。
+~~1 と 2 で閉路の扱いが逆ですので、判断もそのようにする必要があると思います。~~
-閉路の判定は、(実際に辿ってみなくても)各点から出る辺の数によって判断出来るのではないでしょうか。
+~~閉路の判定は、(実際に辿ってみなくても)各点から出る辺の数によって判断出来るのではないでしょうか。
 点から1本だけ辺が出ていれば、開いている部分があります。
 点から3本以上辺が出ていれば、完全な閉路は出来なくなりますし、一部が閉路になった可能性があります。
 全ての点から2本の辺が出ていれば、完全な閉路が出来たということでしょう。
 これらの条件の組み合わせを考えれば判断出来るものと思います。
-**※ざっくり考えたものですので穴がある可能性があります。**
+※ざっくり考えたものですので穴がある可能性があります。~~
 valid 関数を check に名前を変えて、戻り値を DISCARD/CONTINUE/COMPLETE の 3 つとして状況を返すようにしました。
+間違いを指摘頂きまして、結局最後に追加された辺から辿ることになりました。
+間違ったコードのままよりは良いかなと・・・**これが間違っていないとは言い切れません**が。
 ```c
 #include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+//#define TEST
+#define CHECK_LOG
 typedef struct {
   int u; //点1
@@ -24,21 +32,81 @@
   double dist; //点間の距離
 } Adjacent;
+typedef struct {
+  int p, c;
+} PC;
 //判定
 #define DISCARD (-1) //(最期に追加した辺を)破棄
 #define CONTINUE (0) //継続
 #define COMPLETE (1) //完了
 int check(int n, int c, Adjacent **result) {
+#ifdef CHECK_LOG
+  printf("n=%d,c=%d\n", n, c);
+  for(int i=0; i<c; i++) printf("%d-%d\n", result[i]->u, result[i]->v);
+#endif //CHECK_LOG
+  if(c > n) return DISCARD; //辺が多くなったなら破棄
+  int rinf = CONTINUE;
+  int hasClosed = 0; //false
+  //最期の辺(result[c-1])の接続先を追う
+  Adjacent **cpy = memcpy(malloc(sizeof(Adjacent*) * c), result, sizeof(Adjacent*) * c);
+  PC *q = memset(malloc(sizeof(PC) * n), 0, sizeof(PC) * n);
-  int open = 0;
+  int wi = 0, ri = 0;
+  q[wi].p = cpy[c-1]->u; //最後に追加した辺の両端を追加
+  q[wi++].c = 1;
+  q[wi].p = cpy[c-1]->v;
+  q[wi++].c = 1;
+  cpy[c-1] = NULL;
-  for(int i=0; i<n; i++) {
+  while(ri < wi) {
+    PC *pc = &q[ri++];
+    for(int i=0; i<c-1; i++) { //点 p に繋がっている辺を cpy から探し、 p の逆側の点を q に追加、辺を cpy から削除
+      if(cpy[i] == NULL || (cpy[i]->u != pc->p && cpy[i]->v != pc->p)) continue;
+      if(++pc->c > 2) rinf = DISCARD;
+      int np = pc->p == cpy[i]->u ? cpy[i]->v : cpy[i]->u; //p の逆側の点
+      cpy[i] = NULL;
-    int count = 0; //点i が現れる数
+      int found = 0; //false
-    for(int j=0; j<c; j++) if(result[j]->u == i || result[j]->v == i) count ++;
-    if(count > 2) return DISCARD; // 1 つの点から 3 本以上辺が出ているなら破棄
+      for(int j=0; j<wi; j++) { //過去の点に戻った?
-    open |= count == 1;
+        if(q[j].p == np) {
+          hasClosed = 1; //true
+          found = 1; //true
+          if(++q[j].c > 2) rinf = DISCARD;
-  }
+        }
+      }
+      if(!found) {
+        q[wi].p = np;
+        q[wi++].c = 1;
+      }
+    }
+  }
+#ifdef CHECK_LOG
+  printf("wi=%d\n", wi);
-  if(c < n) return open ? CONTINUE : DISCARD; //辺がまだ足りないなら開いていなければならない
+  for(int i=0; i<wi; i++) printf("p=%d,c=%d\n", q[i].p, q[i].c);
+#endif //CHECK_LOG
+  if(hasClosed) {
+    rinf = DISCARD;
+    if(wi == n) {
+      int count = 0;
+      for(int i=0; i<wi; i++) if(q[i].c == 2) count ++;
-  if(c == n) return open ? DISCARD : COMPLETE; //辺が足りたなら閉じていなければならない
+      if(count == n) rinf = COMPLETE; //点全部が 2 辺と接続した閉路なら COMPLETE
+    }
+  }
+  free(cpy);
+  free(q);
+#ifdef CHECK_LOG
+  printf("rinf=%d\n", rinf);
-  return DISCARD; //辺が多くなったなら破棄
+#endif //CHECK_LOG
+  return rinf;
 }
 //greedy法
@@ -71,6 +139,37 @@
 }
 int main(void) {
+#ifdef TEST
+  printf("TEST start\n");
+  Adjacent testdata1[] = {
+      {0,1,100},
+      {2,3,110},
+      {3,4,120},
+      {2,4,130},
+  };
+  Adjacent *test1[] = {
+      &testdata1[0],
+      &testdata1[1],
+      &testdata1[2],
+      &testdata1[3],
+  };
+  if(check(5, 4, test1) != DISCARD) printf("%d error\n", __LINE__);
+  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],
+  };
+  if(check(5, 4, test2) != CONTINUE) printf("%d error\n", __LINE__);
+  printf("end\n");
+#else //TEST
   //ファイル読み込み・ソート等を省略
   int n = 5; //点の数
   int m = 10; //辺の数
@@ -95,11 +194,121 @@
   } else {
     printf("Failure\n");
   }
+#endif //TEST
   return 0;
 }
 ```
 ```
+n=5,c=1
+1-3
+wi=2
+p=1,c=1
+p=3,c=1
+rinf=0
+n=5,c=2
+1-3
+0-3
+wi=3
+p=0,c=1
+p=3,c=2
+p=1,c=1
+rinf=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
+rinf=-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
+rinf=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
+rinf=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
+rinf=-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
+rinf=-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
+rinf=-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
+rinf=-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
+rinf=1
 Final Path: 1 -> 3 -> 0 -> 2 -> 4 -> 1
 Total Distance: 3311.1
 ```

コード修正

2023/07/23 11:45

投稿

jimbe

スコア13318

test CHANGED Viewed

@@ -55,7 +55,7 @@
 //表示
 void print(int c, Adjacent **result) {
-  printf("Final Path: "); fflush(stdout);
+  printf("Final Path: ");
   double total = 0;
   int i = 0;
   int p = result[i]->u;

コード修正: check 関数の戻り値を追加

2023/07/23 11:42

投稿

jimbe

スコア13318

test CHANGED Viewed

@@ -13,6 +13,8 @@
 全ての点から2本の辺が出ていれば、完全な閉路が出来たということでしょう。
 これらの条件の組み合わせを考えれば判断出来るものと思います。
 **※ざっくり考えたものですので穴がある可能性があります。**
+valid 関数を check に名前を変えて、戻り値を DISCARD/CONTINUE/COMPLETE の 3 つとして状況を返すようにしました。
 ```c
 #include <stdio.h>
@@ -23,25 +25,32 @@
 } Adjacent;
 //判定
+#define DISCARD (-1) //(最期に追加した辺を)破棄
+#define CONTINUE (0) //継続
+#define COMPLETE (1) //完了
-int is_valid(int n, int c, Adjacent **result) {
+int check(int n, int c, Adjacent **result) {
   int open = 0;
   for(int i=0; i<n; i++) {
     int count = 0; //点i が現れる数
     for(int j=0; j<c; j++) if(result[j]->u == i || result[j]->v == i) count ++;
-    if(count > 2) return 0; // 1 つの点から 3 本以上辺が出ているなら false
+    if(count > 2) return DISCARD; // 1 つの点から 3 本以上辺が出ているなら破棄
     open |= count == 1;
   }
-  if(c < n) return open; //辺がまだ足りないなら開いていなければならない
+  if(c < n) return open ? CONTINUE : DISCARD; //辺がまだ足りないなら開いていなければならない
-  if(c == n) return !open; //辺が足りたなら閉じていなければならない
+  if(c == n) return open ? DISCARD : COMPLETE; //辺が足りたなら閉じていなければならない
-  return 0; //辺が多くなったなら false
+  return DISCARD; //辺が多くなったなら破棄
 }
 //greedy法
-void greedy(int n, int m, Adjacent *adjacent, Adjacent **result) {
+int greedy(int n, int m, Adjacent *adjacent, Adjacent **result) {
   for(int i=0, c=0; i<m; i++) {
-    result[c] = &adjacent[i];
+    result[c++] = &adjacent[i];
-    if(is_valid(n, c+1, result)) c++;
+    switch(check(n, c, result)) {
+    case COMPLETE: return c;
+    case DISCARD: c--;
+    }
   }
+  return 0;
 }
 //表示
@@ -75,14 +84,17 @@
       {3,4, 871.2},
       {1,2, 1015.1},
       {0,4, 1055.9},
-      {2,4, 1592.3}
+      {2,4, 1592.3},
   };
   Adjacent *result[10] = {0}; //結果保存領域(adjacents の要素へのポインタ)
-  greedy(n, m, adjacents, result);
+  int c = greedy(n, m, adjacents, result);
+  if(c == n) {
-  // 最終的な経路を表示
+    print(c, result); //最終的な経路を表示
+  } else {
-  print(n, result);
+    printf("Failure\n");
+  }
   return 0;
 }

追加

2023/07/23 04:32

投稿

jimbe

スコア13318

test CHANGED Viewed

@@ -6,6 +6,13 @@
 3. 辺の数が多くなった場合：false
 1 と 2 で閉路の扱いが逆ですので、判断もそのようにする必要があると思います。
+閉路の判定は、(実際に辿ってみなくても)各点から出る辺の数によって判断出来るのではないでしょうか。
+点から1本だけ辺が出ていれば、開いている部分があります。
+点から3本以上辺が出ていれば、完全な閉路は出来なくなりますし、一部が閉路になった可能性があります。
+全ての点から2本の辺が出ていれば、完全な閉路が出来たということでしょう。
+これらの条件の組み合わせを考えれば判断出来るものと思います。
+**※ざっくり考えたものですので穴がある可能性があります。**
 ```c
 #include <stdio.h>

説明修正

2023/07/23 03:26

投稿

jimbe

スコア13318

test CHANGED Viewed

@@ -1,4 +1,11 @@
+valid 関数は、最後に追加した辺を用いるかどうかを返します。
+最後に追加した辺を用いるかどうかは、以下の点で判断出来ます。
+1. 辺の数が全ての点を回るのに不足している場合：閉路が出来たら false, 出来なかったなら true
+2. 辺の数が全ての点を回るのに必要な数に達した場合：完全な閉路が出来たら true, 出来なかったら false
+3. 辺の数が多くなった場合：false
-全ての点を回らないうちは閉じないということは、辺の数によって閉じているかいないかの判定を逆にする形になると思います。
+1 と 2 で閉路の扱いが逆ですので、判断もそのようにする必要があると思います。
 ```c
 #include <stdio.h>