Backtracking - biror muammoni yeçiş uçun har bir ehtimoliy kombinatsiyalarni tekşirib çiquvçi va natija topilganda dasturni töxtatuvçi rekursiv algoritm. U tree içida qidiruv yoki tree'ning barça uçlarini (barglarini) topiş kabi amallarni bajarib, har bir tree'ning uçlarigaça tekşirib çiqadi. Tree'ning uçiga yetgaç, qidirilayotgan qiymat topilmasa, kelgan yöli böyiça orqaga qaytişni boşlaydi.

Backtracking algoritmining işlaş prinsipi

Qidiruv har doim tree'ning çap tarafidan boşlanadi va pastga qarab ketadi. Qidirilayotgan natija topilmagunça, daraxtning barglariga yetgaç, orqaga qaytib öng tarafdagi keyingi node'dan qidiruvni davom ettiradi.

Backtracking afzalliklari

• Bruteforce kabi barça elementlarni tekşirib çiqqani uçun, deyarli barça muammolarni hal qila oladi.
• Barça mavjud yeçimlarni topiş uçun işlatiş mumkin.
• Kodni yozişga oson

Kamçiliklari

• Sekin işlaydi
• Ma'lumotlar katta bölsa, qidiruv köp vaqt oladi.
• Rekursiv algoritm bölgani uçun xotira va protsessor resurslarini köp talab qiladi.

Backtrackingga aloqador mavzular

• Depth first search
• Breadth first search