Visual walkthrough — Backtracking — state-space tree, pruning

3.7.16 · D2 · Coding › Algorithm Paradigms › Backtracking — state-space tree, pruning

Yeh parent topic ka ek picture-first companion hai. Agar koi word heavy lage, toh uske saath wali figure dekho — geometry hi idea ko carry karti hai.

Step 1 — Ek decision ek raaste ka mod hai

KYA. Kisi bhi tree se pehle, sirf ek choice hoti hai. Maano hum kuch place kar rahe hain aur hamare paas exactly do options hain: lo ya chhoddo. Yeh single choice ek fork hai — ek point se nikalne wale do raaste.

YAH se kyun shuru karein. Backtracking choices ke upar choices ki stack ke siva kuch nahi hai. Agar hum ek fork ko perfectly nahi samajhte, toh hazaron forks ka ek tree hopeless hai. Isliye pehle atom ko samajhte hain.

PICTURE. Figure dekho: left mein ek bhari hui dot current state hai — jo kuch humne abhi tak decide kiya hai. Usme se do arrows nikalte hain. Har arrow ka label woh decision hai jo hum lete hain. Right mein do dots woh naye states hain jahan hum decide karne ke baad pahunchte hain.

Step 2 — Forks ko stack karo: state-space tree saamne aata hai

KYA. Ab pehle ke baad doosra decision karo, aur uske baad teesra. Har naya fork wahan se nikalta hai jahan pichla humein chhodkar gaya. Unhe sab ek saath draw karna figure mein woh shape deta hai — ek tree.

Tree kyun, list kyun nahi. Kyunki baad ki choice us path par depend karti hai jo wahan pahuncha. "Skip, fir take" kahin alag pahunchata hai "take, fir take" se. Tree bilkul wohi picture hai "decisions ke har path ki".

PICTURE. Upar se neeche ki layers gino. Layer $0$ (sabse upar ki dot) root hai — empty state, abhi tak koi decision nahi. Har neeche ka level = ek aur decision liya gaya. Sabse neeche ki dots ki row leaves hain — wo states jahan decide karne ke liye kuch nahi bacha.

Agar har node se $b$ arrows nikalte hain (branching factor) aur tree $d$ levels deep hai, toh leaves ki sankhya hai:

$\underset{\text{choices per node}}{\underbrace{b}}\times b\times \cdots \times b=b^d$

• $b$ — ek node se kitne decisions fork karte hain (yahan $b=2$: take / skip).
• $d$ — hum kitne deep jaate hain, yaani ek poore solution ko kitne decisions chahiye.
• $b^d$ — total leaves, yaani brute-force count. Yeh daraaune speed se badhta hai; yehi dushman hai.

Step 3 — Depth-first chalao (ek ungli, seedha neeche tak)

KYA. Hum poora tree ek saath nahi dekhte. Hum ise maze ki tarah explore karte hain: ek path par jitna ho sake utna deep jao, aur tabhi jab aur deep nahi ja sakte tab ek step upar aao aur agla arrow try karo. Us order ko depth-first kehte hain.

Depth-first kyun. Kyunki hum solution incrementally build karte hain. Deep jaana = current partial solution mein ek aur decision add karna. Yeh humein ek single state object (Step 6 dekho) reuse karne deta hai har node ko store karne ke bajaye.

PICTURE. Figure mein numbered arrows woh exact order dikhate hain jis mein hamari "ungli" nodes visit karti hai: neeche-neeche-neeche, bottom hit karo, ek upar aao, sibling try karo, aur aage. Yeh bilkul ek depth-first search hai — lekin ek aisi tree par jo hum chalte chalte generate kar rahe hain, memory mein stored tree par nahi.

Step 4 — isValid test: har arrow par ek gate

KYA. Kisi arrow se neeche jaane se pehle, hum ek quick check chalate hain jise ==isValid== kehte hain us state par jo woh arrow lead karega. Agar partial solution pehle se koi rule tod raha hai, toh gate band hai — hum aage nahi badhte.

Yahan kyun, neeche kyun nahi. Ek toota hua partial solution kabhi bhi valid full solution nahi ban sakta — zyada decisions add karna pehle se toodi hui rule ko theek nahi kar sakta. Isliye leaf par check karna poori ek bakwas hai: hum ek poora subtree generate karte sirf sab ko reject karne ke liye.

PICTURE. Figure mein lal ✗ ek arrow par baitha hai. Notice karo uske neeche sab kuch — greyed-out subtree — un states ka set hai jinhe hum visit karte lekin ab kabhi generate hi nahi karte.

Step 5 — Pruning = ek subtree delete karna, aur yeh exponentially kyun fayda karta hai

