backtracking

Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. Backtracking is handiger dan de brute force-methode, omdat niet alle oplossingen bekeken hoeven te worden. De term werd rond 1950 voor het eerst gebruikt door de wiskundige Derrick Henry Lehmer. Bij zoekproblemen moet er een oplossing geselecteerd worden uit een heel aantal plausibele mogelijkheden. Tijdens de oplossing van het probleem moet men keuzes maken. Als achteraf blijkt dat een genomen keuze niet leidt tot een oplossing, of niet tot een optimale oplossing, dan moet men terugkeren naar het keuzemoment. Dit terugkeren noemt men backtracking. Ook de oplossingsmethode als geheel (het algoritme) wordt backtracking genoemd.Na het maken van een nieuwe keuze gaat het algoritme verder tot opnieuw moet terugkeren, of een goede oplossing vindt.