Depft First Search

Depft First Search

Teknik ini melakukan pencarian pada setiap tingkatan atau level dari sebelah kiri sampai ke bagian terdalam terlebih dulu, jika solusi belum ditemukan maka lanjut ke sebelah kanan.
Kelebihan DFS adalah pemakaian memori yang lebih kecil. DFS hanya menyimpan sekitar bd simpul, di mana b adalah fakor percabangan dan d adalah kedalaman solusi. Jika b = 10 dan d = 3, maka jumlah simpul yang disimpan di memori adalah 1 + 10 + 10 + 10 = 31.

Kelemahan pada DFS adalah jika terdapat tingkatan yang sangat dalam maka tidak ada jaminan kalau solusi akan ditemukan. Dan jika terdapat 2 solusi yang ditemukan dilevel berbeda maka DFS tidak bisa menentukan solusi mana yang terbaik.