I denne opplæringen lærer du hva en backtracking-algoritme er. Du vil også finne et eksempel på en backtracking-tilnærming.
En backtracking-algoritme er en problemløsende algoritme som bruker en brute force-tilnærming for å finne ønsket utgang.
Brute force-tilnærmingen prøver ut alle mulige løsninger og velger de beste / beste løsningene.
Begrepet backtracking antyder at hvis den nåværende løsningen ikke er egnet, så backtrack og prøv andre løsninger. Dermed brukes rekursjon i denne tilnærmingen.
Denne tilnærmingen brukes til å løse problemer som har flere løsninger. Hvis du vil ha en optimal løsning, må du gå for dynamisk programmering.
State Space Tree
Et romstatstil er et tre som representerer alle mulige tilstander (løsning eller ikke-oppløsning) av problemet fra roten som en opprinnelig tilstand til bladet som en terminal tilstand.
State Space Tree
Backtracking algoritme
Backtrack (x) hvis x ikke er en løsning returner false hvis x er en ny løsning, legg til i listen over løsninger backtrack (utvid x)
Eksempel Backtracking-tilnærming
Problem: Du vil finne alle mulige måter å ordne 2 gutter og 1 jente på 3 benker. Begrensning: Jente skal ikke være på midtbenken.
Løsning: Det er totalt 3! = 6 muligheter. Vi vil prøve alle mulighetene og få mulige løsninger. Vi prøver rekursivt alle mulighetene.
Alle mulighetene er:
Alle mulighetene
Følgende statlige romtrær viser mulige løsninger.
Statlig tre med alle løsningene
Backtracking-algoritmeapplikasjoner
- For å finne alle Hamiltonian Paths til stede i en graf.
- For å løse N Queen-problemet.
- Labyrintløsningsproblem.
- Ridderens turproblem.
