DouKaku?beta

[topic] 再帰を用いた迷路探索問題

再帰の問題例としての迷路問題。 迷路問題は、迷路に対してスタートとゴールを定義し、スタートからゴールまでの道順を探索することである。探索が成功した場合はその経路を表示し、ゴールにたどり着けない場合はその旨を表示することとする。 このような問題では、まず迷路空間をどのように表現するか考慮する必要がある。たとえば格子状を座標と考えて左上（０，０）と考えて右下を（５，５）と表現した場合はスタート（１，１）からゴール（１，４）まで、 （１，１）－（２，１）－（３，１）－（４，１）－４，２）－（４，３）－（３，３）－（２，３）－（２，４）－（１，４） という経路を通ることによってたどり着くと表現できる。 問題の制約 上記のように座標で考えるをわかりやすいが少し趣向を凝らしてリストを用いて迷路空間を表現し探索することを考えてみる。 リストの構成要素は迷路を構成するそれぞれのマス目となる。よって、マス目1つは、以下のような構造体boxで表現できる。構造対boxは自分自身の上下左右のマスを表すポインタと自分自身の状態を保持するためのflagの意味は以下のコメントの通りである。 **(1)** 上記の迷路問題スタートからゴールに辿り着く最短の経路は、次のように表現できる。 ((((((((start->right)->right)->right)->down)->down)->left)->left)->down)->left = goal のように表現できる。 上記の例では、人間の場合は瞬時に最短経路がわかるが、コンピュータは人間のような空間把握能力はないため、逐次滝に経路をたどることによってコールを探すことになる。つまり、ひたすらある方向に進み進めなくなったら違う方向に進むという事を繰り返してゴールを探索する。そのため、必ずしも最短経路を辿ってゴールできるとは限らない。 **(2)** 上記のプログラムを作成してください。 ヒント まずファイルからデータ（迷路空間）を読み込み、迷路空間を構成する。 そのあとに再帰を用いて、スタートからゴールまで探索する。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
図１-
＊＊＊＊＊＊
＊８０００＊
＊＊＊＊０＊
＊＊０００＊
＊９０＊０＊
＊＊＊＊＊＊


**(1)**

struct {
int flag;
struct box *up;
struct box *down;
struct box *right;
struct box *left;
};
struct box *null = (struct box *)NULL;
struct box *start; struct box *goal;


**(2)**

