Implementasi Algoritma Branch and Bound
Implementasi Algoritma Branch and Bound
Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah.
Algoritma ini memiliki 2 prinsip, yaitu:
- Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching
- Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik
Teknik Algoritma Branch and Bound
Algoritma Branch and Bound dapat menggunakan beberapa titik, yaitu :1. Least Cost Branch and BoundTeknik ini akan menghitung cost dari setiap node yang ada. Node yang memilki cost terkecil diantara node lain, dianggap memiliki kemungkinan paling besar menuju solusi.Tahap :
- node yang memiliki cost terendah akan dibuka dahulu.
- pada sebuah node berlaku b ≤ c(x) ≤ u.
Keterangan :
- b adalah batas bawah.
- c(x) adalah cost dari node x.
- u adalah batas atas.
2. FIFO Branch and BoundMerupakan salah satu teknik dari Algoritma Branch and Bound yang menggunakan bantuan dari Queue untuk proses perhitungan secara First In First Out.Tahap :
- E-node dimasukkan ke dalam queue, kemudian membuat branch (cabang) selanjutnya.
- D-node tiidak dapat digunakan untuk membuat branch selanjutnya.
- Mendapatkan partial space tree (pohon) yang dicari
3. LIFO Branch and BoundMerupakan salah satu teknik dari Algoritma Branch and Bound yang menggunakan bantuan dari stack untuk proses perhitungan secara Last In First Out.Tahap :
- E-node dimasukkan ke dalam stack, kemudian membuat branch (cabang) selanjutnya.
- D-node tiidak dapat digunakan untuk membuat branch selanjutnya.
- Mendapatkan partial space tree (pohon) yang dicari
Implementasi Algoritma Branch and Bound pada permasalahan Knapsack Problem
Dengan kapasitas sebesar 16, carilah keuntungan terbesar dari setiap barang tersebut.
Rumus : awal + (P/W)max* daya angkut yang tersisamaka : 0+6*16 =96
Diperoleh 96 batas awal atau cost dari simpul awal.
Bangkitkan simpul 1, simpul 2, simpul 3, dan simpul 4. Hitung cost dari tiap simpul tersebut.
2. 12 + 5*(16-2) = 82
3. 15 + 6*(16-5) = 81
4. 50 + 6*(16-10)=86
5. 10 + 6*(16-5)=76
setelah simpul dibangkitkan, ditemukan bahwa simpul 4 memiliki cost tertinggi, sehingga simpul 4 akan diperluas untuk membuat simpul 6, 7, 8. Kemudian hitung cost dari simpul 6, 7, 8.
6. (50+12) + 3*(16-10-2) = 74
7. (50+15) + 6*(16-10-5) = 71
8. (50+10) + 6*(16-10-5) = 66
Komentar