Kaj je povratno sledenje (backtracking)?

Question

Accepted Answer

**Povratno sledenje** gradi kandidatne rešitve postopoma in **opusti** (se vrne od) delne kandidate, čim ko ne morejo voditi do veljavne rešitve. Sistematično raziskuje prostor rešitev prek DFS, pri čemer obrezuje slepe ulice.

## Ideja

Izberi -> raziskuj -> izbri izbiro. Poskusi možnost, rekurziviraj; če ne uspe, razveljaviti in poskusi naslednjo.

## Primer: vse permutacije

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

## Klasični problemi

- **N-kraljic**, Sudoku, jahalčev obhod.
- **Podmnožice / kombinacije / permutacije.**
- **Iskanje besed**, reševanje labirinta.

## Kompleksnost

pogosto eksponentna (npr. O(n!) za permutacije), vendar **obrezovanje** dramatično zmanjša praktično iskanje.

## Kdaj uporabiti / pasti

Uporablja se za probleme omejevalnega zadoščevanja in "najdi vse veljavne konfiguracije". Ključna prednost je **zgodnje obrezovanje** — preskoči veje, ki kršijo omejitve. Pozaba, da razveljavimo stanje ("izbri izbiro"), je klasična napaka.

## Zakaj je to pomembno

Povratno sledenje je sistematičen način za raziskovanje kombinatoričnih prostorov brez zamujanja ali ponavljanja kandidatov.

Dobro obrezovanje spremeni neobvladljivo surovo silo v nekaj, kar se zaključi v času.

Ganja solverje za uganke, razporede in probleme omejitev po celotni industriji.