ABSTRAKSI: Pencarian rute terpendek pada sebuah peta GIS adalah satu fitur Mobile GIS yang bermanfaat bagi para penggunanya. Pencarian rute terdiri dua tahapan yaitu pembangungan graf dan pencarian rute itu sendiri.
Algoritma pencarian heuristik A* bisa digunakan untuk masalah pencarian rute namun memiliki kelemahan yaitu besarnya kebutuhan memori. Kelemahan ini menjadikannya kurang ideal bila diimplementasikan pada perangkat bergerak sebagai client Mobile GIS. Algoritma IDA* dan IDA* MREC bisa mengatasi ini namun memiliki kelemahan lain yaitu jumlah ekspansi node yang terlampau banyak. Algoritma IDA* SNC mencoba mengatasi kelemahan semua algoritma ini dengan berperilaku seperti IDA* namun memiliki sebuah cache dan nilai probabilitas untuk mengurangi jumlah node yang diekspansi.
Pada tugas akhir ini, algoritma IDA* SNC diimplementasikan sebagai algoritma pencarian rute terpendek pada Mobile GIS. Hasil uji coba dan analisis menunjukan sejauh mana penghematan pemakaian memori IDA* SNC bila dibandingkan dengan A* dan penurunan ekspansi node bila dibandingkan dengan IDA* MREC dalam masalah pencarian rute terpendek.
Kata Kunci : Mobile GIS, algoritma pencarian, heuristik, pencarian rute terpendek, A*, IDA* MREC, IDA* SNCABSTRACT: Shortest path finding in a GIS map is one of Mobile GIS feature that is very useful for its user. Path finding consist of two steps which is forming graphs and path-finding itself.
A* search algorithm can be used for path finding problem but it has a disadvantage: memory requirement is too much. This disadvantage make its less ideal if implemented on mobile device as Mobile GIS client. IDA* and IDA* SNC try to solve this, but still ,it has another disadvantage: the amount of expanded node is too much. IDA* SNC algorithm tries to solve all of the previous algorithm disadvantage by behave like IDA* but it has a cache and a probability value to reduce the number of node expansion.
On this final final project, IDA * has been implemented as shortest path finding algorithm on Mobile GIS. The testing and analysis result show how far the efficiency of IDA* SNC memory usage compared with A* and the reduce of node expansion compared with IDA* MREC in shortest path finding problem.
Keyword: Mobile GIS, search algorithm, heuristic, shortest path finding, A*, IDA* MREC, IDA* SNC