IMPLEMENTASI ALGORITMA 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

•                    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 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 Pemecahan masalah optimasi Travelling Salesman Problem (TSP) merupakan pekerjaan yang membutuhkan algoritma yang efisien dan Algoritma Branch and Bound merupakan salah satu algoritma untuk memecahkan masalah tersebut. Algoritma Branch and Bound mencari sejumlah solusi yang lengkap untuk masalah yang ada dengan hasil yang terbaik. Walaupun begitu, penggunaan satu per satu secara eksplisit tidak mungkin dilakukan dalam kaitan penambahan sejumlah solusi yang potensial. Penggunaan batas (bound) untuk fungsi yang akan dioptimalkan dikombinasikan dengan nilai solusi terbaik yang ada memungkinkan algoritma untuk mencari bagian-bagian dari sejumlah solusi secara implisit.  Pada titik sembarang sepanjang proses solusi, status solusi yang berkenaan dengan pencarian sejumlah solusi dijelaskan oleh sekelompok ahli yang mempelajari dan belum seluruhnya dieksplorasi tetapi sejauh ini

merupakan solusi terbaik yang ada saat ini. Pada awalnya hanya ada subset yaitu ruang solusi lengkap (complete solution space) dan solusi terbaik sejauh ini yang ditemukan baru 1 (satu) [6]. Subspace yang belum diperiksa direpresentasikan sebagai titik-titik dalam sebuah pohon pencarian yang dihasilkan secara dinamis, dimana awalnya hanya berisi root, dan setiap iterasi dari Algoritma Branch and Bound klasik memproses satu titik.  Iterasi memiliki tiga komponen utama yaitu pemilihan titik untuk diproses, kalkulasi batasan (bound), dan pencabangan. Urutan dari pencarian ini dapat dipertukarkan sembarang sesuai dengan strategi yang dipilih untuk memilih node berikutnya yang akan diproses. Jika pemilihan subproblem berikutnya didasarkan pada nilai batas (bound) dari subproblem, maka operasi pertama dari iterasi setelah pemilihan node adalah pencabangan (branching), yaitu pembagian ruang solusi dari node menjadi dua atau lebih subspace untuk diperiksa dalam sebuah iterasi sub rangkaian.  Untuk setiap rangkaian, akan diperiksa apakah subspace terdiri dari satu solusi, yang kemudian dibandingkan dengan solusi terbaik yang ada selama pencarian. Jika tidak, pembatasan fungsi untuk subspace dihitung dan dibandingkan dengan solusi terbaik yang diperoleh. Jika pencarian tidak dapat dilanjutkan dimana subspace tidak berisi solusi yang optimal, keseluruhan subspace akan dibuang, selain itu subspace akan disimpan dalam kelompok node bersama-sama dengan batasannya (bound). Alternatif lainnya adalah dengan memulai menghitung batas (bound) dari node yang terpilih dan kemudian mencabangkannya jika diperlukan. Node-node yang dibuat kemudian disimpan bersamaan dengan batas dari node yang diproses. Pencarian berakhir saat tidak ada lagi bagian dari ruang solusi yang diperiksa, dan solusi optimal kemudiandicatat sebagai solusi terbaik [7].

·      Pencarian solusi N-Queen Problem dengan cara terpendek menggunakan algoritma Branch and Bound

Prinsip algo ritma Branch and Boundsangat mirip dengan BFS, hanya saja pada algoritmaBranchand Boundditambahkan nilai cost atau ongkos dari setiap  simpul yang bertujuan sebagai penanda prioritas di dalam  antrian. Dengan menambah nilai ongko s dari masing -masing simpul  maka nilai ongko s tersebut  akan menjadi penentu prioritas yang ada di dalam antrianyang di pakai di dalam metode

BFS dengan prioritas terkecil akan

berada pada antrian terdepan.Nilai ongkos pada simpulsimpul bertujuan untuk menyatakan nilai batas (bound). Nilai batas dalam algoritma Branch and Bound dicari dengan suatu fungsi pembat

