Matrix

Matrix Chain MultiplicationReviewPerkalian matriks berantai (Matrix Chain Multiplication), sesuai dengannamanya, adalah perkalian dari serangkaian matriks. Operasi perkalianmatriks adalah operasi yang bersifat asosiatif, yaitu urutan operasi yangdilakukandapatdiubah-ubahdenganbebasdantetaptidakakanberpengaruh pada hasil akhir operasi.Jika kita melakukan perkalian antara dua buah matrix, syaratyangharusdipenuhiadalahbanyaknyajumlahkolompadamatrixpertamaharussamadenganjumlahbaris matrixyangkedua. Yangharus dicari jalan keluarnya dalam hal ini adalah jika kita mengalikanmatriks-matriks tersebut sesuai urutannya, proses yang dilakukan seringkali tidak efektif dan memakan waktu lama. Ini dikarenakan oleh banyaknyaoperasi perkalian integer yang dilakukan.Misalnya diberikan 2 buah matriks :A(3x5)B(5x4)Jumlah perkalian (usaha) yang diperlukan untuk mendapatkan hasilperkalian dari matriks tersebut adalah :3x5x4 = 60 perkalian.Ternyatapilihanurutanperkalianmatriksyangberbedaakanmembutuhkan jumlah perkalian (usaha) yang berbeda pula. Sehinggadenganmemilihurutanperkalianmatriksyangtepat,kitabisamenyelesaikan perkalian matriks berantai tersebut dengan lebih cepat danefisien. Karena dengan memilih urutan perkalian yang tepat, kita dapatmereduksi jumlah perkalian yang harus dilakukan untuk mendapatkan solusiakhir dari perkalian matriks berantai tersebut.Dengan menggunakan metode Matrix Chain Multiplication ini,kita dapat menyelesaikan permasalahan Bagaimana kita mendapatkan rantaiperkalian pada beberapa matrix yang akan menghasilkan biaya komputasiyang paling optimum. MCMini dapat dikerjakan dengan 3 cara yaituiterative (bottom up), memorized, dan rekursif (top down)..Table of scalar multiplications.Split indextable generated by applet.Product computed by applet.Ket gambar :Rumus mencari nilai m adalah sebagai berikut :-1. m [i,j] = 0 -Digunakan apabila indeks ke-i=ke-j2. m[i,j]=m[i,k]+m[k+1,j]+pi-1 pk pj -Digunakan apabila indeks ke-i < ke-j.TujuanMatrixChainMultiplication merupakan contoh Algoritma dariDynamic Programing di mana algoritma MCM tersebut bertujuan untukmenghasilkan biaya komputasi yang paling optimum.