ABSTRAKSI: Kubus Rubik's adalah sebuah permainan teka-teki mekanik yang ditemukan pada tahun 1974 oleh pemahat dan profesor arsitektur Hungaria, Ernő Rubik. Ada dua metode yang dapat dipakai untuk menyelesaikan permasalahan Kubus Rubik 3x3x3 ini, yaitu metode konvensional dan metode pencarian heuristik.
Dalam Tugas Akhir ini, dilakukan analisa perbandingan terhadap kedua metode itu, dimana pada metode konvensional akan dipakai algoritma F2L (First Two Layers), karena dapat menghasilkan solusi yang sistematis dan mudah dipelajari user, sedangkan pada metode pencarian heuristik dipakai algoritma DWA* (Dynamic Weighting A), karena bisa dipastikan dapat memperoleh solusi dan akan lebih optimal, walaupun lebih sulit dipelajari user. Perbandingan algoritma ini dilakukan untuk menganalisa algoritma manakah yang lebih baik dalam pemecahan masalah Rubik, baik dilihat dari kompleksitas waktu asimptotiknya secara teori, maupun dengan mengukur tingkat optimasi solusi yang dihasilkan.
Algoritma DWA mempunyai waktu eksekusi dan ruang memory yang dibutuhkan yang cenderung naik seiring bertambahnya jumlah acakan pada initial state, sedangkan algoritma F2L mempunyai waktu eksekusi yang cenderung stabil. Kompleksitas waktu asimtotik pada Algoritma DWA* akan bernilai ekponensial seiring bertambahnya jumlah acakan pada initial state, sedangkan algoritma F2L bernilai konstan. Dari panjang solusi yang dihasilkan, DWA* menghasilkan solusi yang lebih optimal dibandingkan F2L.Kata Kunci : Kubus Rubik 3x3x3, DWA*, F2LABSTRACT: Rubik's Cube is a mechanical puzzle game, has been discovered by Professor Ernő Rubik in Hungaria, in 1974. There are two method that can be used to solve the 3x3x3 Rubik’s Cube.
There are conventional method and heuristic method can used for it. In this project, the conventional method and heuristic method will be analyze, how the conventional method and heuristic method can solve the Rubik’s Cube. F2L algorithm as a conventional method can produce a systematic solution that easy to learn user. DWA* algorithm as a heuristic method can produce an optimal solution, but it’s not easy to learn by user. In implementation of DWA* and F2L on Rubik’s Cube 3x3x3, will be analyzed comparison of time complexity of the both algorithm, the execution time and memory used by the both algorithm, and size of the solution that the both algorithm produce.
The execution time and memory used by DWA* algorithm will be increase when size of input grow up, and F2L algorithm will still stable. The time complexity of DWA* will be exponential, and F2L will still contant. But the result of DWA* have more optimal solution than result of F2L.Keyword: Rubik’s Cube 3x3x3, DWA*, F2L