contemporary algorhythm 03

行列のかけ算

3つの行列の積

5つの行列の積

かけ算をする順序によって、かけ算をする回数がかわってくる。

樹形図で、かける順序の場合分けをする。
重複するかけ算の順序は、繰り返し、計算することをさけるようにする。

3 5

5 2

2 4

4 6

6 3

の行列

縦横のテーブルを書いて、
2個の行列のかけ算の回数 作業1
3個の行列のかけ算の回数 作業2
4個の行列のかけ算の回数を 作業3
書いていく。
それぞれの升目で、一番、かけ算の作業が少ない順序を選び取っていく。

作業2で、作業1の計算作業を使う。
作業3で、作業2の計算作業を使う。

backtrack & local search
exponential speed up
eaqual partition

数列をとりあげる

ふたつの集合にわける

それぞれの集合の部分集合を書き出す

要素1こ
要素2こ
要素3こ
要素0こ
80 20 53 62 5 15