Perlでケビン・ベーコンの6度

Question

まずはい、これは私のPerlのクラスの宿題のプロジェクトです。私は（それは甘いだろうが）答えを捜しているわけではありません。私はそれを理解するとして、私は使用するための私のデータを整理するBFSと、正規表現を使用する必要があります。私はこの1つ上のいくつかの方向性を必要とします。どのように私はBFSを使用していますか？私は、大規模なスタックを使用し、スタック内の各アイテムを行くのですか？私は巨大なハッシュテーブルを使用する必要がありますか？誰もがこの問題に取り組んでいますか？どのようにそれをやって行きましたか？私はいくつかの方向がすべてである必要があります。これはBSTに似てますか？これは、グラフモジュールを使用しなくても可能ですか？これは、ハッシュ値を使用して可能ですか？

Answer 1

これはの答えのではありませんが、それはあなたの答えに向けたヒントです。

あなたは最高の最初の幅優先探索がグラフにあるものまで見ることで提供しています。

あなたが正規表現を与えられていない場合は、

また、あなたは、のトークン化の問題を考えると、それを調べることがあります。おそらくそれは必要ありません。割り当てをチェックして、あなただけのいくつかの情報ではの吸い込みをできるかどうかを確認します。

Answer 2

グラフを参照してください。

#!/usr/bin/perl

use autodie;
use strict; use warnings;

use Graph;
use Graph::TransitiveClosure::Matrix;

my $dat = 'kevin-bacon.dat';

my $kbg = Graph->new(undirected => 1);

open my $kbf, '<', $dat;

my %movies;

while ( my $line = <$kbf> ) {
    last unless $line =~ /\S/;
    chomp $line;
    my ($u, $m, $v) = split /;/, $line;
    $kbg->add_edge($u, $v);
    $movies{"$u|$v"} = $movies{"$v|$u"} = $m;
}

my $tcm = Graph::TransitiveClosure::Matrix->new($kbg,
    path_length => 1,
    path_vertices => 1,
);

my ($u, $v) = ('Kevin Bacon', 'Yelena Maksimova');

if ( my $n = $tcm->path_length($u, $v) ) {
    printf "%d degrees of separation between %s and %s\n", $n, $u, $v;
}

my @path = $tcm->path_vertices($u, $v);

for my $i ( 0 .. @path - 2 ) {
    my ($u, $v) = @path[$i, $i + 1];
    print qq{$u - $v: $movies{"$u|$v"}\n};
}

ブースト・プロジェクトからkevin-bacon.datを使用します：

3 degrees of separation between Kevin Bacon and Yelena Maksimova
Kevin Bacon - Elisabeth Shue: Hollow Man (2000)
Elisabeth Shue - Lev Prygunov: Saint, The (1997)
Lev Prygunov - Yelena Maksimova: Bezottsovshchina (1976)