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

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

6. Kembali ke langkah 2. 


Nama : IMAM BUKHORI

NPM : 20372004p

Kelas : IF19GX

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

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

Comments

Post a Comment

Popular posts from this blog

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

  Nama       : IMAM BUKHORI NPM        : 20372004P Kelas        : IF 20 DX Sejarah Definisi dan Cara Kerja Algoritma Divide and Conquer A.Sejarah Algoritma Devide and Conquer.     ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya, Anatoliimenemukan algoritma yang lebih cepat untuk mengalikan dua buah bilangan bulatyang besar dengan kompleksitas O(nlog 3). B.  Devinisi Algoritma Devide and Conquer.     Di dalam ilmu komputer, algoritme divide and conquer merupakan algoritme yang sangat populer. Prinsip dari algoritme ini adalah memecah-mecah masalah yang ada menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. C. Cara Kerja Algoritma Devide and Conquer.     Contoh sederhana : Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana. Algoritma perulangan yang digunakan pada kode di atas memang sederhana dan memberikan hasil yang benar,
Read more

Implementasi Algoritma Branch & Bound

Nama: IMAM BUKHORI NPM: 20372004P Kelas: IF 20 DX Metode Branch and Bound  adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin. Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu : Branch  yang artinya membangun semua cabang tree yang mungkin menuju solusi.   Bound  yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala). Teknik Branch and Bound Ada beberapa teknik dalam Branch and Bound yaitu:   FIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch  and Bound secara First In First Out. LIFO Branch and Bound Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out. Least Cost Branch and Bound Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling k
Read more

Implementasi Algoritma Divide and Conquer pada Sorting dan Searching

Image
NAMA              : IMAM BUKHORI NPM              : 20372004P Kelas              : IF 20 DX Algoritma merupakan kumpulan perintah yang memiliki daya guna yang sangat besar bagi masyarakat. Algoritma biasanya digunakan sebagai kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma ini memiliki aplikasi yang bermacam-macam dalam setiap masalah yang ada. Contohnya saja adalah algoritma cara menyelesaikan suatu aritmatika yang rumit, algoritma untuk menghitung luas penampang dari suatu kabel, atau bahkan untuk menghitung bayaran parkir di setiap mal. Salah satu aplikasi bentuk pemrograman ini adalah dalam bahasa permrograman yang disebut bahasa C. Dimana bahasa C ini memiliki suatu aturan-aturan tertentu yang sangat penting sehingga dalam penggunaanya kita harus memperhatikan cara menggunakan aturan tersebut. Salah satu cara penggunaannya adalah dengan array. Dimana array ini merupakan suatu data struktur yang berkoneksi satu sama lain dengan tipe yang sama. Aplikasi array ini bany
Read more