Backtracking
Van Wikipedia
Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. De term werd rond 1950 voor het eerst gebruikt door de wiskundige Derrick Henry Lehmer.
Bij zoekproblemen is het zo dat er een oplossing geselecteerd moet 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 precies backtracking. Ook de oplossingsmethode als geheel (het algoritme) wordt backtracking genoemd. Na het maken van een nieuwe keuze gaat het algoritme verder tot het ofwel opnieuw moet terugkeren, ofwel een goede oplossing vindt.
[bewerk] Toepassingen
Backtracking wordt voornamelijk veel gebruikt bij het evalueren van reguliere expressies. Bepaalde programmeertalen, zoals Prolog, steunen volledig op dit principe.
