Bacon-Zahl in Perl

Question

Zuerst ja, das ist ein Hausaufgaben-Projekt für meine Perl-Klasse. Ich bin nicht auf der Suche nach der Antwort (obwohl das wäre süß). Wie ich es verstehe ich brauche einen BFS und einen regulären Ausdruck verwenden, um meine Daten zur Verwendung zu organisieren. Ich brauche Richtung auf diese. Wie verwende ich ein BFS? Muß ich einen massiven Stapel verwenden und in dem Stapel durch jeden Punkt gehen? Soll ich eine riesige Hash-Tabelle verwenden? Hat jemand auf dieses Problem gearbeitet? Wie haben Sie es zu tun? Ich brauche nur einige Richtung ist alles. Ist das ähnlich einem BST? Ist dies möglich, ohne das Diagramm-Modul? Ist dies möglich, unter Verwendung von Hash-Werten?

Answer 1

Dies ist keine Antwort , aber es ist Hinweise auf Ihre Antwort.

Sie sind am besten gedient, indem man zuerst schauen, was eine Breitensuche in einem Graphen ist.

Auch wenn Sie nicht einen regulären Ausdruck gegeben worden sind, können Sie prüfen, die Tokenisieren Problem und suchen Sie das wieder wett. Möglicherweise, das wird nicht nötig sein. Überprüfen Sie die Zuordnung und sehen, ob Sie können schlürfen in einigen Informationen.

Answer 2

Siehe Graph .

#!/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};
}

Mit kevin-bacon.dat aus dem Boost-Projekt:

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)