Backtracking-algoritmen zijn als probleemoplossende strategieën die verschillende opties helpen verkennen om de beste oplossing te vinden. Ze proberen verschillende paden uit en als de ene niet werkt, gaan ze terug en proberen ze een andere totdat ze de juiste vinden. Het is alsof je een puzzel oplost door verschillende stukjes te testen totdat ze perfect in elkaar passen.
Terugkeren
Inhoudsopgave
- Wat is Backtracking-algoritme?
- Hoe werkt een backtracking-algoritme?
- Voorbeeld van een backtracking-algoritme
- Wanneer moet u een backtracking-algoritme gebruiken?
- Toepassingen van het Backtracking-algoritme
- Basisprincipes van het Backtracking-algoritme
- Standaardproblemen bij het backtracking-algoritme
- Gemakkelijke problemen bij het backtracking-algoritme
- Middelgrote problemen bij het terughalen van het algoritme
- Moeilijke problemen bij het terugdraaien van het algoritme
Wat is Backtracking-algoritme?
Terugkeren is een probleemoplossende algoritmische techniek waarbij stapsgewijs een oplossing wordt gevonden door te proberen verschillende opties En ongedaan maken als ze leiden tot a doodlopend .
Het wordt vaak gebruikt in situaties waarin je meerdere mogelijkheden moet verkennen om een probleem op te lossen, zoals het zoeken naar een pad in een doolhof of het oplossen van puzzels zoals Sudoku . Wanneer een doodlopende weg wordt bereikt, keert het algoritme terug naar het vorige beslissingspunt en verkent een ander pad totdat er een oplossing is gevonden of alle mogelijkheden zijn uitgeput.
Hoe werkt een backtracking-algoritme?
A backtracking-algoritme werkt door recursief alle mogelijke oplossingen voor een probleem te onderzoeken. Het begint met het kiezen van een initiële oplossing en onderzoekt vervolgens alle mogelijke uitbreidingen van die oplossing. Als een uitbreiding tot een oplossing leidt, retourneert het algoritme die oplossing. Als een uitbreiding niet tot een oplossing leidt, keert het algoritme terug naar de vorige oplossing en probeert een andere uitbreiding.
npm schone cache
Het volgende is een algemeen overzicht van hoe een backtracking-algoritme werkt:
constructeur in Java
- Kies een eerste oplossing.
- Ontdek alle mogelijke uitbreidingen van de huidige oplossing.
- Als een uitbreiding tot een oplossing leidt, retourneert u die oplossing.
- Als een uitbreiding niet tot een oplossing leidt, ga dan terug naar de vorige oplossing en probeer een andere uitbreiding.
- Herhaal stap 2-4 totdat alle mogelijke oplossingen zijn onderzocht.
Voorbeeld van een backtracking-algoritme
Voorbeeld: Het vinden van het kortste pad door een doolhof
Invoer: Een doolhof weergegeven als een 2D-array, waar 0 vertegenwoordigt een open ruimte en 1 vertegenwoordigt een muur.
Algoritme:
- Begin bij het startpunt.
- Probeer voor elk van de vier mogelijke richtingen (omhoog, omlaag, links, rechts) in die richting te bewegen.
- Als bewegen in die richting naar het eindpunt leidt, voer dan het gevolgde pad terug.
- Als bewegen in die richting niet naar het eindpunt leidt, ga dan terug naar de vorige positie en probeer een andere richting.
- Herhaal stap 2-4 totdat het eindpunt is bereikt of alle mogelijke paden zijn verkend.
Wanneer moet u een backtracking-algoritme gebruiken?
Backtracking-algoritmen kunnen het beste worden gebruikt om problemen op te lossen die de volgende kenmerken hebben:
- Er zijn meerdere mogelijke oplossingen voor het probleem.
- Het probleem kan worden opgesplitst in kleinere deelproblemen.
- De deelproblemen kunnen zelfstandig worden opgelost.
Toepassingen van het Backtracking-algoritme
Backtracking-algoritmen worden gebruikt in een breed scala aan toepassingen, waaronder:
- Puzzels oplossen (bijvoorbeeld Sudoku, kruiswoordraadsels)
- Het vinden van het kortste pad door een doolhof
- Problemen met plannen
- Problemen met de toewijzing van middelen
- Netwerkoptimalisatieproblemen
Basisprincipes van het backtracking-algoritme:
- Verschil tussen Backtracking en Branch-N-Bound-techniek
- Wat is het verschil tussen Backtracking en Recursie?
Standaardproblemen bij het backtracking-algoritme:
- Het tourprobleem van de ridder
- Rat in een doolhof
- N Koningin Probleem | Terugkeren-3
- Subset Sum-probleem
- m Kleurprobleem
- Hamiltoniaanse cyclus
- Sudoku | Terugkeren-7
- Magneet puzzel
- Verwijder ongeldige haakjes
- Een backtracking-aanpak om n bit Gray Codes te genereren
- Schrijf een programma dat alle permutaties van een gegeven string afdrukt
Gemakkelijke problemen bij het backtracking-algoritme:
- Backtracking om alle subsets te vinden
- Controleer of een gegeven string een somstring is
- Tel alle mogelijke paden tussen twee hoekpunten
- Vind alle afzonderlijke subsets van een bepaalde set
- Zoek of er een pad is met een lengte van meer dan k vanaf een bron
- Druk alle paden af van een bepaalde bron naar een bestemming
- Print alle mogelijke strings die gemaakt kunnen worden door spaties te plaatsen
Middelgrote problemen bij het backtracking-algoritme:
- Touwtrekken
- 8 koningin probleem
- Combinatiesom
- Warnsdorff's algoritme voor het tourprobleem van Knight
- Vind paden van hoekcel naar middelste cel in het doolhof
- Vind het maximale aantal dat mogelijk is door maximaal K-swaps uit te voeren
- Rat in een doolhof met meerdere stappen of sprongen toegestaan
- N Dame in O(n)-veld
Moeilijke problemen bij het backtracking-algoritme:
- Machtsset in lexicografische volgorde
- Woordonderbrekingsprobleem met behulp van Backtracking
- Verdeling van een verzameling in K-deelverzamelingen met gelijke som
- Langst mogelijke route in een matrix met hindernissen
- Vind de kortste veilige route op een pad met landmijnen
- Druk alle palindroompartities van een string af
- Alle oplossingen afdrukken in N-Queen Probleem
- Druk alle langste veel voorkomende subreeksen af in lexicografische volgorde
Snelle links:
- Leer datastructuur en algoritmen | DSA-zelfstudie
- Top 20 interviewvragen over het backtracking-algoritme
- ‘Video’s’ over Backtracking