48 lines
1.4 KiB
Perl
48 lines
1.4 KiB
Perl
use strict;
|
|
use feature 'say';
|
|
|
|
sub matrix_mult_chaining {
|
|
my(@dimensions) = @_;
|
|
my(@cp,@path);
|
|
|
|
# a matrix never needs to be multiplied with itself, so it has cost 0
|
|
$cp[$_][$_] = 0 for keys @dimensions;
|
|
|
|
my $n = $#dimensions;
|
|
for my $chain_length (1..$n) {
|
|
for my $start (0 .. $n - $chain_length - 1) {
|
|
my $end = $start + $chain_length;
|
|
$cp[$end][$start] = 10e10;
|
|
for my $step ($start .. $end - 1) {
|
|
my $new_cost = $cp[$step][$start]
|
|
+ $cp[$end][$step + 1]
|
|
+ $dimensions[$start] * $dimensions[$step+1] * $dimensions[$end+1];
|
|
if ($new_cost < $cp[$end][$start]) {
|
|
$cp[$end][$start] = $new_cost; # cost
|
|
$cp[$start][$end] = $step; # path
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
$cp[$n-1][0] . ' ' . find_path(0, $n-1, @cp);
|
|
}
|
|
|
|
sub find_path {
|
|
my($start,$end,@cp) = @_;
|
|
my $result;
|
|
|
|
if ($start == $end) {
|
|
$result .= 'A' . ($start + 1);
|
|
} else {
|
|
$result .= '(' .
|
|
find_path($start, $cp[$start][$end], @cp) .
|
|
find_path($cp[$start][$end] + 1, $end, @cp) .
|
|
')';
|
|
}
|
|
return $result;
|
|
}
|
|
|
|
say matrix_mult_chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>);
|
|
say matrix_mult_chaining(<1000 1 500 12 1 700 2500 3 2 5 14 10>);
|