Depth-First Search (DFS) adalah salah satu algoritma pencarian yang menggunakan struktur data Stack saat mencapai suatu simpul atau vertex yang terhubung dalam suatu graph. Kemampuannya dalam menemukan simpul-simpul yang belum dikunjungi memudahkan pencarian solusi optimum dalam suatu persoalan termasuk persoalan lintasan terpanjang (longest path problem).Berikut ini merupakan implementasi Algoritma DFS dalam Project Actionscript menggunakan Adobe Flash CS5. Ide dasar dari project ini adalah dimisalkan sebuah robot yang harus menyusuri sebuah ruangan untuk mencari jalan keluar.
Gambaran algoritma pencarian DFS adalah algoritma pencarian mendalam. Hal ini berarti algoritma ini akan mengunjungi node pertama yang dibangkitkan dari node sebelumnya. Misalkan pada gambar disamping, node awal (initial state) adalah satu (1) dari node tersebut dibangkitkan empat arah yang mungkin bisa dilewati si robot yaitu a,b,c,d. Dalam program, node a (level 1) adalah node yang pertama dibangkitkan sehinga node inilah yang pertama dikunjungi. Dari node a (level 1), DFS akan membangkitkan lagi empat arah yang mungkin bisa dilewati si robot (level 2) dan mengunjungi node pertama yang dibangkitkan. Misalkan pada level 3, node yang dibangkitkan pertama kali (Node a di level 3) ternyata node tersebut tidak dapat dilewati maka DFS akan melanjutkan ke node selanjutnya yaitu node b (level 3) dan membangkitkan empat kemungkinan lagi (level 4). Jika empat kemungkinan (misalkan di level 4) tidak dapat dilewati, DFS akan kembali ke node sebelumnya (level 3) dan mengunjungi node selanjutnya. Misalkan semua node di level 3 sudah dikunjungi namun belum menemukan goal state dan semuanya merupakan jalan buntu, DFS akan kembali ke level sebelumnya dan mengunjungi node yang belum dikunjungi. Begitu seterusnya sampai goal state ditemukan.
Dalam program, robot tersebut hanya bisa bergerak ke arah kanan, bawah, kiri dan atas. Arah gerak robot dapat ditunjukkan seperti gambar disamping. Setiap robot tersebut melangkah, robot akan memeriksa apakah jalur a bisa dilewati? Jika bisa, robot akan melangkah dan menandai bahwa lantai tersebut telah dikunjungi. Setelah itu, robot akan memeriksa lagi apakah jalur a bisa dilewati? Jika tidak, robot akan memeriksa jalur b. Agar tidak tersesat, robot hanya akan mengunjungi lantai yang belum dilewati. Lantai yang telah dikunjungi boleh dilewati lagi saat robot tidak menemukan jalan (liat level 4 gambar sebelumnya). Sehingga saat jalur a dan jalur b tidak dapat dilewati, robot akan memeriksa jalur c. Karena jalur c sudah dilewati, robot tidak akan melangkah ke jalur c sebelum memeriksa jalur d. Jika jalur d bisa dilewati, robot akan melangkah ke jalur d. Jika jalur d tidak dapat dilewati, robot akan melewati jalur c (mundur). Ilustrasi tersebut dapat dilihat pada gambar berikut. 
Dalam ruangan tersebut terdapat lantai yang dapat dilewati (lantai putih), lantai yang tidak dapat dilewati (lantai hitam) dan lantai yang telah dilewati (lantai abu-abu). Robot tersebut akan menentukan kemana dia akan melangkah dan merekam lantai mana yang telah ia lewati dan yang belum dilewati. Agar gambaran mengenai DFS menjadi lebih jelas, lantai hitam ditentukan secara random sehingga gerak robot berubah-ubah sesuai letak lantai hitam. Goal state selalu berada di tengah dan lantai di sekitarnya selalu lantai putih. Hal ini dimaksudkan untuk menghindari goal state tersebut tertutup lantai hitam. Andaikan goal state tidak ditemukan (tertutup lantai hitam) robot akan kembali ke node awal (initial state) dan berhenti.
Lebih jelasnya sillahkan download prjoject dalam Adobe Flash CS5 Depth First Search (DFS) Actionscript 2.0
No comments:
Post a Comment