Pengukuran Beban Komputasi Algoritma Dijkstra, A*, dan Floyd-Warshall pada Perangkat Android

ULTIMA Computing

View Publication Info
 
 
Field Value
 
Title Pengukuran Beban Komputasi Algoritma Dijkstra, A*, dan Floyd-Warshall pada Perangkat Android
 
Creator Djojo, Michael Alexander
Karyono, Karyono
 
Description Perkembangan teknologi di bidang komunikasi menciptakan berbagai kemudahan bagi pengguna untuk melakukan pertukaran informasi tanpa mengenal jarak secara geografis. Pada jaringan komunikasi, pertukaran informasi memerlukan pengaturan rute sehingga dicapai jalur terpendek untuk mengoptimalkan proses pengiriman data. Penelitian untuk mencari algoritma jalur terpendek masih terus dilakukan. Penelitian ini membandingkan algoritma Dijkstra, A*, dan Floyd-Warshall dari sisi waktu, beban komputasi dan penggunaan memori. Topologi yang digunakan dalam penelitian adalah topologi jaringan mesh karena dapat mewakili kondisi nyata. Aplikasi berbasis Android dapat digunakan sebagai simulator untuk memetakan vertice dan edge ke dalam kumpulan node dan channel yang saling berhubungan. Kompleksitas komputasi dalam pencarian jalur terpendek menjadi hal yang penting karena terdapat keterbatasan prosesor dan memori. Kompleksitas rute akan sebanding dengan skala jaringan mesh. Dari simulasi diperoleh nilai beban komputasi dan waktu simulasi yang sebanding dengan fungsi kuadrat jumlah simpul untuk ketiga algoritma tersebut. Hasil pengujian menunjukkan algoritma A* memiliki beban komputasi dan waktu simulasi yang paling kecil dibandingkan algoritma Dijkstra dan Floyd-Warshall tanpa mempengaruhi hasil pencarian rute terpendek. Hal ini disebabkan algoritma A* melakukan operasi pencarian dengan memanfaatkan nilai heuristik terhadap simpul tujuan, sehingga tidak semua simpul dilakukan pengecekan. Namun algoritma Dijkstra paling unggul dalam penggunaan memori. Floyd-Warshall menghasilkan nilai kompleksitas yang buruk pada proses pancarian jalur, semua data bobot kanal akan ditampung ke dalam matriks dua dimensi lalu diproses menggunakan operasi perulangan yang bertingkat.
 
Publisher Jurnal Sistem Komputer
ULTIMA Computing
 
Contributor
 
Date 2013-09-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Artikel yang telah di-peer-review
 
Format application/pdf
 
Identifier http://ejournals.umn.ac.id/index.php/SK/article/view/285
 
Source Jurnal Sistem Komputer; Vol 5, No 1 (2013): Ultima Computing
ULTIMA Computing; Vol 5, No 1 (2013): Ultima Computing
2549-4007
2355-3286
 
Language ind
 
Relation http://ejournals.umn.ac.id/index.php/SK/article/view/285/251
 
Rights ##submission.copyrightStatement##
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library