Implementasi Algoritma Branch and 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)

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.

Knapsack Problem Solve

Untuk lebih memahami tahap-tahap penyelesaian permasalahan knapsack ini, kita ambil contoh persoalan seperti yang dituliskan pada bagian Abstrak yaitu dimana seorang pedagang keperluan rumah tangga keliling harus memilih barang-barang yang akan dijual setiap harinya dengan batas daya angkut gerobak yang dimilikinya. Untuk mempermudah, kita misalkan pedagang keliling tersebut hanya memiliki 4 jenis barang untuk dijual dengan berat dan keuntungan penjualan yang berbeda-beda untuk tiap jenisnya.

Gerobak yang akan dipakai untuk mengangkut barang-barang tersebut hanya mampu menampuk beban seberat 16 kg. Berikut merupakan tebel penggambaran beratdan keeuntungan yang akan diperoleh untuk tiap penjualan barang tersebut.

dari tiap tiap simpul anak untuk dapat menentukan simpul mana yang kelak akan dibangkitkan yaitu simpul dengan cost tertinggi dalam penelusuran pohon unutk mencapai solusi dari permasalahan ini. Dalam permasalahan ini, kita akan mencari simpul-simpul yang akan membawa kita pada keuntungan terbesar oleh karena itu urutan pembangkitan simpul akan ditentukan oleh simpul mana yang memiliki cost tertinggi. Cost dari tiap simpul akan ditentukan dengan:

(i) = (i) + (i)
yang dalam hal ini,

(i) = cost untuk simpul i

(i) = cost untuk sampai ke simpul I, dalam hal ini merupakan keuntungan dari simpul akar ke simpul i

(i) = cost dari simpul i untuk sampai ke simpul tujuan, dalam hal ini dapat diperoleh dengan menggunakan

pada tahap awal kita akan melakukan perhitungan dengan menggunakan rumus diatas untuk memperoleh batas awal atau akar dari pohon yang juga merupakan simpul pertama. Pada keadaan ini, batas dihitung dengan pemikiran bahwa belum ada satupun barang yang dimasukan kedalam alat pengangkut maka kita dapat memilih 6 sebagai (P/W) terbesar karena belum ada satu barangpun yang dimasukan kedalam alat pengangkut dan kapasitas daya angkutpun masih utuh yaitu seberat 16 kg.

(i) = (i) + (i)

(1) = keuntungan yang diperoleh sampai disimpul

awal + (P/W)max * daya angkut yang tersisa

= 0 + 6 *

= 96

Maka kita memperoleh 96 batas awal atau cost dari simpul awal.

Bangkitkan simpul-simpul anak dari akar pohon yaitu dengan membangkitkan simpul 1, simpul 2, simpul 3 dan simpul 4 sebagai gambaran dari 4 pilihan barang yang akan dimasukan pertama kali pada alat pengangkut dengan x1 merupakan keuntungan yang akan diperoleh pada penjualan tiap barang tersebut. Kemudian kita akan menghitung cost dari tiap simpul anak yang hidup dan juga kelayakannya untuk tetap hidup atau harus dibunuh. Dalam hal ini, simpul yang jumlah dari lintasannya tidak bisa lagi dibangkitkan (jika ditambah barang lagi kedalam alat pengangkut maka beratnya akan melebihi daya angkut) akan dibunuh.

(2) = 12 + 5*(16-2) = 82

(3) = 15 + 6*(16-5) = 81

(3) = 50 + 6*(16-10)=86

(4) = 10 + 6*(16-5)=76

Dari simpul-simpul yang telah dibangkitkan dan dihitung cost nya, maka diperoleh bahwa simpul 4 lah yang memiliki cost tertinggi oleh karena itu maka simpul 4 akan di perluas lagi. Simpul 6 ,7,8 akan dibangkitkan sebagai perluasan dari simpul 4 dengan barang yang mungkin dimasukan kedalam alat pengangkut adalah barang ke 1,2 dan 4. kemudian kita akan mengkitung cost dari simpul 6,7dan 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

Nama : Lukas
NPM : 20312019
Kelas : IF20DX

Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

Penyelesaian dengan Divide and Conquer

Implementasi Algoritma Divide and Conquer pada Merge Sorting

Implementasi Algoritma Divide and Conquer pada Searching

Algoritma pencarian Binary search adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu:

1. Mencari nilai tengah dari tabel (median).
2. Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah.
3. Mencari setengah sisanya dengan cara yang sama.

SUMBER

Sejarah, Definisi, dan Cara Kerja Algoritma Divide dan Conquer

1. Sejarah Divide and Conquer

Pada zaman dahulu, divide and conquer merupakan strategi militer yang dikenal dengannama divide ut imperes. Saat ini strategi tersebut menjadi strategi fundamental di dalam ilmu komputer dengan nama divide and conquer. Algoritma divide and conquer ini ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya beliau menemukan algoritma yang lebih mangkus untuk mengalikan dua buah bilangan bulat yang besar.

