再帰を用いた迷路探索問題 in Mathematica DouKaku?

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

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

図１-
＊＊＊＊＊＊
＊８０００＊
＊＊＊＊０＊
＊＊０００＊
＊９０＊０＊
＊＊＊＊＊＊


**(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 - Mathematica

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

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

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

実行結果（Mathematicaなのでインデックスがずれます）：
{{2,2},{2,3},{2,4},{2,5},{3,5},{4,5},{4,4},{4,3},{5,3},{5,2}}

<<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]

DouKaku?

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

Posted feedbacks - Mathematica

Index

Feed

Other

Link

Pathtraq