Tarkibga o'tish

Backtracking

Labirintda yo'l qidirayotgansiz. To'g'ridan borsangiz — devorga tiqilasiz. Orqaga qaytib chap tomonga burilasiz — yana devor. Orqaga, bu safar o'ngga — yo'l ochiq. Davom etasiz. Yana to'siq — orqaga, boshqa yo'l. Bu jarayon labirint chiqishiga yetib borguncha yoki barcha yo'llar tekshirilguncha davom etadi.

Bu backtracking — barcha mumkin bo'lgan yo'llarni sistematik ko'rib chiqish, noto'g'ri yo'lga kirilganda orqaga qaytish. Noto'g'ri deyarli bilingan zahot — davom etish besamar, shu joyda to'xtatiladi va orqaga qaytiladi. Bu pruning (kesib tashlash) — tekshirishning bu tarmog'idan voz kechish.

Asosiy g'oya: tanlash daraxtini aylanib chiqish

Backtracking masalalarini qaror daraxti (decision tree) sifatida ko'rish qulay. Har tugun — bitta qaror. Har shox — bir tanlov. Barg — oxirgi holat (muvaffaqiyatli yoki muvaffaqiyatsiz).

Misol: [1, 2, 3] ning barcha permutatsiyalari

                        []
             /           |           \
           [1]          [2]          [3]
          /   \        /   \        /   \
       [1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
         |     |     |     |     |     |
      [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Backtracking bu daraxtni DFS usulida aylanadi: bir shox bo'ylab chuqurga boradi, orqaga qaytadi, boshqa shoxni ko'radi.

Tanlash-Ko'rish-Bekor qilish (Choose-Explore-Unchoose)

Backtrackingning universal shabloni:

FUNCTION BACKTRACK(holat, variantlar)
    IF holat muvaffaqiyatli tugagan
        natijaga qo'shish (yoki RETURN TRUE)
        RETURN

    FOR har bir variant variantlar ichida
        IF variant mos kelmasa     // pruning
            CONTINUE

        variantni tanlash          // holat o'zgartiriladi
        BACKTRACK(yangi_holat, qolgan_variantlar)
        variantni bekor qilish     // holat avvalgiga qaytariladi

Uch bosqich:

Tanlash (Choose): hozirgi holatga bitta variant qo'shiladi. Holat o'zgartiriladi.

Ko'rish (Explore): o'zgartirilgan holat bilan rekursiv chaqiruv.

Bekor qilish (Unchoose): rekursiv chaqiruv qaytgach, holat avvalgiga tiklanadi. Bu boshqa variantlarni tekshirishda toza holat ta'minlaydi.

Bekor qilish — backtrackingning kaliti. Holat tiklansaman, keyingi variant tekshirishda avvalgi tanlashning ta'siri qolmaydi.

Pruning: keraksiz shoxlarni kesish

Barcha variantlarni tekshirish ko'pincha eksponensial. Pruning bu xarajatni kamaytiradi: ma'lum holatda kerakli natijaga yetib bo'lmasligini erta aniqlash va shu shox butunlay tashlab yuborish.

N-vazir masalasida:
  Ustunda allaqachon vazir bor → shu pozitsiyani sinab ko'rmaslik
  Diagonal bo'ylab to'qnashish → bu shox besamar

Sudoku masalasida:
  Qatorda raqam allaqachon bor → shu raqamni sinab ko'rmaslik

Pruning qanchalik kuchli bo'lsa — algoritm shunchalik tez. Ideal pruning barcha keraksiz shoxlarni erta kesadi.

Misol: subset (to'plamning barcha quyi to'plamlari)

[1, 2, 3] ning barcha quyi to'plamlarini topish:

FUNCTION SUBSETS(nums)
    result  = bo'sh list
    current = bo'sh list
    BACKTRACK(nums, 0, current, result)
    RETURN result

FUNCTION BACKTRACK(nums, start, current, result)
    result ga current ni qo'sh   // har bosqichda qo'shiladi

    FOR i = start DAN LENGTH(nums) - 1 GACHA
        current ga nums[i] ni qo'sh      // tanlash
        BACKTRACK(nums, i + 1, current, result)
        current dan oxirgi elementni olib tashlash  // bekor qilish

Dry run:

BACKTRACK(start=0, current=[])    → result: [[]]

  i=0, nums[0]=1: current=[1]
  BACKTRACK(start=1, current=[1]) → result: [[], [1]]

    i=1, nums[1]=2: current=[1,2]
    BACKTRACK(start=2, current=[1,2]) → result: [[], [1], [1,2]]

      i=2, nums[2]=3: current=[1,2,3]
      BACKTRACK(start=3, current=[1,2,3]) → result: [[], [1], [1,2], [1,2,3]]
      Bekor: current=[1,2]

    Bekor: current=[1]
    i=2, nums[2]=3: current=[1,3]
    BACKTRACK(start=3, ...) → result: [..., [1,3]]
    Bekor: current=[1]

  Bekor: current=[]
  i=1, nums[1]=2: current=[2]
  ... va hokazo

Yakuniy natija: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] — 2³ = 8 ta quyi to'plam.

Kombinatsiyalar

Uzunligi k bo'lgan barcha kombinatsiyalar:

FUNCTION COMBINATIONS(nums, k)
    result  = bo'sh list
    current = bo'sh list
    BACKTRACK(nums, 0, k, current, result)
    RETURN result

FUNCTION BACKTRACK(nums, start, k, current, result)
    IF LENGTH(current) = k
        result ga current ni qo'sh
        RETURN

    // Pruning: qolgan elementlar yetmasa davom etma
    remaining = k - LENGTH(current)
    IF LENGTH(nums) - start < remaining
        RETURN

    FOR i = start DAN LENGTH(nums) - 1 GACHA
        current ga nums[i] ni qo'sh
        BACKTRACK(nums, i + 1, k, current, result)
        current dan oxirgi elementni olib tashlash

Pruning satri: agar qolgan elementlar soni kerakli sondan kam bo'lsa — bu shox hech qachon k uzunlikka yetmaydi.

Backtracking vs to'liq qidirish

To'liq qidirish (brute force) barcha holatlarni ko'rib chiqadi — hech qanday kesmasdan. Backtracking esa "ushbu yo'l qaror topib bo'lmaydi" deb erta bilganda kesib tashlaydi.

Sudoku:
  Brute force: har katakka 1-9 raqamlarini sinash (9^81 variant)
  Backtracking: har katakka faqat mos raqamlarni sinash va bekor qilish

N-vazir:
  Brute force: N² pozitsiyadan N ni tanlash
  Backtracking: har qatorda faqat mos ustunlarni sinash

Backtracking eng yomon holatda brute force bilan bir xil, lekin amalda pruning sababli tezroq.

Murakkablik

Backtracking murakkabligini aniq hisoblash qiyin — pruning tufayli amaliy va worst-case keskin farq qiladi.

Permutatsiyalar: n! — n elementning barcha tartiblari.

Kombinatsiyalar: C(n, k) — n dan k ni tanlash.

Quyi to'plamlar: 2^n — har element bormi-yo'qmi.

N-vazir: O(n!) worst case, ammo pruning bilan ancha kam.

Barcha backtracking algoritmlari eksponensial yoki ulardan ham ortiqroq vaqt olishi mumkin. Bu ularning cheklovi — katta kirish uchun mos emas. Amalda ular chekli, kichik massivlar (n ≤ 20) uchun ishlatiladi.

Xotira: rekursiya chuqurligi O(n) — call stack va joriy holat.

Qachon backtracking kerak?

  • Barcha yechimlar kerak bo'lganda (barcha permutatsiyalar, barcha to'plamlar, barcha yo'llar)
  • Bitta yechim kerak, lekin uni topishga hech qanday matematik yo'l yo'q bo'lganda (Sudoku, N-vazir, kriptaritmika)
  • Cheklovlar tizimini qanoatlantiradigan kombinatsiyalar qidirilganda (constraint satisfaction)
  • Kirish kichik bo'lganda — n ≤ 20 atrofida

Qachon backtracking kerak emas?

  • Faqat bitta optimal qiymat kerak bo'lsa — DP yoki greedy
  • Natijalar soni eksponensial, lekin ularni sanash kerak bo'lsa — kombinatorika formulasi
  • Graf traversal yetarli bo'lsa — BFS yoki DFS
  • Kirish katta bo'lsa — backtracking juda sekin bo'ladi

Keng tarqalgan xatolar

Holatni bekor qilishni unutish

Eng keng tarqalgan xato — rekursiv chaqiruvdan keyin holat tiklanmaydi. Natijada keyingi shoxlar noto'g'ri holat bilan boshlanadi:

// Noto'g'ri:
current ga nums[i] ni qo'sh
BACKTRACK(...)
// bekor qilish yo'q — current xato holda qoladi

// To'g'ri:
current ga nums[i] ni qo'sh
BACKTRACK(...)
current dan oxirgi elementni olib tashlash

Holat nusxalanishini to'g'ri boshqarmaslik

Ba'zan rekursiv chaqiruvga holat nusxasi (copy) yuborilib, bekor qilish kerak emas. Bu ham ishlaydi, lekin har chaqiruvda nusxa olish xotirani oshiradi. Qaysi usul qo'llanilayotgani aniq bo'lishi kerak.

Pruning etarli emas

Pruning kuchsiz bo'lsa, backtracking kechikadi. Qo'shimcha cheklovlar (masalan, ketma-ket j > i indeks ishlatish) ko'p nusxalarni kamaytiradi.

Base case noto'g'ri

Rekursiya qachon tugashini aniq belgilamaslik cheksiz rekursiyaga olib kelishi mumkin.

Xulosa

Backtracking — qaror daraxtini DFS bilan aylanish: tanlash, ko'rish, bekor qilish. Har noto'g'ri shox pruning orqali erta kesib tashlanadi.

Universal shablon: tanlash → rekursiv chaqiruv → bekor qilish. Bekor qilish — holatni toza saqlash uchun zarur. Pruning — algoritmni amalda tezlashtiruvchi asosiy mexanizm.

Backtracking yaxshi: barcha yechimlarni qidirish, kichik kirish, constraint satisfaction. Yomon: katta kirish, faqat optimal qiymat kerak bo'lganda.

Permutatsiyalar, kombinatsiyalar, N-vazir, Word Search, Sudoku — bularning hammasi backtrackingning klassik qo'llanishlari.