Snoeien om de tijdslimiet te halen

Onbewerkt terugzoeken kan veel te veel vertakkingen onderzoeken en de tijdslimiet overschrijden. Snoeien verwijdert hopeloze vertakkingen vroeg, zodat je snel blijft. ✂️

Snoeien betekent dat je een vertakking stopt zodra je kunt bewijzen dat die geen geldige of betere oplossing kan opleveren. Je onderzoekt die vertakking dan helemaal niet meer.

Als de huidige gedeeltelijke keuze al een regel overtreedt, keer je onmiddellijk terug. Deze haalbaarheidscontrole voorkomt dat je voortbouwt op een ongeldige toestand.

Houd de beste tot nu toe gevonden oplossing bij. Als het best mogelijke resultaat van een vertakking slechter is, snoei je die weg. Dit is een bovengrens voor de vertakking.

Hier stopt een bovengrens de vertakking wanneer zelfs de optimistische schatting de huidige beste oplossing niet kan verbeteren.

Als je eerst de meest veelbelovende optie probeert, vind je sneller een goed antwoord. Daardoor wordt de bovengrens hoger en kun je later meer vertakkingen snoeien.

Beperk na een keuze wat latere stappen nog kunnen doen. Onmogelijke opties vooraf verwijderen heet propagatie van beperkingen en verkleint de boom.

Als twee vertakkingen elkaars spiegelbeeld zijn, onderzoek je er maar één. Symmetrie doorbreken kan het werk halveren of nog verder verkleinen, zonder oplossingen te verliezen.

Als dezelfde gedeeltelijke toestand opnieuw voorkomt, sla je het resultaat op. Memoïsering verandert herhaalde deelbomen in één snelle opzoeking.

Controleer je snoeivoorwaarde vóór de recursieve aanroep, niet erna. Vroeg snoeien voorkomt het verspilde werk van het uitbreiden van een gedoemde vertakking.

Controleer altijd of het aantal vertakkingen in het slechtste geval past bij de randvoorwaarden. Als het te groot is, heb je sterker snoeien of een nieuwe aanpak nodig.

Je hebt geleerd hoe je kunt snoeien met haalbaarheids- en bovengrenscontroles, een slimme volgorde, het doorbreken van symmetrie en memoïsering om binnen de tijdslimiet te blijven. 🎯