BacktrackingMenengahFase D–FE1E5

Tikus dalam Labirin (Rat in a Maze)

Rat Maze menyelesaikan labirin dengan backtracking: tikus maju sel demi sel menandai jalur, dan bila menemui jalan buntu atau sel terhalang, ia mundur (menghapus sel dari path) lalu mencoba arah lain. Proses maju-mundur-coba lagi berlanjut sampai sel keluar (exit) tercapai. Visualisasi menampilkan jalur yang dijelajahi, sel yang ditolak/di-backtrack, hingga jalur solusi akhir terkunci.

Contoh kasus

Penyelesaian labirin otomatis atau robot penelusur maze yang mencoba tiap cabang dan mundur saat menemui jalan buntu.

Silabus

Rat in a Maze menyelesaikan labirin dengan backtracking: tikus maju menandai jalur dan mundur mencoba arah lain saat mentok.

Tujuan Belajar

·Memahami cara menandai dan membatalkan jalur saat menjelajah
·Menjelaskan pola maju-mundur-coba lagi pada backtracking
·Menerapkan backtracking untuk menemukan jalur keluar labirin

Cara Kerja

·Tikus maju satu sel dan menandainya sebagai bagian jalur
·Coba arah berikutnya yang bebas dan belum dilewati
·Bila menemui jalan buntu atau sel terhalang, mundur
·Hapus sel dari jalur saat mundur lalu coba arah lain
·Ulangi sampai sel keluar (exit) tercapai dan jalur solusi terbentuk

Prasyarat

·Backtracking
·Grid 2D

Contoh Nyata

·Robot penelusur maze mencoba tiap cabang dan mundur saat buntu
·Penyelesaian labirin otomatis di game teka-teki
·Mencari jalan keluar pada peta bercabang secara sistematis

Kompleksitas O(4^(m x n)) pada kasus terburuk