Backtracking adalah algoritma berbasis DFS untuk mencari solusi persoalan. Backtracking merupakan algoritma perbaikan dari brute-force, yang secara sistematis hanya mencari solusi yang mungkin. Umumnya algoritma Backtracking bersifat rekursif, namun ada pula versi backtracking yang iteratif.

Langkah-langkah pencarian solusi adalah sebagai berikut, :
1. Solusi dicari dengan membentuk lintasan dari akarn ke daun. Simpul yang dilahirkan bernama simpul hidup. Simpul hidup yang sedang diperluas dinamakan simpul-E.

2. Jika lintasan yang sedang dibentuk tidak mengarah ke solusi maka simpul-E dibunuh menjadi simpul mati. Fungsi yang digunakan untuk membunuh fungsi adalah fungsi pembatas.

3. Jika pembentukan simpul-E terakhir adalah simpul mati maka proses pencarian diteruskan dengan membangkitkan simpul anak yang lain. Bila tidak ada simpul anak lagi maka pencarian melakukan backtracking ke simpul orangtuanya.

4. Pencarian berakhir bila ditemukan solusi atau tidak ada lagi simpul yang hidup untuk backtrack.

Berikut adalah skema umum dari algoritma backtrack versi iteratif.


Free Template Blogger collection template Hot Deals BERITA_wongANteng SEO theproperty-developer