2

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

4

2 に答える 2

6

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

#!/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.datBoostプロジェクトからの使用：

ケビンベーコンとエレーナマクシモワの間の3度の隔たり
ケビンベーコン-エリザベスシュー：ホロウマン（2000）
Elisabeth Shue-Lev Prygunov：Saint、The（1997）
Lev Prygunov-Yelena Maksimova：Bezottsovshchina（1976）
于 2009-11-06T02:46:18.947 に答える
5

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

最初に幅優先検索がグラフ内でどのようなものかを調べてください。

また、正規表現が与えられていない場合は、トークン化の問題を検討して調べることができます。おそらくそれは必要ないでしょう。課題をチェックして、いくつかの情報を丸呑みできるかどうかを確認してください。

于 2009-11-06T02:56:52.327 に答える