Seis grados de Kevin Bacon en Perl

Question

Primero sí, esta es una tarea de proyecto para mi Perl de la clase.Yo no estoy en busca de la respuesta (a pesar de que sería dulce).Como yo lo entiendo necesito usar un BFS y una expresión regular para organizar mis datos para su uso.Necesito un poco de orientación sobre este.¿Cómo puedo usar un BFS?¿Puedo utilizar una enorme pila e ir a través de cada elemento en la pila?Debo usar un gigante de la tabla hash?Alguien ha trabajado en este problema?¿Cómo hacerlo?Sólo necesito un poco de dirección es de todos.Es esto similar a un BST?Es esto posible sin el uso de la gráfica del módulo?Es esto posible con el uso de valores de hash?

Answer 1

Esto no es un respuesta, pero la insinuación de su respuesta.

Lo mejor es que primero busca lo que una Primera extensión de la Búsqueda es en un gráfico.

También, si no te han dado una expresión regular, usted puede considerar que el encadenamiento problema y mira que.Posiblemente que no serán necesarias.Controlar la asignación y ver si pueden slurp en algunos de la información.

Answer 2

Gráfico .

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

El uso de kevin-bacon.dat del proyecto 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)