Backtracking

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

Websites

  • (en) Backtracking. spel

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.