BFS dan DFS Kelebihan Kekurangan dan Metodenya

Teknik Pencarian Breath First Search (BFS)

Metode pencarian dilakukan pada semua simpul dalam setiap level secara beurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian akan dilakukan pada level berikutnya dan seterusnya sampai ditemukan solusi. Dengan begitu, BFS menjamin ditemukannya solusi (Jika ada solusinya) dan solusi yang terbaik. Dengan kata lain, BFS adalah complete dan optimal. BFS harus menyimpan semua simpul yang pernah dibangkitkan agar dapat melakukan penelusuran simpul-simpul sampai bawah.

Keuntungan BFS yaitu, tidak akan menemukan jalan buntu. Jika ada satu solusi maka BFS akan menemukannya. Jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan (solusi terbaik).

Kelemahan BFS yaitu membutuhkan memori cukup besar, karena menyimpan semua node dalam satu pohon. Selain itu BFS membutuhkan waktu yang cukup lama, karena akan menguji tiap n level untuk menemukan atau mendapatkan solusi pada level yang ke-(n-1)

Teknik Pencarian Depth First Search (DFS)

Pencarian dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang terdalam, solusi masih belum juga ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri (yang sudah dipindai) dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya, dan seterusnya hingga ditemukan solusi.

Kelebihan DFS adalah pemakaian memori yang lebih sedikit. DFS hanya menyimpan sekitar bd dimana b adalah faktor percabangan dan d adalah kedalaman solusi. Hal ini berbeda dengan BFS yang harus menyimpan semua simpul yang pernah dibangkitkan. Kelebihan DFS yang lain yaitu jika solusi pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat.

Kelemahan DFS adalah jika pohon yang dibangkitkan mempunyai level yang sangat dalam, maka tidak menjamin ditemukannya solusi. Artinya DFS tidak complete. Selain itu, jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik, artinya DFS tidak optimal.

#algoritma BFS

#algoritma DFS

#kelebihan kekurangan BFS
#kelebihan kekurangan DFS
#metode BFS
#metode DFS
#teknik pencarian
#AI
#artificial intelligence