Desain dan Analisis Algoritma Breadth First Search Sebagai Metode Penyelesaian Permasalahan Pencarian Cycle Graf: Studi Kasus SPOJ 28409 - Ada and Cycle

Liman, Christyanto (2018) Desain dan Analisis Algoritma Breadth First Search Sebagai Metode Penyelesaian Permasalahan Pencarian Cycle Graf: Studi Kasus SPOJ 28409 - Ada and Cycle. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

[img]
Preview
Text
05111440000087-Undergraduate_Theses.pdf - Accepted Version

Download (1MB) | Preview

Abstract

Permasalahan SPOJ “Ada and Cycle” mengangkat permasalahan perhitungan jarak terpendek yang berawal dari sebuah vertex dan berakhir pada vertex yang sama untuk setiap vertex yang ada. Pada permasalahan ini diberikan parameter masukan berupa jumlah vertex (N) dan sebuah adjacency matrix (H). Tujuan Tugas akhir ini adalah menyusun strategi penyelesaian, melakukan analisis dan desain algoritma dan mengevaluasi hasil dari kinerja algoritma penyelesaian permasalahan “Ada and Cycle” pada situs SPOJ. Metode yang dilakukan adalah pengoptimasian metode Breadth First Search agar memenuhi batasan waktu yang diberikan soal. Pengoptimasian yang dilakukan dibagi menjadi dua, yaitu pengoptimasian masukan dan pengoptimasian algoritma Breadth First Search. Dalam pengoptimasian masukan dibuat fungsi untuk mempercepat pemrosesan masukan. Dalam pengoptimasian algoritma Breadth First Search, dilakukan pengurangan vertex yang tidak perlu dikunjungi sehingga sisi atau edge yang perlu dilewati berkurang. Melalui pengujian dan studi kasus, didapat hasil bahwa metode Breadth First Search yang telah dioptimasi dapat digunakan untuk menyelesaikan kasus SPOJ “Ada and Cycle”. Umpan balik kinerja yang didapat dari algoritma Breadth First Search yang telah dioptimasi pada situs SPOJ adalah 1,76 detik dan penggunaan memori 2,9M dengan kompleksitas O(N^2). =========================================================================== SPOJ “Ada and Cycle” problem brings the problem of ca - lculating the shortest path that starts from a vertex and ends in the same vertex for every available verticles. Input given from the pro - blem are number of verticles (N) and adjacency matrix (H). The ob - jectives of this thesis are compose a strategy to solve the problem, analyze and designing the algorithm, and evaluate the result of al - gorithm’s performance for solving the “Ada and Cycle” problem in SPOJ. The method used is optimizing Breadth Fi rst Search method so it meet the time requirement given by problem. The optimization consist of two part, input optimazion and Breadth First Search al - gorithm optimization. In the input optimization a function is made to accelerate the input process. In th e Breadth First Search algori - thm optimization done by eliminating verticles that can be skipped so the edge that need to be passed is reduced. According to subsequent testing and case study, it appears that optimized Breadth First Search meth od can be used to solve SPOJ “Ada and Cycle” problem. The performance feedback from optimized Breadth First Search method that is submitted to SPOJ is 1.76 seconds and 2.9M memory used with complexcity of O(N2).

Item Type: Thesis (Undergraduate)
Additional Information: RSIf 511.5 Lim d
Uncontrolled Keywords: Breadth First Search, Cycle, Edge, Graf, In Degree, Jarak Terpendek, Out Degree, Vertex
Subjects: Q Science > QA Mathematics > QA76.6 Computer programming.
Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation.
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms
Divisions: Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User: Christyanto Liman
Date Deposited: 13 Nov 2020 12:27
Last Modified: 29 Dec 2020 06:22
URI: https://repository.its.ac.id/id/eprint/59039

Actions (login required)

View Item View Item