Studi Kinerja Algoritma Bidirectional Search pada Penentuan Rute Pergerakan Pemain dalam Maximum Steps Constraint: Studi Kasus Permasalahan Timus Online Judge 1589 - Sokoban

Pratama, Aditya (2020) Studi Kinerja Algoritma Bidirectional Search pada Penentuan Rute Pergerakan Pemain dalam Maximum Steps Constraint: Studi Kasus Permasalahan Timus Online Judge 1589 - Sokoban. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111540000101-Undergraduate_Thesis.pdf - Accepted Version Download (3MB)

Abstract

Dengan berkembangnya teknologi, penyelesaian suatu game juga dikembangkan ke arah yang lebih modern, utamanya untuk game dengan kompleksitas yang tinggi. Contoh dari jenis game ini adalah Sokoban. Artikel ini mengacu pada penyelesaian permasalahan pada Timus Online Judge dengan kode 1589[1] yang berjudul Sokoban, di mana diberikan sebuah puzzle yang merupakan map dua dimensi yang terdiri dari beberapa entitas yang direpresentasikan oleh beberapa karakter. Pendekatan untuk menyelesaikan permasalahan tersebut adalah dengan menggunakan algoritma bidirectional search dengan algoritma A* sebagai forward move dan algoritma Breadth-First Search (BFS) sebagai backward move. Pendekatan heuristic untuk mendapatkan langkah solusi dalam penyelesaian puzzle pada sistem yang dibuat adalah goal pull distance. Analisis algoritma dan pendekatan heuristic lain yang mungkin bisa menyelesaikan permasalahan ini, juga dijelaskan lebih lanjut. Hasil artikel ini belum mampu menyelesaikan secara penuh permasalahan di atas, namun sudah bisa menyelesaikan hingga testcase ke 55 dari 93 testcase yang tersedia, sehingga dari hasil ini bisa disimpulkan bahwa artikel ini berhasil menyelesaikan sebagian besar testcase yang diberikan oleh daring Timus Online Judge. Diharapkan dengan adanya artikel ini dapat memberikan gambaran untuk pengembangan sistem berikutnya pada permasalahan yang sama atau yang serupa.
==================================================================================================================================
With the development of technology, the completion of a game is also developed in a more modern direction, especially for games with high complexity. An example of this type of game is Sokoban. This Final Project (TA) refers to solving a problem in the Timus Online Judge with code 1589[1] entitled Sokoban, where given a puzzle which is a two-dimensional map consisting of several entities represented by several characters. The author's approach to solving this problem is to use the bidirectional search algorithm with the A * algorithm as a forward move and the BFS (Breadth-First Search) algorithm as a backward move. The heuristic approach to get the optimal step in solving the puzzle on the system created is the goal pull distance. Analysis of algorithms and other heuristic approaches that might solve this problem are also further explained. The results of this TA have not been able to fully solve the above problems, but have been able to finish up to the 55th testcase out of 93 testcases, so from this result it can be concluded that this Final Project successfully completed the majority of the testcases given by the online Timus Online Judge. It is hoped that the existence of this TA can provide an overview for subsequent system development on the same or similar problems.

Item Type:	Thesis (Other)
Additional Information:	RSIf 005.1 Pra s-1
Uncontrolled Keywords:	bidirectional search;game theory;graph;sokoban
Subjects:	Q Science > QA Mathematics > QA9.58 Algorithms T Technology > T Technology (General) > T57.5 Data Processing T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T57.62 Simulation
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Aditya Pratama
Date Deposited:	08 May 2023 03:30
Last Modified:	08 May 2023 03:30
URI:	http://repository.its.ac.id/id/eprint/73213

Actions (login required)

View Item