logo

TechCodeview

Algoritmus spätného sledovania

Algoritmy spätného sledovania sú ako stratégie riešenia problémov, ktoré pomáhajú preskúmať rôzne možnosti na nájdenie najlepšieho riešenia. Pracujú tak, že skúšajú rôzne cesty a ak jedna nefunguje, cúvajú a skúšajú inú, kým nenájdu tú správnu. Je to ako riešiť hádanku skúšaním rôznych kúskov, kým do seba dokonale nezapadnú.

Backtracking

Obsah



Čo je to algoritmus spätného sledovania?

Backtracking je algoritmická technika na riešenie problémov, ktorá zahŕňa postupné hľadanie riešenia pokusom rôzne možnosti a zrušenie ak vedú k a slepá ulica .

Bežne sa používa v situáciách, keď potrebujete preskúmať viacero možností na vyriešenie problému, ako je hľadanie cesty v bludisku alebo riešenie hádaniek ako napr. sudoku . Keď sa dosiahne slepá ulička, algoritmus sa vráti k predchádzajúcemu rozhodovaciemu bodu a preskúma inú cestu, kým sa nenájde riešenie alebo sa nevyčerpajú všetky možnosti.

Ako funguje algoritmus spätného sledovania?

A algoritmus spätného sledovania funguje tak, že rekurzívne skúma všetky možné riešenia problému. Začína výberom počiatočného riešenia a potom skúma všetky možné rozšírenia tohto riešenia. Ak rozšírenie vedie k riešeniu, algoritmus toto riešenie vráti. Ak rozšírenie nevedie k riešeniu, algoritmus sa vráti k predchádzajúcemu riešeniu a vyskúša iné rozšírenie.

Nasleduje všeobecný prehľad toho, ako funguje algoritmus spätného sledovania:

  1. Vyberte počiatočné riešenie.
  2. Preskúmajte všetky možné rozšírenia aktuálneho riešenia.
  3. Ak rozšírenie vedie k riešeniu, vráťte toto riešenie.
  4. Ak rozšírenie nevedie k riešeniu, vráťte sa k predchádzajúcemu riešeniu a skúste iné rozšírenie.
  5. Opakujte kroky 2-4, kým sa nepreskúmajú všetky možné riešenia.

Príklad algoritmu spätného sledovania

Príklad: Hľadanie najkratšej cesty cez bludisko

Vstup: Bludisko reprezentované ako 2D pole, kde 0 predstavuje otvorený priestor a 1 predstavuje stenu.

Algoritmus:

  1. Začnite vo východiskovom bode.
  2. Pre každý zo štyroch možných smerov (hore, dole, doľava, doprava) sa pokúste pohybovať týmto smerom.
  3. Ak pohyb v tomto smere vedie ku koncovému bodu, vráťte sa po prejdenej ceste.
  4. Ak pohyb v tomto smere nevedie ku koncovému bodu, vráťte sa na predchádzajúcu pozíciu a skúste iný smer.
  5. Opakujte kroky 2-4, kým nedosiahnete koncový bod alebo kým nepreskúmate všetky možné cesty.

Kedy použiť algoritmus spätného sledovania?

Algoritmy spätného sledovania sa najlepšie používajú na riešenie problémov, ktoré majú nasledujúce charakteristiky:

  • Existuje viacero možných riešení problému.
  • Problém sa dá rozdeliť na menšie podproblémy.
  • Podproblémy je možné riešiť nezávisle.

Aplikácie algoritmu spätného sledovania

Algoritmy spätného sledovania sa používajú v širokej škále aplikácií vrátane:

  • Riešenie hádaniek (napr. sudoku, krížovky)
  • Hľadanie najkratšej cesty cez bludisko
  • Problémy s plánovaním
  • Problémy s alokáciou zdrojov
  • Problémy s optimalizáciou siete

Základy algoritmu spätného sledovania:

  • Rozdiel medzi technikou Backtracking a Branch-N-Bound
  • Aký je rozdiel medzi Backtrackingom a Rekurziou?

Štandardné problémy s algoritmom spätného sledovania:

  • Problém s rytierskym zájazdom
  • Potkan v bludisku
  • N Queen Problém | Backtracking-3
  • Problém podmnožiny súčtu
  • m Problém s farbením
  • Hamiltonovský cyklus
  • Sudoku | Backtracking-7
  • Magnetické puzzle
  • Odstráňte neplatné zátvorky
  • Spätný prístup na generovanie n-bitových šedých kódov
  • Napíšte program na tlač všetkých permutácií daného reťazca

Jednoduché problémy s algoritmom spätného sledovania:

  • Späť na nájdenie všetkých podmnožín
  • Skontrolujte, či je daný reťazec súčtom
  • Spočítajte všetky možné cesty medzi dvoma vrcholmi
  • Nájdite všetky odlišné podmnožiny danej množiny
  • Zistite, či existuje cesta dlhšia ako k od zdroja
  • Vytlačte všetky cesty z daného zdroja do cieľa
  • Vytlačte všetky možné reťazce, ktoré sa dajú vytvoriť umiestnením medzier

Stredné problémy s algoritmom spätného sledovania:

  • Preťahovanie lanom
  • 8 problém kráľovnej
  • Kombinovaná suma
  • Warnsdorffov algoritmus pre problém Knightovho turné
  • Nájdite cesty z rohovej bunky do strednej bunky v bludisku
  • Nájdite maximálny možný počet vykonaním maximálne K swapov
  • Potkan v bludisku s povolenými viacerými krokmi alebo skokmi
  • N Kráľovná v priestore O(n).

Ťažké problémy s algoritmom spätného sledovania:

  • Power Set v lexikografickom poradí
  • Word Break Problem pomocou Backtracking
  • Rozdelenie množiny na K podmnožiny s rovnakým súčtom
  • Najdlhšia možná trasa v matici s prekážkami
  • Nájdite najkratšiu bezpečnú cestu na ceste s nášľapnými mínami
  • Vytlačte všetky palindromické oddiely reťazca
  • Tlač všetkých riešení v probléme N-Queen
  • Vytlačte všetky najdlhšie spoločné podsekvencie v lexikografickom poradí

Rýchle odkazy:

  • Naučte sa dátovú štruktúru a algoritmy | Príručka DSA
  • 20 najčastejších otázok na pohovor o algoritme spätného sledovania
  • „Videá“ na Backtracking