Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky

Domáce Hardware Siete Programovanie Softvér Otázka Systémy

Č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.

Najnovšie články

Copyright © počítačové znalosti Všetky práva vyhradené