Depth First Search
Depth First Search
Pada
Depth First Search (DFS), proses akan dilakukan pada semua anaknya sebelum
dilakukan pencarian ke node-node (titik) yang selevel. Pencarian dimulai dari
node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga
ditemukannya solusi. Stack atau tumpukan adalah struktur data yang setiap
proses baik penambahan maupun penghapusan hanya bisa dilakukan dari posisi
teratas tumpukan. Cara kerja stack adalah LIFO (Last In First Out), dimana data yang terakhir masuk akan keluar
pertama.
Berikut analisis
ruang dan waktu untuk metode pencarian DFS :
1.
Diasumsikan :
·
Pohon pelacakan memiliki cabang yang selalu
sama, yaiu sebanyak b.
·
Tujuan dicapai pada level ke-d
2.
Analisis Ruang
·
Setelah berjalan 1 langkah, stack akan berisi b
node.
·
Setelah berjalan 2 langkah, stack akan berisi
(b-1) + b node.
·
Setelah berjalan 3 langkah, stack akan berisi
(b-1) + (b-1) + b node.
·
Setelah berjalan d langkah, stack akan berisi
(b-1) * d + 1 node, mencapai maksimum.
3.
Analisis Waktu
·
Pada kasus terbaik, DFS akan mencapai tujuan
pada kedalaman d pertama, sehingga dibutuhkan pencarian sebanyak d + 1 node.
·
Pada kasus terburuk, DFS akan mencapai tujuan
pada kedalaman d pada node terakhir, sehingga dibutuhkan pencarian sebanyak 1 +
b + b2 + b3 +….+ bd = (bd+1-1) / (
b-1)
Keuntungan
dari metode ini adalah :
1.
Membutuhkan memori yang relatif kecil, karena hanya
node-node pada lintasan yang aktif saja yang disimpan.
2.
Secara kebetulan, metode DFS akan menemukan solusi
tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
Kelemahan
dari metode ini adalah :
1.
Memungkinkan tidak ditemukannya tujuan yang diharapkan.
2.
Hanya akan mendapatkan 1 solusi pada setiap pencarian.
Gambar 2.16 Pohon
Pencarian Depth First Search
