Artikel ini menjelaskan algoritma Java Matrix Multiplikasi (Dynamic Programming). Bagikan untuk referensi Anda, sebagai berikut:
Deskripsi Masalah: Diberikan N matriks: A1, A2, ..., An, di mana AI dan AI+1 dikalikan, i = 1, 2 ..., n-1. Tentukan urutan perhitungan menghitung matriks produk kontinu, sehingga jumlah perkalian yang diperlukan untuk menghitung matriks produk kontinu dalam urutan ini adalah yang paling sedikit. Data input adalah jumlah matriks dan ukuran masing -masing matriks, dan hasil output adalah urutan perhitungan dan jumlah minimum multiplikasi untuk produk kontinu dari matriks.
Analisis Masalah: Karena multiplikasi matriks memenuhi hukum asosiasi, mungkin ada banyak perintah perhitungan yang berbeda untuk menghitung produk kontinu dari matriks. Pesanan perhitungan ini dapat ditentukan dengan menambahkan kurung. Jika urutan perhitungan produk kontinu matriks sepenuhnya ditentukan, yaitu, produk kontinu telah sepenuhnya dikurung, maka algoritma standar untuk multiplikasi dua matriks dapat berulang kali dipanggil dalam urutan ini untuk menghitung produk kontinu matriks.
Produk matriks yang benar -benar diarahkan dapat ditentukan secara rekursif sebagai:
(1) matriks tunggal sepenuhnya dikurung;
(2) Produk matriks A sepenuhnya dikurung, kemudian dapat direpresentasikan sebagai produk dari 2 produk matriks yang benar -benar kurung B dan C dan tanda kurung yang ditambahkan, yaitu A = (BC)
Misalnya, ada 5 cara berbeda untuk sepenuhnya meng -braket produk matriks A1A2A3A4: (A1 (A2 (A3A4))), (A1 ((A2A3) A4)), ((A1A2) (A3A4)), ((A1 (A2A3)) A4). Setiap metode bracketing sepenuhnya sesuai dengan urutan perhitungan produk yang terhubung dengan matriks, yang menentukan jumlah perhitungan yang diperlukan untuk membuat produk.
Lihat contoh berikut, hitung tiga multiplikasi matriks {a1, a2, a3}; Dimensi masing -masing adalah 10*100, 100*5, 5*50. Hitung jumlah kali yang diperlukan dalam urutan ini ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 kali, hitung jumlah kali yang diperlukan dalam urutan ini (A1*(A2*A3)): 10*5*50+10*100*50 = 75000 kali
Jadi pertanyaannya adalah: bagaimana menentukan urutan operasi sehingga jumlah perhitungan dapat diminimalkan.
Ide Algoritma:
Contoh: Misalkan Anda ingin menghitung produk multiplikasi matriks a1a2a3a4a5a6, di mana dimensi masing -masing matriks adalah:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
Hubungan Rekursif:
Perhitungan desain A [i: j], 1≤i≤j≤n, dan jumlah minimum perkalian yang diperlukan m [i, j], maka nilai optimal dari masalah asli adalah m [1, n].
Ketika i = j, a [i: j] = ai, oleh karena itu, m [i] [i] = 0, i = 1,2,…, n
Ketika saya <j, jika urutan optimal dari [i: j] terputus antara AK dan AK+1, i <= k <j, maka: m [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. Karena posisi titik pemutusan k tidak diketahui selama perhitungan, k belum ditentukan. Namun, hanya ada Ji yang mungkin untuk posisi k. Oleh karena itu, k adalah posisi di mana posisi JI meminimalkan jumlah perhitungan.
Singkatnya, ada hubungan rekursif sebagai berikut:
Bangun solusi optimal:
Jika posisi pemutusan k dari m [i] [j] dilambangkan sebagai s [i] [j], setelah menghitung nilai optimal m [i] [j], solusi optimal yang sesuai dapat dibangun secara rekursif dari S [i] [j]. Angka dalam S [i] [j] menunjukkan bahwa cara terbaik untuk menghitung rantai matriks A [i: j] harus terputus antara matriks AK dan AK+1, yaitu, tanda kurung optimal harus (A [i: k]) (a [k+1: j). Oleh karena itu, dari informasi yang dicatat oleh S [1] [n], kita dapat melihat bahwa tanda kurung optimal untuk menghitung [1: n] adalah (a [1: s [1] [n]]) (a [1] [n] +1: n]). Lebih lanjut secara rekursif, tanda kurung optimal untuk A [1: S [1] [S [1] [S [1] [n]]) adalah (a [S [1] [S [1] [n]]+1: S [1] [S [1] [S [1] [S [1] [n]]). Demikian pula, dapat ditentukan bahwa tanda kurung optimal dari [S [1] [n] +1: n] rusak pada s [1] [n] +1] [n] ... jika kita terus mengulangi ini, kita akhirnya dapat menentukan tanda kurung lengkap yang optimal dari [1: n] dan membangun solusi optimal untuk masalah.
matriks paket; matriks kelas publik {public static void matrixchain (int [] p, int n, int [] [] m, int [] [] s) {for (int i = 1; i <= n; i ++) {m [i] [i] = 0; } untuk (int r = 2; r <= n; r ++) {for (int i = 1; i <= n-r+1; i ++) {int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; s [i] [j] = i; untuk (int k = i+1; k <j; k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; if (t <m [i] [j]) {m [i] [j] = t; s [i] [j] = k; }}}}} public static void traceback (int i, int j, int [] [] s) {if (i == j) return; Traceback (i, s [i] [j], s); Traceback (s [i] [j] + 1, j, s); System.out.println ("Gandakan" + i + "," + S [i] [j] + "dan A" + (s [i] [j] + 1) + "," + j); } public static void main (string [] args) {System.out.println ("Hasil tes wulin.com:"); Matriks mc = matriks baru (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = int int [n] [n]; int s [] [] = int int [n] [n]; int l = p.length-1; mc.matrixchain (p, l, m, s); untuk (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (m [i] [j]+"/t"); } System.out.println (); } System.out.println (); untuk (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (s [i] [j]+""); } System.out.println (); } mc.traceback (1, 6, s); }}Hasil Menjalankan:
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.