Algoritma Branch and Bound 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 mempunyai 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 , dan masukkan semua anak-anak tersebut ke dalam Q. 6. Kembali ke langkah 2. Nama : Bayu Cahyadi NPM : 19316085 Kelas : TK19A Universitas : https://teknokrat.ac.id/ Fakultas : http://ftik.teknokrat.ac.id/