Sei gradi di Kevin Bacon in Perl

Question

Innanzitutto sì, questo è un progetto di compiti per la mia lezione di Perl.Non sto cercando la risposta (anche se sarebbe dolce).A quanto ho capito, devo utilizzare un BFS e un'espressione regolare per organizzare i miei dati per l'uso.Ho bisogno di indicazioni su questo.Come utilizzo un BFS?Utilizzo uno stack enorme ed esamino ogni elemento nello stack?Dovrei usare una tabella hash gigante?Qualcuno ha lavorato su questo problema?Come hai fatto a farlo?Ho solo bisogno di qualche indicazione, tutto qui.È simile a un BST?È possibile senza utilizzare il modulo grafico?È possibile utilizzare i valori hash?

Answer 1

Questo non è un risposta, ma sono suggerimenti per la tua risposta.

Il modo migliore per farlo è cercare innanzitutto in un grafico cos'è una ricerca in ampiezza.

Inoltre, se non ti è stata fornita un'espressione regolare, potresti considerare the tokenizzazione problema e cercalo.Forse non ce ne sarà bisogno.Controlla il compito e vedi se riesci bere in alcune informazioni.

Answer 2

Grafico .

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

Utilizzando kevin-bacon.dat dal progetto Boost:

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)