რა არის ბექტრეკინგი?

Question

Accepted Answer

**ბექტრეკინგი** აშენებს კანდიდატ ამოხსნებს თანმიმდევრობით და **უარყოფს** (ბექტრეკავს) ნაწილობრივი კანდიდატის აზრს, როგორც კი ის არ შეიძლება მიგვიყვანოს მოქმედი ამოხსნებისკენ. ის სისტემატურად აკვლევს ამოხსნის სივრცეს 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-დედოფალი**, სუდოკუ, მხედლის ტური.
- **ქვესიმრავლეები / კომბინაციები / პერმუტაციები.**
- **სიტყვის ძებნა**, ლაბირინთის ამოხსნა.

## სირთულე

ხშირად ექსპონენციალური (მაგ., O(n!) პერმუტაციებისთვის), მაგრამ **მოწყვეტა** მკრთალ ძებნას დრამატულად ამცირებს.

## როდის გამოიყენო / სტკივებები

გამოიყენე შეზღუდვების დაკმაყოფილების და "იპოვე ყველა მოქმედი კონფიგურაცია" ამოცანებისთვის. ძირითადი გამარჯვება არის **ადრეული მოწყვეტა** — გამოტოვე ფილიალი, რომელიც ცვალებელი შეზღუდვები. მდგომარეობის გააუქმება დაჭერის ([[code]]) დავიწყება არის კლასიკური ხარვეზი.

## რატომ აქვს მნიშვნელობა

ბექტრეკინგი არის კომბინატორული სივრცეების სისტემატური გამოკვლევის გზა წამკიდოთ ან კანდიდატების გამეორების გარეშე.

ცხელი მოწყვეტა აქცევს დამაბნეველ ხელმავლო ძალის მეთოდს რაღაცა, რაც დროში სრულდება.

ეს აძლევს პაზლებისთვის, დაგეგმვისთვის და შეზღუდვის ამოცანებისთვის სოლვერებს მთელი ინდუსტრიის მასშტაბით.