Inhoudsopgave:
Definitie - Wat betekent Backtracking?
Backtracking is een algoritme voor het vastleggen van sommige of alle oplossingen voor bepaalde rekenproblemen, met name voor problemen met beperkingen. Het algoritme kan alleen worden gebruikt voor problemen die het concept van een "gedeeltelijke kandidaat-oplossing" kunnen accepteren en maakt een snelle test mogelijk om te zien of de kandidaat-oplossing een complete oplossing kan zijn. Backtracking wordt beschouwd als een belangrijke techniek om problemen met beperkingen en puzzels op te lossen. Het wordt ook beschouwd als een geweldige techniek voor het parseren en vormt ook de basis van veel logische programmeertalen.
Techopedia verklaart Backtracking
Backtracking helpt bij het oplossen van een algemeen probleem door een oplossing te vinden voor het eerste subprobleem en vervolgens recursief te proberen andere subproblemen op te lossen op basis van de oplossing van het eerste probleem. Als het huidige probleem niet kan worden opgelost, wordt de stap teruggezet en wordt de volgende mogelijke oplossing toegepast op eerdere stappen, en gaat vervolgens verder. Een van de belangrijkste dingen bij backtracking is recursie. Het wordt ook beschouwd als een methode voor uitgebreid zoeken met behulp van verdeel en heers. Een backtracking-algoritme eindigt wanneer er geen oplossingen meer zijn voor het eerste subprobleem.
Backtracking is een algoritme dat kan helpen bij de implementatie van niet-determinisme. Het vergt een diepte-eerste zoekopdracht van een gegeven probleemruimte. Het wordt meestal gebruikt in logische programmeertalen zoals Prolog. Overal waar backtracking kan worden toegepast, is het sneller dan de brute force-techniek, omdat het een groot aantal kandidaten elimineert met een enkele test.
