Artikel: Analisis dan Strategi Algoritma - Implementasi Algoritma Branch and Bound

Implementasi Algoritma Branch and Bound

Algoritma Branch and Bound adalah metode algoritma umum untuk mencari solusi optimal dari dari berbagai permasalahan optimasi, terutama untuk optimasi diskrit dan kombinatorial. Sebagaimana pada algoritma runut-balik, algoritma Branch and Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam pohon ruang status. Yang membedakan keduanya adalah bila pada algoritma runut-balik, ruang solusi dibangun secara dinamis berdasarkan skema DFS (Depth First Search), maka pada algoritma Branch and Bound ruang solusi dibangun dengan skema BFS (Breadth First Search). Algoritma Branch and Bound banyak digunakan untuk memecahkan berbagai macam permasalahan antara lain : persoalan Knapsack 0/1, Travelling Salesman Problem (TSP), The N-Queens Problem (Persoalan N-Ratu), Graph Colouring (Pewarnaan Graf), Sirkuit Hamilton, Integer Programming, Nonlinear Programming, Quadratic Assignment Problem (QAP), Maximum Satisfiability Problem (MAX-SAT), dan lain sebagainya.

Prinsip Pencarian Solusi pada Algoritma B&B

Skema BFS = skema FIFO (First In First Out).

· Tinjau kembali persoalan 4-ratu yang diselesaikan dengan skema BFS (murni).

Gambar 7.1 Pohon ruang status yang terbentuk untuk persoalan 4-Ratu dengan metode BFS

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 [HOR78]:

(a) jumlah simpul dalam upapohon X yang perlu dibangkitkan sebelum simpul solusi ditemukan, atau

(b) panjang lintasan dari simpul X ke simpul solusi terdekat (dalam upapohon 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.