迷路の解を見つけるアルゴリズム

質問

縦か横にしか進めない迷路があって
その迷路に解があるかどうか調べるには
どのようにすればよいのでしょうか？

最短距離を求めるというのであればできたのですが
答えがないというのをどのようにすればよいかわかりません。

教えてください。よろしくお願いします。

回答No.10

togino · ベストアンサー

> この任意の点を選ぶために０～３までの
> 乱数を発生することはできたのですが
> 開始点をシステムのカレンダー時刻を設定しているため
>同じ数ばかり出てきてしまいなかなかうまくいきません。

srand((unsigned)time(NULL));
for(i = 0; i < 100; i ++){
　printf("%d ", rand() % 4);
}

これで、実行するたびに違う乱数系列で乱数が生成されます。

お礼

回答有難うございます。

乱数の作り方はあっていたみたいです。

迷路の大きさが偶数奇数を問わない迷路をつくるには
どのようにすればよいのでしょうか？

私は等間隔に壁を設定してその間を生めるというやり方にしたのですがこれだと奇数しかできないので
偶数の場合もできるようにするには
根本的にだめなのだと気づいたしだいです。

回答No.9

togino

> どうやったら全体のプログラムを終了させずに
> maze_visitだけを終了できるのでしょうか？

maze_visit() 関数に返り値を設定すればいいのでは？

int maze_visit(int x,int y,Mazestruct *maze,int n){
　maze->maze_d[x][y]=TRACE;
　if(何か中断したいことが発生) return -1;

　if(maze->maze_d[x+1][y]==ROAD){
　　if(maze_visit(x+1,y,maze,n+1) == -1) return -1;
　}
　... 以下同様

　return 0;
}

初めの maza_visit() 呼び出しの返り値が 0 なら、
全探索して終了したことであり、-1 なら中断してます。

お礼

たびたび有難うございます。

最後にもう一つ質問なのですが
迷路の作成もやっているのですが
その中である一点から任意の点に壁を設定したいのですが
この任意の点を選ぶために０～３までの
乱数を発生することはできたのですが
開始点をシステムのカレンダー時刻を設定しているため
同じ数ばかり出てきてしまい
なかなかうまくいきません。
何かいい方法はないのでしょうか？

回答No.8

togino

投稿してもらったプログラム、正しくは下記の通りになります。

void maze_visit(int x,int y,Mazestruct *maze,int n){

maze->maze_d[x][y]=TRACE;

if(maze->maze_d[x+1][y]==ROAD){
maze_visit(x+1,y,maze,n+1);
}
if(maze->maze_d[x][y+1]==ROAD){
maze_visit(x,y+1,maze,n+1);
}
if(maze->maze_d[x-1][y]==ROAD){
maze_visit(x-1,y,maze,n+1);
}
if(maze->maze_d[x][y-1]==ROAD){
maze_visit(x,y-1,maze,n+1);
}
}