as yaitu suatu fungsi yang bertujuan membangkitkan suatu simpul dengan melihat apakah simpul tersebut mengarah ke simpul solusi dengan memberikan suatu nilai sebagai nilai batas (bound). Cara kerja dari fungsi pembatas dapat berupa [HOR78] yaitu dengan cara mencari jumlah simpul  dalam subpo hon X yang perlu dibangkitkan sebelum simpul solusi ditemukan atau panjang lintasan dari simpul  X ke simpul  solusi terdekat. Simpul  X adalah simpul  dimana akan diberi nilai batas atau nilai ongkos. Gambar dibawah ini adalah realisasi algo ritma BranchandBoundmenggunakan teori pohon dalam persoalan 4-Ratu.

Bila dilihat pada gambar 10, pada simpul-E pertama kali adalah simpul  1,  pada bagian bawah simpul  1 diberi nilai ongkos 4. Simpul 1 dilanjutkan dengan membangkitkan 4 simpul lainnya yaitu simpul 2,3,4, dan 5. Dengan menggunakan fungsi pembatas maka didapat pada simpul 2 dan 5 yaitu X1=1 dan X1=4 diberi nilai ongkos sebesar ∞ yang artinya simpul tersebut akan berada di paling belakang antrian sehingga tidak akan diproses karena tidak mengarah pada simpul solusisehingga tidak mungkin bidak Ratu berada pada posisi (1,1) atau (1,4).

Langkah selanjutnya dengan fungsi pembatas, nilai simpul 3 dan 4 yaitu X1=2 dan X1=3 diberi nilai batas sebesar 3. Simpul-simpul  yang telah diberi nilai batas dimasukkan ke dalam antrian dengan urutan simpul adalah 3,4,2, dan 5.Selanjutnya simpul yang akan diproses berdasarkan antrian adalah simpul 3. Pada simpul 3 dilakukan dengan membangkitkan 3 simpul dengan nama simpul 9,10, dan 11. Simpul-simpul  yang baru dibangki tkan diberi nilai batas dari fungsi pembatas sehingga hasil yang didapat berupa  simpul  9 dan simpul  10 diberi nilai ∞, simpul 11 diberi nilai 2.  Dengan simpul-simpul  yang telah diberikan nilai maka dimasukka n ke dalam antrian sehingga antrian berubah dengan urutan simpul menjadi 11, 4, 2, 5, 9,dan

10. Setelah itu simpul-E dilanjut kan dengan mengambil kepala antrian yaitu simpul 11. Pada simpul 11 dibangkitkan 2 simpul lainya dengan nama simpul 22 dan

23. Simpul 22 diberi ongkos 1 dan simpul 23 diberi ongkos

∞. Nilai simpul yang  telah diberikan dimasukkan ke dalam antrian dengan urutan simpul adalah 22,  4,  2,  5,  9, 10, dan 23.Simpul  dilanjut kan dengan mengambil nilai kepala antrian yaitu simpul 22. Pada simpul 22 diperluas dan di peroleh simpul 30 yang merupakan simpul solusi pertama sehingga hasil pencarian untuk solusi 4-Ratu. Jika dilanjutkan maka akan menemukan solusi yang berikutnya hingga semua antrian selesai diproses.

Dari algo ritma BFSdan algo ritma Branch and Bound dalam N

-

Queen Problem didapat kan bahwa algoritma

Branch and Bound lebih singka t dari algo ritma

BFS dalam  persoalan mencari cara terpendek dari N-Queen Problem. Dalam algo ritma

BFSsemua simpul  hasil perluasan dari simpul-E dipr oses dan diberi nilai pembatas,prosestersebut diulang hingga nilai simpul  solusi ditemuka n. Sedangkan algoritma Branch and Boundmelakukan pencarian dengan cara memberi nilai pembataspada semua simpul perluasan tetapi hanya diproses dari simpul yang memiliki pr ioritas simpul  tersebut  mengarah pada simpul  solusi, sehingga jalan terpendek dalam mencari simpul solusi dapat dengan cepat ditemukan.

Nama : Anan Krisna

NPM : 19312187

Kelas : IF 19 D

Universitas Teknokrat Indonesia : https://teknokrat.ac.id/

Fakultas Teknik dan Ilmu Komputer :http://ftik.teknokrat.ac.id/