Backtracking – biror muammoni yechish uchun har bir ehtimoliy kombinatsiyalarni tekshirib chiquvchi va natija topilganda dasturni to’xtatuvchi rekursiv algoritm. U tree ichida qidiruv yoki tree’ning barcha uchlarini (barglarini) topish kabi amallarni bajarib, har bir tree’ning uchlarigacha tekshirib chiqadi. Tree’ning uchiga yetgach, qidirilayotgan qiymat topilmasa, kelgan yo’li bo’yicha orqaga qaytishni boshlaydi.
Qidiruv har doim tree’ning chap tarafidan boshlanadi va pastga qarab ketadi. Qidirilayotgan natija topilmaguncha, daraxtning barglariga yetgach, orqaga qaytib o’ng tarafdagi keyingi node’dan qidiruvni davom ettiradi.
Backtracking afzalliklari
- Bruteforce kabi barcha elementlarni tekshirib chiqqani uchun, deyarli barcha muammolarni hal qila oladi.
- Barcha mavjud yechimlarni topish uchun ishlatish mumkin.
- Kodni yozishga oson
- Sekin ishlaydi
- Ma’lumotlar katta bo’lsa, qidiruv ko’p vaqt oladi.
- Rekursiv algoritm bo’lgani uchun xotira va protsessor resurslarini ko’p talab qiladi.
Backtrackingga aloqador mavzular