Langsung ke konten utama

Implementasi Algoritma Branch & Bound Pada Masalah Knapsack

 

 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

Jangan Lupa Kunjungi :

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

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

http://ftik.teknokrat.ac.id 

Komentar

Posting Komentar

Postingan populer dari blog ini

Implementasi Algoritma Divide And Conquer Pada Sorting Dan Searching

1.   Implementasi Algoritma Divide and Conquer Merge sort Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama. Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah. 1. Divide     Memilah masalah menjadi sub masalah 2. Conquer     Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif 3. Kombinasi     Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas permasalahan utama Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkahberpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort. 1. Divide   ...
Posting Komentar
Baca selengkapnya

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

    1.          Sejarah Algoritma Devide and Conquer             Awal dari algoritma ini utamanya adalah pengurangan dan penaklukan - masalah       asli secara berturut-turut dipecah menjadi sub-masalah tunggal, dan memang dapat          diselesaikan secara berulang. Pencarian biner, algoritma penurunan-dan-taklukkan di mana sub-masalah berukuran kira-kira setengah dari ukuran aslinya, memiliki sejarah yang panjang. Sementara deskripsi yang jelas tentang algoritma pada komputer muncul pada tahun 1946 dalam sebuah artikel oleh John Mauchly, gagasan untuk menggunakan daftar item yang diurutkan untuk memfasilitasi pencarian tanggal kembali setidaknya sejauh Babylonia pada 200 SM. Algoritma penurunan-dan-taklukkan kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi...
Posting Komentar
Baca selengkapnya