Algoritem za povratno sledenje
Algoritmi za sledenje nazaj so kot strategije za reševanje problemov, ki pomagajo raziskati različne možnosti, da bi našli najboljšo rešitev. Delajo tako, da preizkušajo različne poti in če ena ne deluje, se vrnejo nazaj in poskusijo drugo, dokler ne najdejo prave. To je kot reševanje uganke s preizkušanjem različnih kosov, dokler se popolnoma ne prilegajo.
Sledenje nazaj
Kazalo
- Kaj je algoritem za sledenje nazaj?
- Kako deluje algoritem za sledenje nazaj?
- Primer algoritma za sledenje nazaj
- Kdaj uporabiti algoritem za sledenje nazaj?
- Uporaba algoritma za sledenje nazaj
- Osnove algoritma za sledenje nazaj
- Standardne težave pri algoritmu za sledenje nazaj
- Enostavne težave pri algoritmu za sledenje nazaj
- Srednje težave pri algoritmu za sledenje nazaj
- Težke težave pri algoritmu za sledenje nazaj
Kaj je algoritem za sledenje nazaj?
Sledenje nazaj je algoritemska tehnika za reševanje problemov, ki vključuje postopno iskanje rešitve s poskusi različne možnosti in razveljavitev jih, če vodijo do a slepa ulica .
Običajno se uporablja v situacijah, ko morate raziskati več možnosti za rešitev težave, na primer iskanje poti v labirintu ali reševanje ugank, kot je Sudoku . Ko pride do slepe ulice, se algoritem vrne na prejšnjo točko odločitve in raziskuje drugo pot, dokler ne najde rešitve ali dokler niso izčrpane vse možnosti.
Kako deluje algoritem za sledenje nazaj?
A algoritem za sledenje nazaj deluje tako, da rekurzivno raziskuje vse možne rešitve problema. Začne se z izbiro začetne rešitve, nato pa razišče vse možne razširitve te rešitve. Če razširitev vodi do rešitve, algoritem vrne to rešitev. Če razširitev ne vodi do rešitve, se algoritem vrne k prejšnji rešitvi in poskusi z drugo razširitvijo.
Sledi splošen oris delovanja algoritma za sledenje nazaj:
- Izberite začetno rešitev.
- Raziščite vse možne razširitve trenutne rešitve.
- Če razširitev vodi do rešitve, vrnite to rešitev.
- Če razširitev ne vodi do rešitve, se vrnite na prejšnjo rešitev in poskusite z drugo razširitvijo.
- Ponavljajte korake 2–4, dokler ne raziščete vseh možnih rešitev.
Primer algoritma za sledenje nazaj
primer: Iskanje najkrajše poti skozi labirint
Vnos: Labirint, predstavljen kot 2D niz, kjer 0 predstavlja odprt prostor in 1 predstavlja zid.
Algoritem:
- Začnite na izhodišču.
- Za vsako od štirih možnih smeri (gor, dol, levo, desno) se poskusite premakniti v to smer.
- Če premikanje v tej smeri vodi do končne točke, se vrnite po opravljeni poti.
- Če premikanje v tej smeri ne vodi do končne točke, se vrnite na prejšnji položaj in poskusite v drugi smeri.
- Ponavljajte korake 2–4, dokler ne dosežete končne točke ali dokler ne raziščete vseh možnih poti.
Kdaj uporabiti algoritem za sledenje nazaj?
Algoritme za sledenje nazaj je najbolje uporabiti za reševanje problemov, ki imajo naslednje značilnosti:
- Obstaja več možnih rešitev problema.
- Težavo lahko razdelimo na manjše podprobleme.
- Podprobleme je mogoče rešiti neodvisno.
Uporaba algoritma za sledenje nazaj
Algoritmi za sledenje nazaj se uporabljajo v številnih aplikacijah, vključno z:
- Reševanje ugank (npr. sudoku, križanke)
- Iskanje najkrajše poti skozi labirint
- Težave z razporejanjem
- Težave z dodeljevanjem virov
- Težave z optimizacijo omrežja
Osnove algoritma za sledenje nazaj:
- Razlika med tehniko Backtracking in Branch-N-Bound
- Kakšna je razlika med sledenjem nazaj in rekurzijo?
Standardne težave pri algoritmu za sledenje nazaj:
- Problem viteške turneje
- Podgana v labirintu
- N Queen Problem | Sledenje nazaj-3
- Problem vsote podnabora
- m Težava z barvanjem
- Hamiltonov cikel
- Sudoku | Sledenje nazaj-7
- Magnet Puzzle
- Odstranite neveljavne oklepaje
- Pristop povratnega sledenja za ustvarjanje n-bitnih sivih kod
- Napišite program za izpis vseh permutacij danega niza
Enostavne težave pri algoritmu za sledenje nazaj:
- Sledenje nazaj za iskanje vseh podnaborov
- Preverite, ali je dani niz vsota-niz
- Preštejte vse možne poti med dvema vozliščema
- Poiščite vse različne podmnožice dane množice
- Ugotovite, ali je od vira pot daljša od k
- Natisnite vse poti od danega vira do cilja
- Izpišite vse možne nize, ki jih lahko sestavite s presledki
Srednje težave pri algoritmu za sledenje nazaj:
- Vleka vrvi
- 8 kraljica problem
- Kombinacijska vsota
- Warnsdorffov algoritem za problem Knightovega potovanja
- Poiščite poti od kotne celice do srednje celice v labirintu
- Poiščite največje možno število tako, da izvedete največ K zamenjav
- Podgana v labirintu z dovoljenimi več koraki ali skoki
- N Kraljica v O(n) prostoru
Težke težave pri algoritmu za sledenje nazaj:
- Power Set v leksikografskem vrstnem redu
- Težava z prelomom besed pri uporabi sledenja nazaj
- Razdelitev množice na K podmnožic z enako vsoto
- Najdaljša možna pot v matrici z ovirami
- Poiščite najkrajšo varno pot na poti z minami
- Natisnite vse palindromske particije niza
- Tiskanje vseh rešitev v problemu N-Queen
- Izpišite vsa najdaljša skupna podzaporedja v leksikografskem vrstnem redu
Hitre povezave :
- Naučite se podatkovne strukture in algoritmov | Vadnica DSA
- 20 najboljših vprašanj za intervju o algoritmu za sledenje nazaj
- »Videoposnetki« o sledenju nazaj
