Efisiensi Waktu Algoritma A* Untuk Penentuan Jalur Optimal Pada Peta Geografis

Abstract

Pencarian jalur pada pew geografis mempunyai aplikasi di banyak bidang. Jalur diusahakan supaya optimal, clalam artian adalah jalur terpendek dengan biaya terkecil. Algoritma A* adalah sate dari banyak algoritma pencarian jalur pada pew geografis. Keunggulan dari algoritma ini adalah efesiensi waktu dengan tidak mengorbankan perhitungan biaya. Hal ini dimungkinkan dengan selain memperhitungkan biaya yang diperlukan, algoritma ini juga menggunakan fungsi estimasi untuk memprioritaskan arah pencarian yang benar. Walaupun algoritma ini mempunyai efisiensi waktu, kasus terburuk dapat tetjadi sehingga algoritma ini bekerja seperti algoritma Dijkstra yang dapat dikatakan memerlularm waktu yang cukup lama. Duct hal yang dapat menyebabkan kasus ini adalah keadaan sepadan dan jalur yang dicari memang tidak ada. Dengan menggunakan aproksimasi garis lurus keadaan sepadan dapat di minimalisasikan, dan pendekatan bi-directional dapat digunakan untuk mengatasi masalah ketiadacm jalur. Walaupun begitu, jika jalur memang dapat ditemzikan, pendekatan bi-directional cenderung memperlambat kinerja algoritma A*.