Matrix Chain Multiplication
Rangkaian matriks dijelaskan oleh dims: matriks i memiliki dims[i] baris dan dims[i+1] kolom, sehingga setiap matriks cocok dikalikan dengan matriks berikutnya. Mengalikan matriks p × q dengan matriks q × r memerlukan p × q × r perkalian skalar dan menghasilkan matriks p × r. Setiap cara menempatkan tanda kurung menghasilkan hasil kali akhir yang sama, tetapi biayanya berbeda. Kembalikan jumlah perkalian skalar paling sedikit yang diperlukan untuk mengalikan seluruh rangkaian.
Fungsi
- dimsinteger-array
- ukuran sepanjang rantai: matriks i berukuran dims[i] × dims[i+1]
- Mengembalikaninteger
- jumlah perkalian skalar paling sedikit untuk mengalikan seluruh rantai
Batasan
2 ≤ dims.length ≤ 100, jadi rantai tersebut terdiri dari 1 hingga 99 matriks.1 ≤ dims[i] ≤ 100- Jawabannya paling banyak 98 × 106, jauh di dalam rentang bilangan bulat bertanda 32-bit.
Contoh
- Input
- dims = [4, 10, 3, 12]
- Output
- 264
- Penjelasan
- Mengalikan dua biaya pertama menghasilkan 4 × 10 × 3 = 120 dan menyisakan matriks 4 × 3, yang dikalikan dengan matriks 3 × 12 menambah biaya sebesar 144: totalnya 264. Urutan lainnya membutuhkan biaya 360 + 480 = 840.
- Input
- dims = [6, 2, 7, 3, 5]
- Output
- 132
- Penjelasan
- Kalikan 2 × 7 dengan 7 × 3 (42), hasil 2 × 3 dengan 3 × 5 (30), lalu 6 × 2 dengan hasil 2 × 5 (60): totalnya 132.
- Input
- dims = [3, 7]
- Output
- 0
- Penjelasan
- Hanya ada satu matriks, 3 × 7, jadi tidak ada perkalian dan biayanya 0.
Pertanyaan lanjutan
Bisakah kamu juga menghitung berapa banyak tanda kurung yang berbeda yang menghasilkan biaya minimum?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Lupakan perkalian pertama dan pikirkan perkalian terakhir. Urutan apa pun yang kamu pilih, langkah terakhir mengalikan hasil kali dari bagian kiri rantai dengan hasil kali dari sisanya.
Hasil perkalian matriks di antara dua batas
leftdanrightselalu berupa matriksdims[left] × dims[right]. Jadi, jika langkah terakhir membagi rentang tersebut di batassplit, biayanya adalahdims[left] × dims[split] × dims[right], dan kedua bagiannya merupakan versi lebih kecil dari masalah yang sama.Simpan cara termurah untuk mengalikan matriks di antara batas
leftdanrightdalambest[left][right](0 untuk satu matriks). Nilai ini adalah nilai minimum daribest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]untuk setiapsplityang berada tepat di antara keduanya. Hitung rentang yang sempit sebelum rentang yang lebar.
Solusi
Urutannya mengubah biayanya: 264 dibandingkan dengan 840 pada contoh pertama. Perhatikan perkalian terakhir. Perkalian itu menggabungkan hasil kali dari bagian kiri dan bagian kanan rantai, dan setiap bagian merupakan masalah yang sama pada rantai yang lebih pendek. Sebuah tabel untuk rentang rantai menyelesaikan setiap masalah satu kali, dalam waktu O(n³).
Coba setiap pembagian dengan rekursi biasa
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Beri nomor pada batas rantai dari 0 hingga m-1, dengan m = dims.length: batas k memiliki ukuran dims[k]. Matriks di antara batas left dan right jika dikalikan akan menghasilkan matriks berukuran dims[left] × dims[right], dalam urutan apa pun. Jadi, jika langkah terakhir membagi rentang itu pada split, biayanya adalah dims[left] × dims[split] × dims[right], apa pun yang terjadi di dalam kedua blok. Setiap blok harus dibuat dengan biaya serendah mungkin, jadi cheapest(left, right) adalah jumlah terkecil dari biaya kedua blok ditambah biaya langkah terakhir tersebut, di antara semua split. Mencoba setiap kemungkinan langkah terakhir membuatnya benar.
Fungsi ini menyelesaikan rentang yang sama berulang kali: n matriks membutuhkan 3^(n-1) pemanggilan, sekitar 1.2 × 10^9 untuk 20 matriks, padahal hanya ada sekitar m²/2 rentang yang berbeda.
Algoritma
- Tulis
cheapest(left, right)untuk matriks di antara batasleftdanright. - Jika
right - left < 2, hanya ada satu matriks: kembalikan 0. - Untuk setiap
splityang berada di antaranya, tambahkancheapest(left, split),cheapest(split, right), dandims[left] × dims[split] × dims[right]. - Kembalikan jumlah terkecil.
- Jawabannya adalah
cheapest(0, m-1).
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)Rekursi dengan memo
Intuisi
Satu pemanggilan hanya bergantung pada left dan right. Simpan hasilnya di memo[left][right], dengan setiap sel dimulai dari -1, nilai yang tidak mungkin menjadi biaya nyata, lalu pemanggilan berikutnya membaca sel tersebut alih-alih melakukan rekursi. Setiap pasangan dari sekitar m²/2 pasangan diselesaikan satu kali dengan kurang dari m pemisahan: O(n³), atau 161,700 pemeriksaan pemisahan untuk 99 matriks. Rekursi tidak pernah lebih dalam daripada panjang rantainya, jadi 100 batas muat di tumpukan pemanggilan mana pun.
Algoritma
- Alokasikan
memodenganmbaris danmkolom, setiap sel bernilai -1. - Di
cheapest(left, right), rentang yang terdiri dari satu matriks mengembalikan 0, dan sel yang bukan -1 mengembalikan biaya yang tersimpan. - Jika tidak, hitung biaya setiap
splitpersis seperti yang dilakukan rekursi biasa, lalu ambil nilai minimum. - Simpan nilai minimum tersebut ke dalam
memo[left][right]sebelum mengembalikannya. - Jawabannya adalah
cheapest(0, m-1).
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)Isi tabel agar lebarnya membentang
Intuisi
Setiap sel hanya bergantung pada rentang yang lebih sempit, jadi perulangan dapat mengisi best[left][right] dari rentang yang sempit ke yang lebar. Lebar 1 adalah satu matriks dan nilainya tetap 0; saat kamu mencapai rentang yang lebih lebar, kedua bagian dari setiap pemisahan sudah dihitung. Dengan dims = [6, 2, 7, 3, 5]:
- Lebar 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Lebar 3:
best[0][3]bernilai 78 (pemisahan 1: 0 + 42 + 36),best[1][4]bernilai 72 (pemisahan 3: 42 + 0 + 30). - Lebar 4: pemisahan 1, 2, dan 3 menghasilkan 0 + 72 + 60 = 132, 84 + 105 + 210 = 399, dan 78 + 0 + 90 = 168, jadi
best[0][4] = 132.
Pemisahan teratas pada batas 1 berarti matriks 6 × 2 digabungkan terakhir, seperti pada contoh kedua. Waktu dan memorinya sama dengan versi memo, tanpa rekursi.
Algoritma
- Tetapkan
m = dims.lengthdan alokasikan tabelm × mbernamabestyang berisi nol. - Lakukan perulangan
widthdari 2 sampaim-1. Di dalamnya, lakukan perulanganleftke atas dari 0 selamaright = left + widthmasih berada dalam batas. - Untuk rentang tersebut, hitung
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]untuk setiapsplitdarileft+1sampairight-1, lalu simpan nilai minimum dalambest[left][right]. - Jawabannya ada di
best[0][m-1].
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
Jebakan dan kasus tepi
- Mengalikan pasangan dengan biaya termurah terlebih dahulu. Untuk
[10, 10, 1, 9], pasangan terakhir memiliki biaya termurah (90), tetapi langkah setelahnya memerlukan biaya 900, sehingga totalnya 990. Mengambil pasangan pertama terlebih dahulu memerlukan biaya 190. - Membaca jawaban dari sel yang salah.
dimsmemiliki satu entri lebih banyak daripada jumlah matriks, jadi jawabannya adalahbest[0][m-1], bukanbest[0][m]. - Mengulang
leftke atas dalam perulangan luar. Barisleftkemudian membacabest[split][right]dari baris berikutnya yang masih bernilai 0. Letakkan lebar dalam perulangan luar, atau hitungleftmundur. - Melewatkan kasus satu matriks.
[3, 7]harus mengembalikan 0, dan di R, perulangan2:(m-1)menjadi2:1dan berjalan mundur, jadi tambahkan pemeriksaan.
Pertanyaan yang sering diajukan3
Apa kompleksitas waktu perkalian rantai matriks?
Tabel memiliki sekitar n²/2 rentang dan masing-masing mencoba hingga n pemisahan, sehingga pemrograman dinamis berjalan dalam waktu O(n³) dengan memori O(n²). Rekursi biasa tanpa memo membuat 3^(n-1) pemanggilan untuk n matriks.
Mengapa urutan perkalian matriks penting?
Perkalian matriks bersifat asosiatif, jadi (AB)C dan A(BC) menghasilkan matriks yang sama, tetapi ukuran matriks perantaranya berbeda. Pada contoh pertama, (AB)C membentuk matriks 4 × 3 dan memerlukan biaya 264, sedangkan A(BC) membentuk matriks 10 × 12 dan memerlukan biaya 840.
Bagaimana cara menemukan susunan tanda kurung yang optimal?
Simpan pemisahan terbaik di choice[left][right] di samping best[left][right]. Untuk mencetaknya, satu matriks mencetak namanya; rangkaian yang lebih panjang mencetak tanda kurung buka, bagian hingga choice[left][right], bagian setelahnya, lalu tanda kurung tutup. Ini menambah penggunaan memori sebesar O(n²).
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def matrixChainOrder(dims):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
dims = [4, 10, 3, 12]
Output yang diharapkan
264