Τι είναι το backtracking;

Question

Accepted Answer

Το **Backtracking** κατασκευάζει λύσεις υποψηφίων σταδιακά και **εγκαταλείπει** (υποχωρεί από) έναν μερικό υποψήφιο όταν δεν μπορεί να οδηγήσει σε έγκυρη λύση. Εξερευνά συστηματικά τον χώρο λύσεων μέσω DFS, κόβοντας άκρα που δεν έχουν έξοδο.

## Η ιδέα

Επιλέξτε -> εξερευνήστε -> αναιρέστε την επιλογή. Δοκιμάστε μια επιλογή, επανάληψη· αν αποτύχει, αναιρέστε και δοκιμάστε την επόμενη.

## Παράδειγμα: όλες οι μεταθέσεις

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

## Κλασικά προβλήματα

- **N-queens**, Sudoku, η περιοδεία του ιππότη.
- **Υποσύνολα / συνδυασμοί / μεταθέσεις.**
- **Αναζήτηση λέξεων**, επίλυση λαβυρίνθου.

## Πολυπλοκότητα

Συχνά εκθετική (π.χ. O(n!) για μεταθέσεις), αλλά το **κόψιμο** μειώνει δραστικά την πρακτική αναζήτηση.

## Πότε να χρησιμοποιήσετε / παγίδες

Χρησιμοποιήστε για προβλήματα ικανοποίησης περιορισμών και "βρείτε όλες τις έγκυρες διαμορφώσεις". Το κύριο κέρδος είναι **πρώιμο κόψιμο** — παραλείψτε κλαδιά που παραβιάζουν περιορισμούς. Το να ξεχάσετε να αναιρέσετε την κατάσταση ("αναιρέστε την επιλογή") είναι το κλασικό σφάλμα.

## Γιατί σημαίνει

Το Backtracking είναι ο συστηματικός τρόπος για να εξερευνήσετε συνδυαστικούς χώρους χωρίς να χάσετε ή να επαναλάβετε υποψηφίους.

Το καλό κόψιμο μετατρέπει μια δυσχείριστη επίθεση ωμής δύναμης σε κάτι που τελειώνει στην ώρα του.

Τροφοδοτεί επίλυτες για παζλ, χρονοδιάγραμμα και προβλήματα περιορισμών σε όλο τον κλάδο.