Backtracking ni nini?

Question

Accepted Answer

**Backtracking** hujenga suluhisho la mgombea hatua kwa hatua na **kuacha** (kurudi nyuma kutoka) mgombea wa sehemu mara tu itakaposadikiwa kuwa haiwezi kusababisha suluhisho halali. Inachunguza furaha ya suluhisho kwa njia ya DFS, ikipunguza matawi ya kifo.

## Wazo hilo

Chagua -> chunguza -> futa chaguo. Jaribu chaguo, kurudia; ikiwa haifanyi kazi, futa na jaribu inayofuata.

## Mfano: vibali vyote

```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
```

## Matatizo ya kitamaduni

- **N-wanamfalme**, Sudoku, ziarani ya farasi.
- **Seti ndogo / michanganyiko / vibali.**
- **Utaftaji wa neno**, kutatua labyrinths.

## Ngumu

Habari exponential (mfano, O(n!) kwa vibali), lakini **kupunguza** kupunguza utaftaji wa vitendo sana.

## Lini kutumia / kupiga kelele

Tumia kwa matatizo ya kuridhisha vikwazo na "tafuta mipangilio yote halali". Uritaji mkuu ni **kupunguza mapema** — ruka matawi yanayokiuka vikwazo. Kusahau kurudisha hali ("futa chaguo") ni hitilafu ya kawaida.

## Kwa nini inatofautiana

Backtracking ni njia ya kupanga jinsi ya kuchunguza nafasi za combinatorial bila kukosa au kurudia wagombea.

Kupunguza vizuri hubadilisha nguvu ghafi isiyoweza kupunguzwa kuwa kitu kinachokamilika kwa wakati.

Inaendesha vitatuzi vya misumeno, ratiba, na matatizo ya vikwazo katika tasnia nzima.