contemporary algorhythm 03

行列のかけ算

３つの行列の積

５つの行列の積

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

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

3 5

5 2

2 4

4 6

6 3

の行列

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

作業２で、作業１の計算作業を使う。
作業３で、作業２の計算作業を使う。

backtrack & local search
exponential speed up
eaqual partition

数列をとりあげる

ふたつの集合にわける

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

要素１こ
要素２こ
要素３こ
要素０こ
８０　２０　５３　６２　５　１５