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 :
- Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.
- Bound yang 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
Ada beberapa 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.
APA MASALAH YANG DAPAT DIPECAHKAN DENGAN BRANCH AND BOUND?????
Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree
–Traveling Salesman Problem
–N-Queen Problem
–15 Puzzle Problem
–0/1 Knapsack Problem
–Shortest Path
FIFO BRANCH AND BOUND
•Menggunakan queue
•E-node dimasukkan ke dalam queue, kemudian dibangun branch (cabang) berikutnya.
•D-node tidak digunakan untuk membangun branch berikutnya.
•Didapatkan Partial Space Tree yang dicari.
LIFO BRANCH AND BOUND
•Menggunakan stack
•E-node dimasukkan ke dalam stack, kemudian dibangun branch (cabang) berikutnya.
•D-node tidak digunakan untuk membangun branch berikutnya.
•Didapatkan Partial Space Tree yang dicari.
LEAST COST BRANCH AND BOUND
•Pada teknik FIFO dan LIFO, node dibuka sesuai urutannya
•Pada LC Branch and Bound, node yang memiliki cost terendah dibuka terlebih dulu (menjadi E-node berikutnya)
•Pada sebuah node x berlaku b ≤ c(x) ≤ u
–b adalah batas bawah
–c(x) adalah cost node x
–u adalah batas atas
•Jika terjadi b > u maka simpul x dapat dimatikan (dinyatakan sebagai D-node).
Contoh LC Branch and Bound yaitu Traveling Salesman Problem dapat dipecahkan dengan Least Cost Branch and Bound
•Langkah-langkah penyelesaian
–Gambarkan problem dengan weigthed digraph G={V,E}
–C(i,j) = nilai (cost) pada edge <i,j>, dimana C(i,j)= ∞ , jika tidak ada edge antara i dan j.
–Dengan definisi nilai (cost) di atas, bangun Cost Matrix dari TSP.
–Lakukan reduksi terhadap Cost Matrix, didapat Reduced Cost Matrix.
–Gunakan fungsi pembatas (bound), untuk membangun Search Tree dari Reduced Cost Matrix.
–Dan seterusnya hingga didapat set solusi yang diinginkan.
Sumber : azistakata.blogspot.co.id
