Page 18 - CalonFlipSearching
P. 18
8
= 0 +
2
= 4
Maka data yang dicari (9) berada pada elemen array yang ke-4.
A. Depth-First Search (DFS)
Pencarian DFS dilakukan pada satu node dalam setiap level dari
yang paling kiri. Jika pada level yang paling dalam solusi belum
ditemukan, maka pencarian dilanjutkan pada node sebelah kanan,
node yang yang berada di kiri dapat dihapus dari memori (Baidari, dkk.,
2012). Jika pada level yang paling dalam tidak ditemukan solusi, maka
pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya
sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan
proses backtracking (penelusuran balik untuk mendapatkan jalur yang
dinginkan). Berikut langkah-langkah strategi pencarian DFS:
1. Mengunjungi node v
2. Mengunjungi node w yang bertetangga dengan simpul v
3. Mengulangi DFS dari node w
4. Apabila semua node yang bertetangga sudah dikunjungi,
5. Pencarian selesai, apabila semua node sudah dikunjungi
Kelebihan DFS adalah :
1. Penggunaan memori tidak terlalu banyak, berbeda dengan
BFS yang harus menyimpan semua node yanhg pernah
dibangkitkan
2. Apabila solusi yang dicari berada pada level yang paling kiri,
maka DFS akan menemukan secara cepat
10
