Nama : Diani Widyaningrum
NPM : 21382004P
Kelas : IF 20 Dx
Mata Kuliah : Analisis dan Strategi Algoritma
Metode Branch and Bound adalah
metode umum untuk mencari solusi optimal dari berbagai permasalahan optimasi,
Prinsip kerja metode Branch and Bound adalah mencabangkan variabel keputusan
yang tidak memiliki penyelesain bulat, percabangan dilakukan terus hingga
diperoleh penyelesaian bulat sehingga semua variabel keputusannya bernilai
bulat. Metode branch and bound menggunakan salah satu metode untuk menghasilkan
penyelesaian optimal program linear yang menghasilkan variabel-variabel
keputusan bilangan bulat. Prinsip kerja metode branch and bound adalah
mencabangkan variabel keputusan yang tidak memiliki penyelesain bulat,
percabangan dilakukan terus hingga diperoleh penyelesaian bulat sehingga semua
variabel keputusannya bernilai bulat dan menghasilkan keuntungan maksimal bagi
perusahaan.
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 adalah Teknik
ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil
dikatakan memiliki kemungkinan paling besar menuju solusi.
Masalah yang dapat dipecahkan with 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
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 dari algoritma branch and bound ini adalah :
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.
AAlamat web Program studi, Fakultas, Universitas
http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id
0 komentar:
Posting Komentar