迷路を TRACE で埋め尽くすってことですよね。
else if(maze->maze_d[x+1][y]==TRACE){
のように、一度 TRACE したところを再び maze_visit しては
永久に visit し続けますよ (^^;)

なぜ else if を使ったのでしょうかね？
迷路には右にも下にも両方行ける分岐点はありますよね。

n を探索した格子点と解釈されてますが、違いますよ。
n は探索した深さです。つまるところ、
「右いこうかな？左行こうかな？」って迷って
「とりえず右行こう！」ってした時、もし右がすべて
行き止まりだったら、この分岐点に帰ってきますよね。
その覚えておく（覚えている）分岐点の数が n です。

お礼

アドバイスありがとうございます。

格子点を数えるならこの関数を呼び出した回数を数えればいいのですよね？
staticな変数で呼び出した回数は分るのですが
どうやったら全体のプログラムを終了させずに
maze_visitだけを終了できるのでしょうか？
また、見当はずれなことをやっているかもしれませんが
教えてください。

回答No.7

はなおか じった（@Jitta）

最短経路は、この春のソフトウェア開発技術者試験に出ていましたよ。

■ス■■■■■■■ゴ■■
■１■５■ＢＣＤ■Ｌ■■
■２３４■Ａ■■■ＫＪ■
■３■５■９■Ｂ■■Ｉ■
■４■６７８９Ａ■ＧＨ■
■■■■■■Ａ■■Ｆ■■
■ＧＦＥＤＣＢＣＤＥＦ■
■■■■■■■■■■■■

行けるところに、今のポイントよりも１多いポイントを振ります。ゴールから、１少ないポイントをたどれば最短道のりになります。

　ロボットのプログラム？ロボットのメモリに余裕があれば、迷路を記憶していきます。行き止まりになれば、メモリ上の道を戻って分岐点まで戻り、行き止まりへ続く分岐を閉じればOk。センサーとメモリの両方を比べながら、メモリ上が閉じていればそちらには入らないようにすると、左手（右手）法でありながら、中心にある出口にもたどり着けます。
　１０年前、マッピーに対してプログラムできたのだから、今のロボットでも十分使えるでしょう。

お礼

アドバイス有難うございます。

補足

解を確かめる一歩手前として
迷路を埋め尽くす関数を使ってみたのですが
うまくいきませんでした。
どのようにしたらよいのでしょうか？
ＴＲＡＣＥ＝２、ＷＡＬＬ＝１、ＲＯＡＤ＝０です。
/*迷路の構造体*/
typedef struct Mazestruct{
/*迷路のサイズ（size[0]:横のサイズsize[1]:縦のサイズ）*/
int size[2];
/*スタートの座標(st[0]:横座標st[1]:縦座標(一番左上を(0,0))*/
int st[2];
/*ゴールの座標(goal[0]:横座標goal[1]:縦座標*/
int goal[2];
/*壁と通路のデータ*/
int maze_d[wid_max][len_max];
}Mazestruct;

void maze_visit(int x,int y,Mazestruct *maze,int n){

maze->maze_d[x][y]=TRACE;
if(n>60000){
printf("探索した格子点が60000点を越えました。\n");
printf("探索を終了します。");
}
else if(maze->maze_d[x+1][y]==ROAD){
maze_visit(x+1,y,maze,n+1);
}
else if(maze->maze_d[x][y+1]==ROAD){
maze_visit(x,y+1,maze,n+1);

}
else if(maze->maze_d[x-1][y]==ROAD){
maze_visit(x-1,y,maze,n+1);

}
else if(maze->maze_d[x][y-1]==ROAD){
maze_visit(x,y-1,maze,n+1);

}
else if(maze->maze_d[x+1][y]==TRACE){
maze_visit(x+1,y,maze,n+1);
}
else if(maze->maze_d[x][y+1]==TRACE){
maze_visit(x,y+1,maze,n+1);

}
else if(maze->maze_d[x-1][y]==TRACE){
maze_visit(x-1,y,maze,n+1);

}
else if(maze->maze_d[x][y-1]==TRACE){
maze_visit(x,y-1,maze,n+1);

}
}

回答No.6

arukamun

右手でも左手でもいいからどちらかに固定します。
仮に右手にしたとして、
右手が右壁を触りながら迷路を進めば、出口が迷路の内部にあるような特殊な迷路で無い限り、抜けられると思います。
左手なら左壁を触りながら・・・。

ここで、出口ではなく、入口に出てしまった場合、解が無いということになると思います。

お礼

御礼が遅くなり申し訳ありません。

回答有難うございました。

回答No.5

togino

基本的には、「解がない」ことを調べるには
「全探索」するしか方法がありません。
しかし、幾分か「枝狩り」することが出来ますので
少し高速にすることはできると思います。

（例）ス→ゴ に行く迷路があるとします。

┏ス┳━━━┓
┃↓┃←←←┃
┃↓┗━━↑┃
┃▲→★→●┃
┃↓┃↓┃↓┃
┗━┻━┻ゴ┛

まず、最短経路は
・▲で右に行く
・★で右に行く
・●で下に行く
ですが,

全探索すると、
まず▲で下か右に枝分かれします。
ここで右を選んだ場合、
次に★で下か右に枝分かれしますが、
ここで下を選んだ場合、

『壁にぶつかります』

そうすると、「ス→▲→★→壁」によって
左下の区画は絶対にゴールにたどり着けない
ことが判明します。

つまり、最初の▲で下に行く探索は無意味です。

この枝狩りを効率よくプログラムに組み込んで
見てください。

# RedHat のスクリーンセーバーにこの探索の
# 様子を分かりやすく表示してたものがあって
# 見てて楽しかったのですが・・・

お礼

再起のことを自分自身がよく分っていないようで
なかなかうまくいきません。
回答有難うございました。

回答No.4

kube

こんにちは。

　考え方だけですが、外周が壁に囲まれていて、入り口と出口が一つづつで、中で何かを取得して脱出するというようなルールが無くて、一度通った道が消えてしまうとか、一方通行ドアがあるような特殊な迷路で無い二次元の迷路であれば、片側の壁面をトレースし続けて（壁面沿いに進んで）元の位置（入り口）に戻ったら解が無いと言えると思います。

以上は迷路ゲームで私がよくやる方法です。

お礼

これはゴールが壁沿いになくても可能なものなのですか？

回答有難うございました。

回答No.3

liar_adan

「塗り尽くし」の手法はあります。

(1)まず、スタート地点を特定の色で塗る。
(塗るというのは比喩で、配列か何かで表した迷路の
スタート地点のところに、特定の数値を入れる)

(2)迷路全体をスキャンして、「特定の色」に接する
マスであれば、それもまた「特定の色」に塗る。
それを繰り返す。

(3)「特定の色」に隣り合うマスがなくなれば終わり。
そのときゴールが塗られていなければ行き着くことはできない。

問題は、理論的に迷路の広さの2乗時間がかかることです。
再帰を使った方が早い場合が多いかもしれません。

お礼

現在それでガンバッテいます
アドバイス有難うございました。

回答No.2

neKo_deux

通路と壁を入れ替えて、スタートとゴールを分断できる経路があれば解なしと言えるような？

普通は総当りの全探索の結果、解が見つからなかったので…と持っていくしかないように思います。

お礼

アドバイス有難うございます。

回答No.1

anmochi

う～ん・・・・再帰を使って総当りしかないんじゃないかなぁ・・・・。

お礼

御礼が遅くなり申し訳ありません。

再起を使ってやって見ます。
アドバイス有難うございました。