Mikä on backtracking?

Question

Accepted Answer

**Backtracking** rakentaa kandidaattiratkaisuja vähitellen ja **hylkää** (perääntyy) osittaisen kandidaatin heti, kun se ei voi johtaa kelvolliseen ratkaisuun. Se tutkii ratkaisuavaruutta systemaattisesti DFS:n kautta ja karsii umpikujat.

## Idea

Valitse -> tutki -> peru valinta. Yritä vaihtoehtoa, rekursio; jos epäonnistuu, peru ja yritä seuraavaa.

## Esimerkki: kaikki permutaatiot

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

## Klassiset ongelmat

- **N-queens**, Sudoku, ritarin kierros.
- **Osajoukot / yhdistelmät / permutaatiot.**
- **Sanahaku**, sokkelon ratkaiseminen.

## Monimutkaisuus

Usein eksponentiaalinen (esim. O(n!) permutaatioille), mutta **karsinta** vähentää käytännön hakua dramaattisesti.

## Milloin käyttää / sudenkuopat

Käytä rajoitusten toteuttamisen ja "etsi kaikki kelvolliset kokoonpanot" -ongelmissa. Avaintuki on **varhainen karsinta** — ohita haarat, jotka rikkovat rajoituksia. Unohtaa tilan kumoaminen ("peru valinta") on klassinen virhe.

## Miksi se on tärkeää

Backtracking on systemaattinen tapa tutkia kombinatorisia avaruuksia ilman kandidaattien puuttumista tai toistamista.

Hyvä karsinta muuttaa mahdottoman raakavoiman johonkin, joka valmistuu ajoissa.

Se käyttää ratkaisijöita palapeleille, aikataulutukselle ja rajoitusongelmille koko teollisuudessa.