迷路の出口を探す

アルゴリズムとか凄い弱いので、勉強。
迷路を作って、その出口までのパスを計算する方法ってのを考えてみた。

迷路の図面(sが開始位置で、gがゴール)

上の画像を参考に、状態の集合nodesと二つの状態を結ぶ辺の集合entitiesを用意。
また、現在の位置を表すpointer(初期値はs)も定義する。

# 状態の集合
@nodes = ('g', 's', '1', '2', '3', '4', '5', '6', '7', '8');
# 状態をつなぐパス
@entities = (['s', '1'], ['1', '2'], ['1', '4'], ['2', '3'], ['2', '5'], ['4', '5'], ['4', '7'], ['4', '8'], ['5', '6'], ['5', '8'], ['8', 'g']);
# 現在の位置を表すポインタ
$pointer = 's';

アルゴリズムは多分こんな感じ。
①pointerとつながっているパスをentitiesから検索。
②①でマッチしたentitiesの要素をループ。
　次の状態がgoalでなければ、①へ(pointerにその要素を代入)。

単純。
でもこんなのも分からないで昨日の夜から悶々と考えてたのは秘密ですorz
で、できたソースは以下のとおり(perlで書いてます)。

#!perl -w

# 状態の集合
my @nodes = ('g', 's', '1', '2', '3', '4', '5', '6', '7', '8');
# 状態をつなぐパス
my @entities = (
  ['s', '1'], ['1', '2'], ['1', '4'], ['2', '3'], ['2', '5'], 
  ['4', '5'], ['4', '7'], ['4', '8'], ['5', '6'], ['5', '8'], ['8', 'g']
);

print "start\n";
search(splice(@nodes, 1, 1), 's', 0);
print "end\n";

# 再起探索関数
sub search {
  my ($pointer, $path, $hierar_cnt) = @_;
  my @node = ();
  my $ct = -1;
  
  # 無限ループ防止
  exit if ++$hierar_cnt > 1000;
  
  # pointerの下のノード探索
  map { push @node, $_ if $_->[0] eq $pointer } @entities;
  
  # 下のノードがある場合掘り下げる
  while (1) {
    if (ref $node[++$ct] eq 'ARRAY') {
      # 階層化スペース
      print map { '  ' } 0..$hierar_cnt;
      # ゴール判定
      if ($node[$ct]->[1] eq 'g') {
        print "$path-$node[$ct]->[1] ... ";
        print "Find goal!\n";
      }
      else {
        print "$path-$node[$ct]->[1]\n";
        search($node[$ct]->[1], $path.'-'.$node[$ct]->[1], $hierar_cnt);
      }
    }
    else {
      last;
    }
  }
  unless (defined $node[0]) {
    print map { '  ' } split('-', $path);
    print "  [stop]\n";
  }
}

実行結果はこんな感じ。

start

    s-1

      s-1-2

        s-1-2-3

          [stop]

        s-1-2-5

          s-1-2-5-6

            [stop]

          s-1-2-5-8

            s-1-2-5-8-g ... Find goal!

      s-1-4

        s-1-4-5

          s-1-4-5-6

            [stop]

          s-1-4-5-8

            s-1-4-5-8-g ... Find goal!

        s-1-4-7

          [stop]

        s-1-4-8

          s-1-4-8-g ... Find goal!

end

結構楽しかった！
ちゃんとしたアルゴリズムの手法あんのかな。
ちょっと調べてみよう。

・例題の出典元
人工知能 - 著 菅原研次