Suprapto , 4611412006 (2017) PERBANDINGAN PERFORMANSI PENCARIAN JARAK TERPENDEK MENGGUNAKAN ALGORITMA A STAR (A*) DAN ALGORITMA DIJKSTRA (STUDI KASUS: JALAN PARIWISATA KABUPATEN PATI). Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF - Published Version Download (471kB) | Preview

Abstract

Perjalanan dengan jarak terkecil dari lokasi awal ke lokasi tujuan merupakan harapan para pengguna jalan. Hal ini menyebabkan pengguna jalan harus mengetahui lintasan yang akan dilewati agar bisa memperkirakan lintasan mana yang akan dilalui sehingga bisa ditemukan jarak yang terpendek. Pencarian jarak terpendek dapat dikatakan juga menentukan lintasan yang paling optimal, yaitu lintasan dengan jarak terpendek dan biaya terkecil. Beberapa algoritma yang dapat digunakan untuk mencari jarak terpendek, misalnya algoritma Dijkstra dan algoritma A Star (A*). Algoritma A Star (A*) adalah sebuah algoritma yang telah diperkaya dengan menerapkan suatu heuristik, dengan membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan. Algoritma Dijkstra adalah algoritma untuk menemukan jarak terpendek dari satu titik ke titik lain di graf berbobot. Dalam pencarian jarak terpendek algoritma Dijkstra bekerja dengan mencari bobot yang paling minimal dari suatu graf berbobot. Tujuan penelitian ini untuk membandingkan performansi antara algoritma A Star (A*) dan algoritma Dijkstra adalah untuk mengetahui algoritma mana yang mempunyai performansi komputasi lebih baik dalam menyelesaikan masalah pencarian jarak terpendek. Berdasarkan hasil pengujian untuk setiap jarak lintasan yang ada. Hasil performansi pencarian jarak terpendek menggunakan algoritma A Star (A*) dan algoritma Dijkstra (1) Hasil pencarian lintasan terpendek memperlihatkan jarak pencarian jarak terpendek algoritma A Star (A*) dan algoritma Dijkstra menghasilkan jarak yang sama, (2) Performansi penggunaan memori yang didapat menunjukkan hasil yang sama besar yakni 0,0037155 MB, (3) Waktu eksekusi yang diperlukan menggunakan algoritma A Star (A*) dan algoritma Dijkstra menunjukkan adanya perbedaan yang tidak terlalu signifikan yakni waktu eksekusi algoritma A Star (A*) lebih kecil dari pada algoritma Dijkstra, dengan rata-rata 0,0057586 detik dan 0,011407058 detik. Berdasarkan hasil pengujian membuktikan bahwa algoritma A Star (A*) memiliki performansi lebih baik dibandingkan dengan algoritma Dijkstra dalam hal waktu eksekusi sedangkan dalam pencarian jarak terpendek dan penggunaan memori algoritma Dijkstra memiliki performansi yang sama baik.

Actions (login required)

View Item