Mi a backtracking?

Question

Mi a backtracking?

Accepted Answer

**A backtracking** lépésekben építi fel a jelölti megoldásokat, és **elhagyja** (visszalép) egy részleges jelöltet, amint az nem vezethet érvényes megoldáshoz. Rendszeresen feltárja a megoldási teret DFS-en keresztül, és levágja a halott végeket.

## Az ötlet

Válassz -> fedezz fel -> visszavonás. Próbálj ki egy lehetőséget, rekurziót; ha meghiúsul, vonja vissza és próbálja meg a következőt.

## Példa: minden permutáció

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

## Klasszikus problémák

- **N-királynő**, Sudoku, a lovag túrája.
- **Részhalmazok / kombinációk / permutációk.**
- **Szó keresés**, labirintus megoldása.

## Bonyolultság

Gyakran exponenciális (például O(n!) a permutációkhoz), de a **lenyesés** drámaian csökkenti a gyakorlati keresést.

## Mikor kell használni / buktatók

Használja a kényszerkielégítés és "minden érvényes konfiguráció megkeresése" problémáihoz. A fő nyereség a **korai lenyesés** — hagyja ki azokat az ágakat, amelyek megsértik a megkötéseket. A státusz visszavonásának elfelejtése ("visszavonás") a klasszikus hiba.

## Miért fontos

A backtracking a kombinatorikus terek szisztematikus feltárásának módja anélkül, hogy jelölteket kellene kihagyni vagy megismételni.

A jó lenyesés egy megoldható nyers erőt olyasvalamivé alakít, amely időben befejeződik.

Energiát ad a rejtvények, ütemezés és kényszerprobléma-megoldóknak az egész iparban.