Six degrés de Kevin Bacon en Perl

Question

D'abord oui, c'est un projet de devoirs pour ma classe Perl. Je ne cherche pas la réponse (bien que ce serait doux). Si je comprends bien que je dois utiliser un BFS et une expression régulière pour organiser mes données à utiliser. J'ai besoin de direction sur celui-ci. Comment puis-je utiliser un BFS? Dois-je utiliser une pile massive et passer par chaque élément de la pile? Dois-je utiliser une table de hachage géant? Quelqu'un at-il travaillé sur ce problème? Comment avez-vous à le faire? Je dois juste une certaine direction est tout. Est-ce semblable à un BST? Est-ce possible sans utiliser le module graphique? Est-ce possible en utilisant des valeurs de hachage?

Answer 1

Ce n'est pas réponse , mais il est des conseils à votre réponse.

Vous êtes mieux de vous regarder d'abord jusqu'à ce que une largeur First Search est dans un graphique.

En outre, si vous n'avez pas donné une expression régulière, vous pouvez envisager le tokenizing problème et vérifier. Peut-être cela ne sera pas nécessaire. Vérifiez l'affectation et voyez si vous pouvez simplement slurp dans quelques informations.

Answer 2

Voir Graphique .

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

Utilisation kevin-bacon.dat du projet 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)