I denne vejledning lærer du, hvad en backtracking-algoritme er. Du finder også et eksempel på en backtracking-tilgang.
En backtrackingsalgoritme er en algoritme til problemløsning, der bruger en brute force-tilgang til at finde det ønskede output.
Brute force-tilgangen afprøver alle mulige løsninger og vælger de ønskede / bedste løsninger.
Udtrykket backtracking antyder, at hvis den nuværende løsning ikke er egnet, så backtrack og prøv andre løsninger. Således anvendes rekursion i denne tilgang.
Denne tilgang bruges til at løse problemer, der har flere løsninger. Hvis du vil have en optimal løsning, skal du gå til dynamisk programmering.
Statens rumtræ
Et rumtilstandstræ er et træ, der repræsenterer alle de mulige tilstande (løsning eller ikke-opløsning) af problemet fra roden som en indledende tilstand til bladet som en terminal tilstand.
Statens rumtræ
Backtracking algoritme
Backtrack (x) hvis x ikke er en løsning returner false hvis x er en ny løsning tilføj til listen over løsninger backtrack (udvid x)
Eksempel på tilbagesporingsmetode
Problem: Du vil finde alle de mulige måder at arrangere 2 drenge og 1 pige på 3 bænke. Begrænsning: Pige skal ikke være på midterbænken.
Løsning: Der er i alt 3! = 6 muligheder. Vi vil prøve alle mulighederne og få de mulige løsninger. Vi prøver rekursivt alle mulighederne.
Alle muligheder er:
Alle muligheder
Følgende tilstandsrumtræ viser de mulige løsninger.
Stat træ med alle løsninger
Backtracking algoritme applikationer
- For at finde alle Hamiltonian Paths til stede i en graf.
- For at løse N Queen-problemet.
- Labyrint løsning problem.
- Ridderens turproblem.
