Penerapan Algoritma Backtracking Dalam Penyelesaian Masalah

Abstract

Penelitian ini mengeksplorasi implementasi algoritma Backtracking untuk menemukan jalan keluar dari labirin yang memiliki banyak cabang dan jalan buntu. Algoritma Backtracking dirancang untuk efisiensi tinggi dengan menelusuri simpul tujuan dan memangkas langkah yang tidak perlu, berbeda dengan algoritma Depth First Search (DFS). Penelitian menggunakan matriks labirin berukuran ɳ × ɳ . Hasil penelitian menunjukkan bahwa algoritma ini berhasil menemukan jalan keluar dengan jumlah langkah yang minimal,karena Backtracking merunut balik dari simpul tujuan untuk melihat apakah solusi yang sedang dicari menuju pada simpul 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. Hasil yang didapat dalam penelitian ini berupa jumlah langkah dan simpul- simpul yang dilewati selama pencarian sampai menuju simpul tujuan.