Implementasi Algoritma Branch and Bound

 Pengertian Algoritma Branch and Bound

Algoritma Branch and Bound atau algoritma B&B adalah salah satu dari algoritma yang digunakan untuk menyelesaikan masalah dalam pencarian jalur. Atau suatu algoritma yang mempelajari bagaimana cara memperkecil suatu Search Tree (pohon pencarian) menjadi sekecil mungkin.

Metode ini terdiri dari 2 langkah, yaitu:

Branch (Cabang)

Membuat semua cabang dari pohon pencarian yang mungkin menuju ke solusi.

Bound (Batas)

Mencari dan menghitung node yang merupakan active node (E-node) dan node yang merupakan dead node (D-node) dengan menggunakan suatu syarat, yaitu syarat batas constraint.

Teknik Algoritma Branch and Bound

Algoritma Branch and Bound dapat menggunakan beberapa titik, yaitu :

1. Least Cost Branch and Bound

Teknik 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 Bound

Merupakan 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 Bound

Merupakan 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 tersisa

maka  : 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

https://www.teknokrat.ac.id/

http://ti.ftik.teknokrat.ac.id

http://ftik.teknokrat.ac.id