PERBANDINGAN KINERJA PENDEKATAN DYNAMIC PROGRAMMING DAN ALGORITMA A* DALAM MENENTUKAN RUTE OPTIMAL DARI KAMPUS I MENUJU KAMPUS IV UNIVERSITAS BENGKULU

Studi kasus perjalanan dari Kampus I menuju Kampus IV Universitas Bengkulu
digunakan untuk membandingkan kinerja pendekatan Dynamic Programming (DP)
dan Algoritma A* dalam pencarian rute optimal. Fokus analisis adalah panjang
jalur, jumlah simpul yang dieksplorasi, waktu eksekusi, dan kontribusi hasil dalam
memberikan rekomendasi metode pencarian rute yang tepat untuk aplikasi nyata.
Hasil menunjukkan bahwa kedua metode menghasilkan rute yang sama dengan
jarak tempuh 9.790 meter, yaitu rute �1 → �3 → �4 → �8 → �12 → �13 → �24 →
�35 → �36 → �38 → �39 → �42 → �56. Jumlah simpul yang dieksplorasi
menunjukkan perbedaan kinerja: DP memerlukan 28 tahap pencarian, sedangkan
Algoritma A* hanya 25 langkah pencarian. Selain itu, DP membutuhkan waktu
eksekusi lebih cepat dengan 0,0004 detik, sedangkan Algoritma A* membutuhkan
0,0055 detik. Perbedaan waktu ini tidak signifikan dalam aplikasi nyata.
Kesimpulan menunjukkan bahwa DP dan Algoritma A* keduanya akurat dalam
menentukan rute terpendek, tetapi Algoritma A* lebih efektif digunakan pada kasus
nyata. Kontribusi utama terletak pada rekomendasi Algoritma A* untuk sistem
navigasi modern, sedangkan DP dapat digunakan sebagai metode verifikasi dalam
pencarian rute optimal.
Kata Kunci: Algoritma A*, Dynamic Programming, Rute Optimal, Simpul,
Waktu Eksekusi.