ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー

現実逃避をしながらウェブを眺めていたらダイクストラ法（最短経路問題）にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。

何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。

http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt

実装もしてみました。隣接ノードの表現は、ここではリストを使いました。

#!/usr/bin/env perl
use strict;
use warnings;

package Node;
use base qw/Class::Accessor::Lvalue::Fast/;

__PACKAGE__->mk_accessors(qw/id done cost edges_to prev/);

package Queue;
use base qw/Class::Accessor::Lvalue::Fast/;
__PACKAGE__->mk_accessors(qw/heap heap_contains/);

use Heap::Simple;
use Params::Validate qw/validate_pos/;

sub new {
    my $class = shift;
    my $self = $class->SUPER::new(@_);

    $self->heap          = Heap::Simple->new(elements => 'Any');
    $self->heap_contains = [];

    return $self;
}

sub push {
    my ($self, $node) = validate_pos(@_, 1, 1);
    $self->heap->key_insert( $node->cost => $node );
    $self->heap_contains->[$node->id] = 1;
}

sub pop {
    my $self = shift;
    my $node = $self->heap->extract_first or return;
    $self->heap_contains->[$node->id] = 0;
    return $node;
}

sub contains {
    my ($self, $node) = validate_pos(@_, 1, 1);
    return $self->heap_contains->[$node->id];
}

package main;
use Perl6::Say;
use Heap::Simple;

## edges_to は添字 0 が次のノード、添字1 がエッジのコスト
my $nodes = [
    Node->new({
        id => 0,
        edges_to => [
            [ 1, 5 ],
            [ 2, 4 ],
            [ 3, 2 ],
        ],
    }),

    Node->new({
        id => 1,
        edges_to => [
            [ 0, 5 ],
            [ 2, 2 ],
            [ 5, 6 ],
        ],
    }),

    Node->new({
        id => 2,
        edges_to => [
            [ 0, 4 ],
            [ 1, 2 ],
            [ 3, 3 ],
            [ 4, 2 ],
        ],
    }),

    Node->new({
        id => 3,
        edges_to => [
            [ 0, 2 ],
            [ 2, 3 ],
            [ 4, 6 ],
        ],
    }),

    Node->new({
        id => 4,
        edges_to => [
            [ 2, 6 ],
            [ 3, 2 ],
            [ 5, 4 ],
        ],
    }),

    Node->new({
        id => 5,
        edges_to => [
            [ 1, 6 ],
            [ 4, 4 ],
        ],
    }),
];

## start
$nodes->[0]->cost = 0;

my $q = Queue->new;
$q->push( $nodes->[0] );

## done が今着目中のノード。目の前にあるもののうち最小のもの (greedy)
while (my $done = $q->pop) {
    ## done に隣接するノードのコストを計算
    for my $to (@{$done->edges_to}) {
        my $i    = $to->[0];
        my $cost = $done->cost + $to->[1]; ## コストは done のコスト + to までのエッジのコスト

        ## コストが今持ってるものよりも小さかったら更新
        if ( not defined $nodes->[$i]->cost or $cost < $nodes->[$i]->cost ) {
            $nodes->[$i]->cost = $cost;
            $nodes->[$i]->prev = $done->id;

            if (!$q->contains($nodes->[$i])) {
                $q->push( $nodes->[$i] );
            }
        }
    }
}

for (my $i = 1; $i < @$nodes; $i++) {
    local $_ = $nodes->[$i];
    say sprintf "id: %d, prev: %d, cost: %d", $_->id, $_->prev, $_->cost;
}

実行すると...

% perl dijkstra.pl
id: 1, prev: 0, cost: 5
id: 2, prev: 0, cost: 4
id: 3, prev: 0, cost: 2
id: 4, prev: 2, cost: 6
id: 5, prev: 4, cost: 10

となって、確かに全ノードへの最短路のコストが図にあるのと同じになっています。うまく動いているようです。

貪欲アルゴリズム

ダイクストラ法は、(全ノードを都度考慮するのではなく) 着目しているノードの次のノードだけを見て最小コストを更新すれば良いところがポイントです。いわゆる貪欲 (greedy) アルゴリズムで、単一始点最短路問題ではエッジのコストが非負である場合、数学的にも貪欲戦略が正しいことが証明できます。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション) の第2巻 24章に証明が載っています。

先週のアルゴリズムイントロダクション勉強会は、この貪欲アルゴリズムの章がテーマでした。

貪欲アルゴリズムの実装では、貪欲選択に際して全体の中から目の前にある最小のものあるいは最大のものを選択する...という処理を書くことが多く、また同じような部分問題を何度も解くことになります。例えばダイクストラ法の実装ように、最小のものを更新してそれをまた集合の中に入れるというような実装です。

最小もしくは最大の要素を取ったり更新したりを繰り返すのには優先度付きキューがあると簡単に計算量を抑えた実装が可能です。自分は Perl の場合 Heap::Simple を使うことが多いです。Heap::Simple は XS 版もあり、高速です。

以下は同じく貪欲アルゴリズムで解けるハフマン木構築の実装です。

#!/usr/bin/env perl
use strict;
use warnings;

package Node;
use base qw/Class::Accessor::Lvalue::Fast/;
__PACKAGE__->mk_accessors(qw/left right ascii/);

sub is_leaf {
    my $self = shift;
    !$self->left and !$self->right;
}

package main;
use Perl6::Say;
use Heap::Simple;

sub build_huffman_tree {
    my $text = shift;

    my $count = [];
    for (my $i = 0; $i < 0xff; $i++) {
        $count->[$i] = 0;
    }

    for (unpack("C*", $text)) {
        $count->[$_]++;
    }

    my $heap = Heap::Simple->new(elements => 'Array', order => '<');

    for (my $i = 0; $i < 0xff; $i++) {
        if ($count->[$i] > 0) {
            $heap->insert([ $count->[$i], Node->new({ ascii => $i }) ]);
        }
    }

    while (1) {
        my $x = $heap->extract_first;
        my $y = $heap->extract_first;

        if (not defined $y) {
            return $x->[1];
        }

        my $z = Node->new;
        $z->left  = $x->[1];
        $z->right = $y->[1];

        $heap->insert([ $x->[0] + $y->[0], $z ]);
    }
}

sub traverse {
    my ($node, $path) = @_;

    if ($node->left) {
        my @p = @$path; # copy
        push @p, 0;
        traverse($node->left, \@p);
    }

    if ($node->right) {
        my @p = @$path; # copy
        push @p, 1;
        traverse($node->right, \@p);
    }

    if ($node->is_leaf) {
        say sprintf "%s => %s", chr $node->ascii, join('', @$path);
    }
}

my $text = shift or die "usage: %0 <text>";

my $root = build_huffman_tree $text;
traverse $root, [];

ヒープを使うとあっさり実装できてしまいます。実行結果は

% perl huffman.pl "abracadabra"
a => 0
b => 10
r => 110
c => 1110
d => 1111

となり接頭語符号が得られています。

アルゴリズムイントロダクションの貪欲アルゴリズムの章は、マトロイドとの関連が面白かったです。グラフや行列の独立性などの性質を抽象化したマトロイドという概念があるそうですが、ある問題がマトロイドの構造を持っていると証明できると、その問題は貪欲アルゴリズムで説くことができるそうです。しかし数学的な証明が難しく、半分も理解できていません。

マトロイドで検索すると「もしかしてメトロイド」と言われてしまいます。

花粉症がつらい今日この頃です。