ALGORITMA BRANCH and BOUND

Nama      : Fajar Romadhon
NPM      : 20312091
Kelas      : IF20C

Implementasi Algoritma Branch and Bound

Metode Branch and Bound

Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

1. Branch artinya membangun semua cabang tree yang mungkin menuju solusi.

2. Bound artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).

Teknik Branch and Bound

Berikut adalah teknik dalam Branch and Bound yaitu :

1. FIFO Branch and Bound

adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch and Bound secara First In First Out.

2. LIFO Branch and Bound

adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.

3. Least Cost Branch and Bound

teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi.

Knapsack Problem Branch and Bound

Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang dimana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum. Penyelesaian masalah dengan menggunakan algoritma exhaustive search adalah mengenumerasikan semua kemungkinan barang-barang yang layak atau memenuhi syarat yaitu tidak melebihi batas daya angkut gerobak untuk dijual setiap harinya , kemudian menghitung tiap-tiap keuntungan yang diperoleh dan memilih solusi yang menghasilkan keuntungan terbesar.

Berbeda dengan algoritma exhaustive search yang cukup memakan waktu dan dapat menghasilkan solusi yang optimum, penyelesaian masalah dengan menggunakan algoritma greedy dilakukan dengan memasukan objek satu persatu kedalam gerobak dan tiap kali objek tersebut telah dimasukan kedalam gerobak maka objek tersebut tidak dapat lagi dikeluarkan dari gerobak. Pencarian solusi akan dilakukan dengan memilih salah satu jenis greedy (greedy by weight, greedy by profiit or greedy by density) yang diperkirakan dapat menghasilkan solusi yang optimum. Algoritma Branch and Bound juga merupakan salah satu strategi yang dapat digunakan dalam pencarian solusi optimum dari permasalahan knapsack ini.

Algoritma Branch and Bound

Sebagaimana pada algortima runut-balik, algoritma Branch & Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang Solusi diorganisasikan ke dalam pohon ruang status. Pembentukan pohon ruang status. Pembentukan pohon ruang status pada algoritma B&B berbeda dengan pembentukan pohon pada algoritma runutbalik. Bila pada algoritma runut-balik ruang solusi dibangun secara Depth-First Search(DFS), maka pada algoritma B&B ruang solusi dibangun dengan skema Breadth-First Search (BFS).

Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost). Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Pada prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan. Fungsi heuristik untuk menghitung taksiran nilai tersebut dinyatakan secara umum sebagai :

(i) = (i) + (i)

yang dalam hal ini,

(i) = ongkos untuk simpul i

(i) = ongkos mencapai simpul i dari akar

(i) = ongkos mencapai simpul tujuan dari simpul akar i (perkiraan)

Nilai digunakan untuk mengurutkan pencarian. Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki minimum (Simpul-E). Strategi memilih simpul-E seperti ini dinamakan strategi pencarian berdasarkan biaya terkecil (least cost search).

Prinsip Algoritma Branch and Bound

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Stop.

2. Jika Q kosong, tidak ada solusi . Stop.

3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai (i) paling kecil. Jika terdapatbeberapa simpul i yang memenuhi, pilih satusecara sembarang.

4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak-anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2.

5. Untuk setiap anak j dari simpul i, hitung (j), dan masukkan semua anak-anak tersebut ke dalam antrian Q.

6. Kembali ke langkah 2.

Jangan Lupa Kunjungi Link di Bawah ini J

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

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

http://ftik.teknokrat.ac.id