Anggraeni, Agnesfia (2026) Perancangan Dan Analisis Algoritma Perhitungan Nilai Ekspektasi Waktu Pada Pergerakan Acak Dalam Labirin Menggunakan Metode Conjugate Gradient: Studi Kasus Spoj Another Valentine Maze Game (2D). Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5025201059_Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5025201059_Undergraduate_Thesis.pdf Restricted to Repository staff only Download (1MB) | Request a copy |
Abstract
Another Valentine Maze Game (2D) merupakan permasalahan pada SPOJ yang meminta perhitungan nilai ekspektasi banyak langkah yang diperlukan Tjandra untuk mencapai posisi wanita pada sebuah labirin dua dimensi dengan aturan perpindahan secara acak ke salah satu sel tetangga yang dapat dilalui. Permasalahan ini dapat dimodelkan sebagai proses simple random walk pada graf sehingga hubungan nilai ekspektasi pada setiap simpul membentuk sistem persamaan linear.
Penelitian ini bertujuan merancang dan mengimplementasikan algoritma untuk menyelesaikan permasalahan tersebut menggunakan metode Conjugate Gradient. Tahapan penyelesaian diawali dengan pembacaan data labirin, pencarian simpul yang dapat dijangkau menggunakan Breadth-First Search (BFS), transformasi labirin menjadi graf, pembentukan sistem persamaan linear berdasarkan konsep simple random walk, kemudian penyelesaian sistem persamaan linear menggunakan metode Conjugate Gradient tanpa membentuk matriks koefisien secara eksplisit. Hasil implementasi menunjukkan bahwa program berhasil memperoleh status Accepted pada situs SPOJ. Berdasarkan pengujian lokal diperoleh rata-rata waktu eksekusi sebesar 15,63 ms, sedangkan pada pengujian melalui SPOJ diperoleh rata-rata waktu eksekusi sebesar 0,386 ms dengan penggunaan memori sebesar 5,2 MB. Hasil tersebut menunjukkan bahwa implementasi mampu menghasilkan keluaran yang benar dengan performa yang stabil pada lingkungan pengujian yang digunakan.
==================================================================================================================================
Another Valentine Maze Game (2D) is a problem in SPOJ that requires calculating the expected number of moves required for Tjandra to reach the woman's position in a two-dimensional maze with random movement rules to one of the accessible neighboring cells. This problem can be modeled as a simple random walk on a graph, so that the relationship between the expected values at each vertex forms a system of linear equations. This research aims to design and implement an algorithm to solve this problem using the Conjugate Gradient method. The solution steps begin with reading the maze data, finding reachable vertices using Breadth-First Search (BFS), transforming the maze into a graph, forming a system of linear equations based on the concept of a simple random walk, and then solving the system of linear equations using the Conjugate Gradient method without explicitly forming a coefficient matrix. The implementation results show that the program successfully achieved Accepted status on the SPOJ website. Based on local testing, the average execution time was 15.63 ms, while testing through SPOJ resulted in an average execution time of 0.386 ms, with 5.2 MB of memory usage. These results show that the implementation is able to produce correct output with stable performance in the test environment used.
| Item Type: | Thesis (Other) |
|---|---|
| Uncontrolled Keywords: | Breadth-First Search, Conjugate Gradient, Random Walk, Sistem Persamaan Linear. Breadth-First Search, Conjugate Gradient, Random Walk, Systems of Linear Equations. |
| Subjects: | Q Science T Technology > T Technology (General) |
| Divisions: | Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | AGNESFIA ANGGRAENI |
| Date Deposited: | 28 Jul 2026 02:49 |
| Last Modified: | 28 Jul 2026 02:49 |
| URI: | http://repository.its.ac.id/id/eprint/138461 |
Actions (login required)
 |
View Item |