Implementasi Algoritma Backtracking untuk Mencari Jalan Keluar Labirin

Abstract

Labirin merupakan teka- teki yang sering kali menjadi sebuah permainan/game. Labirin memiliki banyak cabang dan jalan buntu yang membuat labirin sulit untuk dicari jalan keluarnya.  Algoritma pencarian dapat  memudahkan  pencarian  jalan  keluar  sebuah  labirn,  namun  tidak  semua  algoritma  pencarian  dapat diimplementasikan pada sebuah labirin. Oleh karena itu menentukan algoritma yang tepat menjadi salah satu faktor penentu untuk mencari jalan keluar sebuah labirin. Algoritma Backtracking merupakan salah satu dari algoritma pencarian yang memiliki tingkat efisiensi yang tinggi karena Backtracking merunut balik dari simpul tujuan untuk  melihat  apakah solusi  yang  sedang  dicari  menuju  pada  simp ul  tujuan  yang  diinginkan.  Dengan demikian algoritma Backtracking dapat memangkas langkah-langkah yang tidak perlu dalam sebuah pencarian dan dapat mencari rute terpendek dalam sebuah pencarian. Dari sisi tersebut algoritma Backtracking memiliki kelebihan dibandingan algoritma Depth First Search yang tidak mempertimbangkkan apakah solusi yang sedang dicari menuju pada titik tujuan yang diinginkan. Penelitian ini dilakukan dengan menggunakan labirin berupa matriks dengan ukuran n x n dan menggunakan algoritma Backtracking untuk mencari jalan keluar dari labirin, hasil  yang  didapat  dalam  penelitian  ini  berupa  jumlah  langkah  dan  simpul-  simpul  yang  dilewati  selama pencarian sampai menuju simpul tujuan.