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