Innholdsfortegnelse:
Definisjon - Hva betyr backtracking?
Backtracking er en algoritme for å fange opp noen eller alle løsninger på gitte beregningsproblemer, spesielt for problemer med begrensningstilfredshet. Algoritmen kan bare brukes til problemer som kan akseptere begrepet "delvis kandidatløsning" og tillater en rask test for å se om kandidatløsningen kan være en komplett løsning. Backtracking anses som en viktig teknikk for å løse problemer og gåter med begrensninger. Det regnes også som en flott teknikk for analysering og danner også grunnlaget for mange logiske programmeringsspråk.
Techopedia forklarer Backtracking
Backtracking hjelper deg med å løse et overordnet problem ved å finne en løsning på det første delproblemet og deretter rekursivt forsøke å løse andre delproblemer basert på løsningen av det første problemet. Hvis det nåværende problemet ikke kan løses, spores trinnet tilbake og den neste mulige løsningen brukes på tidligere trinn, og fortsetter deretter videre. En av de viktigste tingene i backtracking er rekursjon. Det blir også betraktet som en metode for uttømmende søk ved bruk av kløft og erobring. En backtracking-algoritme slutter når det ikke er flere løsninger på det første delproblemet.
Backtracking er en algoritme som kan bidra til å oppnå implementering av nondeterminisme. Det tar et første dybdesøk i et gitt utgaverom. Det brukes mest i logiske programmeringsspråk som Prolog. Uansett hvor backtracking kan brukes, er det raskere enn brute force-teknikken, ettersom det eliminerer et stort antall kandidater med en enkelt test.
