Algoritma Branch & 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, hitung


, dan masukkan semua anak-anak tersebut ke dalam Q.


6.   Kembali ke langkah 2. 






Nama          : M Athallah Permana A


NPM            : 19316019


Kelas           : TK 19 C


 


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


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

Komentar

Posting Komentar

Postingan populer dari blog ini

Desain Eksperimen

    xperimental Design (Desain Eksperimen)  Experiment Design (Desain Eksperimen) T Suatu percobaan adalah suatu pengujian teori yang menggunakan pengamatan yang sengaja diatur dengan syarat tertentu. Ronald Fisher adalah seseorang yang berpendapat perlu menggunakan statistika untuk merancang suatu percobaan.   Perencanaan dari peneliti adalah menyusun secara sistematik tiap faktor yang berlainan secara simultan.  Dengan proses matematika kita dapat memilih syarat untuk merancang urutan serta langkah percobaan sehingga kita memperoleh hasil yang optimum.  Rancangan percobaan adalah suatu prosedur memilih syarat dan banyaknya percobaan yang akan dilakukan. Rancangan yang paling efisien dilihat dari segi matematis adalah efisien dalam waktu, biaya dan sesatan eksperimen atau yang lebih dikenal dengan error. Sesatan eksperimen adalah kesalahan-kesalahan yang disebabkan antara lain dengan adanya variasi dari materi eksperimen yang seharusnya homogen tetapi keho...
Baca selengkapnya

SEJARAH PROTOTYPING

Gambar
  METODE PROTOTYPING METODE PROTOTYPING Menurut Raymond McLeod, prototype didefinisikan sebagai alat yang memberikan ide bagi pembuat maupun pemakai potensial tentang cara system berfungsi dalam bentuk lengkapnya, dan proses untuk menghasilkan sebuah prototype sisebut prototyping. Prototyping adalah proses pembuatan model sederhana software yang mengijinkan pengguna memiliki gambaran dasar tentang program serta melakukan pengujian awal. Prototyping memberikan fasilitas bagi pengembang dan pemakai untuk saling berinteraksi selama proses pembuatan, sehingga pengembang dapat dengan mudah memodelkan perangkat lunak yang akan dibuat. Prototyping merupakan salah satu metode pengembangan perangat lunak yang banyak digunakan. Model tersebut dapat berupa tiga bentuk : 1.      Prototipe kertas atau model berbasis komputer yang menjelaskan bagaimana interaksi antara pemakai dan komputer. 2.      Prototipe yang mengimplementasikan beber...
Baca selengkapnya

Cara kerja Automatic Teller Machine (ATM)

Gambar
  ATM ini adalah perangkat elektronik yang hanya digunakan oleh nasabah bank untuk memproses transaksi rekening. Pengguna mengakses akun mereka melalui kartu plastik (kartu ATM) jenis khusus yang dikodekan dengan informasi pengguna pada strip magnetik. Strip berisi kode identifikasi yang dikirimkan ke komputer pusat bank dengan modem. Dan yang terbaru, kartu ATM diharuskan sudah memakai teknologi   chips . Pengguna memasukkan kartu ke dalam ATM untuk mengakses akun dan memproses transaksi akun mereka. Keuntungan dari ATM Menyediakan layanan 24 jam Memberikan privasi dalam komunikasi perbankan Mengurangi beban kerja staf bank Memberikan catatan mata uang baru kepada pelanggan ATM memberikan kenyaman untuk nasabah bank Sangat bermanfaat bagi para pelancong ATM memberikan layanan cepat dan tepat Fitur ATM Transfer dana antar rekening bank atau bank lain Mengecek saldo Mencetak daftar transaksi terbaru Ubah pin Anda Setor uang tunai Isi ulang ponsel prabayar Pembayaran tagihan Tar...
Baca selengkapnya