Febriani, Zahrah Ayu Afifah (2020) Penerapan Struktur Data Tree dan Algoritma Greedy dalam Pencarian Solusi Optimal pada Permasalahan SPOJ DOM – Domino’s Effect. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111640000108-Undergraduate_Thesis.pdf Download (2MB) | Preview |
Abstract
Permasalahan pada tugas akhir ini berasal dari soal pada situs SPOJ dengan judul DOM – Domino’s Effect. Permasalahan ini membahas tentang adanya suatu susunan ubin domino dalam garis lurus dan akan ditentukan banyaknya langkah minimal yang harus dilakukan agar dapat menjatuhkan semua ubin yang ada disertai dengan penentuan posisi dan arah ubin yang harus digerakkan. Ubin domino yang digerakkan dapat menjatuhkan ubin domino lain dalam jangkauannya sesuai dengan arah geraknya. Diketahui banyaknya ubin domino, tinggi masing – masing ubin, dan jarak antar dua ubin yang bersebelahan.
Tugas akhir ini merancang penyelesaian masalah dengan menerapkan algoritma greedy dan struktur data general tree dengan memanfaatkan algoritma Depth First Search (DFS) dalam penelusuran node. Tree dan DFS digunakan saat proses mendapatkan subsolusi. Subsolusi yang didapatkan saat iterasi pada setiap ubin dapat menyusun hasil akhir dari permasalahan.
Solusi yang dikembangkan berjalan dengan kompleksitas O(N), dimana N adalah banyaknya ubin domino dalam suatu susunan. Solusi ini berhasil menemukan hasil akhir dengan cepat.
========================================================
The problems in this thesis comes from SPOJ site with the title DOM – Domino’s Effect. This problem discusses about a number of domino tiles placed perpendicularly to the surface. The goal of this problem is to.find the minimum number of tiles that need to be toppled, in order for all the dominoes to fall including the position and direction of the toppled tiles. Domino tiles that are moved can knock down other domino tiles within their range in the direction they are moving. Given the number of domino tiles, the height of each tile, and the distance between two adjacent tiles.
This thesis designs problem solving by applying the greedy algorithm and tree data structure using Depth First Search (DFS) algorithm for node traversing. Tree and DFS is used in the process of getting the subsolution. Subsolution obtained at iteration on each tile can construct the final result of this problem.
The complexity of the developed solution is O (N), where N is the number of domino tiles in an arrangement. This solution is successful in finding the final result quickly.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.73 Feb p-1 • Febriani, Zahrah Ayu Afifah |
| Uncontrolled Keywords: | Algoritma Greedy, DFS, Tree, Ubin Domino |
| Subjects: | T Technology > T Technology (General) T Technology > T Technology (General) > T57.84 Heuristic algorithms. |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Zahrah Ayu Afifah Febriani |
| Date Deposited: | 06 Aug 2020 04:48 |
| Last Modified: | 17 May 2023 14:18 |
| URI: | http://repository.its.ac.id/id/eprint/76738 |
Actions (login required)
 |
View Item |