DESAIN DAN ANALISIS ALGORITMA DIJKSTRA DAN METODE VISIBILITY GRAPH NAIVE UNTUK PENYELESAIAN PERSOALAN SPOJ THE ARCHIPELAGO

Reva Yoga Pradana
Submission Date: 2016-07-19 16:55:57
Accepted Date: 2016-11-23 18:14:55

Abstract


Permasalahan pada SPOJ 780 The Archipelago adalah sebagai berikut. Diberikan sekumpulan pulau yang memiliki beberapa terminal dan area terlarang yang tidak boleh dilewati selama jalur darat di pulau tersebut. Kemudian, dicari kemungkinan rute terpendek yang menghubungkan terminal di suatu pulau ke terminal di pulau yang lain, tanpa melewati area terlarang manapun, dan total jarak pada 1 pulau harus dibulatkan ke atas. Untuk menyelesaikan permasalahan tersebut, dibutuhkan algoritma Visibility Graph Navie, untuk mengetahui titik-titik mana saja yang dapat dilalui, dan algoritma Dijkstra untuk mengetahui rute terpendeknya. Selain itu, juga dilakukan beberapa optimasi untuk mempercepat kinerja sistem, yaitu dengan cara penyederhanaan penggambaran entitas halangan, pengurangan jumlah vertex yang harus dicek visibilitasnya, dan penggunaan backtracking dari vertex tujuan hingga vertex sumber untuk mengetahui total jarak pada tiap pulau.

Cara kerja dari sistem adalah sebagai berikut. Diberikan masukan sesuai deskripsi permasalahan. Setelah masukan berhasil diolah, sistem akan memanggil algoritma Dijkstra. Pada tiap current vertex yang dihasilkan di dalam Dijkstra, sistem akan memanggil algoritma Visibility Graph Naive, untuk mengecek visibilitas dari vertex tersebut dengan vertex lain yang se-pulau, agar dapat diketahui vertex mana saja yang menjadi tetangganya. Dijkstra akan berhenti saat current vertex merupakan vertex tujuan. Kemudian saat Dijkstra telah berhenti, sistem akan menghitung total jarak pada tiap pulau, total jarak keseluruhan, dan menyimpan posisi yang dipilih pada rute terpendek

Hasil akhir menunjukkan bahwa sistem dapat berjalan cukup cepat berkat optimasi yang baik, dengan waktu rata-rata sebesar 0.2763 detik dan memori rata-rata 10.533 MB.

Keywords


Graph with Obstacles, Computational Geometry, Shortest Path, Visibility Graph, Dijkstra

References


O. C. M. v. K. M. O. Mark de Berg, Computational Geometry, 3rd penyunt., Berlin Heidelberg: Springer-Verlag, 2008.

S. Halim dan F. Halim, Competitive Programming 2, Singapore: Lulu Publisher, 2011.

Ĺ. Kuszner, “SPOJ.com - Problem ARCHPLG,” 15 March 2006. [Online]. Available: http://www.spoj.com/problems/ARCHPLG/.

A. Levitin, The Design & Analysis of Algorithms, 3rd penyunt., Pearson Education, Inc., 2012.


Full Text: PDF

CC Licencing


Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

Refbacks

  • There are currently no refbacks.


Lembaga Penjaminan Mutu, Pengelolaan dan Perlindungan Kekayaan Intelektual (LPMP2KI) ITS
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.