11/12

1. Matrix -chain multiplication

A 라는 매트릭스가 p x q, B라는 매트릭스가 q x r 일때

두개의 매트릭스를 곱하면 AB = p x r 이 된다.

이떄 이 값을 구하는 비용은 pqr 이 된다.

A,B,C 매트릭스가 존재할때 각각 곱하여서 ABC를 구하고자 할떄

Ax(BxC) 와 (AxB)xC의 값은 동일하지만 계산하게 되는 비용이 다르게 된다.

A부터 각각 10 x 100  , 100 x 5 , 5 x 100 크기의 매트릭스 라고 할때

전자의 경우는

100 x 5 x 100   = 50000     , 10 x 100x 100 = 100000

50000+100000 = 150000 이라는 비용이 든다.

근데 후자의 경우

10 x 100 x 5 = 5000 ,   10 x 5 x 100 = 5000

5000 + 5000 = 10000 이라는 비용이 듬으로써 전자의 경우와 비용에서의 차이가 난다.

만약 A1 x A2 ..... An의 모든 곱을 구하려 할떄 결과는 동일하지만 가장 효율적인 비용을 가지게 찾을 필요가 있다.

M_ij =  { 0   i= j        ,    min_i<=k<j ( M_ik+ M_(k+1)j + r_i-1 x r_k x r_j ) } 라는 공식으로 구하면 된다.

 

Bellman -ford

최소 길이를 찾는 알고리즘이다.

다익스트라와 다르게 negative weight가 있어도 적용이 된다.

하지만 negative weight가 cycle로 돌게 되면 안된다.