Algoritma Branch and Bound

    

Nama : Eko Haryadi

Npm   : 19316029

Kelas : Tk 19 A

·       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).

·       Nilai ongkos pada setiap simpul i menyatakan taksiran ongkos termurah lintasan dari simpul i ke simpul solusi (goal node):

= nilai taksiran lintasan termurah dari

simpul status i ke status tujuan

·       Dengan kata lain,  menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status i.

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.

·       Fungsi heuristik untuk menghitung taksiran cost:

        = ongkos untuk simpul i

            = ongkos mencapai simpul i dari akar

       = ongkos mencapai simpul tujuan dari simpul i.

·   Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki minimum.

Algoritma B&B:

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 mempunyaipaling 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, dan masukkan semua anak-anak tersebut ke dalam Q.

6.   Kembali ke langkah 2. 

Nama          : Eko Haryadi

NPM            : 19316029

Kelas           : Tk 19 A

 

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

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