KYA. Tree mein upar gate band karna pruning kehlata hai. Kyunki ek band gate ek node nahi balki uske neeche laka poora subtree remove karta hai, ek sasta sa test hazaron dead-ends mita sakta hai.

Yeh exponential leverage kyun hai. Agar hum depth $k$ par ek arrow prune karte hain (root ko depth $0$ maanke), toh jo subtree hum delete karte hain usmein abhi $d-k$ depth baaki thi grow karne ke liye. Us ek cut se maari gayi leaves ki sankhya:

$\text{leaves removed}=b^{d-k}$

• $d-k$ — pruned arrow ke neeche kitne decision-levels baaki the.
• $b^{d-k}$ — woh leaves jo pruned arrow ke neeche laki thi, sab ek test se gone.
• Message padho: upar prune karo (chhota $k$) → exponent $d-k$ bada hai → ek bada cut.

PICTURE. Do cuts dikhaye gaye hain. Upar wala cut (root ke paas) ek mota subtree remove karta hai; neeche wala cut (leaf ke paas) almost kuch nahi remove karta. Isliye parent note kehta hai "ek bure subtree ki root kaatna exponentially zyada dead-ends ko khatam karta hai".

Step 6 — Make / explore / undo rhythm (drawing honest kyun rehti hai)

KYA. Hum poore tree ke liye ek mutable state reuse karte hain. Kisi arrow se neeche jaate hue hum decision add karte hain; wapas upar aate hue hum ise remove karte hain — exactly parent ka state restore karte hain.

Undo mandatory kyun hai. Ek child explore karne ke baad, hum sibling ko parent ke exact state se try karna chahte hain. Agar hum apna decision remove karna bhool gaye, toh sibling ko ek corrupted state mileга — jaise humne ek extra arrow draw kiya jo wahan tha hi nahi.

PICTURE. Ek edge par do coloured half-arrows follow karo: neeche wala half hai add(x) (move karo), upar wala half hai remove(x) (undo). Yeh pairs mein aane chahiye, recursion ko bracket karte hue, matching parentheses ki tarah.

def backtrack(state):
    if is_complete(state):
        record(state); return
    for choice in candidates(state):
        if is_valid(state, choice):   # Step 4 gate
            state.add(choice)         # DOWN  = make
            backtrack(state)          # deeper
            state.remove(choice)      # UP    = undo  <-- never skip

Yeh mutate-and-restore discipline hi true backtracking ko plain Recursion ya stored-tree DFS se alag karti hai.

Step 7 — Edge & degenerate cases (jo log bhool jaate hain)

KYA. Ek derivation tabhi trustworthy hai jab woh extremes par survive kare. Char corner cases, har ek draw ki gayi:

1. Root pehle se hi complete hai ($d=0$). Koi decisions nahi chahiye — empty state hi answer hai. Tree ek single dot hai; hum record karte hain aur rok dete hain.
2. Har gate depth 1 par band ho jaata hai. Koi valid solution exist nahi karta. Hum saare top arrows prune karte hain aur empty set return karte hain — correctly "impossible" report karte hain.
3. Koi gate kabhi band nahi hota (adversarial input). Kuch bhi prune nahi kiya ja sakta; hum saari $b^d$ leaves visit karte hain. Pruning ne humein yahan kuch nahi diya.
4. Branching factor har level par kam hota hai. Permutations mein, baaki choices $n,n-1,\dots ,1$ tak girti hain, isliye count $n!$ hai, $b^d$ nahi — tree neeche jaate jaate sankri hoti hai.

Case 3 sabse zyada kyun matter karta hai. Yeh honest complexity claim prove karta hai:

PICTURE. Char mini-trees side by side: single-dot root, all-pruned-at-top tree, fully-grown unprunable tree, aur sankri hoti permutation tree.

Ek picture mein summary

KYA. Sab kuch ek saath: ek poora state-space tree, ek depth-first finger-path numbered, do gates ✗ se band, unke delete kiye gaye do subtrees shaded out, aur ek edge jo down-add / up-remove pair dikhata hai. Agar tum yeh single frame samajh gaye, toh page samajh gaye.

Connections

• Parent topic — poora method aur code.
• Depth-First-Search — woh exploration order jo hamari ungli follow karti hai.
• Recursion — woh mechanism jo decisions stack aur unstack karta hai.
• N-Queens, Sudoku-Solver, Permutations-and-Combinations — trees jinhe yeh exact picture describe karti hai.
• Branch-and-Bound — boolean gate ki jagah numeric bound se pruning.
• Dynamic-Programming — $b^d$ se bachne ka ek alag raasta: overlapping subproblems reuse karo.
• Time-Complexity — kyun $O(b^d)$ worst case mein pruning ke baad bhi survive karta hai.