Pencarian Mendalam Pertama (Depth First Search)

Pencarian Mendalam Pertama (Depth First Search)

Pencarian dengan metode Depth First Search (DFS) dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi. Sebagai ilustrasinya dapat dilihat pada gambar 2.4.

Gambar 2.4 Pencarian mendalam pertama (Depth First Search)

(Sumber: Artificial Intelligence , Suyanto.ST.Msc, 2011)

Berdasarkan gambar , proses pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke cabang sebelumnya, turun ke bawah jika memang masih ada cabangnya. Begitu seterusnya hingga diperoleh tujuan (goal). Operasi semacam ini dikenal dengan sebutan backtracking.

Keuntungan dari metode DFS:

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, sehingga tidak memboros waktu untuk melakukan sejumlah besar keadaan ‘dangkal’ dalam permasalahan graf/pohon.

Kelemahan dari metode DFS:

1.      Memungkinkan tidak ditemukannya tujuan yang diharapkan.

2.      Hanya akan mendapatkan satu solusi pada setiap pencarian.

Share this post