terugkeermethoden

Terugkeermethoden is een verzamelnaam voor oplossingsstrategieën die terugkeren naar eerder gemaakte keuzes om verder te zoeken naar geldige oplossingen. De term wordt vooral gebruikt in informatica, wiskunde en operationeel onderzoek, waar problemen bestaan uit een combinatie van variabelen en beperkingen. Het basisidee is om stap voor stap een oplossing op te bouwen en bij conflict of gebrek aan mogelijkheden terug te keren naar de vorige stap om een andere optie te proberen.

De kern van terugkeermethoden is een systematische verkenning van de ruimtelijke toestanden die een oplossing kunnen vormen. Bij elk knooppunt wordt een waarde aan een variabele toegekend en worden de daarbij behorende beperkingen gecontroleerd. Als deze beperkingen worden geschonden, wordt teruggekeerd naar een eerdere beslissing (backtracking) en wordt een andere waarde geprobeerd. Doel is om alle mogelijke combinaties te doorlopen totdat een geldige oplossing is gevonden of alle opties zijn uitgeput.

Om de efficiëntie te verhogen worden diverse technieken toegepast. Forward checking beperkt reeds mogelijke toekomstige keuzes zodra een variabele is toegewezen. Constraint propagation, zoals arc-consistentie (AC-3), probeert consistente waarden voor meerdere variabelen te afdwingen. Geheugen- en tijdsbesparingen worden vaak bevorderd door heuristieken voor variabele- en waardevolgorde, zoals minimum remaining values, degree heuristic en least constraining value. Ook wiskundige methoden zoals branch and bound kunnen worden gebruikt om grote delen van de zoekruimte uit te sluiten.

Toepassingen van terugkeermethoden zijn onder meer het oplossen van puzzels (bijv. Sudoku, N-valen), constraint satisfaction problems (planning en timetabling) en bepaalde combinatorische optimalisatieproblemen. De prestaties hangen sterk af van de structuur van het probleem en de gebruikte heuristieken.