1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#!/usr/bin/perl -w
# Matrix chain multiplication
# Author: Chao-Kuei Hung http://www.cyut.edu.tw/~ckhung
# License: GPL
#
# This program is part of algotutor. Yet it can also run as a
# stand-alone text mode program that requires no other modules.
# When used as a stand-alone program, it requires as a list
# of arguments alternating numbers and matrix names, like this:
# matrixchain -e ansi 32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35
my (@name, $best);
sub print_expr {
my ($i, $j) = @_;
if ($i >= $j) {
print($name[$i]);
} else {
print("(");
print_expr($i,$best->[$i][$j]{cut});
print(" * ");
print_expr($best->[$i][$j]{cut}+1,$j);
print(")");
}
}
sub matrixchain {
my ($chain, $can) = @_;
my (@dim, $show, $left, $size, $i, $expr);
my ($cell) = sub { return $show->cell(
($_[0]+1) % ($#name+2), ($_[1]+$#name+2) % ($#name+2)
); };
while ($#$chain > 0) {
my ($d, $n) = splice @$chain, 0, 2;
print " $n:${d}x$chain->[0]";
push @dim, $d;
push @name, $n;
}
print "\n";
push @dim, @$chain;
if (ref $can) {
$show = Board->new(-canvas=>$can, -width=>$#name+2, -height=>$#name+2,
-node_opts=>{ -size=>Vector->new(50,40), -shape=>"rectangle" } );
map { $cell->(-1,$_)->configure(-text=>$name[$_], -status=>"done"); } 0..$#name;
map { $cell->($_,-1)->configure(-text=>$name[$_], -status=>"done"); } 0..$#name;
$expr = $can->createText(@{ $show->rc2xy($#name+2, int(($#name+1)/2) ) },
-justify=>"center", -text=>"expr");
}
for ($left=0; $left<=$#name; ++$left) {
$best->[$left][$left] = { val => 0 };
if (ref $can) {
$cell->($left,$left)->configure(-text=>0, -status=>"done");
for ($i=$left+1; $i<=$#name; ++$i) {
$cell->($i,$left)->configure(-status=>"hidden");
}
}
}
$can->set_mark(2) if ref $can;
for ($size=1; $size<=$#name; ++$size) {
for ($left=0; $left<=$#name-$size; ++$left) {
$cell->($left,$left+$size)->configure(-text=>"?", -status=>"focus")
if ref $can;
my ($s, $t);
$best->[$left][$left+$size] = { val => 1e99 };
for ($i=0; $i<$size; ++$i) {
$s = $best->[$left][$left+$i]{val} . " + " .
$best->[$left+$i+1][$left+$size]{val} . " + " .
$dim[$left] . " * " .
$dim[$left+$i+1] . " * " .
$dim[$left+$size+1];
$t = eval $s;
if (ref $can) {
$can->itemconfigure($expr, -text=>"$t = $s");
$cell->($left, $left+$i)->configure(-status=>"focus");
$cell->($left+$i+1, $left+$size)->configure(-status=>"focus");
if ($i >= 1) {
$cell->($left, $left+$i-1)->configure(-status=>"done");
$cell->($left+$i, $left+$size)->configure(-status=>"done");
}
$can->set_mark(1);
}
if ($t < $best->[$left][$left+$size]{val}) {
$best->[$left][$left+$size] = { val=>$t, cut=>$left+$i };
}
}
if (ref $can) {
$t = $best->[$left][$left+$size];
$t = $t->{val} . "\n" . $name[$t->{cut}] . "|" . $name[$t->{cut}+1];
$cell->($left,$left+$size)->configure(-text=>$t, -status=>"done");
$can->itemconfigure($expr, -text=>"");
$cell->($left, $left+$size-1)->configure(-status=>"done");
$cell->($left+$size, $left+$size)->configure(-status=>"done");
$can->set_mark(2);
}
}
}
for ($i=1; $i<=$#name; ++$i) {
printf " %2s ", $name[$i];
}
print "\n";
for ($left=0; $left<$#name; ++$left) {
print " " x $left;
for ($i=$left+1; $i<=$#name; ++$i) {
my ($t) = sprintf "%d:%s|%s",
$best->[$left][$i]{val},
$name[$best->[$left][$i]{cut}],
$name[$best->[$left][$i]{cut}+1];
printf "%11s", $t;
}
print " $name[$left]\n";
}
print_expr(0, $#name);
print "\n";
}
if ($0 =~ /matrixchain$/) {
my ($chain) = $#ARGV >= 0 ? \@ARGV :
[qw(32 A 35 B 24 C 30 D 36 E 25 F 40 G 34 H 35)];
matrixchain($chain);
}
1;
|
