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
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
Const jumlahTitik As Integer = 5
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
Dim daftarBiaya(,) As Double = New Double(jumlahTitik - 1, jumlahTitik - 1) { _
{0, 10, 0, 0, 11}, _
{12, 0, 20, 6, 9}, _
{0, 15, 0, 14, 0}, _
{0, 7, 5, 0, 0}, _
{0, 0, 8, 13, 0} _
}
2. Hitung rata-rata biaya pada semua data
Nilai ini nantinya akan digunakan untuk perkiraan nilai biaya apakah akan melebihi bound atau tidak
Dim rata2 As Integer = 0
Dim count As Integer = 0
For i As Integer = 0 To jumlahTitik - 1
For j As Integer = 0 To jumlahTitik - 1
If daftarBiaya(i, j) <> 0 Then
rata2 += daftarBiaya(i, j)
count += 1
End If
Next
Next
rata2 /= count
3. Lakukan perhitungan pencarian jalur melalui semua titik yang ada
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 3a)
CariJalurTerbaik(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, BiayaTerbaik)
Memasuki perhitungan pada fungsi CariJalurTerbaik
3a. Lakukan perhitungan pada masing-masing titik (poin 3a1 – 3a3)
For i As Integer = 0 To jumlahTitik - 1
. . .
3a1. Beri nilai awal calon jalur dengan nilai -1
For j As Integer = 0 To jumlahTitik - 1
calonJalur(j) = -1
Next
3a2. Lakukan perhitungan pada masing-masing titik selain titik awal (poin 3a2a – 3a2c)
For j As Integer = 0 To jumlahTitik - 1
If daftarBiaya(i, j) <> 0 Then
. . .
3a2a. Masukkan titik awal pada calon jalur yang sedang dihitung
calonJalur(0) = i
3a2b. Inisialisasi titik titik yang sudah dihitung dengan nilai false,
kemudian tandai titik awal dengan nilai True agar tidak dapat digunakan dalam perhitungan selanjutnya
Dim titikTerpilih(jumlahTitik - 1) As Boolean
titikTerpilih(i) = True
3a2c. Lakukan pencarian jalur dimulai dari titik awal yang terpilih
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan dibawah ini
CariJalur(jumlahTitik, rata2, daftarBiaya, jalur, biaya, titikTerpilih, calonJalur, totalCalonJalur, 1)
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
If jumlahTitikTerpilih >= jumlahTitik Then
If totalCalonJalur < biayaTerbaik Then
biayaTerbaik = totalCalonJalur
Array.Copy(calonJalur, jalurTerbaik, jumlahTitik)
End If
. . .
3a2c2. Lakukan perhitungan dibawah ini apabila kondisi diatas tidak terpenuhi (poin 3a2c2a – 3a2c2c)
Else
. . .
3a2c2a. Lakukan pengecekan terhadap sisa titik yang akan dihitung
Apabila perkiraan sisa titik akan melebihi bound biaya terbaik, maka hentikan perhitungan
Dim sisaTitik As Integer = jumlahTitik - jumlahTitikTerpilih
If totalCalonJalur + rata2 * sisaTitik >= biayaTerbaik Then
Return
End If
3a2c2b. Dapatkan indeks titik yang terakhir kali dihitung untuk digunakan sebagai titik awal pada perhitungan berikutnya
Dim idxTitikTerakhir As Integer = calonJalur(jumlahTitikTerpilih - 1)
3a2c2c. Lakukan perhitungan pada masing-masing titik untuk titik-titik yang belum terpilih dan memiliki jarak dengan titik terakhir (poin 3a2c2c1 – 3a2c2c3)
For i As Integer = 0 To jumlahTitik - 1
If titikTerpilih(i) = False AndAlso daftarBiaya(idxTitikTerakhir, i) <> 0 Then
. . .
3a2c2c1. Masukkan titik ini sebagai titik berikutnya pada calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang sudah terpilih
calonJalur(jumlahTitikTerpilih) = i
titikTerpilih(i) = True
3a2c2c2. Lakukan proses percabangan / branch,
yaitu Ulangi fungsi ini menggunakan titik yang baru sebagai titik awal
CariJalur(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, biayaTerbaik, titikTerpilih, _
calonJalur, totalCalonJalur + daftarBiaya(idxTitikTerakhir, i), jumlahTitikTerpilih + 1)
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
calonJalur(jumlahTitikTerpilih) = -1
titikTerpilih(i) = False
3a3. Jika biaya jalur yang baru ditemukan lebih baik dari biaya jalur terbaik,
maka ambil jalur tersebut sebagai jalur terbaik
If biaya < biayaTerbaik Then
biayaTerbaik = biaya
Array.Copy(jalur, jalurTerbaik, jumlahTitik)
End If
Hasil akhir adalah: (klik untuk perbesar gambar)
Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
