Six degrés de Kevin Bacon en Perl

Question

D'abord oui, ceci est un projet de devoirs pour ma classe Perl. Je ne cherche pas la réponse (bien que ce serait gentil). Si je comprends bien, j'ai besoin d'utiliser un BFS et une expression régulière pour organiser mes données pour l'utilisation. J'ai besoin d'une direction sur celui-ci. Comment utiliser un BFS? Est-ce que j'utilise une pile massive et passe par chaque élément de la pile? Dois-je utiliser une table de hachage géante? Est-ce que quelqu'un a travaillé sur ce problème? Comment l'as-tu fait? J'ai juste besoin d'une direction, c'est tout. Est-ce similaire à 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 une réponse , mais il est des notes vers votre réponse.

Vous êtes mieux servi en recherchant d'abord ce qu'est une première recherche dans un graphique.

En outre, si vous n'avez pas reçu d'expression régulière, vous pouvez envisager le problème de création de jetons et le rechercher. Peut-être que ce ne sera pas nécessaire. Vérifiez l'affectation et voyez si vous pouvez juste slurp dans certaines informations.

Answer 2

Voir 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}; 
} 

En utilisant 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)