Backtracking

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Depthfirst.png

Backtracking is een methode die gebruikt wordt bij zoekproblemen in de informatica. Backtracking is handiger dan de brute kracht 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.

Toepassingen[bewerken]

Backtracking wordt voornamelijk veel gebruikt bij het evalueren van reguliere expressies. Bepaalde programmeertalen, zoals Prolog, steunen volledig op dit principe. Backtracking wordt ook gebruikt in het diff-algoritme waarmee het verschil tussen twee teksten of bestanden kan worden bepaald.

Een ander algoritme dat gebruik maakt van backtracking is het DPLL-algoritme, voor het vervullen van een logische formule, waarbij gebacktrackt kan worden op de keuze van de literal die gekozen is om waar te maken.

Zie ook[bewerken]

Literatuur[bewerken]

  • Gilles Brassard, Paul Bratley, Fundamentals of Algorithmics, Prentice-Hall, 1995

Externe links[bewerken]