Analisis dan Strategi Algoritma - Implementasi Algoritma Branch and Bound

A. Pengertian Algoritma Branch and Bound

        Branch and bound adalah metode algoritmik general untuk menemukan solusi optimal dari berbagai masalah optimasi, khususnya pada diskrit dan optimasi kombinatorial. Dasarnya adalah pendekatan enumerasi dengan cara mematikan(pruning) search space yang tidak mengarah ke solusi. Metode ini pertama kali diperkenalkan oleh A.H. Land dan A.G. Doig pada tahun 1960. Branch and bound prosedur memerlukan dua alat. Yang pertama adalah cara untuk men-cover regional feasible dengan beberapa subregional feasible yang lebih kecil. Ini disebut branching. Karena pemanggilan prosedur dilakukan berulang-ulang secara rekursif, maka semua subregional akan secara alami membentuk sturktur pohon. Yang kedua adalah bounding, yaitu cara untuk mencari nilai batas atas atau batas bawah.

        Proses pencarian (branching) pada metode ini menggunakan skema BFS. Pada skema BFS simpul yang dibangkitkan terlebih dahulu adalah simpul yang bertetanggaan dengan simpul akar.Proses pemilihan simpul-E, simpul yang akan diexpand, pada algoritma branch and bound tidak seperti pada metode BFS murni. Pada BFS murni pemilihan simpul-E berdasarkan urutan pembangkitan sedangkan pada algoritma branch and bound simpul-E dipilih berdasarkan niliai ongkos. Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound). Jadi hasil optimasi yang diperoleh melalui algoritma ini bergantung pada keakuratan pemilihan fungsi “bound” tersebut. Tidak ada cara yang baku untuk menentukan fungsi “bound”, mungkin saja masalah yang sama memiliki rumus perhitungan nilai batas yang berbeda-beda.

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. Di asumsikan 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

1	Const jumlahTitik As Integer = 5

B. Implementasi Penggunaan Algoritma Branch dan Bround

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

1 2 3 4 5 6 7

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

1 2 3 4 5 6 7 8 9 10 11

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)

1	CariJalurTerbaik(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, BiayaTerbaik)

Memasuki perhitungan pada fungsi CariJalurTerbaik

3.1 Lakukan perhitungan pada masing-masing titik (poin 3.1.1 – 3.1.3)

1 2	For i As Integer = 0 To jumlahTitik - 1 . . .

3.1.1 Beri nilai awal calon jalur dengan nilai -1

1 2 3

For j As Integer = 0 To jumlahTitik - 1     calonJalur(j) = -1 Next

3.1.2 Lakukan perhitungan pada masing-masing titik selain titik awal (poin 3.1.2.1 – 3.1.2..1)

1 2 3

For j As Integer = 0 To jumlahTitik - 1     If daftarBiaya(i, j) <> 0 Then     . . .

3.1.2.1 Masukkan titik awal pada calon jalur yang sedang dihitung

1	calonJalur(0) = i

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

1 2	Dim titikTerpilih(jumlahTitik - 1) As Boolean titikTerpilih(i) = True

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

1	CariJalur(jumlahTitik, rata2, daftarBiaya, jalur, biaya, titikTerpilih, calonJalur, totalCalonJalur, 1)

Memasuki Perhitungan pada fungsi CariJalur

3.1.2.3.1 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

1 2 3 4 5 6

If jumlahTitikTerpilih >= jumlahTitik Then     If totalCalonJalur < biayaTerbaik Then         biayaTerbaik = totalCalonJalur         Array.Copy(calonJalur, jalurTerbaik, jumlahTitik)     End If . . .

3.1.2.3.2 Lakukan perhitungan dibawah ini apabila kondisi diatas tidak terpenuhi (poin 3a2c2a – 3.1.2.3.2.3)

1 2	Else . . .

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

1 2 3 4

Dim sisaTitik As Integer = jumlahTitik - jumlahTitikTerpilih If totalCalonJalur + rata2 * sisaTitik >= biayaTerbaik Then     Return End If

3.1.2.3.2.2 Dapatkan indeks titik yang terakhir kali dihitung untuk digunakan sebagai titik awal pada perhitungan berikutnya

1	Dim idxTitikTerakhir As Integer = calonJalur(jumlahTitikTerpilih - 1)

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

1 2 3

For i As Integer = 0 To jumlahTitik - 1     If titikTerpilih(i) = False AndAlso daftarBiaya(idxTitikTerakhir, i) <> 0 Then     . . .

3.1.2.3.2.3.1 Masukkan titik ini sebagai titik berikutnya pada calon jalur yang sedang dihitung
dan tandai titik ini sebagai titik yang sudah terpilih

1 2	calonJalur(jumlahTitikTerpilih) = i titikTerpilih(i) = True

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

1 2	CariJalur(jumlahTitik, rata2, daftarBiaya, jalurTerbaik, biayaTerbaik, titikTerpilih, _           calonJalur, totalCalonJalur + daftarBiaya(idxTitikTerakhir, i), jumlahTitikTerpilih + 1)

3.1.2.3.2.3.3 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

1 2	calonJalur(jumlahTitikTerpilih) = -1 titikTerpilih(i) = False

3.1.3 Jika biaya jalur yang baru ditemukan lebih baik dari biaya jalur terbaik,
maka ambil jalur tersebut sebagai jalur terbaik

1 2 3 4

If biaya < biayaTerbaik Then     biayaTerbaik = biaya     Array.Copy(jalur, jalurTerbaik, jumlahTitik) End If

Nama : Senda Wahyu Andika

NPM  : 19316031

Kelas : TK 19C

Fakultas         : http://ftik.teknokrat.ac.id/

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