DouKaku?から
再帰の問題例としての迷路問題。（中略）上記のプログラムを作成してください。（再帰を用いた迷路探索問題）
再帰のない言語やあっても深さの制限が厳しい言語があるので、手法は限定しないほうがいいでしょう（構造体とかリストとかも）。これはDouKaku?のすべてのトピックについて言えることですが、この問題が特に異常なのは、学校の宿題を人にやらせようとしているからでしょうか（参考：C/C++の宿題を片付けます 56代目）
私は宿題はどうでもいいので、なるべく楽な解決を目指します
例えばグラフアルゴリズムを標準サポートしている処理系（含Mathematica）なら、最短経路も特に難しいということはないでしょう（愚直なエージェントを実装したいということがあるかもしれませんが）
必要なパッケージをロードします
<<DiscreteMath`GraphPlot`; <<DiscreteMath`Combinatorica`;
迷路を定義し、データ構造を整えます
- num: 座標を数字に変換する補助関数
- pos: 数字を座標に変換する補助関数
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]
{{2,2},{2,3},{2,4},{2,5},{3,5},{4,5},{4,4},{4,3},{5,3},{5,2}}
おまけ：変換した結果のグラフを描画すると下のようになります
GraphPlot[FromUnorderedPairs@arcs,VertexStyleFunction->>Automatic];
Related posts:
