M.Hiroi's Home Page

Linux Programming

お気楽 Perl プログラミング超入門

[ PrevPage | Perl | NextPage ]

経路の探索

今回は、地図上の A 地点から B 地点までの道順を求める、といった「経路の探索」と呼ばれる問題を取り上げます。「探索」にはいろいろな種類があります。たとえば、パズルを解く場合、あらゆる可能性の中から正解に行き着く手順を探すことですから、探索の一つと考えることができます。そして、探索でよく用いられる最も基本的な方法に「バックトラック (backtracking)」があります。

簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけませんね。つまり、失敗したら後戻りして別の道を選ぶ、という試行錯誤をゴールに行き着くまで繰り返すわけです。これがバックトラックの基本的な考え方です。

バックトラックは迷路を解くだけではなく、いろいろな問題に応用できる方法です。とくに、すべての解を求める場合、バックトラックが適しています。すべての解をもれなく見つけることができます。もちろん、経路の探索もバックトラックで解くことができます。

このほかに、もう一つ基本的な方法として「幅優先探索」があります。バックトラックの場合、失敗したら後戻りして別の道を選び直しますが、幅優先探索の場合は、全ての経路について並行に探索を進めていきます。幅優先探索は最短手順を求めるのに適したアルゴリズムですが、問題によっては必要となるメモリの量がとても多くなり、幅優先探索を使用することができない場合があります。このような場合、「反復深化」という方法を使うと、多少時間はかかりますが、少ないメモリで最短手順を求めることができます。今回はこの 3 つの方法で経路を求めてみましょう。

●グラフ

まず最初に「グラフ (graph)」というデータ構造を説明します。一般にグラフというと、 円グラフや折れ線グラフといった図表を思い出す人が多いと思います。数学の「グラフ理論」では、いくつかの点とそれを結ぶ線でできた図形を「グラフ」といいます。次の図を見てください。


      図 : グラフの例

上図に示すように、グラフは点とそれを接続する線から構成されています。点のことを「頂点 (vertex)」や「節点 (node)」と呼び、線のことを「辺 (edge)」や「弧 (arc)」と呼びます。グラフには 2 種類あって、辺に向きの無いグラフを「無向グラフ」といい、辺に向きがあるグラフを「有向グラフ」といいます。有向グラフは一方通行の道と考えればいいでしょう。 次の図を見てください。


          図 : 有向グラフと無向グラフ

たとえば、図 (1) では A 地点から B 地点へ行くことができますが、一方通行のため B 地点から A 地点に戻ることはできません。これが有効グラフです。(2) の無効グラフでは、A 地点から B 地点へ行くことができるし、逆に B 地点から A 地点に戻ることもできます。

データ間のさまざまな関係を表す場合、グラフはとても役に立ちます。たとえば、下図のように経路をグラフで表すことができます。


      図 : 経路図

上図ではアルファベットで頂点を表しています。この例では経路をグラフで表していますが、このほかにもいろいろな問題をグラフで表現することができます。

●隣接行列と隣接リスト

グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。経路図を隣接行列で表すと次のようになります。

  │A B C D E F G
─┼─────── 
 A│0 1 1 0 0 0 0
 B│1 0 1 1 0 0 0
 C│1 1 0 0 1 0 0
 D│0 1 0 0 1 1 0
 E│0 0 1 1 0 0 1
 F│0 0 0 1 0 0 0
 G│0 0 0 0 1 0 0

  図 : 隣接行列

A に接続している頂点は B と C なので、A 行の B と C に 1 をセットし、接続していない頂点には 0 をセットします。経路が一方通行ではない無向グラフの場合は、A 列の B と C にも 1 がセットされます。これを Perl でプログラムすると、次のようになります。

リスト : 隣接行列

@adjacent = (
  [0, 1, 1, 0, 0, 0, 0],  # A
  [1, 0, 1, 1, 0, 0, 0],  # B
  [1, 1, 0, 0, 1, 0, 0],  # C
  [0, 1, 0, 0, 1, 1, 0],  # D
  [0, 0, 1, 1, 0, 0, 1],  # E
  [0, 0, 0, 1, 0, 0, 0],  # F
  [0, 0, 0, 0, 1, 0, 0],  # G
);

頂点 A から G を数値 0 - 6 に対応させます。隣接行列を @adjacent とすると、無名の配列を使って 2 次元配列にします。頂点 $i と頂点 $j がつながっていれば、$adjacent[$i][$j] に 1 をセットします。頂点 $i と $j が一方通行でなければ $adjacent[$j][$i] も 1 になります。

隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。

 A => (B, C)
 B => (A, C, D) 
 C => (A, B, E)
 D => (B, E, F)
 E => (C, D, G)
 F => (D)
 G => (E)


  図 : 隣接リスト

これを Perl でプログラムすると次のようになります。

リスト : 隣接リスト

%adjacent = (
    A => ['B', 'C'],
    B => ['A', 'C', 'D'], 
    C => ['A', 'B', 'E'],
    D => ['B', 'E', 'F'],
    E => ['C', 'D', 'G'],
    F => ['D'],
    G => ['E']
);

連想配列 %adjacent に隣接リストをセットします。添字には頂点の名前をそのまま使えばいいでしょう。セットする隣接リストの要素も頂点の名前をセットします。

ところで、隣接リストにも欠点があります。たとえば、E と G が接続しているか調べるには、データを順番に調べていくしか方法がありません。このため、接続の判定に時間がかかることがあるのです。まあ、頂点に接続されている辺の数が少なければ、処理速度が極端に遅くなることはないでしょう。

●バックトラックによる探索

それではプログラムを作りましょう。今回は隣接リストを使って、A から G までの経路をバックトラックで求めます。バックトラックを再帰呼び出しで実現する場合、次の頂点へ進むことを再帰呼び出しに対応させるのがポイントです。

たとえば、経路を探索する関数を search としましょう。search は引数として現在地点の頂点を受け取ることにします。最初は search(A) と呼び出します。そして、A から B へ進むには search(B) と呼び出します。これで B へ進むことができます。

それでは、A に戻るにはどうしたらいいのでしょう。search(B) は search(A) から呼び出されたので、search(B) の実行を終了すれば、呼び出し元である search(A) に戻ることができます。つまり、関数の実行を終了すれば、一つ手前の地点にバックトラックできるのです。このように再帰呼び出しを使うと、進むことと戻ることを関数呼び出しで簡単に実現することができます。

●プログラムの作成

それでは具体的に説明しましょう。経路は配列に頂点を格納して表すことにします。プログラムは次のようになります。

リスト : 深さ優先探索

# 配列に同じ要素があるか
sub member {
    my ($n, $xs) = @_;
    foreach my $x (@$xs) {
        return 1 if $x eq $n;
    }
    0;
}

# 深さ優先探索
sub dfs {
    my ($goal, $path) = @_;
    my $x = $path->[-1];
    if ($goal eq $x) {
        print "@$path\n";
    } else {
        my $ls = $adjacent{$x};
        foreach my $y (@$ls) {
            if (!member($y, $path)) {
                push @$path, $y;
                dfs($goal, $path);
                pop @$path;
            }
        }
    }
}

探索は関数 dfs で行います。引数 $goal がゴール、$path が経路を表す無名の配列です。最初に、$path の末尾から現在地点 $x を取り出します。そして、$x がゴール $goal かチェックします。これが再帰呼び出しの停止条件になります。ゴールに到達したら print で経路を表示します。ここで探索を終了することもできますが、バックトラックすることで全ての経路を見つけることができます。

ゴールに到達していない場合、%adjacent から頂点 $x の隣接リストを取り出して変数 $ls にセットします。foreach 文で @$ls の要素を順番に取り出して変数 $y にセットし、dfs を再帰呼び出しします。このとき、経路に含まれている頂点を選んではいけません。そうしないと、同じ道をぐるぐると回る巡回経路が発生し、ゴールまでたどり着くことができなくなります。

