Dembo, William Albertus (2019) Desain dan Analisis Algoritma Local Search Dengan Metode Hill Climbing pada Permasalahan Graceful Labelling Pada General Tree. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05111540000075-Undergraduate_Theses.pdf Download (1MB) | Preview |
Abstract
Graceful labelling dari suatu graf G dengan N node adalah injeksi f : V (G) -> 0, 1, 2, ... ,N - 1 sehingga ketika setiap edge xy ϵ E(G) diberi label |f(x) - f(y)| maka semua label pada edge berbeda. Pada Tugas Akhir ini akan dirancang penyelesaian permasalahan graceful labelling pada general tree dengan batasan maksimal jumlah node pada tree adalah 27. Permasalahan ini dapat diselesaikan dengan menggunakan algoritma Local Search dengan metode Hill Climbing dan dibantu dengan batasan tabu. Hal yang harus perhatikan adalah bagaimana menghasilkan ruang pencarian solusi dari permasalahan ini sehingga dapat ditelusuri solusinya menggunakan teknik heuristik. Hasil dari tugas akhir ini telah berhasil menyelesaikan permasalahan di atas dengan cukup efisien, dengan waktu penyelesaian terbaik 0.17 detik dan penggunaan memori 16 MB.
================================================================================================
A graceful labelling of a graph G with N nodes is an injection f : V (G) -> 0, 1, 2, ...,N - 1 such that when each edge xy ϵ E(G) is assigned the label, |f(x)-f(y)|, all of the edge labels are distinct. This undergraduate thesis will design the problem solving of graceful labelling in general tree with nodes in tree limited to 27. This problem can be solved using local search algorithm with hill climbing method and tabu limit. The difficult thing from this method is the correct way to generate the solution search space so it can be traversed by heuristic method. The result shows that graceful labelling problem in general tree is succesfully solved efficiently with best time of 0.17 seconds and memory usage of 16 MB.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 006.746 Dem d-1 2019 |
| Uncontrolled Keywords: | graceful labelling, local search, hill climbing, heuristik |
| Subjects: | Q Science > QA Mathematics > QA76.9.D33 Data compression (Computer science) Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | William Albertus Dembo |
| Date Deposited: | 21 Jul 2021 06:07 |
| Last Modified: | 21 Jul 2021 06:07 |
| URI: | http://repository.its.ac.id/id/eprint/60973 |
Actions (login required)
 |
View Item |