Indholdsfortegnelse:
Definition - Hvad betyder backtracking?
Backtracking er en algoritme til at fange nogle eller alle løsninger til givne beregningsproblemer, især til problemer med begrænsningstilfredshed. Algoritmen kan kun bruges til problemer, der kan acceptere begrebet "delvis kandidatløsning" og tillader en hurtig test for at se, om kandidatløsningen kan være en komplet løsning. Backtracking betragtes som en vigtig teknik til at løse problemer og gåder med begrænsningstilfredshed. Det betragtes også som en fantastisk teknik til parsning og danner også grundlaget for mange logiske programmeringssprog.
Techopedia forklarer Backtracking
Backtracking hjælper med at løse et overordnet problem ved at finde en løsning på det første delproblem og derefter rekursivt forsøge at løse andre delproblemer baseret på løsningen af det første problem. Hvis det aktuelle problem ikke kan løses, spores trinet tilbage, og den næste mulige løsning anvendes til tidligere trin og fortsætter derefter videre. Faktisk er en af de vigtigste ting i backtracking rekursion. Det betragtes også som en metode til udtømmende søgning ved hjælp af kløft og erobring. En backtracking-algoritme slutter, når der ikke er flere løsninger til det første underproblem.
Backtracking er en algoritme, der kan hjælpe med at opnå implementering af nondeterminisme. Det tager en dybdegående søgning af et givet problemområde. Det bruges mest i logiske programmeringssprog som Prolog. Hvor som helst backtracking kan anvendes, er det hurtigere end brute force-teknikken, da det eliminerer et stort antal kandidater med en enkelt test.
