Co je backtracking?

Question

Co je backtracking?

Accepted Answer

**Backtracking** buduje kandidátní řešení postupně a **opouští** (ustupuje z) částečného kandidáta jakmile nemůže vést k platnému řešení. Systematicky prozkoumává prostor řešení prostřednictvím DFS a odsekává slepé uličky.

## Myšlenka

Zvolte -> prozkoumejte -> zrušte volbu. Vyzkoušejte možnost, opakujte; pokud selže, vraťte se a vyzkoušejte další.

## Příklad: všechny permutace

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

## Klasické problémy

- **N-queens**, Sudoku, rytířův tah.
- **Podmnožiny / kombinace / permutace.**
- **Vyhledávání slov**, řešení labyrintu.

## Složitost

Často exponenciální (např. O(n!) pro permutace), ale **prořezávání** dramaticky snižuje praktické hledání.

## Kdy použít / úskalí

Verejte pro problémy splňování omezení a "najít všechny platné konfigurace". Klíčová výhoda je **brzké prořezávání** — přeskočte větve, které porušují omezení. Zapomenutí vrátit stav ("zrušit volbu") je klasická chyba.

## Proč to je důležité

Backtracking je systematický způsob, jak prozkoumat kombinatorické prostory bez vynechání nebo opakování kandidátů.

Dobré prořezávání přeměňuje nezvladatelné hrubé síly na něco, co se stihne včas.

Zapouzuje řešitele pro hádanky, plánování a problémy s omezením v celém průmyslu.