Evaluasi Kinerja Teknik Pencarian DFS dan BFS

Aspek Penilaian

1. Completeness
   • Menjamin ditemukan solusi jika ada.
2. Optimality
   • Apakah jalur ke solusinya memiliki biaya minimal?
3. Kompleksitas Waktu
   • Waktu yang diperlukan untuk mencapai solusi.
4. Kompleksitas Ruang
   • Memori yang diperlukan selama pencarian.

Istilah Khusus

• B (Branching Factor): Maksimum percabangan dari suatu simpul.
• D: Kedalaman dari solusi terbaik.
• M: Maksimum kedalaman dari ruang status.

Ilustrasi dengan 8-Puzzle

• Hillstate: Status awal.
• Goalstate: State akhir yang diinginkan.
• Aksi yang mungkin dilakukan: up, down, left, right.

Contoh Pohon Ruang Status

• Simpul menunjukkan state atau kondisi ubin kosong.
• Pencabangan dari simpul adalah aksi yang mungkin dilakukan.

DFS (Depth-First Search)

• Ilustrasi DFS pada 8-Puzzle:
  • Contoh langkah: simpul 1 -> 18 -> 28 -> 29 -> 30 -> 31.
• Properti DFS:
  • Completeness: Dijamin selama ada penanganan untuk redundant paths dan repeated states.
  • Optimality: Belum tentu optimal karena pencarian dilakukan secara mendalam.
  • Kompleksitas Waktu: B Pangkat M (kedalaman maksimum).
  • Kompleksitas Ruang: BM (lebih efisien daripada BFS).

BFS (Breadth-First Search)

• Ilustrasi BFS pada 8-Puzzle:
  • Urutan pencarian sesuai kedalaman: akar -> kedalaman 1 -> kedalaman 2, dst.
  • Semua simpul pada satu kedalaman dibangkitkan terlebih dahulu.
  • Contoh langkah: simpul 1 -> 3 -> 7 -> 14 -> 26 -> 46.
• Properti BFS:
  • Completeness: Dijamin mendapatkan solusi selama branching factor terbatas.
  • Optimality: Dijamin optimal jika langkah ke state berikutnya dianggap berbiaya sama.
  • Kompleksitas Waktu: B Pangkat D (kedalaman solusi).
  • Kompleksitas Ruang: B Pangkat D (tidak efisien).

Kesimpulan

• DFS: Efisien dalam ruang tapi belum tentu optimal dan kompleksitas waktu tinggi.
• BFS: Optimal dalam solusi dan terjamin memperoleh solusi, tetapi tidak efisien dalam ruang.
• Pendekatan gabungan: Mengambil manfaat terbaik dari DFS dan BFS.

Video Selanjutnya

• Pembahasan mengenai backtracking dalam DFS.