このチェックを関数 member で行います。member は配列 $xs を線形探索して、引数 $n と等しい要素があれば真 (1) を返します。見つからない場合は偽 (0) を返します。member の返り値が偽ならば、push で $path の末尾に $y を追加し、dfs を再帰呼び出しします。戻ってきたら、$path から末尾の要素を pop で取り除きます。あとは dfs('A', ['G']) と呼び出すだけです。

●実行結果

実行結果は次のようになります。

$ perl dfs.pl
A B C E G
A B D E G
A C B D E G
A C E G

4 通りの経路を見つけることができました。バックトラックによる探索は経路を先へ先へ進めるので「縦形探索」とか「深さ優先探索 (depth first search)」と呼ばれています。このため、結果を見てもわかるように、最初に見つかる経路が最短経路とは限りません。最短経路を求めるのに適したアルゴリズムが「幅優先探索 (breadth first search)」です。

●幅優先探索

バックトラックによる探索は一つの経路を先へ先へと進めていきます。このため最初に見つかる経路が最短経路であるとは限りません。幅優先探索は全ての経路について平行に探索を進めていくため、最初に見つかる経路が最短経路となります。それでは、同じ経路図を使って幅優先探索を具体的に説明しましょう。

幅優先探索の様子を下図に示します。


                  図 : 幅優先探索

まず、出発点 A から一つ進んだ経路 (2 節点) を全て求めます。この場合は、[A B] と [A C] の 2 つあり、これを全て記憶しておきます。次に、これらの経路から一つ進めた経路 (3 節点) を全て求めます。経路 [A B] は [A B C] と [A B D] へ進めることができますね。ほかの経路 [A C] も同様に進めて、全ての経路を記憶します。あとはこの作業をゴールに到達するまで繰り返せばいいのです。

上図では、4 節点の経路 [A C E G] でゴールに達していることがわかります。このように幅優先探索では、最初に見つかった経路が最短距離 (または最小手数) となるのです。この性質は、全ての経路を平行に進めていく探索順序から考えれば当然のことといえるでしょう。このことから、バックトラックの縦形探索に対して、幅優先探索は「横形探索」と呼ばれます。このあとも探索を繰り返せば、すべての経路を求めることができます。

完成までの最小手数を求めるパズルを解く場合、幅優先探索を使ってみるといいでしょう。ただし、探索を進めるにしたがって、記憶しておかなければならないデータの総数が爆発的に増加する、つまりメモリを大量消費することに注意してください。

今回の経路図の場合、メモリを大量消費することはありませんが、問題によってはマシンに搭載されているメモリが不足するため、幅優先探索を実行できない場合もあるでしょう。したがって、幅優先探索を使う場合は、メモリの消費量を抑える工夫も必要になります。

●経路の管理

経路の管理ですが、「キュー (queue)」というデータ構造を使うと簡単にプログラムできます。キューは「待ち行列」といわれるデータ構造です。たとえば、チケットを買う場合窓口に長い列ができますが、それと同じだと考えてください。チケットを買うときは、列の途中に割り込むことはできませんね。いちばん後ろに並んで順番を待たなければいけません。列の先頭まで進むと、チケットを購入することができます。


         図 : キューの構造

このように、要素を取り出す場合は列の先頭から行い、要素を追加する場合は列の後ろに行うデータ構造が「キュー」なのです。キューは「先入れ先出し (FIFO : first-in, first-out)」とも呼ばれます。

Perl の場合、配列にデータをセットするときに push を使い、データを取り出すときに shift を使うと、キューを実現することができます。逆に、unshift と pop を使ってもかまいません。

幅優先探索でのキューの動作を下図に示します。


          図 : 幅優先探索とキューの動作

