Backtracking search , backtracking er en generel metode til at finde løsninger på et problem, der kræver en fuldstændig opregning af alle mulige muligheder i et bestemt sæt M. Som regel giver det dig mulighed for at løse problemer, der stiller spørgsmål som: “List alle mulige muligheder . .." , "Hvor mange måder ...", "Er der en måde ...", "Finder et objekt ...", osv.
Udtrykket backtracking blev opfundet i 1950 af den amerikanske matematiker Derrick Henry Lehmer .
Mindre ændringer af tilbagesporingsmetoden relateret til datarepræsentation eller implementeringsfunktioner har andre navne: branch and bound metode , dybde-først søgning , forsøg og fejl metode osv. Backtracking søgning blev opfundet af mange forskere næsten samtidigt og uafhængigt før dens formelle beskrivelse.
Løsningen af problemet ved tilbagesporingsmetoden reduceres til den successive udvidelse af en delvis løsning. Hvis en sådan udvidelse ved næste trin mislykkes, så vender de tilbage til en kortere delløsning og fortsætter søgningen yderligere. Denne algoritme giver dig mulighed for at finde alle løsninger på problemet, hvis de findes. For at fremskynde metoden forsøger de at organisere beregninger på en sådan måde, at de så tidligt som muligt identificerer åbenlyst uegnede muligheder. Det kan ofte reducere tiden til at finde en løsning markant.
Et klassisk eksempel på brugen af en backtracking-algoritme er otte dronninger-problemet . Dens ordlyd er som følger: "Arranger 8 dronninger på et standard 64-cellers skakbræt, så ingen af dem er under angreb af en anden." Først placeres en dronning på brættet, og derefter forsøger de at placere hver næste dronning, så den ikke bliver slået af de allerede etablerede dronninger. Hvis en sådan indstilling ikke kan foretages på næste trin, går de et trin tilbage og prøver at placere den tidligere installerede dronning et andet sted.
Derudover giver tilbagesporingsmetoden dig mulighed for at løse mange andre opregningsproblemer. For eksempel, ved at bruge det kan du få alle undersæt , placeringer , permutationer , kombinationer af et givet sæt M.
Tilbagesporingsmetoden er generisk. Det er ret nemt at designe og programmere algoritmer til løsning af problemer ved hjælp af denne metode. Tiden til at finde en løsning kan dog være meget lang, selv med små dimensioner af problemet (mængden af indledende data), og den er så lang (det kan være år eller endda århundreder), at der ikke kan være tale om praktisk anvendelse . Derfor, når man designer sådanne algoritmer, er det nødvendigt at teoretisk estimere tiden for deres arbejde på specifikke data. Der er også selektionsproblemer, som du kan bygge unikke, "hurtige" algoritmer til, der gør, at du hurtigt kan få en løsning selv med store problemdimensioner. Tilbagesporingsmetoden er ineffektiv i sådanne problemer.
| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||