Penyelesaian Permasalahan SPOJ 7627 - Driving Direction Menggunakan Geometri Komputasional Dan Algoritma Dijkstra

Nainggolan, Hesekiel (2025) Penyelesaian Permasalahan SPOJ 7627 - Driving Direction Menggunakan Geometri Komputasional Dan Algoritma Dijkstra. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025201054-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (5MB) | Request a copy

Abstract

Sphere Online Judge (SPOJ) adalah platform berbasis peramban yang berfokus pada sistem penilaian program dengan sekitar 13.000 permasalahan asli yang dirancang oleh komunitas ahli pembuat soal. Salah satu permasalahan classical yang terdapat pada platform ini adalah Driving Direction. Dalam permasalahan SPOJ 7627 – Driving Direction, terdapat bidang geometri yang direpresentasikan dalam bidang kartesian dua dimensi. Bidang geometri lingkaran dengan titik pusat A(ax,ay) menuju titik pusat B(bx,by) dicari jalur terpendeknya. Dalam proses pencarian jalur lintasan terpendek(shortest path), terdapat penghalang berupa bidang geometri persegi panjang. Untuk mencari jalur terpendek lingkaran A ke lingkaran B, terdapat ketentuan bahwa lingkaran tidak boleh memotong penghalang persegi panjang, atau setidaknya hanya dapat bersinggungan.Permasalahan SPOJ 7627 – Driving Direction berhasil diselesaikan. Dalam menyelesaikan permasalahan, tugas akhir ini menerapkan pendekatan geometri komputasional, teori graf dan algoritma Dijkstra dalam mencari jalur lintasan terpendek. Geometri komputasional digunakan untuk menentukan semua node valid yang merupakan node terdekat yang tidak memotong penghalang persegi panjang atau hanya bersinggungan. Pada implementasinya juga digunakan algoritma Dijkstra untuk mencari jalur lintasan terpendek dari graf yang terbentuk. Metode pengujian pada tugas akhir ini terdiri dari pengujian kebenaran, yaitu mengirimkan kode sumber program dari implementasi desain algoritma ke situs penilaian daring Sphere Online Judge (SPOJ). Berdasarkan hasil pengujian, permasalahan SPOJ 7627 – Driving Direction berhasil diselesaikan dengan solusi kode sumber program mendapatkan hasil accepted dengan rata-rata waktu yang dibutuhkan 0,284 detik dan memori rata-rata 14 MB dengan kompleksitas waktu O(n^3). Hasil ini menunjukkan bahwa desain algoritma efektif dan efisien dalam menyelesaikan permasalahan SPOJ 7627 – Driving Direction.
====================================================================================================================================
Sphere Online Judge (SPOJ) is a browser-based platform focused on a program assessment system with around 13,000 original problems designed by a community of expert problem makers. One of the classical problems found on this platform is Driving Direction. In the SPOJ – 7627 Driving Direction problem, there is a geometric plane represented in a two-dimensional Cartesian plane. The geometric plane of a circle with center point A(ax,ay) towards center point B(bx,by) is searched for the shortest path. In the process of finding the shortest path, there is an obstacle in the form of a rectangular geometric plane. To find the shortest path from circle A to circle B, the circle must not intersect the rectangular barrier, or at most, may only be tangent to it. The SPOJ 7627 – Driving Direction problem has been solved. In solving the problem, the final project applies to the computational geometry approach, graph theory and Dijkstra's algorithm in finding the shortest path. Computational geometry is used to determine all valid nodes which are the closest nodes that do not intersect rectangular barriers or are only tangent. In its implementation, the Dijkstra algorithm is also used to find the shortest path of the formed graph. The testing method in this final project consists of correctness testing, which involves submitting the program’s source code from the algorithm design implementation to the online judge site Sphere Online Judge (SPOJ). Based on the test results, the SPOJ 7627 – Driving Direction problem was successfully solved with the source code solution program getting accepted results with an average time required of 0.284 seconds and an average memory of 14 MB with a time complexity of O(n^3). These results indicate that the algorithm design is effective and efficient in solving the SPOJ 7627 – Driving Direction.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	algoritma dijkstra, geometri komputasional, shortest path, computational geometry, dijkstra's algorithm, shortest path
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Hesekiel Nainggolan
Date Deposited:	16 Jul 2025 01:35
Last Modified:	16 Jul 2025 01:35
URI:	http://repository.its.ac.id/id/eprint/119836

Actions (login required)

View Item