最初は、(1) のように出発点をキューにセットしておきます。次に、キューから経路を取り出し、(2) のように経路 [A] を一つ進めて、経路 [A B] [A C] を作り、それをキューに追加します。(3) では、経路 [A B] を取り出して、一つ進めた経路 [A B C] と [A B D] をキューに追加します。あとはキューに経路がある間、探索処理を繰り返します。

キューは先入れ先出し (FIFO) の性質を持つデータ構造です。距離の短い経路から順番に処理されるため、幅優先探索として機能するわけです。

●プログラムの作成 (2)

幅優先探索を行う関数 bfs は次のようになります。

リスト : 幅優先探索

sub bfs {
    my ($start, $goal) = @_;
    my @que = ([$start]);
    while (@que > 0) {
        my $path = shift @que;
        my $x = $path->[-1];
        if ($goal eq $x) {
            print "@$path\n";
        } else {
            my $ls = $adjacent{$x};
            foreach my $y (@$ls) {
                if (!member($y, $path)) {
                    my $new_path = [@$path];
                    push @$new_path, $y;
                    push @que, $new_path;
                }
            }
        }
    }
}

# 実行
bfs('A', 'G');

配列 @que がキューを表します。@que は出発点 $start を格納した経路 [$start] で初期化します。あとは、キューに経路があるあいだ while 文で探索を行います。最初に、キューから経路を取り出して変数 $path にセットします。そして、$path の末尾の要素 (現在位置) を取り出し、それを変数 $x にセットします。

$x が $goal と等しければ print で $path を表示します。そうでなければ、経路を一つ進めます。頂点 $y が経路 $path に含まれていなければ、$path に $y を追加した新しい経路 $new_path を作成し、それをキュー @que に追加します。これですべての経路を求めることができます。

●実行結果 (2)

それでは、実際に実行してみましょう。

$ perl bfs.pl
A C E G
A B C E G
A B D E G
A C B D E G

結果を見ればおわかりのように、最初に見つかる経路が最短で、最後に見つかる経路が最長となります。当然ですが、経路の総数は 4 通りとなります。

●反復深化

幅優先探索は最短手数を求めるのに適したアルゴリズムですが、生成する局面数が多くなると大量のメモリを必要とします。このため、メモリが不足するときは、幅優先探索を使うことができません。深さ優先探索の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らないという問題点があります。

それでは、大量のメモリを使わずに最短手数を求める方法はないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限値を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。

たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように制限値を 1 手ずつ増やしていくわけです。このアルゴリズムを「反復深化 (iterative deeping)」といいます。

反復深化は最短手数を求めることができるアルゴリズムですが、幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。ただし、同じ探索を何度も繰り返すため実行時間が増大するという欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。

●プログラムの作成 (3)

それでは、同じ経路図を使って反復深化を具体的に説明しましょう。反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う関数を作り、上限値を1手ずつ増やしてその関数を呼び出せばいいのです。プログラムは次のようになります。

リスト : 反復深化

# 反復深化 (深さ優先探索)
sub dfs {
    my ($goal, $path, $limit) = @_;
    my $x = $path->[-1];
    if ($limit == @$path) {
        print "@$path\n" if $goal eq $x;
    } else {
        my $ls = $adjacent{$x};
        foreach my $y (@$ls) {
            if (!member($y, $path)) {
                push @$path, $y;
                dfs($goal, $path, $limit);
                pop @$path;
            }
        }
    }
}

# 実行
foreach my $limit (1 .. 7) {
    print "----- $limit -----\n";
    dfs('G', ['A'], $limit);
}

関数 dfs の引数 $limit が上限値を表します。経路の長さが上限値 $limit に達したら探索を打ち切ります。このとき、ゴールに到達したかチェックします。あとは、$limit の値を増やしながら dfs を呼び出せばいいわけです。

●実行結果 (3)

それでは実行結果を示しましょう。

$ perl ids.pl
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
A C E G
----- 5 -----
A B C E G
A B D E G
----- 6 -----
A C B D E G
----- 7 -----

