Backtracking
Backtracking is een methode die in de informatica in zoekalgoritmen wordt gebruikt. Backtracking is handiger dan de brute force-methode, omdat het met backtracking niet nodig is alle oplossingen te onderzoeken. De wiskundige Derrick Henry Lehmer noemde de methode omstreeks 1950 voor het eerst backtracking.
Bij zoekproblemen moet er tussen een heel aantal plausibele mogelijkheden een oplossing worden geselecteerd. 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, maar ook de oplossingsmethode als geheel, het algoritme, wordt backtracking genoemd. Na het maken van een nieuwe keuze gaat het algoritme verder tot het opnieuw moet terugkeren of een goede oplossing vindt.
Backtracking kan eventueel op een recursieve manier worden geprogrammeerd.
Backtracking wordt vooral veel bij het evalueren van reguliere expressies gebruikt. Bepaalde programmeertalen, zoals Prolog, steunen volledig op dit principe. Een algoritme dat gebruikmaakt van backtracking is het DPLL-algoritme.
Literatuur[bewerken | brontekst bewerken]
- G Brassard en P Bratley. Fundamentals of Algorithmics, 1995. ISBN 978-0133350685
Websites[bewerken | brontekst bewerken]
- (en) Backtracking. spel