Algoritma divide and conquer 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 disortir untuk memfasilitasi pencarian berasal dari setidaknya sejauh Babylonia pada 200 SM. Algoritma divide and conquer kuno lainnya adalah algoritma Euclidean untuk menghitung pembagi persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi subproblem ekuivalen yang lebih kecil dan lebih kecil, yang berasal dari beberapa abad SM.

Contoh awal dari algoritma bagi dan aklukkan dengan beberapa subproblem adalah deskripsi Gauss tahun 1805 tentang apa yang sekarang disebut algoritma Cooley-Tukey fast Fourier transform (FFT), meskipun dia tidak menganalisis jumlah operasinya secara kuantitatif, dan FFT tidak tersebar luas sampai ditemukan kembali lebih dari satu abad kemudian.

Algoritma D&C dua subproblem awal yang secara khusus dikembangkan untuk komputer dan dianalisis dengan tepat adalah algoritma pengurutan gabungan, yang ditemukan oleh John von Neumann pada tahun 1945. Contoh penting lainnya adalah algoritma yang ditemukan oleh Anatolii A. Karatsuba pada tahun 1960 yang dapat mengalikan dua angka n- digit dalam O operasi (dalam notasi Big O). Algoritma ini membantah dugaan tahun 1956 Andrey Kolmogorov operasi akan diperlukan untuk tugas itu. Sebagai contoh lain dari algoritma bagi-dan-taklukkan yang awalnya tidak melibatkan komputer, Donald Knuth memberikan metode yang biasanya digunakan kantor pos untuk merutekan surat: surat diurutkan ke dalam kantong terpisah untuk wilayah geografis yang berbeda, masing-masing kantong ini diurutkan sendiri ke dalam batch untuk sub-wilayah yang lebih kecil, dan seterusnya sampai dikirimkan. Ini terkait dengan jenis radix, dijelaskan untuk mesin sortir kartu berlubang sejak tahun 1929.

2. Definisi Algoritma Divide and Conquer

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

Langkah-langkah umum algoritma Divide and Conquer :

• a.Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama )
• b.Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
• c.Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula

3. Cara Kerja Divide and Conquer

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif ( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif.

Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array.

Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu :

• a. Merge sort
• b. Insert sort
• c. Quick sort
• d. Selection sort

Solusi Permasalah Sorting

Pengertian

sort merupakan salah satu jenis sorting. Ide dari algoritma ini adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah. Pembandingan elemen-elemen ini akan terus diulang hingga tidak perlu dilakukan penukaran lagi.

Permasalahan

Urutkan {4 2 5 3 9} dari kecil ke besar

Solusi

Menggunakan cara Bubble Sort

Langkah-langkah dalam pengurutan dalam bubble sort, sebagai berikut: misalkan kita mempunyai sebuah array dengan elemen-elemen “ 4 2 5 3 9”. Proses yang akan terjadi apabila menggunakan algoritma bubble sort adalah sebagai berikut:

Pass pertama
(4 2 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 5 3 9)
(2 4 5 3 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 4 3 5 9)
Pass kedua
(2 4 3 5 9) menjadi (2 4 3 5 9)
(2 4 3 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
Pass ketiga
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)
(2 3 4 5 9) menjadi (2 3 4 5 9)

Dilihat dari proses di atas, sebenarnya pada pass kedua, langkah kedua, array telah terurut. Namun algoritma tetap dilanjutkan hingga pass kedua berakhir. Pass ketiga dilakukan karena definisi terurut dalam algoritma bubble sort adalah tidak ada satupun penukaran pada suatu pass, sehingga pass ketiga dibutuhkan untuk memverikasi keurutan array tersebut

Kekurangan dan Kelebihan Bubble Sort

Kelebihan Bubble Sort :

1. Proses penghitungan Bubble sort merupakan metode yang paling sederhana
2. Algoritma Bubble Sort mudah dipahami
3. Langkah atau tahapan dalam pengurutan data sangat sederhana.

Kekurangan Bubbe Sort :

1. Proses penghitungan Bubble Sort menggunakan metode pengurutan termasuk paling tidak efisien walaupun dianggap sederhana. Karena proses pengurutan data dilakukan dengan tahapana satu - satu, mulai dari data paling awal sebelah kiri, sampai data terakhir
2. Ketika data yang kita punya banyak atau dalam jumlah yang besar, maka proses penghitungan akan semakin lama dan lambat. Karena proses pengurutan data secara tunggal (satu - satu).
3. Jumlah pengulangan akan tetap sama sampai ke data yang terakhir, walaupun sebagian data yang ada telah terurut.

SUMBER
https://media.neliti.com/media/publications/126448-ID-analisis-perbandingan-algoritma-bubble-s.pdf
http://kelompok1ka2.blogspot.com/2015/10/kelebihan-dan-kekurangan-metode-bubble.html