🚀
Desain dan Analisis Algoritma

Dynamic Programming Lanjutan

Matrix Chain · Optimal BST · Floyd–Warshall

Topik
MCM
Matrix Chain Multiplication
Topik
Optimal BST
Minimasi biaya pencarian
Topik
Floyd–Warshall
All‑Pairs Shortest Paths
Rekap Singkat DP Dasar

Syarat DP & Pola Umum

  • • **Optimal Substructure**: solusi optimal dapat dibangun dari solusi optimal submasalah. Contoh: shortest path, knapsack, LCS. [web:110][web:113][web:111]
  • • **Overlapping Subproblems**: submasalah yang sama muncul berulang dalam solusi rekursif naif (misal Fibonacci, edit distance). [web:107][web:111]
  • • Pola umum DP: pilih state → tulis recurrence → tentukan base case → implementasi top‑down (memoization) atau bottom‑up (tabulation). [web:111][web:116]
  • • Tujuan materi lanjutan: menerapkan pola ini pada problem yang lebih “matematis” dan multi‑dimensi. [web:108][web:114]
Topik 1 — Matrix Chain Multiplication

Motivasi: Mengalikan Banyak Matriks

Diberikan n matriks A₁, A₂, …, Aₙ dengan ukuran yang kompatibel, kita ingin menghitung A₁·A₂·…·Aₙ dengan **jumlah operasi perkalian skalar minimum**. [web:119][web:125]

  • • Perkalian matriks bersifat asosiatif: (A₁A₂)A₃ = A₁(A₂A₃), tetapi jumlah operasi berbeda. [web:119][web:125]
  • • Masalahnya: tentukan **urutan pembubuhan tanda kurung** (parenthesization) yang paling murah. [web:119]
  • • Contoh klasik bahwa DP bisa mengubah solusi brute force eksponensial menjadi O(nÂł). [web:125]

Representasi dimensi biasanya dengan array d[0..n] sehingga Aᵢ berukuran d[i−1] × d[i]. [web:119][web:125]

Matrix Chain — State & Recurrence

Merancang DP untuk MCM

Definisikan state: M[i, j] = minimum banyaknya multiplikasi skalar untuk menghitung Aᵢ·…·Aⱼ. [web:119][web:125]

  • • Goal: M[1, n].
  • • Basis: M[i, i] = 0 (satu matriks tidak perlu dikalikan). [web:119][web:125]
  • • Recurrence: coba semua posisi pemisahan k antara i dan j. [web:119][web:125]

Untuk i ≤ k < j:

Biaya = M[i, k] + M[k+1, j] + d[i−1]·d[k]·d[j]

M[i, j] = min0≤k<j (M[i, k] + M[k+1, j] + d[i−1]·d[k]·d[j]). [web:119][web:125]

// DP bottom-up untuk Matrix Chain Multiplication function matrixChain(d[0..n]): buat array M[1..n][1..n] berisi 0 // l = panjang chain for l ← 2 to n: for i ← 1 to n-l+1: j ← i + l - 1 M[i,j] ← ∞ for k ← i to j-1: cost ← M[i,k] + M[k+1,j] + d[i-1]*d[k]*d[j] if cost < M[i,j]: M[i,j] ← cost return M[1,n] // Kompleksitas waktu: O(n³), ruang: O(n²). [web:125]
Topik 2 — Optimal Binary Search Tree

Minimasi Biaya Pencarian

Diberikan kunci terurut K₁ < K₂ < … < Kₙ dengan probabilitas akses p₁..pₙ dan probabilitas miss (eksternal) q₀..qₙ. Tujuan: bangun BST yang meminimalkan **expected search cost**. [web:126][web:120]

  • • Setiap kunci dan dummy leaf memiliki probabilitas pencarian. [web:126]
  • • Biaya = ∑ pᾢ¡depth(Kᾢ) + ∑ q⹟¡depth(dummyâąź). [web:126][web:120]
  • • “Balanced” belum tentu optimal; kita ingin “probability‑weighted depth” minimum. [web:126][web:120]

Masalah memiliki optimal substructure dan overlapping subproblems → cocok untuk DP. [web:126][web:120]

Optimal BST — State & Recurrence

Merancang DP untuk Optimal BST

Definisi state klasik (mengikuti CLRS):

  • • e[i, j] = biaya expected minimum dari subtree yang berisi kunci Kᾢ..Kâąź. [web:126][web:120]
  • • w[i, j] = total probabilitas pᾢ..pâąź dan qᵢ₋₁..qâąź. [web:126][web:120]

Basis:

  • • e[i, i−1] = qᵢ₋₁ (subtree kosong di antara kunci). [web:126]
  • • w[i, i−1] = qᵢ₋₁. [web:126]

Recurrence untuk 1 ≤ i ≤ j ≤ n:

e[i, j] = minᵢ≤r≤ⱼ ( e[i, r−1] + e[r+1, j] ) + w[i, j]. [web:126][web:120]

Intuisi: pilih setiap Kᾣ sebagai root, jumlahkan biaya subtree kiri & kanan, tambah total probabilitas sebagai kenaikan kedalaman. [web:126][web:120]

// Sketsa DP bottom-up untuk Optimal BST for i ← 1 to n+1: e[i, i-1] ← q[i-1] w[i, i-1] ← q[i-1] for l ← 1 to n: // panjang interval kunci for i ← 1 to n-l+1: j ← i + l - 1 e[i, j] ← ∞ w[i, j] ← w[i, j-1] + p[j] + q[j] for r ← i to j: cost ← e[i, r-1] + e[r+1, j] + w[i, j] if cost < e[i, j]: e[i, j] ← cost // e[1, n] = biaya expected minimum BST optimal // Waktu: O(n³), ruang: O(n²). [web:126][web:120]
Topik 3 — Floyd–Warshall

All‑Pairs Shortest Paths dengan DP

Floyd–Warshall menghitung jarak terpendek antara setiap pasangan simpul dalam graf berarah berbobot (bisa bobot negatif tanpa siklus negatif). [web:124][web:127]

Ini contoh DP dengan tiga indeks (i, j, k), dimana k menyatakan “boleh menggunakan simpul 1..k sebagai simpul perantara”. [web:124][web:127]

State & Recurrence

  • • dᵏ[i][j] = jarak terpendek dari i ke j yang hanya boleh menggunakan simpul {1..k} sebagai intermediate. [web:124][web:127]
  • • Basis: d⁰[i][j] = bobot edge langsung i→j (atau ∞ jika tidak ada), dan d⁰[i][i] = 0. [web:124]
  • • Recurrence untuk k ≥ 1: dᵏ[i][j] = min(dᵏ⁻¹[i][j], dᵏ⁻¹[i][k] + dᵏ⁻¹[k][j]). [web:124][web:127]

Implementasi biasanya melakukan pembaruan in‑place pada matriks jarak dengan tiga loop bersarang (k, i, j). [web:124]

Floyd–Warshall — Pseudocode & Analisis

Implementasi Singkat

// Floyd–Warshall untuk all-pairs shortest paths function floydWarshall(dist[0..n-1][0..n-1]): // dist[i][j] diinisialisasi dengan bobot edge i→j, atau ∞ // dist[i][i] = 0 for k ← 0 to n-1: for i ← 0 to n-1: for j ← 0 to n-1: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] ← dist[i][k] + dist[k][j] return dist // Kompleksitas waktu: O(n³), ruang: O(n²). [web:124][web:127]

Kaitan dengan DP

  • • DP di atas “jumlah simpul perantara yang boleh digunakan”. [web:124][web:127]
  • • Optimal substructure: jika jalur terpendek i→j lewat k, maka bagian i→k dan k→j juga jalur terpendek dengan himpunan simpul perantara yang lebih kecil. [web:124][web:127]
  • • Overlapping: banyak pasangan (i, j) diupdate berkali‑kali ketika menambah simpul perantara baru. [web:124][web:127]

Floyd–Warshall menunjukkan bahwa DP tidak selalu “array 1D/2D sederhana”; kadang indeks state mewakili dimensi yang abstrak seperti “tahap”. [web:127]

Ringkasan Kompleksitas

Perbandingan Tiga Problem DP Lanjutan

Problem State Recurrence Waktu Ruang
Matrix Chain Multiplication M[i, j] M[i, j] = minₖ (M[i, k] + M[k+1, j] + d[i−1]d[k]d[j]) [web:119][web:125] O(n³) O(n²)
Optimal BST e[i, j], w[i, j] e[i, j] = minᵣ ( e[i, r−1] + e[r+1, j] ) + w[i, j] [web:126][web:120] O(n³) O(n²)
Floyd–Warshall d[i, j] (implisit dᵏ) d[i, j] = min(d[i, j], d[i, k] + d[k, j]) [web:124][web:127] O(n³) O(n²)
Kesimpulan

Dari DP Dasar ke DP Lanjutan

Problem lanjutan seperti Matrix Chain, Optimal BST, dan Floyd–Warshall menunjukkan bahwa desain state dan recurrence yang tepat memungkinkan kita memecahkan problem optimisasi yang semula tampak sulit dengan kompleksitas polinomial O(n³).

🧠
Abstraksi
Berpikir dalam bentuk interval (i, j) atau “tahap k” memperkaya intuisi DP.
📐
Desain
Fokus pada definisi state yang tepat sebelum menulis kode.
🧪
Latihan
Semakin kompleks problem, semakin penting latihan merancang DP sendiri.
1 / 10