迷路を脱出する経路探索プログラムをＣ言語で作成するには？

質問

迷路を脱出する経路を探索するプログラムを作成したいのですが、
何をすればいいのかまったくわかりません、
サンプルプログラムや解決ヒント等、
データの提供お願いします。
かなりこまってます。

回答No.3

naoya0302 · ベストアンサー

私も、部活で迷路脱出のプログラムを最近作りました。そのときには、本を参考に再起処理を使って作りました。
一応サンプルプログラムです。
#include<stdio.h>
int meiro[][]={{　省略　}};

int Si,Sj,Ei,Ej,success,sp,ri[100],rj[100];

int tansaku(int,int);

main()
{
sp=0;
success=0;
Si=1; Sj=1; Ei=7; Ej=7;

printf("\n迷路の探索");
if(tansaku(Si,Sj)==0){
//出口が見つからなかった
}
}
int tansaku(int i,int j)
{
int k;
static int path=1;

meiro[i][j]=1;
ri[sp]=i; rj[sp]=j; sp++;

if(i==Ei && j==Ej){
//出口が見つかった時の処理
//この時点で、ri,rjに経路が記録されている
success=1;
}//全経路検索　一度通ったところは通らない
if(meiro[i][j+1]==0) tansaku(i,j+1);
if(meiro[i+1][j]==0) tansaku(i+1,j);
if(meiro[i][j-1]==0) tansaku(i,j-1);
if(meiro[i-1][j]==0) tansaku(i-1,j);

sp--;
meiro[i][j]=0; //別経路探索のため
return(success);
}

確か本を参考に、こんなプログラムを作ったはずです。
ソースは、学校のパソコンに保存されているので性格かはわかりませんが・・・。
一応再起処理で全経路を検索しますが、広い空間があるとうまくいかないことがありました。
meiro[][]の二次元配列は、0が通路、1が自分が通った通路、2が壁です。
このプログラムは、迷路を壁で囲ってある状態にしていないと無限ループになるので、そこも注意してください。
迷路が大きいと時間がかかってしまうので、途中で中断できるようになればそれなりのものができると思います。

この回答を、投稿の前に確認したところ、字下げしたのがすべて無視されてました。
字下げなしの見にくいプログラムになってしまい、すみません。

回答No.4

Interest

趣味で迷路探索ロボット（マイクロマウス）を作っています。
迷路探索アルゴリズムは定番がいくつかありますので、それを紹介します。

(a) 行き当たりバッタリ
　　- 有限時間でゴールできる保証はない。
　　- アルゴリズムとはいえないかもしれない。

(b) 幅優先探索
　　- アルゴリズムの教科書を開くと必ず出てくるやつ。
　　- やってることは「しらみつぶし」だが、効率的なやりかた。
　　- すでに探索した区間は探索しない。

(c) 左手法（右手法でも同じ）
　　- 迷路探索の最も基本。
　　- 左手を壁に当てたまま進み続ける。
　　- ループする迷路は抜けられない。

(c') 拡張左手法（左手法の応用）
　　- 一度通った区画は再び入らない。
　　- 「仮想壁」がミソ。

(c'') トレモー法
　　- 拡張左手法を一般化したもの。

(d) 求心法
　　- ゴールに近ければ近いほど小さい評価値を設定する。
　　- その評価値が低いほう低い方へたどっていきゴールを目指す。

(e) 足立法
　　- 迷路探索と最短経路導出を同時にやってしまおうという便利な探索方法。
　　- 名前の由来は最初にやった人が「足立さん」という方だった、という説が有力。

(f) 等高線法（ポテンシャル法）
　　- ゴールから迷路全体への歩数マップを作る。
　　- 現在位置から歩数が小さくなる方向へ移動する。
　　- 移動中に壁が見つかったら、歩数マップを作り直す。

それぞれを解説するとここでは書ききれませんから、あとはここで出てきたキーワードを元に google 等で検索してみてください。

回答No.2

2531kbps

Cなら通路の分岐点でその関数を呼ぶことにより、行き止まり = ゴールになるまで再帰的にコールしたらどうかなあ？
あとは、すこし改造すれば、自分が通ったブロックをカウントすることにより最短コースも分かるし。

ただ、これは総当たり戦なので遅いですね。

回答No.1

BLUEPIXY

以前、javascriptで簡単な迷路脱出プログラムを書いたことがあります。
参考ＵＲＬを参照
迷路をどう表現するかで、経路探索も違ってくると思います。
参考ＵＲＬでの経路探索は、よくある壁に手をついて進むという方針で進むという方法になっています。

参考URL：

http://okweb.jp/kotaeru.php3?qid=1143763