Apakah itu backtracking?

Question

Accepted Answer

**Backtracking** membina calon penyelesaian secara berperingkat dan **meninggalkan** (backtrack daripada) sesuatu calon separa sebaik sahaja ia tidak boleh membawa kepada penyelesaian yang sah. Ia meneroka ruang penyelesaian secara sistematik melalui DFS, sambil memangkas jalan buntu.

## Ideanya

Pilih -> teroka -> nyahpilih. Cuba sesuatu pilihan, recurse; jika ia gagal, batalkannya dan cuba yang seterusnya.

## Contoh: semua permutasi

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

## Masalah klasik

- **N-queens**, Sudoku, knight's tour.
- **Subset / kombinasi / permutasi.**
- **Word search**, penyelesaian maze.

## Kompleksiti

Selalunya eksponen (cth., O(n!) untuk permutasi), tetapi **pemangkasan** mengurangkan carian praktikal secara dramatik.

## Bila digunakan / perangkap

Guna untuk masalah constraint-satisfaction dan "cari semua konfigurasi yang sah". Kemenangan utamanya ialah **memangkas awal** — langkau cabang yang melanggar kekangan. Terlupa membatalkan keadaan ("un-choose") ialah pepijat klasik.

## Mengapa ia penting

Backtracking ialah cara sistematik untuk meneroka ruang kombinatorik tanpa terlepas atau mengulang calon.

Pemangkasan yang baik menukar brute force yang tidak terurus menjadi sesuatu yang selesai tepat pada masanya.

Ia menggerakkan penyelesai untuk teka-teki, penjadualan, dan masalah kekangan di seluruh industri.