Implementasi Algoritma Branch and Bound
Nama : Berliana
Npm : 20312133
Kelas : IF 20E
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 :
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).
Algoritma Branch & Bound(B&B)
•Digunakan untuk persoalan optimisasi →meminimalkan atau
memaksimalkan suatu fungsi objektif, yang tidak melanggar batasan(constraints)
persoalan
•B&B: BFS + least cost search–BFS murni: Simpul
berikutnya yang akan diekspansi berdasarkan urutan pembangkitannya (FIFO)
•B&B:
–Setiap
simpul diberi sebuah nilai cost: ĉ(i) = nilai taksiran lintasan termurah ke
simpul status tujuanyang melalui simpul status i.
–Simpul berikutnya yang akan di-expand tidak
lagiberdasarkan urutan pembangkitannya, tetapi simpul yang memiliki costyang
paling kecil (least cost search)
–pada kasus minimasi.
•Persamaan:
–Pencariansolusidenganpembentukanpohonruangstatus
–‘Membunuh’ simpulyang tidak‘mengarah’ kesolusi
•Perbedaan:
–
‘nature’ persoalanyang bisadiselesaikan:
•
Backtracking: Takadabatasan(optimisasi),
umumnyauntukpersoalannon-optimisasi
·
B&B:
–
Persoalan optimisasi
–
Untuk setiap simpul pada pohon
ruang-status, diperlukan suatu cara penentuan batas(bound) nilai terbaik fungsi
objektif pada setiap solusi yang mungkin, dengan menambahkan komponen pada
solusi sementara yang direpresentasikan simpul –Nilai dari solusi terbaik
sejauh ini
–
Pembangkitan simpul: ...
#
B&B vs Backtracking (2)
•Perbedaan:
–Pembangkitan simpul:
•Backtracking: umumnyaDFS
•B&B : beberapa‘aturan’ tertentu→paling
umum‘best-first rule’
“Fungsi Pembatas”
•Algoritma B&B juga menerapkan “pemangkasan”
pada jalur yang dianggap tidak lagi mengarah pada solusi.
•Kriteria pemangkasan secara umum:
–
Nilai simpul tidak lebih baik dari nilai
terbaik sejauh ini
–
Simpul tidak merepresentasikan solusi
yang ‘feasible’ karena ada batasan yang dilanggar
–
Solusi yang feasible pada simpul
tersebut hanya terdiri atas satu titik→tidak ada pilihan lain; bandingkan nilai
fungsi obyektif dengan solusi terbaik saat ini, yang terbaik yang diambil
Persoalan N-Ratu (The N-Queens Problem)
• Diberikan sebuah papan permainan yang berukuran N
X N dan N buah ratu. Bagaimanakah menempatkan N buah ratu(Q) itu pada petak-petak
papan permainan sedemikian sehingga tidak ada dua ratu atau lebih yang terletak
pada satu baris yang sama, atau pada satu kolom yang sama, atau pada satu diagonal
yang sama.
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.
Solusi 4-Ratu dengan
BFS- dengan Pembatasan (FIFO-Branch and Bound)
Strategi Pencarian
B&Buntuk4-RatudenganLeast Cost Search
• Simpul hidup yang
menjadi simpul-E(xpand) ialah simpul yang mempunyai nilai cost terkecil (least
cost search)→salah satu jenis aturan
• Untuk setiap simpul
X, nilai batas ini dapat berupa [HOR78]:
1. jumlah simpul dalam
upapohon X yang perlu dibangkitkan
sebelum simpul solusi ditemukan
2. panjang lintasan
dari simpul X ke simpul solusi terdekat (dalam upapohon X ybs)→misal ini yang
dipilih untuk persoalan 4-ratu
Solusi 4-Ratu dengan
Branch & Bound dengan Least Cost Search
•Asumsi: letak simpul
solusi diketahui (panjang lintasan solusi = 4)
•Cost simpul hidup X:
panjang lintasan dari simpul X ke simpul solusi terdekat (subpohon X). •Cost =
∞ jika tidak ada simpul solusi di subpohon tersebut.
Kunjungi Link di Bawah ini :
Komentar
Posting Komentar