No. 202, Kota Cirebon-Jawa Barat 45134; marsani.asfi@gmail.com
Abstrak. Dalam perhitungan komputasi seringkali memanfaatkan
operasi perkalian matriks. Jenis perkalian matrik yang dilakukan
melibatkan perkalian yang berantai. Operasi perkalian matriks yang
berantai sifat operasi perkaliannya adalah asosiatif, dimana urutan
operasi yang dilakukan dapat diubah-ubah dengan bebas dan tetap tanpa
mempengaruhi hasil akhir operasi. Pilihan urutan perkalian matriks
berantai yang berbeda akan membutuhkan jumlah perkalian (usaha)
yang berbeda pula. Oleh karena itu, diperlukan urutan perkalian matriks
yang tepat, sehinggapenyelesaian perkalian matriks berantai tersebut
dapat lebih cepat dan efisien. Artikel ini akan membahas implementasi
dalam menentukan urutan perkalian matrik secara berantai dengan
penggunaan algoritma dynamic programming dalam mencari solusi
optimum urutan perkalian.Dynamic Programmingmerupakan salah satu
teknik perancangan algoritma yang dikembangkan untuk menyelesaikan
permasalahan yang sangat kompleks dengan memecah permasalahan
tersebut menjadi banyak sub-permasalahan.Hasil akhir dari
implementasi ini adalah suatu aplikasi komputer yang dapat digunakan
untuk menentukan urutan perkalian matrik yang efisien secara otomatis.
Aplikasi juga dilengkapi dengan perhitunganlangkahefektif dari
pemilihan urutan perkalian.
berantai
operations. The type of matrix chain multiplication operations that are
chain properties of multiplication operations are associative, where the
sequence of operations performed can be changed freely and permanently
without affecting the final outcome of the operation. The choice of
247
amounts of multiplication (effort). Therefore, the right matrix
multiplication sequence is needed, so that the completion of the chain
matrix multiplication can be faster and more efficient. This paper will
discuss the implementation of determining the sequence of matrix
multiplication sequentially with the use of dynamic programming
algorithms in finding the optimum solution for the multiplication
sequence. Dynamic Programming used in this article because it is one of
the algorithm design techniques in solving very complex problems
through problem solving approaches into many sub-solutions. The final
result of this implementation is a computer application that can be used
to determine the order of multiplication of efficient matrices automatically
and also equipped with the calculation of the effective steps of
multiplication sequence selection.
matrices
Dalam perkalian matrik operasi perkalian yang dilakukan antar matrik adalah
operasi perkalian yang bersifat asosiatif. Urutan perkalian antar matrik yang
satu dengan yang lainnya dapat diubah dengan bebas dan tidak akan
mempengaruhi hasil akhir operasi perkalian tersebut. Selain itu, syarat utama
perkalian antar matrik adalah jumlah kolom pada matrik pertama harus sama
dengan jumlah baris pada matriks kedua. Proses perkalian untuk beberapa
matrik merupakan perkalian yang bersifat berantai atau Matrix Chain
Multification.
Walaupun dalam urutan proses perkalian matrik yang satu dengan yang lain
bebas, penentuan urutan proses perkalian ini seringkali tidak efektif dan
memakan waktu lama. Dalam komputasi perkalian matrik, terjadi perkalian
integer dengan urut-urutan proses perkalian matrik yang berbeda akan
menghasilkan proses komputasi yang berbeda juga, cenderung lama dan
tidak efektif. Oleh karena itu, diperlukan suatu mekanisme komputasi yang
dapat digunakan untuk menentukan urutan perkalian matrik yang optimal
dari beberapa pemilihan urutan perkalian yang ada.
Metode Matrix Chain Multiplication(MCM), dapat digunakan untuk
menyelesaikan permasalahan dalam penentuan urutan rantai perkalian pada
248
beberapa matrik. Biaya komputasi yang akan dihasilkan adalah yang paling
optimum.
dibahas oleh Virnawati et. al.(2008) dan Pradana, S.A., (2012)yang membahas
tentang evaluasi kinerja algoritma MCM dan implementasinya dalam bahasa
java, serta beberapa pengujian secara analitis matematika untuk mendapatkan
solusi optimal dari perkalian matrik berantai.
Dalam artikel ini akan dipaparkan terkait implementasi dari metode MCM
dengan menggunakan bahasa pemrograman VB.Net. Aplikasi komputer yang
dibuat dapat digunakan untuk menentukan urutan perkalian matrik yang
efisien secara otomatis. Aplikasi juga dilengkapi dengan perhitungan langkah
efektif dari pemilihan urutan perkalian.
2. Tinjauan Teori
2.1. Dynamic Programming
memecahkan masalah-masalah berdasarkan hasil dari urutan pemilihan.
Dynamic Programming membagi masalah menjadi bagian-bagian yang lebih
kecil dan sederhana. Masalah-masalah yang dibagi-bagi kedalam masalah
yang sederhana selanjutnya diselesaikan. Hasil dari submasalah akan
digabungkan dengan submasalah lainnya untuk mendapatkan solusi global
dari masalah(Horowitz & Sahmi, 1979).
Ilustrasi algoritma Matrix Chain Multification(MCM) ini, misal diketahui 4
buah matrik (A,B,C dan D) dengan dimensi sebagai berikut :
a. Matrik A, dengan dimensi matrik 301
b. Matrik B, dengan dimensi matrik 140
c. Matrik C, dengan dimensi matrik 4010
d. Matrik D, dengan dimensi matrik 1025
Jika dilakukan perkalian matrik maka kemungkinan-kemungkinan
kombinasi perkalian yang muncul antara lain :
249
Dalam komputasi urut-urutan tersebut walaupun tidak mempengaruhi hasil
perkalian yang diperoleh, tapi dalam penentuan urutan perkalian akan
menghasilkan tahapan komputasi yang berbeda. Sebagai contoh, urutan
perkalian ((A.B).(C.D)) akan menghasilkan (A.B), 1200 perkalian dan (C.D),
10000 perkalian, sedangkan untuk (AB)(CD) memerlukan 30000 perkalian.
Jadi total perkalian yang diperlukan adalah 41200 langkah perkalian. Begitu
juga untuk penentuan urutan lainnya.
Untuk mendapatkan urutan perkalian yang optimal digunakanlah MCM.
Algoritma MCM dapat dikerjakan dengan 3 cara yaitu iterative (bottom up),
memorized, dan rekursif (top down). Berikut algoritma MCM :
Matrix-Chain-Order(p)
2. for i ←1 to n
3. do m[i, i] ←0
4. for l ←2 to n dimana l adalah panjang rantai.
5. do for i ←1 to n − l + 1
6. do j ←i + l − 1
7. m[i, j] ←∞
8. for k ←i to j − 1
9. do q ←m[i, k] + m[k + 1, j] + pi−1pkpj
10. if q < m[i, j]
11. then m[i, j] ←q
12. s[i, j] ←k
13 return m and s
Solusi minimum dari perkalian berantai diselesaikan dengan ketentuan
berikut :
250
[, ] = { 0 , =
≤<{[, ] + [ + 1, ] + −1 ∗ ∗ }, < (1)
3. Analisa dan Implementasi
Persoalan perkalian matriks berantai adalah dengan langkah-langkah berikut
(Cormen, et.al. 2001) : 1. Inisialisasi Dimensi Matrik, pada tahapan ini matrik dengan dimensi tertentu
disusun dalam bentuk array yang menyimpan nilai dimensinya. Sebagai contoh matrik pada bagian 2.2, disusun dalam array =
{30,1,40,10,25}. Array p ini dijadikan sebagai inisialisasi awal bersama
dengan ukuran dari indeks array p tersebut yaitu bernilai 5. 2. Rekursif Untuk Mencari Nilai Optimal, di tahapan ini dilakukan proses
rekursif untuk menentukan nilai minimal dari proses perkalian skalar.
M[i,j] sebagai array dengan indeks i dan j yang digunakan untuk
menghitung Ai,j =Ai . Ai+1 ... Aj. Proses rekursif dari m[i,j] dilakukan
dengan, ketentuan :
251
a. Jika nilai i=j maka [, ] = [, ] = 0. b. Jika nilai i < j, dengan asumsi optimal split ada dinilai k dengan i ≤k<j,
maka nilai m[i,j] ditentukan berdasarkan persamaan 1, yaitu : [, ] = [, ] + [ + 1, ] + −1 ∗ ∗ . Proses berlanjut terus
secara rekursif sampai nilai k berada i ≤ k < .
c. Nilai m[i,j] yang terpilih adalah nilai [, ]yang minimal. d. Nilai k yang menghasilkan [, ] minimal disimpan dalam array s,
dengan ketentuan [, ] = . 3. Hitung Nilai Optimal, di tahapan ini dihitung masing-masing nilai
komputasi yang optimal. 4. Susun Perkalian Berantai yang Optimal, di tahapan ini urutan perkalian
matrik berantai akan dibentuk berdasarkan nilai dari array s.
Ilustrasi analisa terlihat dalam Diagram 1.
Diagram 1. MindMap analisa MCM untuk perkalian 4 matriks
3.2. Implementasi Implementasi Perkalian matrik berantai ini menggunakan bahasa
pemrograman Visual Basic.Net (VB.Net).
252
4.1. Hasil Implementasi
Gambar 3.Tampilan Implementasi
Implementasi perangkat lunak seperti pada gambar 3 terdiri dari tiga bagian
utama, yaitu :
1. Nilai Masukkan Dimensi Matrik, bagian ini digunakan sebagai inputan
matrik yang akan digunakan sebagai perkalian berantai. Sebagai contoh
seperti matrik pada bagian 2.2.
a. Matrik A, dimensi matrik 30x1. Dimensi inputan adalah 30 dan 1
b. Matrik B, dimensi matrik 1x40. Dimensi inputan adalah 40
c. Matrik C, dimensi matrik 40x10. Dimensi inputan adalah 40
d. Matrik D, dimensi matrik 10x25. Dimensi inputan adalah 10 dan 25
2. Proses untuk mendapatkan keluaran optimal serta urutan perkalian
berantai yang optimal. Tombol PROSES berisi perintah sebagai berikut
Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles Button3.Click
Dim size As Integer
Dim pesan As String
arr(i) = CInt(strArr(i))
& " Urutan Optimalnya adalah =" &sm
Untuk modul MCM, seperti berikut ini :
Function matOrder(ByVal array() As Integer, ByVal n As Integer) As Integer
Dim i, j, q, k, length, minMul(n, n) As Integer
Dim bracket(n, n) As Integer
For i = 1 To n
minMul(i, i) = 0
For i = 1 To n - length '+ 1
j = i + length - 1
254
minMul(i, j) = q
bracket(i, j) = k
MCM.
Sub print(ByVal s(,) As Integer, ByVal i As Integer, ByVal j As Integer,
ByRef name As Char)
Dim nama As Integer
If i = j Then
'sm = sm & "A" & i
print(s, s(i, j) + 1, j, name)
sm = sm & ")"
End If
End Sub
matrik secara berantai.
Matrik Dimensi Matrik
A=30x1
B =1x40
C=40x10
D=10x25
15,10,25,50,10,20 19500 ((A(B(CD)))E)
Dari tabel 1, terlihat bahwa pengujian aplikasi untuk beberapa matrik telah
berhasil dilakukan dan menghasilkan nilai dan urutan perkalian berantai
matrik yang optimal.
Aplikasi nyata dari penggunaan algoritma perkalian matrix berantai ini sering
digunakan dalam proses perhitungan komputasi yang kompleks yang
melibatkan matrik dengan dimensi yang cukup besar. Optimasi perhitungan
yang tepat diharapkan dapat meningkatkan proses atau kinerja perhitungan,
sehingga hasil yang didapat dalam penggunaannya dapat lebih hemat
memori dan komplesitas yang lebih optimal.2\s
5. Simpulan
hasil perhitungan optimal dari perkalian matrik berantai untuk beberapa
contoh matrik.
optimal dari perkalian matrik berantai.
Daftar Pustaka
Cormen, Thomas H; Leiserson, Charles E; Rivest, Ronald L; Stein, Clifford (2001).
"15.2: Matrix-chain multiplication". Introduction to Algorithms. Second Edition.
MIT Press and McGraw-Hill. pp. 331–338. ISBN 978-0-262-03293-3.
Horowitz & Sahmi, (1979). Fundamental of Computer Algorithms. Mc-Graw Hill,
New York
Strategi Algoritma.
(http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2012-
2019
Virnawati, F., Putri, J. U., & Ernastuti, E. (2008, August). Evaluasi Kinerja
Algoritma Perkalian Matriks Berantai Dengan Teknik Dynamic Programming.
In Proceeding, Seminar Ilmiah Nasional Komputer dan Sistem Intelijen
(KOMMIT 2008). Gunadarma University.