Implementasi Algoritma Branch dan Bound

 Nama                       :    Clara Maradini              

Npm                         :    21312072        

Kelas                        :    Informatika 21 C

Matakuliah               :   Analisis dan Strategi Algoritma

Dosen Pengampu      : Ajeng Savitri Puspaningrum, M.Kom


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

Website Fakultas : ftik.teknokrat.ac.id




Algoritma Branch dan 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 :

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 : 

FIFO Branch and Bound

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

LIFO Branch and Bound

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


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. 

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


Knapsack Problem

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).

Komentar

Posting Komentar

Postingan populer dari blog ini

Sejarah Virtual Memory

Gambar
  A. Sejarah Memori  Nama : Clara Maradini  Kelas : Informatika C 21  Npm : 21312072 Website : https://spada.teknokrat.ac.id/course/index.php?categoryid=2                  http://spada.teknokrat.ac.id Perkembangan micro computer, atau yang lebih sering disebut dengan PC (Personal Computer) yang sedemikian pesat tentunya tidak lepas dari kebutuhan manusia akan informasi yang harus diolah oleh PC serta tentu saja perkembangan teknologi, khususnya teknologi perangkat keras, perangkat lunak, serta fungsi atau algoritma yang digunakan dalam memproses informasi yang diolah tersebut. Masih terbekas dalam ingatan kita akan perayaan 20 tahun PC yang jatuh pada bulan Agustus 2001 yang lalu, yang apabila kita cermati saat ini kita berada pada masa dimana PC telah menjadi bagian yang tidak dapat dipisahkan dari kehidupan kita. Jika pada awal ditemukannya, PC masih dianggap sebagai barang mahal, kini hampir semua or...
Baca selengkapnya

Perbedaan Threads dan Proses

Gambar
Nama : Clara Maradini Kelas : Informatika C 21 Npm : 21312072 Website : https://spada.teknokrat.ac.id/course/index.php?categoryid=2                  http://spada.teknokrat.ac.id Definisi Thread dan Proses serta Perbedaan nya Definisi Proses Prosesnya adalah pelaksanaan suatu program dan melakukan tindakan yang relevan yang ditentukan dalam suatu program, atau itu adalah unit eksekusi di mana suatu program berjalan. Sistem operasi membuat, menjadwalkan dan mengakhiri proses untuk penggunaan CPU. Proses lain yang dibuat oleh proses utama dikenal sebagai proses anak. Suatu operasi proses yang dikendalikan dengan bantuan PCB (Process control Block) dapat dianggap sebagai otak dari proses tersebut, yang berisi semua informasi penting mengenai suatu proses seperti id proses, prioritas, keadaan, PWS dan isi register CPU . PCB juga merupakan struktur data berbasis kernel yang menggunakan tiga jenis fungsi yaitu penjadwalan, pengir...
Baca selengkapnya

Algoritma

Nama                             :     Clara Maradini                  Npm                               :     21312072           Kelas                              :     Informatika 21 C Matakuliah                  :   Analisis dan Strategi Algoritma Dosen Pengampu       : Ajeng Savitri Puspaningrum, M.Kom Website Kampus :  https://www.teknokrat.ac.id/ Website Fakultas : ftik.teknokrat.ac.id Pengertian Algoritma Algoritma adalah metode atau langkah yang direncanakan secara tersusun dan berurutan untuk menyelesaikan atau me...
Baca selengkapnya