Pencarian Rute Terpendek Menggunakan Iterative Deepening A* dengan Stochastic Node Caching Studi Kasus Mobile GIS
| Main Author: | Dimas Wibisono Prakoso |
|---|---|
| Format: | Bachelors |
| Terbitan: |
Universitas Telkom
, 2008
|
| Subjects: | |
| Online Access: |
https://openlibrary.telkomuniversity.ac.id/pustaka/93891/pencarian-rute-terpendek-menggunakan-iterative-deepening-a-dengan-stochastic-node-caching-studi-kasus-mobile-gis.html |
Daftar Isi:
- 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.<br> 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.<br> 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.<br>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.<br> 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.<br> 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.<br>Keyword: Mobile GIS, search algorithm, heuristic, shortest path finding, A*, IDA* MREC, IDA* SNC