TUGAS 5 ALGORITMA (BFS)

pada tanggal

https://pin.it/6jJcZzm5y

 
APA ITU ALGORITMA BFS ?

    Algoritma Breadth First Search adalah algoritma pencarian melebar yang dilakukan dengan mengunjungi node pada level n terlebih dahulu sebelum mengunjungi node-node pada level n+1. Cara kerja algoritma Breadth First Search yaitu masukkan simpul ujung ke dalam sebuah antrean kemudian ambil simpul dari awal antrean. Lakukan pengecekan apakah simpul awal merupakan solusi. Jika simpul merupakan solusi pencarian selesai dan hasil dikembalikan. Jika simpul bukan merupakan solusi, masukan seluruh simpul yang bertetangga dengan simpul tersebut. Apabila semua simpul sudah dicek dan antrean kosong, pencarian selesai dengan mengembalikan hasil solusi tidak ditemukan. Pencarian diulang dari simpul awal antrean. 

Kasus: Memilih barang ke tas (Knapsack) :

        Kamu punya tas dengan kapasitas 10 kg. Ada 5 barang dengan berat dan nilai berbeda.

Kamu ingin membawa barang yang total nilainya paling besar, tapi tidak boleh lebih dari 10 kg.

Data barang (berat, nilai):

•       Barang 1: (6 kg, 30)

•       Barang 2: (3 kg, 14)

•       Barang 3: (4 kg, 16)

•       Barang 4: (2 kg, 9)

•       Barang 5: (5 kg, 20)

Tujuan: Pilih barang apa saja yang dibawa agar total nilainya paling besar. 

PENYELESAIAN MENGGUNAKAN ALGORITMA BFS : 

Bayangkan kita sedang berdiri di sebuah persimpangan : 

  • Setiap kali kita memutuskan “ambil barang ini atau tidak”, kita bergerak ke state baru.
  • Kita pakai BFS supaya bisa menyapu semua kemungkinan pilihan dari yang sedikit barang ke banyak barang.

Misalnya:

  • Awal (tas kosong, 0 kg, nilai 0).

  • Dari sini kita bisa memilih: ambil barang 1, atau lewati barang 1.

  • Dari tiap pilihan, kita lanjut ke barang berikutnya, lagi-lagi punya 2 opsi: ambil atau lewati.

  • Begitu terus sampai semua barang diperiksa.

Dengan BFS, kita gunakan queue untuk menyimpan state (barang_ke, total_berat, total_nilai, daftar_barang_yang_diambil).

DATA BARANG : 
1. Barang 1: (6 kg, 30) 
2. Barang 2: (3 kg, 14) 
3. Barang 3: (4 kg, 16) 
4. Barang 4: (2 kg, 9) 
5. Barang 5: (5 kg, 20) 

Kapasitas Tas  = 10kg

IMPLEMENTASI CODE JAVA :





OUTPUT : 



KESIMPULAN

    BFS menyapu semua kemungkinan mulai dari tas kosong, lalu coba tambahkan barang satu per satu. Setiap kombinasi dicek apakah melebihi kapasitas atau tidak. Saat kombinasi {1, 3} ditemukan, nilainya 46, dan ternyata itu yang paling besar di antara semua kombinasi valid.














Komentar

Posting Komentar