結果を見ればおわかりのように、最初に見つかる解が最短手数になります。このプログラムでは全ての経路を求めましたが、最短手数を求めるだけでよい場合は、解が見つかった時点で探索を終了すればいいでしょう。


●プログラムリスト1

#
# dfs.pl : 経路の探索 (深さ優先探索)
#
#          Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;

# 隣接リスト
my %adjacent = (
    A => ['B', 'C'],
    B => ['A', 'C', 'D'], 
    C => ['A', 'B', 'E'],
    D => ['B', 'E', 'F'],
    E => ['C', 'D', 'G'],
    F => ['D'],
    G => ['E'] );

# 配列に同じ要素があるか
sub member {
    my ($n, $xs) = @_;
    foreach my $x (@$xs) {
        return 1 if $x eq $n;
    }
    0;
}

# 深さ優先探索
sub dfs {
    my ($goal, $path) = @_;
    my $x = $path->[-1];
    if ($goal eq $x) {
        print "@$path\n";
    } else {
        my $ls = $adjacent{$x};
        foreach my $y (@$ls) {
            if (!member($y, $path)) {
                push @$path, $y;
                dfs($goal, $path);
                pop @$path;
            }
        }
    }
}

# 実行
dfs('G', ['A']);

●プログラムリスト2

#
# bfs.pl : 経路の探索 (幅優先探索)
#
#          Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;

# 隣接リスト
my %adjacent = (
    A => ['B', 'C'],
    B => ['A', 'C', 'D'], 
    C => ['A', 'B', 'E'],
    D => ['B', 'E', 'F'],
    E => ['C', 'D', 'G'],
    F => ['D'],
    G => ['E'] );

# 配列に同じ要素があるか
sub member {
    my ($n, $xs) = @_;
    foreach my $x (@$xs) {
        return 1 if $x eq $n;
    }
    0;
}

# 幅優先探索
sub bfs {
    my ($start, $goal) = @_;
    my @que = ([$start]);
    while (@que > 0) {
        my $path = shift @que;
        my $x = $path->[-1];
        if ($goal eq $x) {
            print "@$path\n";
        } else {
            my $ls = $adjacent{$x};
            foreach my $y (@$ls) {
                if (!member($y, $path)) {
                    my $new_path = [@$path];
                    push @$new_path, $y;
                    push @que, $new_path;
                }
            }
        }
    }
}

# 実行
bfs('A', 'G');

●プログラムリスト3

#
# ids.pl : 経路の探索 (反復深化)
#
#          Copyright (C) 2015-2023 Makoto Hiroi
#
use strict;
use warnings;

# 隣接リスト
my %adjacent = (
    A => ['B', 'C'],
    B => ['A', 'C', 'D'], 
    C => ['A', 'B', 'E'],
    D => ['B', 'E', 'F'],
    E => ['C', 'D', 'G'],
    F => ['D'],
    G => ['E'] );

# 配列に同じ要素があるか
sub member {
    my ($n, $xs) = @_;
    foreach my $x (@$xs) {
        return 1 if $x eq $n;
    }
    0;
}

# 反復深化 (深さ優先探索)
sub dfs {
    my ($goal, $path, $limit) = @_;
    my $x = $path->[-1];
    if ($limit == @$path) {
        print "@$path\n" if $goal eq $x;
    } else {
        my $ls = $adjacent{$x};
        foreach my $y (@$ls) {
            if (!member($y, $path)) {
                push @$path, $y;
                dfs($goal, $path, $limit);
                pop @$path;
            }
        }
    }
}

# 実行
foreach my $limit (1 .. 7) {
    print "----- $limit -----\n";
    dfs('G', ['A'], $limit);
}

初版 2015 年 5 月 3 日
改訂 2023 年 3 月 19 日

Copyright (C) 2015-2023 Makoto Hiroi
All rights reserved.

[ PrevPage | Perl | NextPage ]