Backtracking er en strategi for å finne løsninger på problemer som tilfredsstiller begrensninger. Begrepet "backtrack" ble først laget av den amerikanske matematikeren DH Lehmer på 1950 -tallet .
Problemer som må tilfredsstille visse typer begrensninger er komplette problemer, hvor rekkefølgen på løsningselementene ikke spiller noen rolle. Disse problemene består av et sett (eller en liste) med variabler som hver enkelt må tildeles en verdi underlagt problemets begrensning. Teknikken skaper alle mulige kombinasjoner av elementer for å få en løsning. Dens viktigste fordel er at kombinasjoner i de fleste implementeringer kan unngås ved å sette grensefunksjoner (eller beskjære) og redusere utførelsestiden .
Tilbakesporing er nært knyttet til kombinatorisk søk .
I hovedsak er ideen å finne den best mulige kombinasjonen på et gitt tidspunkt, og det er derfor denne typen algoritmer sies å være et dybdesøk . Under søket, hvis et feil alternativ blir funnet, går søket tilbake til forrige trinn og tar neste alternativ. Når mulighetene er uttømt, returneres forrige valg og neste alternativ (barn [hvis vi mener et tre]) tas. Hvis det ikke finnes andre alternativer, mislykkes søket. På denne måten skapes et implisitt tre, der hver node er en tilstand av løsningen (delløsning ved indre noder eller totalløsning ved bladnoder).
Normalt blir denne typen algoritme vanligvis implementert som en rekursiv prosedyre . I hvert kall til prosedyren tas en variabel og alle mulige verdier tilordnes den, og kaller prosedyren etter tur for hver av de nye tilstandene. Forskjellen med dybdesøk er at bundne funksjoner vanligvis er utformet på en slik måte at noen tilstander ikke genereres hvis de ikke skal føre til noen løsning, eller til en dårligere løsning enn den vi allerede har. Dette sparer minneplass og utførelsestid.
Noen heuristikk brukes ofte for å fremskynde prosessen. Siden variabler kan behandles i hvilken som helst rekkefølge, er det generelt mer effektivt å prøve å være så restriktiv som mulig med de første (det vil si de første med minst mulig verdier). Denne prosessen beskjærer søketreet før avgjørelsen tas og den rekursive subrutinen kalles.
Når du velger hvilken verdi som skal tildeles, utfører mange implementeringer en Forward Checking (FC) for å se hvilken verdi som begrenser færrest mulig antall verdier, på en måte som forutser a) bevaring av en mulig løsning og b) gjør at løsningen som ble funnet ikke er uthevet. begrensninger.
Noen svært sofistikerte implementeringer bruker en grensefunksjon, som undersøker om en løsning kan finnes fra en delløsning. I tillegg sjekkes det om delløsningen som feiler kan øke effektiviteten til algoritmen betydelig. På grunn av bruken av disse bundne funksjonene, er det nødvendig å være veldig grundig i implementeringen slik at de ikke er veldig dyre beregningsmessig sett, siden det mest normale er at de utføres for hver node eller trinn i algoritmen. Det skal bemerkes at effektive grenser opprettes på en lignende måte som heuristiske funksjoner , det vil si ved å lempe på begrensningene for å oppnå større effektivitet.
For å opprettholde den nåværende løsningen med minimale kostnader, opprettholder tilbakesporingsalgoritmer kostnadene for den beste løsningen i en variabel som varierer med hver nye beste løsning som finnes. Derfor, hvis en løsning er dårligere enn den som nettopp ble funnet, vil ikke algoritmen oppdatere løsningen. På denne måten vil den alltid returnere den beste løsningen den har funnet. Og husk, livet er et tilbakespor
Backtracking brukes i implementeringen av programmeringsspråk som Planner Programming Language og Prolog . Den brukes også i kompilatorparsing. Bruken av det i kunstig intelligens har vært svært viktig, og har gitt opphav til nye typer søk som A star .
Denne metoden ser etter en løsning som i backtracking-metoden, men hver løsning har en tilhørende kostnad og løsningen som søkes er en av minimumskostnader kalt optimal. I tillegg til å forgrene en foreldreløsning (gren) til barn, er det et spørsmål om å eliminere de barn hvis etterkommere har en kostnad som overstiger det optimale ønsket ved å begrense kostnadene for etterkommerne til barnet (bundet). Måten å dimensjonere på er en kunst som avhenger av hvert enkelt problem. Bounding reduserer søketiden for den optimale løsningen ved å "beskjære" undertrærne til dyre etterkommere.