Čo je späť?

BackTracking je všeobecná algoritmická technika, ktorá sa používa na rekurzívne riešenie problémov tým, že sa snaží postupne vybudovať riešenie, jeden kus naraz. Ak v ktoromkoľvek okamihu algoritmus zistí, že súčasný prístup nemôže viesť k platnému riešeniu (zasiahne „slepú uličku“), „spätne“ - vráti posledný krok alebo niekoľko krokov a pokúsi sa iný prístup. Tento proces pokračuje, kým sa nenájde riešenie alebo sa preskúmajú všetky možnosti.

Myslite na to ako na skúmanie bludiska:

* Začnete pri vchode a vyskúšate cestu.

* Ak dosiahnete slepú uličku, vrátite sa späť na poslednú križovatku a vyskúšajte inú cestu.

* Stále to robíte, kým nenájdete výstup (riešenie) alebo nepreskúmate všetky cesty.

Kľúčové charakteristiky spätného sledovania:

* rekurzívne: Algoritmy spätného sledovania sú vo svojej podstate rekurzívne. Každý rekurzívny hovor skúma inú vetvu priestoru riešenia.

* pokus a chyba: Je to prístup k pokusu a omylu. Snaží sa rôzne možnosti a odhodí tie, ktoré nevedú k riešeniu.

* Prieskum prieskumu: Algoritmus systematicky skúma celý stav stavu (všetky možné riešenia), často používa štruktúru podobnú stromu, ktorá predstavuje vyhľadávanie.

* prerezávanie: Kľúčovým aspektom je schopnosť prerezávať (zlikvidovať) vetvy vyhľadávacieho stromu skoro, ak je zistené, že nemôžu viesť k platnému riešeniu. To výrazne zvyšuje účinnosť.

Bežné aplikácie spätného sledovania:

* Nájdenie všetkých možných permutácií množiny: Generovanie všetkých možných usporiadaní prvkov.

* Riešenie problému N-queens: Umiestnenie N šachové kráľovné na šachovnicu N × N tak, aby sa žiadne dve kráľovné neohrozili navzájom.

* Riešenie hádaniek sudoku: Vyplňovanie prázdnych buniek mriežky sudoku podľa pravidiel hry.

* Generovanie všetkých podmnožiny množiny: Nájdenie všetkých možných kombinácií prvkov zo súboru.

* Grafové priechodné algoritmy (napr. Hĺbkové vyhľadávanie): Preskúmanie všetkých ciest v grafe.

* Problémy s obmedzením: Problémy, keď riešenia musia spĺňať súbor obmedzení.

Príklad (zjednodušené n-queens):

Predstavte si, že umiestnite dve kráľovné na šachovnici 2x2. Algoritmus spätného sledovania by:

1. Skúste umiestniť prvú kráľovnú do ľavého horného rohu.

2. Skúste umiestniť druhú kráľovnú do pravicového rohu. Toto je neplatné (Queens sa navzájom útočia).

3. Backtrack:Odstráňte druhú kráľovnú.

4. Skúste umiestniť druhú kráľovnú do ľavého dolného rohu. To je neplatné.

5. ZadnýTrack:Odstráňte druhú kráľovnú.

6. ZadnýTrack:Odstráňte prvú kráľovnú.

7. Skúste umiestniť prvú kráľovnú do pravicového rohu ... a tak ďalej, kým sa nenájde riešenie (alebo jeho nedostatok).

V podstate je spätné sledovanie výkonnou, ale potenciálne výpočtovo drahou technikou na riešenie problémov, keď je priestor riešenia veľký a je potrebné ho systematicky skúmať. Účinnosť závisí od toho, ako efektívne môže algoritmus prerezať vyhľadávací priestor.

• Predchádzajúca strana: Ako je logaritmický algoritmus spätného styku implementovaný vo vrstve Mac, aby sa predišlo zrážke? 
• Ďalšia strana: Aký je proces získavania údajov?