Perl에서 6 도의 Kevin Bacon

Question

첫째, 이것은 내 Perl 수업을위한 숙제 프로젝트입니다. 나는 대답을 찾고 있지 않습니다 (달콤하지만). 이해할 수 있듯이 사용을 위해 데이터를 구성하려면 BFS와 정규 표현식을 사용해야합니다. 나는 이것에 대한 방향이 필요하다. BFS를 어떻게 사용합니까? 거대한 스택을 사용하고 스택의 각 항목을 통과합니까? 거대한 해시 테이블을 사용해야합니까? 이 문제를 해결 한 사람이 있습니까? 어떻게 하셨나요? 방향이 모두 필요합니다. 이것은 BST와 비슷합니까? 그래프 모듈을 사용하지 않고 가능합니까? 해시 값을 사용하여 가능합니까?

Answer 1

이것은 아닙니다 대답, 그러나 그것은 당신의 대답에 대한 힌트입니다.

당신은 먼저 폭이 넓은 첫 번째 검색이 그래프에 무엇인지 찾아서 가장 잘 제공됩니다.

또한 정기적 인 표현을받지 않은 경우 다음을 고려할 수 있습니다. 토큰 화 문제를 해결하고 찾으십시오. 아마도 필요하지 않을 것입니다. 과제를 확인하고 할 수 있는지 확인하십시오 슬러프 일부 정보에서.

Answer 2

보다 그래프.

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

사용 kevin-bacon.dat 부스트 프로젝트에서 :

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)