Jika kita melakukan perkalian antara dua buah matrix, syarat yang harus dipenuhi adalah banyaknya jumlah kolom pada matrix pertama harus sama dengan jumlah baris matrix yang kedua. Yang harus dicari jalan keluarnya dalam hal ini adalah jika kita mengalikan matriks-matriks tersebut sesuai urutannya, proses yang dilakukan sering kali tidak efektif dan memakan waktu lama. Ini dikarenakan oleh banyaknya operasi perkalian integer yang dilakukan. Misalnya diberikan 2 buah matriks :
A(2x4)
B(4x5)
Jumlah perkalian (usaha) yang diperlukan untuk mendapatkan hasil perkalian dari matriks tersebut adalah :
2x4x5 = 40 perkalian.
Ternyata pilihan urutan perkalian matriks yang berbeda akan membutuhkan jumlah perkalian (usaha) yang berbeda pula. Sehingga dengan memilih urutan perkalian matriks yang tepat, kita bisa menyelesaikan perkalian matriks berantai tersebut dengan lebih cepat dan efisien. Karena dengan memilih urutan perkalian yang tepat, kita dapat mereduksi jumlah perkalian yang harus dilakukan untuk mendapatkan solusi akhir dari perkalian matriks berantai tersebut.
Dengan menggunakan metode Matrix Chain Multiplication ini, kita dapat menyelesaikan permasalahan Bagaimana kita mendapatkan rantai perkalian pada beberapa matrix yang akan menghasilkan biaya komputasi yang paling optimum. MCM ini dapat dikerjakan dengan 3 cara yaitu iterative (bottom up), memorized, dan rekursif (top down).
Table of scalar multiplications.
Split index
table generated by applet.
Ket gambar :
- Rumus mencari nilai m adalah sebagai berikut :
1. m [i,j] = 0 Digunakan apabila indeks ke-i=ke-j
2. m[i,j]=m[i,k]+m[k+1,j]+pi-1 pk pj Digunakan apabila indeks ke-i < ke-j.
Matrix Chain Multiplication merupakan contoh Algoritma dari Dynamic Programing di mana algoritma MCM tersebut bertujuan untuk menghasilkan biaya komputasi yang paling optimum.
Sumber : “Laporan algoritma dan pemograman 2 Matrix Chain Multiplication”, sistem informasi Institut Teknologi Sepuluh November, Surabaya.
Tidak ada komentar:
Posting Komentar