In deze tutorial leer je wat een backtracking-algoritme is. Ook vindt u een voorbeeld van een backtracking-benadering.
Een backtracking-algoritme is een probleemoplossend algoritme dat een brute force-benadering gebruikt om de gewenste output te vinden.
De Brute Force-aanpak probeert alle mogelijke oplossingen uit en kiest de gewenste / beste oplossingen.
De term backtracking suggereert dat als de huidige oplossing niet geschikt is, je dan teruggaat en andere oplossingen probeert. Bij deze benadering wordt dus recursie gebruikt.
Deze benadering wordt gebruikt om problemen op te lossen die meerdere oplossingen hebben. Wil je een optimale oplossing, dan moet je gaan voor dynamisch programmeren.
State Space Tree
Een ruimtetoestandboom is een boom die alle mogelijke toestanden (oplossing of niet-oplossing) van het probleem weergeeft, van de wortel als een begintoestand tot het blad als een eindtoestand.
State Space Tree
Backtracking-algoritme
Backtrack (x) als x geen oplossing is, retourneer false als x een nieuwe oplossing is, voeg toe aan lijst met oplossingen backtrack (expand x)
Voorbeeld van een backtracking-benadering
Probleem: U wilt alle mogelijke manieren vinden om 2 jongens en 1 meisje op 3 banken te plaatsen. Beperking: meisje mag niet op de middelste bank zitten.
Oplossing: er zijn er in totaal 3! = 6 mogelijkheden. We zullen alle mogelijkheden proberen en de mogelijke oplossingen zoeken. We proberen alle mogelijkheden recursief.
Alle mogelijkheden zijn:
Alle mogelijkheden
De volgende toestandsruimtestructuur toont de mogelijke oplossingen.
Staatsboom met alle oplossingen
Backtracking-algoritme-toepassingen
- Om alle Hamiltoniaanse paden in een grafiek te vinden.
- Om het N Queen-probleem op te lossen.
- Doolhof probleem oplossen.
- Het tourprobleem van de ridder.
