Wisna, Komang Yogananda Mahaputra (2021) Desain dan Analisis Algoritma Genetika dengan Algoritma Greedy Sebagai Metode Optimasi Skor Permainan Puzzle pada Studi Kasus Permasalahan SPOJ Challenge 2624 JAWB: JawBreaker Game. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 05111740000114-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
05111740000114-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 April 2023. Download (3MB) | Request a copy |
Abstract
Jawbreaker puzzle adalah suatu permainan klasik komputer yang dirilis oleh Microsoft pada tahun 2003. Permainan puzzle Jawbreaker juga dikenal dengan nama lain seperti Clickomania atau SameGame. Permainan puzzle Jawbreaker merupakan salah satu permasalahan NP-Complete pada bidang ilmu komputer.
Desain algoritma greedy dengan penambahan teknik heuristik di dalam penentuan langkah permainan dalam optimalisasi skor permainan puzzle dibahas dalam tugas akhir ini. Teknik heuristik yang digunakan adalah evolutionary search untuk mencari beban fitur optimal pada algoritma greedy. Algoritma genetika digunakan sebagai metode evolutionary search pada penyelesaian permasalahan ini. Tugas akhir ini menggunakan permasalahan JAWB - JawBreaker Game pada situs penilaian daring SPOJ sebagai studi kasus uji kebenaran algoritma. Berdasarkan uji coba yang dilakukan pada situs SPOJ maupun lokal, algoritma ini berhasil menyelesaikan permasalahan ini dengan skor rata-rata 60.219,447, waktu eksekusi rata-rata 1,96s dan penggunaan memori rata-rata 4,76 MB.
======================================================================================================
Jawbreaker puzzle is a classic computer game released by Microsoft in 2003. Jawbreaker game puzzle is also known as Clickomania or SameGame and it is one of the NP-Complete puzzles in the computer science field.
This thesis will discuss designing a greedy algorithm with the addition of a heuristic technique to find the optimal move to solve this score optimization problem. The heuristic technique used in this solution is an evolutionary search to search for the best weight for the greedy algorithm. Genetic Algorithm is used as the evolutionary search method for this solution to solve this problem. This thesis used a problem named JAWB - JawBreaker Game that is listed in Sphere Online Judge (SPOJ) as the case study to verify the correctness. Based on the local and online judge experiment performed, this algorithm successfully solved the problem by 60219.447 average score, 1.96s average time execution and 4.76 MB average memory used as the result.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | algoritma genetika, greedy, jawbreaker, np-complete, optimalisasi, puzzle genetic algorithm, greedy, jawbreaker, np-complete, optimization, puzzle |
| Subjects: | Q Science > QA Mathematics > QA166 Graph theory Q Science > QA Mathematics > QA402.5 Genetic algorithms. Interior-point methods. Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.84 Heuristic algorithms. |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Komang Yogananda Mahaputra Wisna |
| Date Deposited: | 03 Mar 2021 02:20 |
| Last Modified: | 03 Mar 2021 02:20 |
| URI: | http://repository.its.ac.id/id/eprint/83237 |
Actions (login required)
 |
View Item |