Backtracking là gì?

Question

Backtracking là gì?

Accepted Answer

**Backtracking** (quay lui) xây dựng các lời giải ứng viên một cách tăng dần và **từ bỏ** (quay lui khỏi) một ứng viên bộ phận ngay khi nó không thể dẫn đến một lời giải hợp lệ. Nó khám phá không gian lời giải một cách hệ thống thông qua DFS, cắt tỉa (pruning) các ngõ cụt.

## Ý tưởng

Chọn -> khám phá -> bỏ chọn. Thử một phương án, đệ quy; nếu thất bại, hoàn tác nó và thử phương án tiếp theo.

## Ví dụ: tất cả các hoán vị

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # lời giải hoàn chỉnh
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # chọn
            backtrack(path, remaining[:i] + remaining[i+1:])  # khám phá
            path.pop()                             # bỏ chọn (quay lui)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 hoán vị
```

## Các bài toán kinh điển

- **N-queens**, Sudoku, hành trình quân mã (knight's tour).
- **Tập con / tổ hợp / hoán vị.**
- **Tìm từ trong lưới (word search)**, giải mê cung.

## Độ phức tạp

Thường là hàm mũ (ví dụ O(n!) với hoán vị), nhưng **cắt tỉa** giảm phạm vi tìm kiếm thực tế một cách đáng kể.

## Khi nào dùng / những cạm bẫy

Dùng cho các bài toán thỏa mãn ràng buộc (constraint-satisfaction) và "tìm tất cả các cấu hình hợp lệ". Lợi thế then chốt là **cắt tỉa sớm** — bỏ qua các nhánh vi phạm ràng buộc. Quên hoàn tác trạng thái ("bỏ chọn") là lỗi kinh điển.

## Tại sao điều này quan trọng

Backtracking là cách hệ thống để khám phá các không gian tổ hợp mà không bỏ sót hay lặp lại các ứng viên.

Cắt tỉa tốt biến một phép vét cạn bất khả thi thành một thứ kết thúc kịp giờ.

Nó vận hành các bộ giải cho các bài toán câu đố, lập lịch và ràng buộc trên khắp ngành công nghiệp.