Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
BackTracking je výkonná algoritmická technika používaná na riešenie problémov, ktoré zahŕňajú hľadanie riešenia medzi veľkými možnosťami možností. Funguje tým, že postupne buduje kandidátske riešenia a opustí („spätné sledovanie“) kandidáta, len čo zistí, že kandidát nemôže viesť k platnému riešeniu. Predstavte si to ako šikovný, štruktúrovaný spôsob, ako vykonať hĺbkové vyhľadávanie prostredníctvom rozhodovacieho stromu.
Kľúčové nápady:
* Prírastková budova: Spätné sledovanie riešení krok za krokom a pridanie jedného kusu naraz.
* prerezávanie (spokojnosť s obmedzením): V každom kroku skontroluje, či súčasné čiastočné riešenie spĺňa obmedzenia problému. Ak to tak nie je, okamžite sa vzdá tejto cesty a vráti sa k predchádzajúcemu rozhodnutiu. Tento krok prerezávania dramaticky znižuje vyhľadávací priestor.
* rekurzia (často): Backtracking sa často implementuje pomocou rekurzívnych funkcií, kde každé rekurzívne volanie predstavuje výber alebo krok v procese budovania riešenia.
* Strom rozhodnutia: Proces vyhľadávania môžete vizualizovať ako strom rozhodovania, kde každý uzol predstavuje stav (čiastočné riešenie) a hrany predstavujú možnosti alebo akcie. Spätné sledovanie skúma tento strom hĺbkovým spôsobom.
Ako to funguje (všeobecný algoritmus):
1. Začnite s prázdnym (alebo čiastočne inicializovaným) roztokom.
2. Vyberte možnú hodnotu alebo akciu na rozšírenie aktuálneho riešenia.
3. Skontrolujte platnosť:
* Ak je riešenie platné (vyhovuje obmedzeniam):
* Je riešenie kompletné?
* Áno: Vráťte riešenie.
* Nie: Rekurzívne zavolajte funkciu spätného sledovania, aby ste urobili ďalšiu voľbu a pokračovali v budovaní riešenia.
* Ak je riešenie neplatné (porušuje obmedzenia):
* backtrack: Odpustite poslednú voľbu a vyskúšajte inú. Ak boli všetky možnosti vyskúšané na tejto úrovni, vráťte sa na predchádzajúcu úroveň.
4. Žiadne riešenie: Ak boli všetky možné možnosti vyčerpané bez nájdenia platného riešenia, naznačte, že neexistuje žiadne riešenie.
Analogia:Riešenie bludiska
Predstavte si, že riešite bludisko. Začnete pri vchode a vyskúšate rôzne cesty.
* Pohybujte sa vpred: „Výber“ sa posuniete po ceste.
* dobrá cesta (platná): Ak sa zdá, že cesta vedie k východu, pokračujete.
* slepá ulička (neplatná): Ak dosiahnete slepú uličku, „spätne“ vytiahnete kroky na poslednú križovatku (rozhodovací bod) a vyskúšajte inú cestu.
* vyriešené: Ak dosiahnete východ, našli ste riešenie.
Bežné prípady použitia pri programovaní:
* Problémy s obmedzením spokojnosti (CSP): Problémy, v ktorých cieľom je nájsť súbor hodnôt pre premenné, ktoré spĺňajú súbor obmedzení.
* n-queens Problém: Umiestnenie šachových kráľovien na šachovnicu NXN tak, aby sa žiadne dve kráľovné neohrozili navzájom.
* Sudoku Solver: Vyplňovanie mriežky 9x9 s číslicami tak, aby každý riadok, stĺpec a subgrid 3x3 obsahovali všetky číslice od 1 do 9.
* mapa sfarbenie: Priradenie farieb regiónom na mape, takže žiadne dve susedné oblasti majú rovnakú farbu.
* Problémy s kombinatorickou optimalizáciou: Nájdenie najlepšieho riešenia z veľkej sady možných kombinácií.
* Problém s cestovným predajcom (TSP): Nájdenie najkratšej možnej trasy, ktorá navštevuje každé mesto v zozname a vracia sa do východiskového mesta (spätné sledovanie sa môže použiť pre malé inštancie, ale iné algoritmy sú pre väčšie inštancie efektívnejšie).
* Problém s batohom: Určenie najcennejšej podskupiny položiek, ktoré sa zmestia do batohu s obmedzenou hmotnosťou.
* Problém s podmnožinou: Nájdenie podskupiny množiny čísel, ktorá sa sumarizuje na danú cieľovú hodnotu.
* analýza analýzy a syntaxe:
* Gramatiky bez kontextu: Spätné sledovanie sa dá použiť v analyzátoroch na vyskúšanie rôznych odvodení vety, až kým sa nenájde platný strom analýzy.
Príklad:N-queens Problém (zjednodušený)
Zobrazme problém N-queens s n =4 (doska 4x4).
`` `Python
def is_safe (doska, riadok, col):
"" "Kontroluje, či je umiestnenie kráľovnej na palubu [riadok] [col] v bezpečí." "
# Skontrolujte rovnaký stĺpec
pre i v rozsahu (riadok):
Ak doska [i] [col] ==1:
nepravdivý
# Skontrolujte ľavú uhlopriečku horného horného
pre I, J v Zip (rozsah (riadok -1, -1, -1), rozsah (col -1, -1, -1)):
Ak doska [i] [j] ==1:
nepravdivý
# Skontrolujte pravý horný diagonál
pre I, J v Zip (rozsah (riadok -1, -1, -1), rozsah (col + 1, 4)):
Ak doska [i] [j] ==1:
nepravdivý
návrat pravda
def solve_n_queens_util (doska, riadok):
"" RECURSIVE POZOROVANIE PODPORUJÚCE RIEŠENIE PROBLÉMU N-QUEENS. ""
Ak riadok ==4:# Všetky kráľovné sú úspešne umiestnené
návrat pravda
Pre Col v rozsahu (4):
Ak je IS_SAFE (doska, riadok, col):
doska [riadok] [col] =1 # Umiestnite kráľovnú
Ak vyriešte_n_queens_util (doska, riadok + 1):# rekurzívne umiestnite ďalšiu kráľovnú
návrat pravda
doska [riadok] [col] =0 # BackTrack:Odstráňte kráľovnú, ak to nevedie k riešeniu
návrat false # Žiadne riešenie pre tento riadok sa nenašlo
def solve_n_queens ():
"" "Rieši problém N-queens pre n =4." "
doska =[[0 pre _ v rozsahu (4)] pre _ v rozsahu (4)] # Inicializujte prázdnu dosku
Ak nie je vyriešenie_n_queens_util (doska, 0):
tlač („Riešenie neexistuje“)
návrat
# Vytlačte riešenie
pre riadok v palube:
tlač (riadok)
solve_n_queens ()
`` `
Vysvetlenie kódu:
1. `IS_SAFE (doska, riadok, col) Kontroluje, či je bezpečné umiestniť kráľovnú na `Board [Row] [Col]`. Kontroluje konflikty v rovnakom stĺpci a diagonáloch.
2. `solve_n_queens_util (doska, riadok)`:
* Základný prípad: `Ak riadok ==4:` Ak sme dosiahli posledný riadok (všetky umiestnené Queens), máme riešenie, takže vráťte `true`.
* iterácia: Slučka cez každý stĺpec v aktuálnom riadku (`pre COL v rozsahu (4)`).
* Skontrolujte bezpečnosť: `Ak je IS_SAFE (doska, riadok, col):` Ak je bezpečné umiestniť kráľovnú do tohto stĺpca:
* Umiestnite kráľovnú: `doska [riadok] [col] =1`
* RECULSIVE CALL: `Ak solve_n_queens_util (doska, riadok + 1):` rekurzívne sa pokúste umiestniť ďalšiu kráľovnú do nasledujúceho riadku. Ak sa tento rekurzívny hovor vráti „true“, znamená to, že z tohto bodu bolo nájdené riešenie, takže sa vrátime aj „true“.
* backtrack: `doska [riadok] [col] =0` Ak rekurzívny hovor vráti` false` (nebolo nájdené žiadne riešenie), my * vrátime * umiestnenie kráľovnej (backtrack) a vyskúšajte ďalší stĺpec v aktuálnom riadku.
* v tomto riadku žiadne riešenie: „Návrat false` Ak sme vyskúšali všetky stĺpce v aktuálnom riadku bez toho, aby sme našli riešenie, znamená to, že neexistuje platné umiestnenie kráľovien, takže sa vraciame„ false “.
3. `solve_n_queens ()`:
* Inicializuje dosku.
* Hovory `Solve_n_queens_util` na spustenie procesu spätného sledovania.
* Vytlačí riešenie, ak sa nachádza.
Výhody spätného sledovania:
* Systematické vyhľadávanie: Zaručuje nájdenie riešenia, ak existuje (vyčerpávajúce vyhľadávanie).
* prerezávanie: Vyhýbajte sa skúmaniu nepotrebných odvetví vyhľadávacieho priestoru, vďaka čomu je efektívnejšia ako prístup brutálnej sily.
* Koncepčná jednoduchosť: Základná myšlienka je relatívne ľahko zrozumiteľná.
Nevýhody spätného sledovania:
* Čas zložitosť: Môže mať stále vysokú časovú zložitosť (v najhoršom prípade exponenciálne) pre veľké problémy, pretože by to mohlo preskúmať mnoho slepých uličiek.
* Vesmírna zložitosť: Môže vyžadovať významnú pamäť, najmä pri hlbokej rekurzii.
Kľúčové úvahy o aplikácii spätného sledovania:
* obmedzenia: Jasne definujte obmedzenia problému.
* Výber akcie: Opatrne zvážte, ako sa rozhodnúť pri každom kroku.
* Stratégia prerezávania: Vypracujte účinnú stratégiu prerezávania na odstránenie neplatných kandidátov čo najskôr. To je rozhodujúce pre výkon.
* Štruktúra problému: Spätné sledovanie funguje najlepšie pre problémy, kde je možné ľahko vyhodnotiť čiastočné riešenia z hľadiska platnosti.
Stručne povedané, spätné sledovanie je všestranná technika riešenia problémov, ktorú je možné aplikovať na širokú škálu problémov. Systematickým skúmaním možných riešení a prerezávaním vyhľadávacieho priestoru ponúka silný prístup k hľadaniu riešení, ktoré spĺňajú konkrétne obmedzenia. Aj keď v najhoršom prípade môže mať vysokú časovú zložitosť, starostlivé spokojnosť s obmedzeniami a efektívne prerezávanie môžu výrazne zlepšiť jeho výkon.