Çfarë është backtracking?

Question

IT Interview Practice · Accepted Answer

**Backtracking** ndërton zgjidhje kandidate në mënyrë inkrementale dhe **braktis** (kthehet mbrapa nga) një kandidat i pjesshëm sapo ai nuk mund të çojë në një zgjidhje të vlefshme. Ai shploron në mënyrë sistematike hapësirën e zgjidhjeve përmes DFS, duke prerë degë të vdekura.

## Ideja

Zgjidh -> shploron -> zhbën zgjedhjen. Provo një opsion, rekurzivizohu; nëse dështon, zhbën atë dhe provo tjetrën.

## Shembull: të gjitha permutacionet

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

## Probleme klasike

- **N-mbretëresha**, Sudoku, turata e kalit.
- **Nënbashkësi / kombinacione / permutacione.**
- **Kërkimi i fjalës**, zgjidhja e labirintit.

## Kompleksiteti

Shpesh eksponencial (p.sh., O(n!) për permutacionet), por **prerja** zvogëlon ndjeshëm kërkimin praktik.

## Kur të përdorni / grackat

Përdorni për probleme të kënaqjes me kufizimet dhe "gjej të gjitha konfiguracionet e vlefshme". Fitorja kryesore është **prerja e hershme** — shmangu degët që shkelin kufizimet. Harresa për të zhbërë gjendjen ("zhbën zgjedhjen") është gabimi klasik.

## Pse është e rëndësishme

Backtracking është mënyra sistematike për të shploruar hapësirat kombinatorike pa humbur ose përsëritur kandidatë.

Prerja e mirë shndërron një forcë brute të paturpësmershme në diçka që mbaron në kohë.

Ajo drejton zgjidhësit për enigma, planifikim dhe probleme kufizimet në të gjithë industriën.

Ideja

Shembull: të gjitha permutacionet

Probleme klasike

Kompleksiteti

Kur të përdorni / grackat

Pse është e rëndësishme

Pyetje të ngjashme