簡単な経路探索をしてみたよ

Perl

再帰とかラムダ式の勉強をするために、Lispを触ってました。参考にしたのはこちらのページ。
M.Hiroi's Home Page / xyzzy Lisp Programming
なんか、Lispよりも同ページのパズルにハマったり。さて、Lispも色々面白いんですけれどもまだ僕には読みづらくて、少し複雑なプログラムになると頭で組み立てづらくなります。そこで、上のリンクにあるバックトラックによる経路の探索を、練習のためにPerlで書き直してみました。アルゴリズムは把握したので、なるべく上のお手本を見ないで作ってみました。
なお、元となるグラフは上記リンクとまったく同じです。

#!perl
use strict;

# ハッシュでグラフを表現。
my %adjacent = (
  'A' => [qw(B C)],
  'B' => [qw(A C D)],
  'C' => [qw(A B E)],
  'D' => [qw(B E F)],
  'E' => [qw(C D G)],
  'F' => [qw(D)],
  'G' => [qw(E)],
  );

sub backtrack_search {
  my ($path, $goal) = @_;
  my $point = $path->[0];

  if ($point eq $goal) {
    # ゴールに到着
    @$path = reverse @$path;
    print "found: @$path\n";}
  else {
    my @next_point;
    for my $q ( @{ $adjacent{$point}} ) {
      # 探索に現在までの経路を含まない
      next if grep { $_ eq $q } @$path;
      push @next_point, $q;
    }
    for (@next_point) {
      backtrack_search([$_, @$path], $goal);
    }
  }
}

backtrack_search([ qw(A) ], 'G');
  • 一番最後の配列を手に入れる方法が思いつかなかったので、リストを反転して出力してます。
  • グラフはハッシュで表現してます。すごく見づらいです。
  • 特にアップする必要もないんだけど、更新がとまってたので。

幅優先探索はまた明日。