Algoritma dalam metode pencarian dibagi menjadi dua yakni pencarian buta atau blind search dan heuristic search. Kali ini kami akan membahas salah satu pencarian buta atau blind search yakni Depth First Search.
Algoritma jenis ini merupakan salah satu algoritme terpopuler yang sering digunakan dalam menemukan seluruh simpul yang berasal dari sebuah graf atau tree.
Section Artikel
Apa Itu Depth First Search
Algoritma Depth First Search merupakan algoritma pencarian yang mendalam yang diawali dengan node awal kemudian dilanjutkan dengan hanya melakukan kunjungan pada node anak yang paling kiri di tingkat selanjutnya.
Depth first traversak merupakan algoritma rekursif yang dimanfaatkan dalam menemukan semua simpul graf maupun tree. Traversal itu sendiri artinya mengunjungi node yang berasal dari sebuah graf secara keseluruhan.
Depth First Search atau yang disingkat dengan DFS dipelajari pertama kali mulai dari abad ke – 19 oleh seorang matematikawan asal Prancis bernama Prancis Charles Pierre Tremaux yang merupakan strategi memecahkan suatu labirin.
DFS menjadi salah satu algoritma yang digunakan secara umum untuk melintasi dan mencari sebuah struktur data graph maupun tree dengan teknik backtracking. Tree itu sendiri merupakan graph yang terhubung dan tidak ada sirkuit di dalamnya.
Jika sudah menemukan sebuah solusi, tidak perlu lagi proses backtracking atau penelusuran balik dalam menemukan jalur sesuai dengan yang diharapkan.
Cara Kerja Depth First Search
Untuk dapat mengerti dan memahami bagaimana cara kerja algoritma yang satu ini, terlebih dahulu coba untuk memahami labirin seperti pada berikut ini.
Bagaimana cara kita memecahkan labirin tersebut? Pastinya kita akan memilih rute mengikuti jalanan, terus berjalan hingga kita menemukan jalan buntu. Ketika kita menemui jalan buntu, kita akan melangkah dan memilih mundur kemudian mencari jalan yang belum kita coba sebelumnya. Kita akan memilih mengambil rute baru. Jika di depan kita menemukan jalan buntu lagi, kita akan melangkah mundur lagi hingga mendapat solusi dan jalan keluar yang benar.
Algoritma depth first search memiliki cara kerja yang serupa dengan labirin di atas. Algoritma ini akan terus menelusuri simpul dengan berlandaskan pendekatan secara mendalam.
Prioritas utama dari algoritma DFS adalah pertama – tama mengunjungi simpul hingga level yang paling dalam. Lalu jika menemukan jalan yang buntu, atau tidak ada lagi simpul yang bertetangga, algoritma tersebut akan mengecek simpul yang sebelumnya sudah dikunjungi dan yang memiliki tetangga dengan simpul lain yang sebelumnya tidak dikunjungi, kemudian menelusuri simpul tersebut.
Atau dengan kata lain, simpul cabang atau anak yang sebelumnya sudah dikunjungi terlebih dahulu seperti pada ilustrasi DFS di bawah ini.
Kelebihan Depth First Search
Berikut beberapa kelebihan Depth First Search yang perlu kalian ketahui.
- DFS bisa menemukan sebuah solusi tanpa harus memeriksa berbagai ruang pencarian sama sekali. Hal tersebut sangat menguntungkan terutama ketika banyak solusi yang diterima, DFS akan menghentikan tepat pada salah satu solusi yang sesuai.
- DFS lebih efisien dan efektif dibanding algoritma lainnya karena ruang pencariannya memiliki banyak cabang, oleh karena itu tidak diperlukan eksekusi terhadap semua simpul yang terdapat di level tertentu yang ada pada daftar open.
- DFS hanya membutuhkan memori yang relatif kecil. Hal tersebut dikarenakan node yang ada pada lintasan yang aktif saja yang akan disimpannya.
Kekurangan Depth First Search
Di balik kelebihannya, terdapat pula beberapa kekurangan dari algoritma Depth First Search antara lain sebagai berikut.
- Tidak memungkinkan ditemukan sebuah tujuan yang sesuai dengan harapan. Melainkan, hanya akan ada satu solusi pada masing – masing pencarian.
- Adanya peluang tidak ditemukannya sebuah solusi yang optimal yang diperlukan.
- Memungkinkan terjebak pada sebuah jalur pencarian yang tidak diperlukan atau tidak berguna.
Contoh Depth First Searchi
Berikut contoh DFS jika dimasukkan dalam studi kasus pencarian jarak terdekat Arad – Bucharest dan berikut Peta Rumania.
Untuk menyelesaikan kasus yang seperti ini, diperlukan gambaran peta graph yang lebih sederhana. Kita dapat mengubah Peta Rumania menjadi bentuk peta graph sederhana seperti pada berikut ini.
- Penyelesaian
Algoritma DFS merupakan algoritma pencarian yang memulai dari nodel yang paling awal kemudian menuju node anak yang paling kiri di tingkatan selanjutnya. Berdasarkan gambar si bawah ini, kita bisa menggambarkan Tree saat menyelesaikan sebuah kasus menggunakan algoritma DFS.
Pada tree ini, tidak semua kota ditulis, misalnya kota yang terhubung dari node S dan T dengan lengkap. Oleh karena itu, target B akan menemukan anak paling kiri yang mana pencarian akan berhenti. Dengan begitu, pohon yang ditengah dan yang kanan tidak akan dilewatinya.
Demikian gambaran dari penyelesaian pencarian kota B dengan menggunakan algoritma Depth First Search.
- Implementasi
- Penjelasan
Proses pencarian rute dengan menggunakan algoritma ini akan mengerjakan pencarian secara mendalam yang dimulai dengan node yang paling awal. Kemudian akan berlanjut dengan menelusuri node anak yang paling kiri di tingkat selanjutnya.
Pada pohon yang sebelumnya, targetnya berada pada anak terdalam yang paling kiri. Dengan itu, berhasil mendapatkan rute sesuai dengan algoritma DFS yakni A Z O S F R.
Berdasarkan hasil pencarian sebelumnya, jarak dari Arad menuju Bucharest akan ditemukan dengan memanfaatkan algoritma DFS seperti pada gambar berikut ini.
Kesimpulan
Pada studi kasus yang dijelaskan ini, algoritma DFS kurang efisien dengan path – cost 607 KM. Meskipun demikian, pada kasus yang lain, ada kemungkinan bahwa algoritma Depth First Search bisa jadi lebih efisien, tergantung kasusnya masing – masing.
Begitulah penjelasan mengenai algoritma Depth First Search beserta dengan contoh studi kasus dan penyelesaiannya. Semoga mudah dimengerti dan dipahami. Terima kasih.