void visit(struct box *b,...) {
①ゴールに到達できない場合は次の処理を行う。
②現在の通路を通過したことを示すフラグを立てる
③上が空いてれば上に移動
④下が空いてれば下に移動
⑤右が空いてれば右に移動
⑥左が空いてれば左に移動
｝
post comment

Posted feedbacks - Nested

Flatten Hidden 
再帰のない言語やあっても深さの制限が厳しい言語があるので、
手法は限定しないほうがいいのではないでしょうか
（構造体とかリストとかも）。
要は迷路が解ければいいわけで。

例えばグラフアルゴリズムを標準サポートしている処理系なら、
最短経路も特に難しいということはないかと
（愚直なエージェントを実装したいということがあるかもしれませんが）

num：座標を数字に変換する補助関数
pos：数字を座標に変換する補助関数

実行結果（Mathematicaなのでインデックスがずれます）：
{{2,2},{2,3},{2,4},{2,5},{3,5},{4,5},{4,4},{4,3},{5,3},{5,2}}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
<<DiscreteMath`GraphPlot`;
<<DiscreteMath`Combinatorica`;

tmp={
      "******",
      "*8000*",
      "****0*",
      "**000*",
      "*90*0*",
      "******"};
maze=Characters/@tmp;
n=Length@First@maze;
num[i_,j_]:=n (i-1)+j
pos[x_]:={Quotient[x,n,1]+1,Mod[x,n,1]}

start=num@@First@Position[maze,"8"];
goal=num@@First@Position[maze,"9"];
arcs={};
Do[
    If[maze[[i,j]]!="*",
      If[maze[[i,j+1]]!="*",
        AppendTo[arcs,{num[i,j],num[i,j+1]}]];
      If[maze[[i+1,j]]!="*",
        AppendTo[arcs,{num[i,j],num[i+1,j]}]]],
    {i,1,Length@maze-1},{j,1,n-1}];

sol=ShortestPath[FromUnorderedPairs@arcs,start,goal];
If[Head@sol===ShortestPath || Length@sol==1,False,
  pos/@sol]

>>194
学校の宿題だったんですね。
すいませんでした、Mathematicaなんかでやってしまって。
でも、ここは多言語クックブックなので、言語と実装方法を指定しても無駄だと思いますよ。
ところで、締め切り思いっきり過ぎちゃってますけど、大丈夫でしょうか、いろんな意味で。

see: C/C++の宿題を片付けます 56代目

CやC++でスタックオーバフローの検出の仕方を教えてください。

書き忘れました。スレヌシ限定で！

スレヌシではないけど、参考ページをペタっとな

see: スタックオーバーフローのハンドリング

"上記のプログラム"とはどのようなプログラムでしょうか？ 任意のデータ形式のファイルを読み込み、その迷路を解き、経路を任意の形式で出力するプログラムを作成すれば良いのでしょうか？ 再帰を使うことは必須でしょうか?ループで書いてもいいと思うのですが…。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

#define STR_LEN 512 

int deque(struct box *b);
void print_pass();
void pop(struct box **pass_tail);
void push(struct box *b, struct box **pass_tail);
void link_up_down(struct box **head1, struct box **head2, struct box **tail2);
void link_right_left(int type, struct box **head, struct box **tail);
void read_maze(FILE *fp);
int visit(struct box *b, struct box **pass_head, struct box **pass_tail);
int main(void);

struct box{
    int flag;            //-1=壁, 0=通路, 1=通過, 8=スタート, 9=ゴール 
    struct box *up;        //上のマスへのポインタ
    struct box *down;    //下のマスへのポインタ
    struct box *right;    //右のマスへのポインタ
    struct box *left;    //左のマスへのポインタ
    struct box *pass_next;   //探索経路上、次のマスへのポインタ
    struct box *pass_prev;   //探索経路上、前のマスへのポインタ
};

struct box *null = (struct box *)NULL;    //リストの終端として利用
struct box *start, *goal;                //スタート及びゴール

//リストの先頭から方向を示す整数を返す[経路出力用]
int deque(struct box *b){
    if(b->pass_next == b->up) return 0;
    if(b->pass_next == b->down) return 1;
    if(b->pass_next == b->right) return 2;
    if(b->pass_next == b->left) return 3;
    return -1;
}

//戻りなし経路の表示
void print_pass()
{
    static const char *dirstr[] = {"up", "down", "right", "left"};
    struct box *b;
    for(b = start; b != goal; b = b->pass_next) {//スタートからゴールまで
        printf("%s ", dirstr[deque(b)]);//探索した経路を表示していく
    }
}

//リストの最後の要素を削除する[経路出力用]
void pop(struct box **pass_tail) 
{
    struct box *b = *pass_tail;
    *pass_tail = b->pass_prev;//前のマスに戻る
    b->pass_prev->pass_next = null;//リンクの削除
    b->pass_prev = null;
}

//リストの最後に要素を追加する[経路出力用]
void push(struct box *b, struct box **pass_tail){

    b->pass_prev = *pass_tail;//次のマスから前のマスへのリンク
    b->pass_prev->pass_next = b;//前のマスから次のマスへのリンク
    *pass_tail = b;//次のマスに進む
}

//up及びdownのリンクを作成する
void link_up_down(struct box **head1, struct box **head2, struct box **tail2){

    if(*head2 == null) {//リストが空ならば
        *head2 = *head1;//read_mazeで読み込んだ行の左端を迷路の左上端とする
    } else {
        struct box *p1, *p2;//p1は現在の行の分、p2は前の行の分
        for(p1 = *head1, p2 = *tail2; p1 != null && p2 != null; p1 = p1->right, p2 = p2->right) {//1行読み込む
            p1->up = p2;//現在のマスから上へのリンク
            p1->up->down = p1;//上から現在のマスへのリンク
        }
    }
    *tail2 = *head1;//tail2の更新
}

//right及びleftのリンクを作成する。
void link_right_left(int type, struct box **head, struct box **tail) {
    /* この関数内でのリストは，引数で**head,**tailとして与えられているので，*head,*tailで扱う．*/
    // typeで指定されたboxを作成する．
    struct box *p = (struct box*)malloc(sizeof(struct box));

    /* boxであるp の flag , right , leftを決定 */

    p->flag = type;//それぞれ初期化。左右リンク作成前なので、type以外をnullとしておく
    p->up = p->down = p->left = p->right = p->pass_next = p->pass_prev = null;
    if(*head == null) { // もしリストがカラだったら，リストの要素がないのだから p が先頭
        *head = p;//リストの先頭に追加する
    } else {
        p->left = *tail;//前のマスへのリンク
        p->left->right = p;//左から現在のマスへのリンク
    }
    *tail = p;//リストの末尾をpとする
}

//迷路データを読み込む
void read_maze(FILE *fp)
{
    struct box *head1,*tail1,*head2,*tail2;//それぞれ左右のリンクの左端と右端、迷路全体の左上と左下
    unsigned int i;
    char buffer[STR_LEN];//読み込んだ行の保管用

    //１本ずつ左右のリストを生成し、２本のリストから上下のリンクを生成する。
    head2 = tail2 = null;//端二か所を空のリストとする
    while(!feof(fp)){//ファイルの終わりまで

        head1 = tail1 = null;//左右リンクの端を空のリストとする

        if(fgets(buffer, STR_LEN - 1, fp) == NULL) //ファイルから読み込み
            break;
        for(i = 0; i < strlen(buffer) - 1; i++){//読み込んだ行の文字数だけ

            // ファイル中の文字(char型)を整数(int型)で表す
            int type;
            switch(buffer[i]) {
            case '*':
                type = -1;
                break;
            case '0':
            case '8':
            case '9':
                type = buffer[i] - '0';
                break;
            default:
                printf("迷路データに規定外の文字'%c'があります。\n", buffer[i]);
                return ;
            }

            // 左右リンクを作成
            link_right_left(type, &head1, &tail1);

            // startとgoalの決定
            if(type == 8) {
                start = tail1;
            } else if(type == 9) {
                goal = tail1;
            }
        }

        /*  (上下のリンクを生成) */
        link_up_down(&head1,&head2, &tail2);
        
    }
}

int visit(struct box *b, struct box **pass_head, struct box **pass_tail){
    //ゴールならば・・・
    if(b->flag == 9){
        printf("goal!\n");
        return(0);
    }
    
    //現在のマス目を通過済みとする
    if(b->flag == 0) b->flag = 1;
    
    //上方向が空いているなら上にいく
    if(b->up != null && (b->up->flag == 0 || b->up->flag == 9)) {
        printf("up ");
        push(b->up, pass_tail);//経路出力用に、リストの最後に追加しておく
        if(visit(b->up, pass_head, pass_tail) == 0)return(0);//再帰を利用して迷路を探索していく
        pop(pass_tail);//リストの最後を削除する
    }
    
    //下方向が空いているなら下にいく
    if(b->down != null && (b->down->flag == 0 || b->down->flag == 9)) {
        printf("down ");
        push(b->down, pass_tail);
        if(visit(b->down, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }
    
    //右方向が空いているなら右にいく
    if(b->right != null && (b->right->flag == 0 || b->right->flag == 9)) {
        printf("right ");
        push(b->right, pass_tail);
        if(visit(b->right, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }

    //左方向が空いているなら左にいく
    if(b->left != null && (b->left->flag == 0 || b->left->flag == 9)) {
        printf("left ");
        push(b->left, pass_tail);
        if(visit(b->left, pass_head, pass_tail) == 0)return(0);
        pop(pass_tail);
    }

    //4方向行き詰まりなので前のマスへ戻る
    printf("return! "); 

    //現在のマス目を未通過に戻す
    b->flag = 0;

    return(1);
}

int main(void){
    FILE *fp;
    int menu=-1;/* メニュー用*/
    char fileName[STR_LEN];    //迷路データファイル名
    struct box *pass_head=null,*pass_tail=null;

    //迷路データファイル名の決定
    while(menu < 0 || menu > 3)
    {
        printf("0.終了\n");
        printf("1. meirodata.txt を読み込む\n");
        printf("2. data.txt を読み込む\n");
        printf("3. 読み込むファイルを指定する\n");
        printf("メニューから選択して下さい。 : ");
        scanf("%d",&menu);
    }

    if(menu==0)return(0);
    if(menu==1)strcpy(fileName,"meirodata.txt");
    if(menu==2)strcpy(fileName,"data.txt");
    if(menu==3)
        scanf("%s",fileName);

    //ファイルを開く
    if((fp = fopen(fileName, "r")) == NULL){
        fprintf(stderr, "file read error!\n");
        exit(1);
    }
    //迷路を読み込む
    read_maze(fp);
    fclose(fp);
    //経路を探索する
    printf("探索経路----------\n");
    pass_head = pass_tail = start;
    visit(start,&pass_head,&pass_tail);
    printf("戻りなし経路----------\n");

    print_pass();

    printf("goal!\n------------------\n");

    return(0);
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]