Pencarian Rute Terpendek Menggunakan Iterative Deepening A* dengan Stochastic Node Caching Studi Kasus Mobile GIS

Dimas Wibisono Prakoso

Informasi Dasar

113010095
005.1
Karya Ilmiah - Skripsi (S1) - Reference

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

Subjek

Informatika Teori dan Pemrograman
 

Katalog

Pencarian Rute Terpendek Menggunakan Iterative Deepening A* dengan Stochastic Node Caching Studi Kasus Mobile GIS
 
 
Indonesia

Sirkulasi

Rp. 0
Rp. 0
Tidak

Pengarang

Dimas Wibisono Prakoso
Perorangan
M. Zuliansyah, Agung Toto Wibowo
 

Penerbit

Universitas Telkom
Bandung
2008

Koleksi

Kompetensi

 

Download / Flippingbook

 

Ulasan

Belum ada ulasan yang diberikan
anda harus sign-in untuk memberikan ulasan ke katalog ini