Penerapan Binary Search Algorithm Untuk Menghitung Shortest Path Pada Permukaan Silinder Dengan Studi Kasus SPOJ Cylindes Shortest Path On a Cylinder

Agustian, Yovi (2021) Penerapan Binary Search Algorithm Untuk Menghitung Shortest Path Pada Permukaan Silinder Dengan Studi Kasus SPOJ Cylindes Shortest Path On a Cylinder. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

Text 05111740000125-Yovi-Agustian-Buku_TA.pdf - Accepted Version Restricted to Repository staff only until 1 October 2023. Download (3MB) | Request a copy

Abstract

Shortest path problem adalah permasalahan pencarian rute terpendek yang menghubungkan dua buah titik. Dalam ilmu geometri, shortest path antara dua buah titik pada permukaan objek disebut dengan geodesic. Untuk mencari geodesic pada bidang datar dapat dilakukan dengan menarik garis lurus antara dua buah titik. Permasalahan yang timbul selanjutnya adalah bagaimana cara mencari geodesic pada permukaan silinder.

Tugas akhir ini mengulas penggunaan algoritma binary search untuk menyelesaikan permasalahan shortest path on a cylinder (SPOJ Cylindes), dengan metode penyelesaian berupa pencarian optimum angle pada cylinder edge untuk membentuk composite path yang merupakan shortest path antara dua buah titik pada permukaan silinder tersebut. Dalam kasus khusus di mana kedua buah titik berada pada cylinder wall terdapat tiga alternatif path yang perlu diperhatikan. Alternatif path pada kasus khusus ini berdasar pada paper “Multiple Shortest Paths On Cylindrical Surfaces In Pre-Hilbert Spaces”.

Dari hasil pengujian studi kasus yang diberikan, algoritma binary search dapat menyelesaikan permasalahan dengan baik dan efisien dengan waktu eksekusi rata-rata 0,02 detik dan penggunaan memori rata-rata 5,31 MB.
======================================================================================================
The shortest path problem is a problem of finding the shortest route that connects two points. In geometry, the shortest path between two points on the surface of an object is called a geodesic. Finding a geodesic on a plane can be done by drawing a straight line between two points. The following problem was how to find geodesic on the cylinder surface.

This thesis discussed the use of the binary search algorithm to solve the problem of the shortest path on a cylinder (SPOJ Cylindes), by the method of finding the optimum angle on the cylinder edge to form a composite path which is the shortest path between two points on the cylinder surface. In special case where both points are on the cylinder wall there are three alternative paths to consider. The alternative path in this particular case is based on the paper “Multiple Shortest Paths On Cylindrical Surfaces In Pre-Hilbert Spaces”.

From the testing results of given case studies, the binary search algorithm can solve the problems well and efficiently by an average execution time of 0.02 seconds and an average memory usage of 5.31 MB.

Item Type:	Thesis (Undergraduate)
Subjects:	T Technology > T Technology (General) > T57.84 Heuristic algorithms.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Yovi Agustian
Date Deposited:	27 Jul 2021 14:53
Last Modified:	30 Jul 2021 04:20
URI:	http://repository.its.ac.id/id/eprint/84520

Actions (login required)

View Item