PENCARIAN RUTE TERPENDEK DENGAN METODE DFS 

Saat ini teknologi dan informasi di dunia berkembang dengan sangat pesat. Banyak aspek kehidupan yang awal mulanya dilakukan oleh sekelompok manusia atau makhluk hidup mulai digantikan dengan suatu sistem yang lebih canggih dan lebih simple. Hal itu ditunjang dengan tuntutan dan gaya hidup manusia yang saat ini membutuhkan teknologi ringkas agar seluruh pekerjaan dapat dilakukan secara cepat, tepat dan efisien. Salah satunya yakni dalam menentukan rute yang dapat ditempuh dalam perjalanan dari kota C ke kota E dengan menggunakan algoritma Depth First Search Algorithm.

Algoritma Depth First Search (DFS) adalah suatu metode pencarian pada sebuah pohon dengan menelusuri satu cabang sebuah pohon sampai menemukan solusi. Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri dan dilanjutkan pada node sebelah kanan.

Cara kerja : Cara kerja algoritma depth first search hampir sama. Algoritma ini melakukan penelusuran simpul dengan pendekatan mendalam. Metode Depth First search mengeksplor setiap kemungkinan cabang yang mungkin akan menjadi sebuah solusi sebelum mengeksplor ke cabang yang lain. Membuat tabel index dan decesion tree untuk mempermudah penelitan agar mendapatkan solusi yang sesuai dengan tujuan.

Kefektifan suatu algortima pencarian dalam menemukan rute atau tujuan tergantung pada proses atau langkah-langkah yang di berikan oleh algortima itu sendiri, sehingga ada algoritma tertentu yang sesuai untuk pencarian rute terpendek ada juga algoritma tertentu yang sesuai untuk pencarian perjalanan yang paling efektif dan efisien.

Kelebihan dan Kekurangan DFS

a. Kelebihan DFS

Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

b. Kekurangan DFS

Jika pohon yang dibangkitkan mempunyai level dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).

Jika terdapat lebih dari 1 solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

Deskripsi permasalahan 

Pada permasalahan ini mengambil contoh kasus perjalanan transportasi alat dengan menggunakan

jalur Bus. Pada simulasi jalur bus yang digunakan adalah jalur transportasi yang ada antara kota

C menuju ke kota E.

Tujuan

Menemukan solusi untuk perjalanan dari kota C menuju ke kota E dengan metode Dept First Search (DFS)

Metode Depth First search mengeksplor setiap kemungkinan cabang yang mungkin akan menjadi sebuah solusi sebelum mengeksplor ke cabang yang lain. Membuat tabel index dan decesion tree untuk mempermudah penelitan agar mendapatkan solusi yang sesuai dengan tujuan.

CONTOH SOAL 

HASIL DAN DISKUSI 

Hasil penggunaan metode DFS :

C-A-B-D-G-E

dengan total bobot

5+7+2+7+2 = 23

KESIMPULAN

Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Metode ini melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.