ALGORITMA DAN KOMPLEKSITAS (Branch and Bound)

Algoritma Branch and Bound (B&B)

 Algoritma Branch and Bound (B&B) juga merupakan metode pencarian di dalam ruang solusi secara sistematis.
 Algoritma runut-balik skema DFS  Algoritma B&B skema BFS
 Untuk mempercepat pencarian ke simpul solusi, maka setiap simpul diberi sebuah nilai ongkos (cost).
 Simpul berikutnya yang akan diekspansi tidak lagi berdasarkan urutan pembangkitannya (sebagaimana pada BFS murni), tetapi simpul yang memiliki ongkos yang paling kecil (least cost search) –pada kasus minimasi.
 Nilai ongkos pada setiap simpul i menyatakan taksiran ongkos termurah lintasan dari simpul i ke simpul solusi (goal node): 
)( ˆ i c = nilai taksiran lintasan termurah dari  simpul status i ke status tujuan 
 Dengan kata lain, ) (ˆ ic
 menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status i. 

KASUS BFS DISELESAIKAN DENGAN SKEMA MURNI

 Solusi pertama dicapai pada simpul 30, yaitu X= (2, 4, 1, 3). Dengan skema BFS murni / FIFO, kita harus memperluas dulu simpul 12, simpul 15, dan simpul 16 sebelum memperluas simpul 22 yang melahirkan simpul solusi, yaitu simpul 30.
 Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost).
 Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound).
 Simpul hidup yang menjadi simpul-E ialah simpul yang mempunyai nilai batas terkecil (strategi  pencarian berdasarkan biaya terkecil(least cost search)).
 Untuk setiap simpul X, nilai batas ini dapat berupa : 1. jumlah simpul dalam subpohon X yang perlu  dibangkitkan sebelum simpul solusi ditemukan, atau 2. panjang lintasan dari simpulX ke simpul solusi terdekat (dalam subpohon X ybs)
 Misal digunakan ukuran (b):

 Pemberian nilai batas seperti pada persoalan N-Ratu di atas adalah nilai batas yang ideal, karena letak simpul solusi diketahui.
 Pada umumnya, untuk kebanyakan persoalan, letak simpul solusi tidak diketahui, karena itu, dalam prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan.
 Fungsi heuristik untuk menghitung taksiran cost: 

 Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki c ˆ minimum

ALGORITMA BRANCH AND BOUND
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node),  maka solusi telah ditemukan.  Stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai ) (ˆ ic paling kecil. Jika terdapat beberapa simpul i  yang memenuhi, pilih satu secara sembarang.
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua  anak-anaknya.  Jika i tidak mempunyai anak, kembali ke langkah 2. 5. Untuk setiap anak j dari simpul i, hitung ) (ˆ jc , dan masukkan semua anak-anak tersebut ke dalam Q.
6. Kembali ke langkah 2.

PERSOALAN PERDAGANGAN KELILING (TRAVELLING SALESPERSON PROBLEM - TSP)
Misalkan 
(i) G=(V,E) adalah graf lengkap TSP
(ii) V=n = jumlah simpul dalam graf G.     
 Simpul- simpul diberi nomor 1, 2, …, n.
(iii) cij = bobot sisi (i, j) (iv) perjalanan (tur) berawal dan berakhir di simpul 1.   (v) S adalah ruang solusi, yang dalam hal ini 
S = { (1,  , 1)   adalah permutasi (2, 3, ..., n) } 

Solusi TSP dinyatakan sebagai  X = (1, x1, x2, ..., xn – 1, 1) yang dalam hal ini         
 xo= xn = 1 (simpul asal = simpul akhir= 1).

Contoh instansiasi persoalan TSP:

 Ongkos atau nilai batas untuk setiap simpul dihitung dengan menggunakan matriks ongkos-tereduksi (reduced cost matrix) dari graf G.
 Sebuah matriks dikatakan tereduksi jika setiap kolom dan barisnya mengandung paling sedikit satu buah nol dan semua elemenlainnyanon-negatif.

Contoh :
Tinjau graf lengkap berarah TSP dengan n = 5

Lakukan reduksi baris:

Kemudian, lakukan reduksi kolom (dari hasil reduksi baris di atas):

Total jumlah semua pengurang = (10 + 2 + 2 + 3 + 4) + (1 + 3) = 25.

Nilai 25 ini adalah nilai batas untuk simpul akar, 

Selanjutnya, misalkan A adalah matriks tereduksi untuk simpul R. 
Misalkan S adalah anak dari simpul R sedemikian sehingga sisi (R, S) pada pohon ruang status berkoresponden dengan sisi (i, j) pada perjalanan. 
Jika S bukan simpul daun, maka matriks bobot tereduksi untuk simpul S dapat dihitung sebagai berikut:

(a) ubah semua nilai pada baris i dan kolom j menjadi . Ini untuk mencegah agar tidak ada lintasan yang keluar dari simpul i atau masuk pada simpul j; 
(b) ubah A(j, 1) menjadi . Ini untuk mencegah penggunaan sisi (j, 1); 
(c) reduksi kembali semua baris dan kolom pada matriks A kecuali untuk elemen . 
Jika r adalah total semua pengurang, maka nilai batas untuk simpul S adalah:   

Hasil reduksi ini menghasilkan matriks B.

Perhitungan selanjutnya:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Pohon ruang status yang terbentuk sampai saat ini adalah:

Karena tidak ada lagi simpul hidup di dalam pohon ruang status, maka X = (1, 4, 2, 5, 3, 1) menjadi solusi persoalan TSP di atas dengan bobot 28.







Terima Kasih telah membacanya semoga bermanfaat