迷路をグラフで解くということ

DouKaku?から。

再帰の問題例としての迷路問題。(中略)上記のプログラムを作成してください。(再帰を用いた迷路探索問題

再帰のない言語やあっても深さの制限が厳しい言語があるので、手法は限定しないほうがいいでしょう(構造体とかリストとかも)。これはDouKaku?のすべてのトピックについて言えることですが、この問題が特に異常なのは、学校の宿題を人にやらせようとしているからでしょうか(参考:C/C++の宿題を片付けます 56代目)。

私は宿題はどうでもいいので、なるべく楽な解決を目指します。

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

必要なパッケージをロードします。

<<DiscreteMath`GraphPlot`;
<<DiscreteMath`Combinatorica`;

Mathematicaの新しいバージョンではパッケージ名が変わっています。

Needs["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}}

これで終わりです。

おまけ

変換した結果のグラフを描画すると下のようになります(新しいバージョンでは、「VertexStyleFunction->Automatic」の代わりに「VertexLabeling -> True」としてください)

GraphPlot[FromUnorderedPairs@arcs,VertexStyleFunction->Automatic];