Kas yra grįžtamasis paieška (backtracking)?

Question

Accepted Answer

**Grįžtamoji paieška** sukuria kandidatines sprendimus nuosekliai ir **atsisakyti** (grįžti atgal iš) dalinę kandidatę, kai tik matyti, kad ji negali vesti prie tinkamo sprendimo. Ji sistematiškai tyrinėja sprendimo erdvę per DFS, apkertant negalinius šakų.

## Idėja

Pasirinkti -> tyrinėti -> atšaukti pasirinkimą. Spróbą variantą, rekursyviai; jei nepavyks, anuliuoti jį ir bandyti kitą.

## Pavyzdys: visos permutacijos

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

## Klasikinės problemos

- **N-karalienės**, Sudoku, riterio žygis.
- **Poaibiai / kombinacijos / permutacijos.**
- **Žodžio paieška**, labirinto sprendimas.

## Sudėtingumas

Dažnai eksponentinis (pvz., O(n!) permutacijoms), bet **apkerpimas** sumažina praktinę paiešką dramatiškai.

## Kada naudoti / spąstai

Naudokite apribojimo tenkinimo ir "rasti visas tinkamas konfigūracijas" problemoms. Pagrindinė nauda yra **ankstyvesnis apkerpimas** — praleiskite šakas, kurios pažeidžia apribojimus. Užmiršti atšaukti būsenos ("atšaukti pasirinkimą") yra klasikinė klaida.

## Kodėl tai svarbu

Grįžtamoji paieška yra sistemingas būdas tyrinėti kombinatorines erdves nepraleidžiant ar nekartojanot kandidačių.

Geras apkerpimas paverčia nesuvaidinamą grubią jėgą į ką nors, kas baigiasi laiku.

Ji naudojama pasaulinėse užduoties sprendimų sistemose, suplanuojant ir apribojimo problemose.