Diwangkara, Brama (2019) Desain dan Analisis Algoritma Dijkstra dan Struktur Data Two Dimensional Binary Indexed Tree pada Penyelesaian Persoalan: URI Online Judge Journey Through The Kingdom. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111540000150-Undergraduate_Theses.pdf Download (1MB) | Preview |
Abstract
Permasalahan dalam Tugas Akhir ini merupakan sebuah permasalahan yang melibatkan sebuah rentang pencarian. Dalam permasalahan ini, diketahui terdapat sebuah negara yang masing – masing provinsinya membentuk sebuah pola seperti array dua dimensi. Pada soal ini diberikan jalur dan ongkos untuk berpindah dari satu provinsi ke provinsi lainnya. Dari berbagai jalur yang diberikan, struktur data harus mampu memilih jalur dengan harga
terendah. Pada Tugas Akhir ini, dirancang penyelesaian permasalahan Journey Through the Kingdom dalam pencarian jalur dengan ongkos terendah dari rentang yang diberikan. Permasalahan ini dapat diselesaikan dengan menggunakan Algoritma Dijkstra dan Struktur Data Binary Indexed Tree 2D untuk mendapatkan jalur dengan ongkos terendah secara optimal. Beberapa hal yang harus diperhatikan adalah mengenai cara pemilihan node yang belum dan sudah dipilih oleh Dijkstra melalui Struktur Data Binary Indexed Tree 2D. Hasil dari Tugas Akhir ini telah berhasil menyelesaikan permasalahan di atas dengan cukup efisien, dengan kompleksitas waktu sebesar O(log(NM)) per query.
================================================================================================
The problem in this final project is a problem that involves a search range. In this problem, it is known that there is a country where each province forms a pattern such as a two dimensional array. In this case, the route and costs are given to move from one province to another. From the various lines provided, the data structure must be able to choose the path at the lowest price. In this Final Project, a solution will be designed to solve the Journey Through the Kingdom problem with the lowest cost of the given range. This problem can be solved by using the Dijkstra Algorithm and Binary Indexed Tree 2D data structures to get the path with the lowest cost optimally. Some things to note are about how to select nodes that have not been and have been selected by
the Dijkstra through 2D Binary Indexed Tree data structure. The results of this final project have succeeded in solving the above problems quite efficiently, with a time complexity of O (log (NM)) per query.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.1 Diw d-1 2019 |
| Uncontrolled Keywords: | array, binary indexed tree 2D, dijkstra, node, |
| Subjects: | Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T57.83 Dynamic programming |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Brama Diwangkara |
| Date Deposited: | 09 Jul 2021 06:32 |
| Last Modified: | 09 Jul 2021 06:32 |
| URI: | http://repository.its.ac.id/id/eprint/60915 |
Actions (login required)
 |
View Item |