Analisis Perbandingan Algoritme Runut Balik, Brute Force dan Breadth First Search pada Permainan Pencarian Kata

AGUS ADI NUGROHO, Prof. Sri Hartati, M.Sc, Ph.D

2022 | Tesis | MAGISTER ILMU KOMPUTER

Dalam penelitian ini telah dibuat suatu aplikasi permainan pencarian kata yaitu permainan yang mencari kata yang tersusun secara acak pada sebuah grid. Masalah utama yang diangkat yaitu membandingkan proses pencarian dan hasil pengujian berupa waktu dengan menggunakan algoritme runut balik, breadth first search serta brute force sehingga dapat menentukan algoritme mana yang proses pencariannya memiliki jalur yang lebih sedikit dan tidak memerlukan waktu yang lama dalam menemukan solusi. Solusi dari permasalahan tersebut yaitu melakukan analisis perbandingan pada pengujian semua kata yang ada dalam permainan. Pengujian terdiri dari pengujian semua kata, level permainan dan juga kelompok kata. Pengujian tersebut digunakan untuk membandingkan waktu pencarian masing-masing algoritme. Berdasarkan hasil pengujian rata-rata waktu disimpulkan algoritme runut balik memiliki waktu 12,77 detik, algoritme brute force 16,26 detik dan juga algoritme breadth first search sekitar 14,17 detik. Dari hasil pengujian itu dapat disimpulkan bahwa algoritme runut balik merupakan algoritme yang lebih cepat tepat untuk diimplementasikan pada permainan ini.

In this research, a word search games application has been made, namely a game that looks for words arranged randomly on a grid. The main problem raised is comparing the search process and the test results in the form of time using the backtracking algorithm, breadth first search and brute force so that it can determine which algorithm has fewer paths and does not require a long time to find a solution. The solution of this problem is to do a comparative analysis on testing all the words in the game. The test consists of testing all words, game levels and also word groups. The test is used to compare the search times of each algorithm. Based on the results of the time test, it is concluded that the backtracking algorithm has a time of 12.77 seconds, the brute force algorithm is 16.26 seconds and the breadth first search algorithm is around 14.17 seconds. From the test results, it can be concluded that the tracing back algorithm is a faster algorithm that is appropriate to be implemented in this game.

Kata Kunci : Permainan pencarian kata, Runut balik, Brute force dan Breadth First Search