UMN Knowledge Center

Analisis perbandingan beban komputasi algoritma dijkstra,a*, dan floyd-warshall dalam topologi jaringan mesh

Djojo, Michael Alexander (2013) Analisis perbandingan beban komputasi algoritma dijkstra,a*, dan floyd-warshall dalam topologi jaringan mesh. Bachelor Thesis thesis, Universitas Multimedia Nusantara.

[img]
Preview
Text
HALAMAN AWAL.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (896kB) | Preview
[img]
Preview
Text
BAB I.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (777kB) | Preview
[img]
Preview
Text
BAB II.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (839kB) | Preview
[img]
Preview
Text
BAB III.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (792kB) | Preview
[img] Text
BAB IV.pdf
Restricted to Registered users only
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (997kB)
[img]
Preview
Text
BAB V.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (893kB) | Preview
[img]
Preview
Text
BAB VI.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (809kB) | Preview
[img]
Preview
Text
BAB VII.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (755kB) | Preview
[img]
Preview
Text
DAFTAR PUSTAKA.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (813kB) | Preview
[img]
Preview
Text
LAMPIRAN.pdf
Available under License Creative Commons Attribution Non-commercial Share Alike.

Download (1MB) | Preview

Abstract

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. Setiap edge pada jaringan mesh tersebut memiliki nilai sehingga membentuk suatu graf berbobot (weighted graph). Simulator jaringan OMNeT++ digunakan untuk memetakan vertice dan edge ke dalam kumpulan node dan channel yang saling berhubungan. Beban 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 beban komputasi yang buruk pada proses pancarian jalur, semua data bobot kanal akan ditampung ke dalam matriks dua dimensi lalu diproses menggunakan operasi perulangan yang bertingkat. Dalam penelitian ini juga dilakukan implementasi algoritma shortest path terhadap perangkat seluler berbasis Android. Hasil pengujian memperoleh hasil bahwa bahwa algoritma A* unggul dalam hal kompleksitas komputasi maupun waktu simulasi. Pengukuran kompleksitas dan waktu yang dihasilkan terhadap perangkat Android sebanding dengan pengujian pada simulator.

Item Type: Thesis (Bachelor Thesis)
Subjects: Q Science > QA Mathematics > QA76 Computer software
Z Bibliography. Library Science. Information Resources > ZA Information resources > ZA4050 Electronic information resources > ZA4150-4380 Computer network resources
Divisions: Fakultas Teknik Informatika > Program Studi Teknik Komputer
Depositing User: mr admin umn
Date Deposited: 02 Aug 2017 07:37
Last Modified: 05 Oct 2017 03:10
URI: http://kc.umn.ac.id/id/eprint/1539

Actions (login required)

View Item View Item