બેકટ્રેકિંગ શું છે?

Question

બેકટ્રેકિંગ શું છે?

Accepted Answer

**બેકટ્રેકિંગ** અમુક ઉકેલોને ધીમે ધીમે બનાવે છે અને **છોડી દે છે** (પાછળ ફર્કે છે) આંશિક ઉમેદવાર તરીકે જલદી જ તે માન્ય ઉકેલ તરફ દોરી શકતું નથી. તે DFS દ્વારા સમાધાન સ્થાનને વ્યવસ્થિત રીતે અનુસંધાન કરે છે, મૃત છેડાને છાંટી કાઢે છે.

## આ વિચાર

પસંદ કરો -> શોધો -> અનપસંદ કરો. એક વિકલ્પ પર પ્રયાસ કરો, પુનરાવર્તિત કરો; જો તે નિષ્ફળ જાય, તો તેને પરિવર્તન કરો અને આગલો પ્રયાસ કરો.

## ઉદાહરણ: બધી ક્રમચય

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## શાસ્ત્રીય સમસ્યાઓ

- **N-રાણી**, સુડોકુ, નાઇટની યાત્રા.
- **સબસેટ્સ / સંયોજન / ક્રમચય.**
- **શબ્દ શોધ**, મેઝ હલ કરવું.

## જટિલતા

ઘણીવાર ઘાતાંકીય (દા.ત., ક્રમચયો માટે O(n!)), પરંતુ **છાંટવું** વ્યવહારુ શોધને નાટકીય રીતે ઘટાડે છે.

## ક્યારે ઉપયોગ કરવું / ભ્રમણ

બંધન-સંતુષ્ટि અને "બધી માન્ય રૂપરેખાઓ શોધો" સમસ્યાઓ માટે ઉપયોગ કરો. મુખ્ય લાભ **જલદી છાંટવું** છે — શાખાઓ છોડી દો જે અવરોધો ભંગ કરે છે. સ્થિતિ "અનપસંદ કરવું" ભૂલી જવું એ શાસ્ત્રીય બગ છે.

## આ શા આવશ્યક છે

બેકટ્રેકિંગ એ સંયોજન સ્થાનોને વ્યવસ્થિત રીતે શોધવાનો માર્ગ છે કોઈ ઉમેદવારને ગુમ કર્યા વિના અથવા પુનરાવર્તન કર્યા વિના.

રાજ્યની છાંટવું એક અસંભવ બળ-બળને સમયમાં સમાપ્ત થાય તેવી બાબતમાં રૂપાંતરિત કરે છે.

તે પઝલ, શેડ્યુલીંગ અને સંપૂર્ણ ઉદ્યોગ જુड়ा પરિબળ સમસ્યાઓ માટે દ્રાવક શક્તિ આપે છે.