Penentuan Rute Terpendek Menggunakan Variasi Fungsi Heuristik Algoritme A* Pada Mobile Devices

Abstract

GPS (Global Positioning System) is a technology that can help people in reaching the destination place in a fastest time and shortest route. Many mobile devices, some of them are cellular phones, have GPS facility. But this type of cellular phone is still expensive. This research intended to develop a shortest path searching application for mobile devices using variation of heuristic function A* algorithm, such as Manhattan, Euclidian, and Square of Euclidian. In addition, we intended to compare the execution time of these heuristic functions in finding shortest route. The data used in the experiment was Bogor Agricultural University map that obtained from Bogor Agricultural University Facility and Property Directorate. The map ought to modified to grid form to be appeared in cellular phone screen. The matrix that used to grid had a size of 15 x 12 and values of 0, 1, 5, 6, 7, 8, 9, and 10. Value of 0 expressed walkable route, and value of 1 expressed unwalkable route. The rest values expressed the map facilities, like faculties and rectorate buildings. The experiments indicated that Square of Euclidian had faster execution time and less amount of checked nodes than other heuristic functions. The lack was that this algorithm did not always provide shortest route. Euclidian heuristic function had slower execution time and more amount of checked nodes than others, whereas Manhattan have faster execution time and less amount of checked node than Euclidian. Euclidian and Manhattan heuristic function always provide shortest route in finding destination.