投稿2017/05/07 05:59
学校の課題で迷路探索のプログラムを動かすアルゴリズムの問題に取り組んでいるのですが、課題のファイルを読み込むとコアダンプをおこしてしまい動作しませんでした。
読み込む配列を減らすと動作するのでおそらく容量かなにかの問題と思うのですが、家のパソコンではすべて課題のファイルでは動かず手つかずとなっています。
大変お手数ですが、以下の書いたプログラムで何か変更する点等がございましたらご指摘していただけるとありがたいです。
言語はC言語を使用しています。読んでいただきありがとうございます。よろしくお願いいたします。
C
1#include <stdio.h> 2#include <stdlib.h> 3 4#define yoko 101 /*横*/ 5#define tate 101 /*縦*/ 6#define N 1000 7 8int counter=0; 9int qcounter=0; 10int qlist=0; 11int olist=0; 12 13struct queue{ 14 int data[N]; 15 int head; 16 int tail; 17}; 18 19void initialize(struct queue *q){ 20 int i; 21 22 q->head=0; 23 q->tail=0; 24 for(i=0; i < N; ++i){ 25 q->data[i]=' '; 26 } 27} 28 29 30void enqueue(struct queue *q, int i){ 31 32 if (q->tail >= N) { 33 printf("This queue is full! \n"); 34 }else{ 35 q->data[q->tail]=i; 36 q->tail++; 37 } 38 39 qcounter++; 40 41 if(qcounter > qlist){ 42 qlist = qcounter; 43 } 44} 45 46int dequeue(struct queue *q){ 47 int j; 48 49 if(q->head == q->tail){ 50 return -1; 51 }else{ 52 j=q->data[q->head]; 53 q->head++; 54 qcounter--; 55 return j; 56 } 57} 58 59 60 61void next(char x[101][101] , int s, int t, struct queue *Q){ 62 int i, j; 63 counter++; 64 65 if(x[s+1][t] == 'G' || x[s][t+1] == 'G' || x[s-1][t] == 'G' || x[s][t-1] == 'G'){ 66 printf("GOAL\n"); 67 printf("%d回読み込まれました。\n", counter); 68 printf("キューの必要メモリ量：%d\n", qlist); 69 printf("オープンリストの必要メモリ量：%d\n", olist); 70 71 printf("\n"); 72 for(i=0;i<tate;i++){ 73 for(j=0;j<yoko;j++){ 74 printf("%c", x[i][j]); 75 } 76 printf("\n"); 77 } 78 79 exit(0); 80 } 81 82 if(x[s+1][t] == '0'){ /*下へとループ*/ 83 x[s+1][t] = '2'; 84 olist++; 85 86 printf("\n"); 87 for(i=0;i<tate;i++){ 88 for(j=0;j<yoko;j++){ 89 printf("%c", x[i][j]); 90 } 91 printf("\n"); 92 } 93 94 s = s+1; 95 printf("current position:%d,%d", s, t); //現在の座標を表示 96 enqueue(Q, s); 97 enqueue(Q, t); 98 s = s-1; 99 } 100 101 if(x[s][t+1] == '0'){ /*右へとループ*/ 102 x[s][t+1] = '2'; 103 olist++; 104 105 printf("\n"); 106 for(i=0;i<tate;i++){ 107 for(j=0;j<yoko;j++){ 108 printf("%c", x[i][j]); 109 } 110 printf("\n"); 111 } 112 113 t = t+1; 114 printf("current position:%d,%d", s, t); //現在の座標を表示 115 enqueue(Q, s); 116 enqueue(Q, t); 117 t = t-1; 118 } 119 120 if(x[s-1][t] == '0'){ /*上へとループ*/ 121 x[s-1][t] = '2'; 122 olist++; 123 124 printf("\n"); 125 for(i=0;i<tate;i++){ 126 for(j=0;j<yoko;j++){ 127 printf("%c", x[i][j]); 128 } 129 printf("\n"); 130 } 131 132 s = s-1; 133 printf("current position:%d,%d", s, t); //現在の座標を表示 134 enqueue(Q, s); 135 enqueue(Q, t); 136 s = s+1; 137 } 138 139 140 if(x[s][t-1] == '0'){ /*上へとループ*/ 141 x[s][t-1] = '2'; 142 olist++; 143 144 printf("\n"); 145 for(i=0;i<tate;i++){ 146 for(j=0;j<yoko;j++){ 147 printf("%c", x[i][j]); 148 } 149 printf("\n"); 150 } 151 152 t = t-1; 153 printf("current position:%d,%d", s, t); //現在の座標を表示 154 enqueue(Q, s); 155 enqueue(Q, t); 156 t = t+1; 157 } 158 159 s = dequeue(Q); 160 t = dequeue(Q); 161 162 next(x, s, t, Q); 163} 164 165 166void main(){ 167 int s=0, t=0; 168 int flag=0; 169 char data[yoko][tate]; 170 char mozi; 171 FILE *fp; /*ファイルポインタ*/ 172 173 fp = fopen("zikken.txt","r"); 174 for(s=0;s<tate;s++){ 175 for(t=0;t<yoko;t++){ 176 data[s][t] = fgetc(fp); 177 } 178 mozi = fgetc(fp); 179 mozi = fgetc(fp); 180 } 181 182 for(s=0;s<tate;s++){ 183 for(t=0;t<yoko;t++){ 184 printf("%c", data[s][t]); 185 } 186 printf("\n"); 187 } 188 189 fclose(fp); 190 191 s=1; t=1; /*スタート地点*/ 192 data[s][t] = 'S'; 193 data[yoko-2][tate-2] = 'G'; 194 195 struct queue Q; 196 197 initialize(&Q); 198 199 200 next(data, s, t, &Q); 201 202 return; 203}
text
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 210000000000000000010000010000010000010000000100000000000000010000000001000000000100000000000100000001 3・ 4・ 5・
文字数制限のため以下は省略いたします。申し訳ありません。読み込みたいデータは101101の配列、0が通れる道、1が壁、2がすでに通った道というように考えています。ちなみに1111の同様の配列では動くことができました。
使用しているパソコンはcpu core i7 2600、メモリは10GBです。
よろしくお願いいたします。
回答6件
0
恐らくスタックオーバーフローだと思います。特にデバグビルドの場合関数呼び出しにかなりのスタックを消費します。
※VS2015だと、スタックメモリが１ＭＢでnextの呼び出しに228byteぐらい消費しますので、next関数呼び出し4500近くでスタックオーバーフローになります。スタックメモリを増やせば応急処置的に回避できるかもしれません。
課題が再帰処理だったものをQueueを使ったものに変えるというものではありませんか？
せっかくQueueを使っているのでnext関数を再帰的に呼び出さず、next関数を
do {next呼び出しの除く今の処理} while(Queueにデータありの判定);
にすれば、良いと思います。
というか、そのように準備ができているような気がします。
投稿2017/05/09 08:53
総合スコア277
0
コアを吐くならコアダンプしてみればいいと思います。
gdbでコアを解析してみてください。
直感ではスタックが壊れてるのかなと思います。main関数内で静的にqueueを作ればスタックが消費されます。また、nextは再帰関数なのでこれも呼び出すたびにスタックが消費されます。
struct queue Q;をmain関数の外に出してグローバル変数として定義するか、mallocを使ってヒープから確保して下さい。
C
1struct queue *Q = (struct queue *)malloc(seizof(struct queue)); 2if (Q == NULL) { 3 perror("memory allocation failed."); 4 return -1; 5} 6
もしくはプログラムを動かす前にスタックサイズを変更してください。
bash
1#スタックを100Mに. 2$ulimit -s 102400 3
投稿2017/05/09 02:18
総合スコア910
0
一応ソースを見返して気になった点を指摘しておきます。
#1. 改行コードの読み飛ばし
改行コードが何かチェックしないで読み飛ばしていますね。
テキストエディタで保存して\r\nとして保存されない場合があります。
課題のテキスト、改行が\nだけなんてことはありませんか？
C
1for(s=0;s<tate;s++){ 2 for(t=0;t<yoko;t++){ 3 data[s][t] = fgetc(fp); 4 } 5 mozi=fgetc(fp); 6 mozi=fgetc(fp); // ここです 7}
改行が\nでも、\r\nでも大丈夫なようにしましょう。
C
1char c; 2while((c=fgetc(fp)) != '\0') 3{ 4 if (c == '\n' || c == '\r') 5 { 6 if (t != 0) 7 { 8 t = 0; 9 s += 1; 10 } 11 continue; 12 } 13 data[s][t++] = c; 14}
エラーを起こしそうで気付きにくい最たるものはコレです。
以降はエラー原因ってわけではないので全部オマケです。
#2.フォーマットチェック
可能であれば、縦横101文字ずつとなっているかファイル読み込み時にチェックしましょう。
・ファイル読み込み時にtやsの値が101となっているのかチェックする
・外周が全て1で埋められているかチェックする
#3.縦と横の意味が1度変わっている
ファイル読み込み前、配列作成時はdata[yoko][tate]としているのに
各ループでは先に縦を回しています。
for(i=0;i<tate;i++){ for(j=0;j<yoko;j++){ printf("%c", x[i][j]); } printf("\n"); }
正方形じゃなければエラーの原因になりえます。
※コンパイルエラーになるので大丈夫だとは思いますが
#4.data配列を初期化する
ファイル読み込み時のdata配列はちゃんと初期化しておきましょう。
char data[yoko][tate]; => char data[yoko][tate] = {0};
#5.探索時のチェック
101を超えて探索しないようにコードで制限しましょう。
文字1は壁ですが、1の外は真空です。コードでも念のため、触れないようにしましょう。
#6.出力しすぎ
コンソール上で動作させた時の動作速度をあげるためにprintfするものを減らしましょう。
デフォルトだと探索の途中経過全てを表示していますが、コンソールアウトは結果を待って実行されるので全体的な動作が遅くなります。
101*101の探索経過をダンプすると日が暮れます。
#7.同じコードを見たら関数化する
同じコードを見たら関数化しましょう。
例えば出力のコードはこれでいいでしょうし
void print(char x[tate][yoko]) { int i, j; for(i=0;i<tate;i++){ for(j=0;j<yoko;j++){ printf("%c", x[i][j]); } printf("\n"); } }
探索のコードも同じことをしていますから纏めることができます
void move(char x[tate][yoko], int s, int t, struct queue *Q) { // 関数が範囲外をみないようにするためのチェック if (s >= tate) { return; } if (t >= yoko) { return; } if(x[s][t] == '0'){ x[s][t] = '2'; olist++; //現在の座標を表示 printf("current position:%d,%d\n", s, t); print(x); enqueue(Q, s); enqueue(Q, t); } }
まとめるとnextメソッドはこんな風に短くなります。
動作も共通になり、変更時の手間が大幅に減ります。
void next(char x[101][101] , int s, int t, struct queue *Q){ int i, j; counter++; if(x[s+1][t] == 'G' || x[s][t+1] == 'G' || x[s-1][t] == 'G' || x[s][t-1] == 'G'){ printf("GOAL\n"); printf("%d回読み込まれました。\n", counter); printf("キューの必要メモリ量：%d\n", qlist); printf("オープンリストの必要メモリ量：%d\n", olist); printf("\n"); print(x); exit(0); } move(x, s+1, t, Q); // 下 move(x, s, t+1, Q); // 右 move(x, s-1, t, Q); // 上 move(x, s, t-1, Q); // 左 s = dequeue(Q); t = dequeue(Q); next(x, s, t, Q); }
投稿2017/05/09 02:10
編集2017/05/09 02:15
総合スコア1591
0
走らせると思いっきりThis queue is full!が表示されますし
これ表示した後処理を止めていないのが問題です。
バッファオーバーフローを起こしても値を書き込み続けているので運が悪ければ死にます。
そして見ているのはそれです。
とりあえずは、Nのサイズ上げてください。
あと、queue is fullになったら実行を止めてexitさせましょう。
投稿2017/05/08 09:16
総合スコア1591
0
別物ですが、ご質問者様のプログラムを参考に作成してみました。
c
1#include <stdio.h> 2#include <stdlib.h> 3 4#define yoko 101 /*横*/ 5#define tate 101 /*縦*/ 6#define N yoko * tate * 2 7 8int counter=0; 9int qcounter=0; 10int qlist=0; 11int olist=0; 12int muki=0; 13 14struct queue{ 15 int data[N]; 16 int head; 17 int tail; 18}; 19 20void initialize(struct queue *q){ 21 q->head=0; 22 q->tail=0; 23} 24 25void enqueue(struct queue *q, int i){ 26 27 if (q->tail >= N) { 28 printf("This queue is full! \n"); 29 }else{ 30 q->data[q->tail]=i; 31 q->tail++; 32 } 33 34 qcounter++; 35 36 if(qcounter > qlist){ 37 qlist = qcounter; 38 } 39} 40 41int dequeue(struct queue *q){ 42 int j; 43 44 if(q->head == q->tail){ 45 return -1; 46 }else{ 47 j=q->data[q->tail-1]; 48 q->tail--; 49 qcounter--; 50 return j; 51 } 52} 53 54int houkou(struct queue *q){ 55 int j; 56 57 if(q->head == q->tail){ 58 return -1; 59 }else if (q->data[q->tail+1] == q->data[q->tail-1]){ 60 if ( q->data[q->tail] > q->data[q->tail-2] ){ 61 j=2; 62 }else{ 63 j=0; 64 } 65 }else if(q->data[q->tail+1] > q->data[q->tail-1]){ 66 j=3; 67 }else{ 68 j=1; 69 } 70 return j; 71} 72 73void next(char x[101][101] , int s, int t, struct queue *Q, int muki){ 74 int i, j; 75 counter++; 76 77 if(x[s+1][t] == 'G' || x[s][t+1] == 'G' || x[s-1][t] == 'G' || x[s][t-1] == 'G'){ 78 printf("GOAL\n"); 79 printf("%d回読み込まれました。\n", counter); 80 printf("キューの必要メモリ量：%d\n", qlist); 81 printf("オープンリストの必要メモリ量：%d\n", olist); 82 printf("\n"); 83 exit(0); 84 } 85 86 switch (muki) { /* 下:0 右:1 上:2 左:3*/ 87 case 0: /* 下向き */ 88 if (x[s][t-1] == '0'){ /*左へとループ 3*/ 89 x[s][t-1] = '2'; 90 olist++; 91 t = t-1; 92 printf("current position:%d,%d", s, t); //現在の座標を表示 93 enqueue(Q, s); 94 enqueue(Q, t); 95 muki = 3; 96 }else if(x[s+1][t] == '0'){ /*下へとループ 0*/ 97 x[s+1][t] = '2'; 98 olist++; 99 s = s+1; 100 printf("current position:%d,%d", s, t); //現在の座標を表示 101 enqueue(Q, s); 102 enqueue(Q, t); 103 muki = 0; 104 }else if(x[s][t+1] == '0'){ /*右へとループ 1*/ 105 x[s][t+1] = '2'; 106 olist++; 107 t = t+1; 108 printf("current position:%d,%d", s, t); //現在の座標を表示 109 enqueue(Q, s); 110 enqueue(Q, t); 111 muki = 1; 112 }else{ 113 t = dequeue(Q); 114 s = dequeue(Q); 115 muki = houkou(Q); 116 } 117 break; 118 case 1: /* 右向き */ 119 if(x[s+1][t] == '0'){ /*下へとループ 0*/ 120 x[s+1][t] = '2'; 121 olist++; 122 s = s+1; 123 printf("current position:%d,%d", s, t); //現在の座標を表示 124 enqueue(Q, s); 125 enqueue(Q, t); 126 muki = 0; 127 }else if (x[s][t+1] == '0'){ /*右へとループ 1*/ 128 x[s][t+1] = '2'; 129 olist++; 130 t = t+1; 131 printf("current position:%d,%d", s, t); //現在の座標を表示 132 enqueue(Q, s); 133 enqueue(Q, t); 134 muki = 1; 135 }else if (x[s-1][t] == '0'){ /*上へとループ 2*/ 136 x[s-1][t] = '2'; 137 olist++; 138 s = s-1; 139 printf("current position:%d,%d", s, t); //現在の座標を表示 140 enqueue(Q, s); 141 enqueue(Q, t); 142 muki = 2; 143 }else{ 144 t = dequeue(Q); 145 s = dequeue(Q); 146 muki = houkou(Q); 147 } 148 break; 149 case 2: /* 上向き */ 150 if (x[s][t+1] == '0'){ /*右へとループ 1*/ 151 x[s][t+1] = '2'; 152 olist++; 153 t = t+1; 154 printf("current position:%d,%d", s, t); //現在の座標を表示 155 enqueue(Q, s); 156 enqueue(Q, t); 157 muki = 1; 158 }else if (x[s-1][t] == '0'){ /*上へとループ 2*/ 159 x[s-1][t] = '2'; 160 olist++; 161 s = s-1; 162 printf("current position:%d,%d", s, t); //現在の座標を表示 163 enqueue(Q, s); 164 enqueue(Q, t); 165 muki = 2; 166 }else if (x[s][t-1] == '0'){ /*左へとループ 3*/ 167 x[s][t-1] = '2'; 168 olist++; 169 t = t-1; 170 printf("current position:%d,%d", s, t); //現在の座標を表示 171 enqueue(Q, s); 172 enqueue(Q, t); 173 muki = 3; 174 }else{ 175 t = dequeue(Q); 176 s = dequeue(Q); 177 muki = houkou(Q); 178 } 179 break; 180 case 3: /* 左向き */ 181 if (x[s-1][t] == '0'){ /*上へとループ 2*/ 182 x[s-1][t] = '2'; 183 olist++; 184 s = s-1; 185 printf("current position:%d,%d", s, t); //現在の座標を表示 186 enqueue(Q, s); 187 enqueue(Q, t); 188 muki = 2; 189 }else if (x[s][t-1] == '0'){ /*左へとループ 3*/ 190 x[s][t-1] = '2'; 191 olist++; 192 t = t-1; 193 printf("current position:%d,%d", s, t); //現在の座標を表示 194 enqueue(Q, s); 195 enqueue(Q, t); 196 muki = 3; 197 }else if(x[s+1][t] == '0'){ /*下へとループ 0*/ 198 x[s+1][t] = '2'; 199 olist++; 200 s = s+1; 201 printf("current position:%d,%d", s, t); //現在の座標を表示 202 enqueue(Q, s); 203 enqueue(Q, t); 204 muki = 0; 205 }else{ 206 t = dequeue(Q); 207 s = dequeue(Q); 208 muki = houkou(Q); 209 } 210 break; 211 default: 212 exit(2); 213 break; 214 } 215 216 printf("\n"); 217 for(i=0;i<tate;i++){ 218 for(j=0;j<yoko;j++){ 219 printf("%c", x[i][j]); 220 } 221 printf("\n"); 222 } 223 224 next(x, s, t, Q, muki); 225 226} 227 228 229void main(){ 230 int s=0, t=0; 231 int flag=0; 232 char data[yoko][tate]; 233 char mozi; 234 FILE *fp; /*ファイルポインタ*/ 235 236 fp = fopen("zikken.txt","r"); 237 for(s=0;s<tate;s++){ 238 for(t=0;t<yoko;t++){ 239 data[s][t] = fgetc(fp); 240 } 241 mozi = fgetc(fp); 242 mozi = fgetc(fp); 243 } 244 245 for(s=0;s<tate;s++){ 246 for(t=0;t<yoko;t++){ 247 printf("%c", data[s][t]); 248 } 249 printf("\n"); 250 } 251 252 fclose(fp); 253 254 s=1; t=1; /*スタート地点*/ 255 data[s][t] = 'S'; 256 data[yoko-2][tate-2] = 'G'; 257 258 struct queue Q; 259 260 initialize(&Q); 261 262 263 next(data, s, t, &Q, muki); 264 265 return; 266}
zikken.txtが簡単なケースなので「S～G」まで辿り着きます。右手壁伝いのロジックです。
できればファイルを載せて頂けると原因が分かると思います。
ファイルはCRLFですよね。またマシンスペックは充分だと思います私のは、core5(8G)です。
投稿2017/05/08 03:45
編集2017/05/08 16:44
総合スコア4070
0
パソコンの物理メモリが足りないとは思えないですね。
このプログラムだと（入力データにも依存しますが）定数Nを12000位にしないとキューが不足しえます。
投稿2017/05/07 12:38
総合スコア4830
あなたの回答
tips
プレビュー
Q&A
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/05/11 21:16
2017/05/15 01:26