I den här handledningen lär du dig vad en backtracking-algoritm är. Du hittar också ett exempel på en backtracking-metod.
En backtracking-algoritm är en algoritm för problemlösning som använder en brute force-metod för att hitta den önskade utgången.
Brute force-metoden testar alla möjliga lösningar och väljer önskade / bästa lösningar.
Termen backtracking antyder att om den aktuella lösningen inte är lämplig, backtrack och prova andra lösningar. Således används rekursion i detta tillvägagångssätt.
Detta tillvägagångssätt används för att lösa problem som har flera lösningar. Om du vill ha en optimal lösning måste du gå till dynamisk programmering.
Statligt rymdträd
Ett rymdtillståndsträd är ett träd som representerar alla möjliga tillstånd (lösning eller icke-lösning) av problemet från roten som ett initialtillstånd till bladet som ett terminal tillstånd.
Statligt rymdträd
Backtracking-algoritm
Backtrack (x) om x inte är en lösning returnerar false om x är en ny lösning lägg till i listan över lösningar backtrack (expandera x)
Exempel på backtracking
Problem: Du vill hitta alla möjliga sätt att ordna 2 pojkar och 1 flicka på 3 bänkar. Begränsning: Flickan ska inte vara på mittbänken.
Lösning: Det finns totalt 3! = 6 möjligheter. Vi kommer att testa alla möjligheter och få de möjliga lösningarna. Vi testar rekursivt alla möjligheter.
Alla möjligheter är:
Alla möjligheter
Följande tillståndsutrymme visar de möjliga lösningarna.
Statligt träd med alla lösningar
Backtracking-algoritmapplikationer
- För att hitta alla Hamiltonian Paths i en graf.
- För att lösa N Queen-problemet.
- Labyrintlösningsproblem.
- Riddarens turnéproblem.
