Algoritma B&B (Branch and Bound)


Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah.
Algoritma ini memiliki 2 prinsip, yaitu:

  • Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching
  • Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik



Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik yang ada
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awal Titik Tujuan Biaya
Titik A Titik B 10
Titik A Titik E 11
Titik B Titik A 12
Titik B Titik C 20
Titik B Titik D 6
Titik B Titik E 9
Titik C Titik B 15
Titik C Titik D 14
Titik D Titik B 7
Titik D Titik C 5
Titik E Titik C 8
Titik E Titik D 13

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
heldkarpawal



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah


Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan inisialisasi daftar jalur sesuai dengan data yang tersedia
Terdapat matriks berukuran [jumlah titik x jumlah titik] untuk menyimpan jalur dari masing-masing titik
Jika tidak ada jalur diantara 2 titik, maka nilai jalurnya adalah 0

2. Hitung rata-rata biaya pada semua data
Nilai ini nantinya akan digunakan untuk perkiraan nilai biaya apakah akan melebihi bound atau tidak

3. Lakukan perhitungan pencarian jalur melalui semua titik yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3a)

Memasuki perhitungan pada fungsi CariJalurTerbaik

3a. Lakukan perhitungan pada masing-masing titik (poin 3a1 – 3a3)

3a1. Beri nilai awal calon jalur dengan nilai -1

3a2. Lakukan perhitungan pada masing-masing titik selain titik awal (poin 3a2a – 3a2c)

3a2a. Masukkan titik awal pada calon jalur yang sedang dihitung

3a2b. Inisialisasi titik titik yang sudah dihitung dengan nilai false,
kemudian tandai titik awal dengan nilai True agar tidak dapat digunakan dalam perhitungan selanjutnya

3a2c. Lakukan pencarian jalur dimulai dari titik awal yang terpilih
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini

Memasuki Perhitungan pada fungsi CariJalur

3a2c1. Jika semua titik sudah terpilih, maka bandingkan total biaya jalur ini dengan total biaya terbaik
Jika total biaya jalur ini kurang dari total biaya terbaik, maka ambil total jalur ini sebagai jalur terbaik

3a2c2. Lakukan perhitungan dibawah ini apabila kondisi diatas tidak terpenuhi (poin 3a2c2a – 3a2c2c)

3a2c2a. Lakukan pengecekan terhadap sisa titik yang akan dihitung
Apabila perkiraan sisa titik akan melebihi bound biaya terbaik, maka hentikan perhitungan

3a2c2b. Dapatkan indeks titik yang terakhir kali dihitung untuk digunakan sebagai titik awal pada perhitungan berikutnya

3a2c2c. Lakukan perhitungan pada masing-masing titik untuk titik-titik yang belum terpilih dan memiliki jarak dengan titik terakhir (poin 3a2c2c1 – 3a2c2c3)

3a2c2c1. Masukkan titik ini sebagai titik berikutnya pada calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang sudah terpilih

3a2c2c2. Lakukan proses percabangan / branch,
yaitu Ulangi fungsi ini menggunakan titik yang baru sebagai titik awal

3a2c2c3. Setelah semua kemungkinan cabang pada titik tersebut sudah dihitung,
maka keluarkan titik ini dari calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang belum terpilih

3a3. Jika biaya jalur yang baru ditemukan lebih baik dari biaya jalur terbaik,
maka ambil jalur tersebut sebagai jalur terbaik


Hasil akhir adalah: (klik untuk perbesar gambar)

cmd84

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
bb akhir


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *