Шесть степеней Кевина Бэкона в Perl
-
18-09-2019 - |
Вопрос
Во-первых, да, это домашнее задание для моего курса Perl.Я не ищу ответа (хотя это было бы мило).Насколько я понимаю, мне нужно использовать BFS и регулярное выражение для организации данных для использования.Мне нужно какое-то направление по этому поводу.Как использовать БФС?Использую ли я огромную стопку и просматриваю каждый ее элемент?Должен ли я использовать гигантскую хеш-таблицу?Кто-нибудь работал над этой проблемой?Как вы это сделали?Мне просто нужно какое-то направление, вот и все.Это похоже на BST?Возможно ли это без использования модуля графа?Возможно ли это с использованием хеш-значений?
Решение
Это не отвечать, но это намек на ваш ответ.
Лучше всего сначала посмотреть, что такое поиск в ширину, на графике.
Кроме того, если вам не было задано регулярное выражение, вы можете рассмотреть возможность токенизация проблема и посмотрите это.Возможно, это не понадобится.Проверьте задание и посмотрите, сможете ли вы просто хлебать в некоторой информации.
Другие советы
Видеть График.
#!/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
из проекта 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)