Kuliah Program Dinamis

Pengantar

• Topik: Penyelesaian persoalan dengan algoritma Program Dinamis (Dynamic Programming).
• Tujuan kuliah: Menjelaskan gambaran umum algoritma dan penyelesaian masalah dengan algoritma ini.

Apa itu Program Dinamis?

• Definisi: Metode pemecahan masalah dengan menguraikan solusi menjadi sekumpulan tahap (stages).
• Solusi masalah dianggap sebagai serangkaian keputusan yang saling berkaitan.
• Kata "program" berarti perencanaan, sedangkan "dinamis" menunjukkan pencarian solusi yang berkembang.

Aplikasi Program Dinamis

• Umumnya digunakan untuk menyelesaikan masalah optimasi.
• Contoh masalah:
  • Memaksimumkan keuntungan (contoh: masalah knapsack).
  • Meminimumkan bobot (contoh: Traveling Salesman Problem - TSP).

Perbedaan dengan Algoritma Greedy

• Algoritma Greedy: Menghasilkan satu keputusan terbaik di setiap tahap.
• Program Dinamis: Menghasilkan lebih dari satu keputusan dengan mempertimbangkan semua kemungkinan.

Prinsip Optimalitas

• Jika solusi keseluruhan optimal, maka bagian solusinya juga harus optimal.
• Contoh ilustrasi: Menggunakan hasil optimal dari tahap sebelumnya untuk menghitung ongkos tahap berikutnya.

Karakteristik Masalah yang Diselesaikan dengan Program Dinamis

1. Solusi dapat dibagi menjadi beberapa tahap, masing-masing dengan satu keputusan.
2. Masing-masing tahap memiliki satu atau lebih status yang berhubungan.
3. Hasil dari keputusan pada setiap tahap ditransformasikan ke status berikutnya.
4. Ongkos meningkat secara teratur.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap sebelumnya.
6. Hubungan rekursif untuk mengidentifikasi keputusan terbaik.
7. Optimalitas berlaku pada masalah tersebut.

Pendekatan pada Program Dinamis

• Terdapat dua pendekatan utama:
  1. Maju (Forward): Menghitung dari tahap 1 hingga N.
  2. Mundur (Backward): Menghitung dari tahap N hingga 1.

Langkah-langkah Pengembangan Algoritma Program Dinamis

1. Menentukan karakteristik dan struktur masalah.
2. Mendefinisikan formula rekursif.
3. Melakukan perhitungan menggunakan pendekatan maju atau mundur.
4. Rekonstruksi solusi dari tahap terakhir ke tahap pertama.

Contoh Masalah: Lintasan Terpendek

• Masalah: Menentukan lintasan terpendek dari simpul 1 ke simpul 10 pada graf berbobot.
• Pendekatan: Menggunakan prinsip optimalitas untuk menghitung bobot optimal dari setiap simpul.
• Hasil: Lintasan terpendek memiliki bobot total 11.

Contoh Masalah: Knapsack Problem

• Masalah: Memilih objek dengan bobot dan keuntungan tertentu sehingga total keuntungan maksimal dalam kapasitas yang diberikan.
• Pendekatan: Menentukan keputusan berdasarkan kapasitas yang tersisa setelah memasukkan objek.

Kesimpulan

• Program Dinamis adalah teknik yang kompleks namun bermanfaat untuk menyelesaikan masalah optimasi.
• Penting untuk memahami struktur masalah dan prinsip optimalitas agar dapat menerapkan algoritma ini dengan efektif.