Backtracking — state-space tree, pruning: Foundations

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

Is page par kuch bhi assumed nahi hai. Parent note (topic) padhne se pehle, usme aane wale har word aur symbol par aapki pakad honi chahiye. Hum har ek ko ek picture se banate hain, us order mein jo har idea ko pichle wale par tikne deta hai.

1. Ek "decision" aur ek "partial solution"

Kisi bhi tree ya recursion se pehle, atom yeh hai: ek decision.

Pehli figure dekho. Baayein taraf ek khali tray hai (partial solution = kuch nahi choose kiya). Aap jo bhi arrow follow karte ho woh tray mein ek item add karta hai. Ek complete solution ek bhari hui tray hai; ek dead end woh tray hai jismein aap legally kuch aur nahi jod sakte.

Topic ko yeh kyun chahiye: poori method hai "partial solution ko decision by decision badhao". Agar aap ek adha-bana hua answer picture nahi kar sakte, toh upar ka kuch bhi samajh nahi aayega.

2. Tree — root, node, edge, leaf, branch, subtree

Decisions ki har sequence ko ek branching diagram ki tarah draw kiya ja sakta hai. Mathematicians ise tree kehte hain (ulta draw kiya: root upar).

Topic ko yeh kyun chahiye — payoff sentence: ek buri partial choice kisi node par baithti hai, aur uske subtree ka har leaf us galti ko inherit karta hai. Toh agar aap prove kar sako ki ek node hopeless hai, aap uska poora subtree ek hi baar mein delete kar dete ho. Yahi ek fact backtracking ko fast banata hai. Figure mein laal X dekho: ek edge wahan kaatne se ek saath chaar leaves mit gayin.

3. Recursion — woh tool jo tree ko walk karta hai

Hamare liye base case hai "partial solution complete hai → use record karo aur return karo". Har non-base node kehta hai "har valid child ke liye, khud ko us child par call karo". Gehri mechanics ke liye Recursion dekho; yahaan sirf yeh chahiye: ek self-call ka matlab hai 'ek node aur gehre jao', aur return ka matlab hai 'wapas upar aao'.

Topic ko yeh kyun chahiye: parent ka generic template ek recursive function hai. Recursion ke bina "go deeper / come back" ka motion ka koi clean form nahi hota.

4. DFS — woh order jismein recursion nodes visit karta hai

Recursion hamein ek natural visiting order deta hai, aur iska ek naam hai.

Figure mein numbered arrows follow karo: 1 → 2 → 3 (leaf mili) → wapas upar → 4 (next sibling) → phir gehre. Yahi recursion automatically karta hai: self-call dive karta hai, return climb karta hai. Depth-First-Search dekho.

Topic ko yeh kyun chahiye: parent kehta hai "Depth-First order mein explore kiya". Depth-first ki wajah se partial solution finish (ya fail) hoti hai uske siblings ke touch hone se pehle — aur yahi woh waqt hai jab hume prune karne ka mauka milta hai.

5. Feasibility test — `is_valid` aur "promising"

Topic ko yeh kyun chahiye: pruning sirf yahi hai — "har node par is_valid run karo aur failures ko expand karne se mana karo". Koi feasibility test nahi → koi pruning nahi → plain brute force.

6. Pruning aur backtracking — dono named actions

7. Parent ki formula ke symbols

Parent ki boxed recursion compact notation use karti hai. Yeh har piece hai:

8. Branching factor $b$ , depth $d$ , aur $b^{d}$

Parent ki complexity $b$ , $d$ , aur $b^{d}$ use karti hai. Inhe tree picture se banao.

$b^{d}$ leaves kyun? Level 0 mein 1 node hai. Har node $b$ children banata hai, toh level 1 mein $b$ hai, level 2 mein $b \cdot b = b^{2}$ hai, … level $d$ mein $b^{d}$ hai. Chhota superscript $d$ ka matlab hai " $b$ ko $d$ baar khud se multiply karo".

Topic ko yeh kyun chahiye: $b^{d}$ un-pruned tree ka size hai. Yeh explosively badhta hai (woh superscript hi wajah hai ki 4 queens mein $4^{4} = 256$ leaves hain). Pruning is growth se ladhti hai. Time-Complexity dekho aur, worst-case Big-O baat ke liye, Branch-and-Bound dekho.

Recall Quick check:

$b^{d}$ "exponential" kyun hai? Kyunki variable ( $d$ ) exponent mein hai. Ek level add karo aur count $b$ se multiply ho jaata hai, add nahi — size har level par kam se kam double-and-then-some ho jaati hai. Pruning worst case kyun kam nahi karta? ::: Ek adversarial input har node ko end tak bhi promising dikha sakta hai, toh kuch cut nahi hota aur aap poora $b^{d}$ pay karte ho.

Prerequisite map

Ise top-down padhlo: atom (decision) tree aur recursion dono ko feed karta hai; recursion + tree DFS dete hain; feasibility test plus DFS pruning dete hain; pruning plus undo full backtracking dete hain; tree ki shape $b$ , $d$ , aur $b^{d}$ cost deti hai. Saare arrows topic par converge karte hain.

Equipment checklist

Khud ko test karo — sirf zor se jawab dene ke baad reveal karo.

"Decision" aur "partial solution" hain

ek move jo aap karte ho, aur abhi tak ke saare moves se bana incomplete answer.

Root, node, edge, leaf

root = upar empty solution; node = partial solution; edge = ek decision; leaf = complete solution ya dead end.

Subtree, aur ek kaatna kyun matter karta hai

ek node plus uske neeche sab kuch; uska har leaf us node ki partial choice inherit karta hai, toh ek cut exponentially many dead ends ko khatam karta hai.

Loop ke upar recursion kyun

tree ki nested shape ko "gehre jao, phir wapas aao" chahiye; ek self-call = gehre jao, return = wapas chadhna.

Base case

stopping condition — yahaan, "partial solution complete hai → record karo aur return karo".

DFS

next sibling try karne se pehle ek branch mein jitna ho sake utna gehre jao.

is_valid / promising node

ek fast veto; ek promising node woh partial solution hai jo abhi bhi valid complete answer ban sakta hai.

Pruning vs backtracking

pruning = doomed subtree explore na karne ka decide karna; backtracking = parent par wapas jaane ke liye last move ko mechanically undo karna.

Formula mein

s + x

state

s

mein ek aur chosen decision

x

append kiya (arithmetic nahi).

Union symbol

⋃

"har valid branch ke solutions ko combine karo".

b

d

b^{d}

branching factor, depth, aur un-pruned tree mein leaves ki sankhya.

b^{d}

exponential kyun hai

depth exponent mein hai, toh har naye level par node count

b

se multiply ho jaata hai.

Connections

Recursion — woh self-calling mechanism jis par DFS sawaar hai.
Depth-First-Search — exact visiting order.
Time-Complexity — jahan se $b^{d}$ aur Big-O aate hain.
Branch-and-Bound — numeric bounds ke saath pruning, agla step upar.
N-Queens, Sudoku-Solver, Permutations-and-Combinations — pehle problems jo upar sab kuch use karte hain.
Backtracking (parent topic)