Rangkuman: Rat in a Maze

Backtracking Algorithm

1. Pengertian

Rat in a Maze (Tikus dalam Labirin) adalah masalah klasik yang menggambarkan pencarian jalur dari titik awal ke titik tujuan dalam sebuah labirin atau matriks. Matriks tersebut biasanya terdiri dari sel-sel yang mewakili jalur yang bisa dilalui (misalnya, 1) dan rintangan yang tidak bisa dilalui (misalnya, 0).

Tujuannya adalah untuk menemukan satu atau semua kemungkinan jalur yang dapat dilewati tikus dari sel awal (biasanya [0][0]) ke sel tujuan (biasanya [N-1][N-1]). Masalah ini seringkali diselesaikan menggunakan pendekatan **Backtracking**.

2. Konsep Dasar & Pendekatan Backtracking

Algoritma Backtracking mengeksplorasi semua kemungkinan jalur secara rekursif. Pada setiap langkah, tikus mencoba bergerak ke salah satu dari empat arah (atas, bawah, kiri, kanan). Jika langkah tersebut valid (tidak keluar batas, bukan rintangan, dan belum pernah dikunjungi di jalur ini), maka tikus mencoba langkah tersebut dan menandainya sebagai bagian dari jalur saat ini. Jika langkah tersebut tidak membawa ke solusi atau buntu, tikus "mundur" (backtrack) dan mencoba arah lain.

Langkah-langkah Algoritma Backtracking:

Mulai dari posisi awal tikus (biasanya [0][0]).
Buat matriks solusi yang sama ukurannya dengan labirin, diinisialisasi dengan 0. Ketika tikus melewati sebuah sel, tandai sel tersebut dengan 1 di matriks solusi.
Fungsi rekursif `solveMaze(x, y)` dipanggil untuk posisi saat ini `(x, y)`.
Kasus Dasar:
- Jika posisi `(x, y)` adalah posisi tujuan (exit), berarti jalur ditemukan. Tandai sel ini di matriks solusi dan return `true`.
Langkah Rekursif:
- Jika posisi `(x, y)` valid (dalam batas, bukan rintangan, belum dikunjungi di jalur saat ini):
  1. Tandai `(x, y)` di matriks solusi sebagai bagian dari jalur (misalnya, `solution[x][y] = 1`).
  2. Coba bergerak ke semua kemungkinan arah (misal: Bawah, Kanan, Atas, Kiri) secara rekursif:
    - Jika `solveMaze(x+1, y)` berhasil, return `true`.
    - Jika `solveMaze(x, y+1)` berhasil, return `true`.
    - ... dan seterusnya untuk arah lain.
  3. Jika tidak ada arah yang berhasil (tikus buntu), maka "mundur" (backtrack). Hapus tanda `(x, y)` dari matriks solusi (misalnya, `solution[x][y] = 0`) dan return `false`.
- Jika posisi `(x, y)` tidak valid (rintangan, di luar batas, atau sudah dikunjungi di jalur ini), return `false`.

3. Contoh Ilustrasi

Misalkan labirin $4 \times 4$ ($0$ = rintangan, $1$ = jalan):


Maze:
[[1, 0, 0, 0],
 [1, 1, 0, 1],
 [0, 1, 0, 0],
 [1, 1, 1, 1]]

Start: (0,0), End: (3,3)

Salah satu jalur solusi (1 menandakan jalur tikus):


Solution Path:
[[1, 0, 0, 0],
 [1, 1, 0, 0],
 [0, 1, 0, 0],
 [0, 1, 1, 1]]

Visualisasi akan menunjukkan tikus bergerak dari (0,0) ke (1,0), (1,1), (2,1), (3,1), (3,2), (3,3).

4. Pseudocode Algoritma


FUNCTION solveMaze(maze):
    N = maze.ROWS
    solution_path = CREATE N x N array, filled with 0s

    IF findPath(maze, 0, 0, solution_path, N) == FALSE:
        PRINT "Tidak ada jalur yang ditemukan"
        RETURN FALSE

    PRINT "Jalur ditemukan:"
    PRINT solution_path // Cetak matriks solusi
    RETURN TRUE

FUNCTION findPath(maze, x, y, solution_path, N):
    // Jika mencapai tujuan
    IF x == N-1 AND y == N-1 AND maze[x][y] == 1:
        solution_path[x][y] = 1
        RETURN TRUE

    // Periksa apakah (x, y) valid dan belum dikunjungi di jalur ini
    IF x >= 0 AND x < N AND y >= 0 AND y < N AND maze[x][y] == 1 AND solution_path[x][y] == 0:
        solution_path[x][y] = 1 // Tandai sebagai bagian dari jalur

        // Coba bergerak ke bawah
        IF findPath(maze, x + 1, y, solution_path, N) == TRUE:
            RETURN TRUE

        // Coba bergerak ke kanan
        IF findPath(maze, x, y + 1, solution_path, N) == TRUE:
            RETURN TRUE
        
        // Coba bergerak ke atas (opsional, tergantung arah yang diizinkan)
        IF findPath(maze, x - 1, y, solution_path, N) == TRUE:
            RETURN TRUE

        // Coba bergerak ke kiri (opsional, tergantung arah yang diizinkan)
        IF findPath(maze, x, y - 1, solution_path, N) == TRUE:
            RETURN TRUE

        // Jika tidak ada arah yang berhasil, backtrack (hapus dari jalur)
        solution_path[x][y] = 0
        RETURN FALSE

    RETURN FALSE // Posisi tidak valid

5. Kompleksitas Waktu & Ruang

Kompleksitas Waktu: $O(4^{N \times N})$ pada kasus terburuk (tanpa pruning, jika bisa mencoba 4 arah di setiap sel), karena setiap sel bisa dikunjungi dan ada 4 pilihan arah. Namun, dengan pruning (tidak mengunjungi sel yang sudah dikunjungi atau rintangan), kompleksitasnya jauh lebih baik, tetapi masih eksponensial. Lebih tepatnya $O(2^{N \times N})$ jika hanya bisa 2 arah (misal: kanan dan bawah) atau $O(\text{jumlah_sel} \times \text{jumlah_arah})$ yang dieksplorasi.
Kompleksitas Ruang: $O(N^2)$ untuk menyimpan matriks labirin dan matriks solusi. Stack rekursi juga bisa mencapai $O(N^2)$ pada kasus terburuk (untuk jalur terpanjang).

6. Aplikasi

Pencarian jalur dalam permainan video (pathfinding).
Robotika untuk navigasi otonom.
Penyelesaian Sudoku dan puzzle berbasis grid lainnya.
Permasalahan routing di jaringan komputer.