Branch and Bound untuk Masalah Knapsack 0/1
Pendahuluan
Masalah Knapsack 0/1 adalah masalah optimasi klasik dalam ilmu komputer. Masalah ini melibatkan penentuan set item yang optimal untuk dimasukkan ke dalam knapsack dengan kapasitas terbatas, di mana setiap item memiliki nilai dan berat tertentu. Tujuannya adalah untuk memaksimalkan nilai total item dalam knapsack tanpa melebihi kapasitasnya.
Metode Branch and Bound adalah teknik pencarian solusi yang efektif untuk memecahkan masalah optimasi kombinatorial seperti Knapsack 0/1. Metode ini menggunakan prinsip pembagian dan menaklukkan untuk secara sistematis mengeksplorasi ruang solusi dan memotong cabang yang tidak menjanjikan.
Algoritma Branch and Bound
Algoritma Branch and Bound untuk Masalah Knapsack 0/1 melibatkan langkah-langkah berikut:
-
Inisialisasi:
- Buat pohon pencarian dengan simpul akar mewakili solusi kosong.
- Hitung nilai batas atas untuk solusi optimal, biasanya dengan menggunakan heuristik.
-
Pembangkitan Cabang:
- Pilih simpul yang belum dieksplorasi dari pohon pencarian.
- Buat dua cabang baru dari simpul terpilih:
- Cabang 1: Menambahkan item saat ini ke dalam knapsack.
- Cabang 2: Tidak menambahkan item saat ini ke dalam knapsack.
-
Penghitungan Batas Bawah:
- Untuk setiap cabang baru, hitung batas bawah nilai untuk solusi yang dapat dicapai dengan melanjutkan pencarian dari cabang tersebut.
-
Pemotongan Cabang:
- Jika batas bawah untuk cabang tertentu lebih rendah dari nilai batas atas saat ini, potong cabang tersebut karena tidak mungkin mencapai solusi yang lebih baik.
-
Pemilihan Simpul:
- Pilih simpul yang belum dieksplorasi dengan batas bawah tertinggi untuk dieksplorasi selanjutnya.
-
Pengulangan:
- Ulangi langkah 2-5 sampai semua cabang telah dieksplorasi atau solusi optimal ditemukan.
Contoh
Misalkan kita memiliki knapsack dengan kapasitas 10 dan 5 item dengan nilai dan berat sebagai berikut:
| Item | Nilai | Berat |
|---|---|---|
| 1 | 60 | 5 |
| 2 | 100 | 10 |
| 3 | 120 | 6 |
| 4 | 40 | 3 |
| 5 | 20 | 2 |
Langkah-langkah Branch and Bound:
-
Inisialisasi:
- Pohon pencarian dimulai dengan simpul akar mewakili solusi kosong.
- Batas atas diinisialisasi dengan nilai total semua item (240).
-
Pembangkitan Cabang:
- Pilih simpul akar.
- Buat dua cabang:
- Cabang 1: Tambahkan item 1 (nilai = 60, berat = 5) ke dalam knapsack.
- Cabang 2: Jangan tambahkan item 1.
-
Penghitungan Batas Bawah:
- Cabang 1: Batas bawah = 60 (nilai item 1).
- Cabang 2: Batas bawah = 0 (tidak ada item yang ditambahkan).
-
Pemotongan Cabang:
- Tidak ada cabang yang dipotong karena batas bawah keduanya lebih rendah dari batas atas.
-
Pemilihan Simpul:
- Pilih cabang 1 (batas bawah lebih tinggi).
-
Pengulangan:
- Ulangi langkah 2-5 untuk cabang 1.
- Buat dua cabang baru:
- Cabang 1.1: Tambahkan item 2 (nilai = 100, berat = 10).
- Cabang 1.2: Jangan tambahkan item 2.
- Hitung batas bawah untuk kedua cabang:
- Cabang 1.1: Batas bawah = 160.
- Cabang 1.2: Batas bawah = 60.
- Pilih cabang 1.1 (batas bawah lebih tinggi).
- Lanjutkan proses pembangkitan cabang, penghitungan batas bawah, dan pemotongan cabang hingga solusi optimal ditemukan.
Keuntungan dan Kerugian
Keuntungan:
- Dapat menemukan solusi optimal untuk masalah Knapsack 0/1.
- Lebih efisien daripada pendekatan brute force, yang memeriksa semua kemungkinan solusi.
Kerugian:
- Kompleksitas ruang dan waktu bisa tinggi, terutama untuk masalah dengan banyak item.
- Dapat sulit untuk menemukan batas bawah yang efektif untuk memangkas cabang yang tidak menjanjikan.
Kesimpulan
Metode Branch and Bound adalah teknik yang efektif untuk memecahkan Masalah Knapsack 0/1. Metode ini secara sistematis mengeksplorasi ruang solusi dan memotong cabang yang tidak menjanjikan dengan menggunakan batas bawah dan batas atas. Meskipun bisa kompleks, metode ini dapat menemukan solusi optimal untuk masalah ini.
