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.
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: | http://repository.its.ac.id/id/eprint/59039 |
Actions (login required)
 |
View Item |