Garsia, Modista (2020) Penerapan Struktur Data link-cut tree pada Penyelesaian Permasalahan SPOJ 32679 ADAROADS: Ada and Roads. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000031-Undergraduate Thesis.pdf Download (2MB) | Preview |
Abstract
Tugas Akhir ini berangkat dari adanya permasalahan Ada and Roads pada SPOJ, yang menceritakan bahwa Ada si kepik adalah seorang Petani. Ia ingin menanam buah dan sayur (vertex) pada lahannya. Untuk mempermudah dalam merawat tanamannya, Ada ingin membangun jalan (edge) yang menghubungkan tanamannya. Akan tetapi setiap jalan yang dibangun mempunyai biaya perbaikan, dan Ada ingin agar jalan yang dibangun mempunyai biaya perbaikan seminimal mungkin. Agar tidak ada jalan yang sia-sia dibangun, maka Ada ingin agar jalan yang dibangun tidak membentuk cycle (siklus).
Syarat yang harus tersedia dalam permasalahan di atas menimbulkan hal-hal baru yang membutuhkan metode penyelesaian yang tepat: (1) adanya vertex dan edge dari suatu graf yang akan terus menerus diperbarui sambil menghitung total cost, sehingga menghasilkan cost seminimal mungkin, (2) apabila vertex dan edge terus menerus diperbarui, maka bentuk graf akan berubah setiap pembaruan. Dari (1) dan (2) ini diperlukan struktur data yang efisien dan dinamis untuk menyelesaikan permasalahan ADAROADS.
Solusi dari permasalahan ADAROADS diimplementasikan dengan menggunakan struktur data dinamis yaitu link-cut tree. Solusi yang dibuat mampu melewati batasan masalah pada soal dengan waktu 7,34 detik dan memori sebesar 29MB dan meraih peringkat pertama.
========================================================
This thesis starts from SPOJ: Ada and Roads problems, which tells Ada the Ladybug is a farmer. She grows many fruits and vegetables (vertex). She has to take care of them so she builds many roads (edge) between them. She also doesn't want to keep unnecessary roads so after builting a road she cleans the rest of roads so her road-system doesn't contain any needless cycles. Each road has some maintenance cost and she always keeps roads in such ways that the total cost is minimized.
The condition which should exist on the problem caused new matters that need a proper solution as follows: (1) the vertices and edges of a graph which continues to be updated whilst calculate its total cost to produce the minimum cost, (2) if the vertices and edges are continuously being updated, then the graph structure will always be changed by its update. By (1) and (2), the efficient and dynamic structure data is needed to solve the ADAROADS problem.
The solution of ADAROADS problem has been implemented by using dynamic data structure, i.e., link-cut tree. This solution has been able to solve the problem with 7,34 seconds and memory of 29MB and ranked at first.
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSIf 005.746 Gar p-1 2020 |
| Uncontrolled Keywords: | Dynamic Graphs, Edge Insertion, Edge Deletion |
| Subjects: | Q Science > QA Mathematics > QA76.F56 Data structures (Computer science) |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering |
| Depositing User: | Garsia Modista |
| Date Deposited: | 22 Jun 2023 08:02 |
| Last Modified: | 22 Jun 2023 08:02 |
| URI: | http://repository.its.ac.id/id/eprint/72926 |
Actions (login required)
 |
View Item |