het backtracking-algoritme somt een reeks gedeeltelijke kandidaten op die in principe op verschillende manieren kunnen worden ingevuld om alle mogelijke oplossingen voor het gegeven probleem te bieden. De voltooiing wordt stapsgewijs gedaan, door een opeenvolging van kandidaat-uitbreidingsstappen.
conceptueel worden de gedeeltelijke kandidaten weergegeven als de knooppunten van een boomstructuur, de potentiële zoekboom. Elke gedeeltelijke kandidaat is de ouder van de kandidaten die van hem verschillen door een enkele uitbreidingsstap; de bladeren van de boom zijn de gedeeltelijke kandidaten die niet verder kunnen worden verlengd.
het backtracking-algoritme doorkruist deze zoekboom recursief, van de root naar beneden, in depth-first order. Bij elk knooppunt c controleert het algoritme of c kan worden voltooid tot een geldige oplossing. Als dat niet lukt, wordt de hele subboom die op c is geworteld overgeslagen (gesnoeid). Anders controleert het algoritme (1) of c zelf een geldige oplossing is en rapporteert het aan de gebruiker; en (2) somt recursief alle subbomen van c op. de twee tests en de kinderen van elk knooppunt worden gedefinieerd door door de gebruiker gegeven procedures.
daarom is de werkelijke zoekboom die door het algoritme wordt doorkruist slechts een deel van de potentiële boom. De totale kosten van het algoritme is het aantal knooppunten van de werkelijke boom keer de kosten van het verkrijgen en verwerken van elk knooppunt. Met dit feit moet rekening worden gehouden bij het kiezen van de potentiële zoekboom en het uitvoeren van de snoeitest.
PseudocodeEdit
om backtracking toe te passen op een specifieke klasse van problemen, moet men de gegevens P voor de specifieke instantie van het probleem dat moet worden opgelost, en zes procedurele parameters, root, reject, accept, first, next, en output. Deze procedures moeten de instance data P als parameter nemen en het volgende doen:
- root (P): retourneer de gedeeltelijke kandidaat aan de root van de zoekboom.
- reject (P, c): geef alleen waar terug als de gedeeltelijke kandidaat c niet de moeite waard is om in te vullen.
- accepteren(P,c): geef true terug als c een oplossing van P is, en false anders.
- first (P, c): Genereer de eerste extensie van kandidaat c.
- next(P,s): Genereer de volgende alternatieve extensie van een kandidaat, na de extensie s.
- output(P,c): Gebruik de oplossing c van P, naargelang de toepassing.
het backtracking-algoritme reduceert het probleem tot de backtrack aanroep (root (P)), waarbij backtrack de volgende recursieve procedure is:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
use considerationsEdit
de reject procedure zou een Booleaanse-waarde functie moeten zijn die alleen true retourneert als het zeker is dat geen mogelijke uitbreiding van c een geldige oplossing is voor P. als de procedure geen definitieve conclusie kan bereiken, zou ze false moeten retourneren. Een onjuist waar resultaat kan ertoe leiden dat de BT-procedure een aantal geldige oplossingen mist. De procedure kan aannemen dat reject(P,t) false retourneerde voor elke voorouder t van c in de zoekboom.
aan de andere kant hangt de efficiëntie van het backtracking-algoritme af van de ‘reject return true’ voor kandidaten die zo dicht mogelijk bij de root zitten. Als reject altijd false retourneert, zal het algoritme nog steeds alle oplossingen vinden, maar het zal gelijk zijn aan een brute-force zoekopdracht.
de accept procedure moet true retourneren als c een complete en geldige oplossing is voor de probleem instantie P, en false anders. Het kan aannemen dat de gedeeltelijke kandidaat c en al zijn voorouders in de boom de afwijzingstest hebben doorstaan.
de Algemene pseudocode hierboven gaat er niet van uit dat de geldige oplossingen altijd bladeren van de potentiële zoekboom zijn. Met andere woorden, het geeft de mogelijkheid toe dat een geldige oplossing voor P verder kan worden uitgebreid om andere geldige oplossingen op te leveren.
de eerste en volgende procedures worden gebruikt door het backtracking-algoritme om de kinderen van een knooppunt c van de boom op te sommen, dat wil zeggen de kandidaten die van c verschillen door een enkele uitbreidingsstap. De call first (P, c) moet het eerste kind van c opleveren, in een bepaalde volgorde; en de aanroep volgende (P, s) moet de volgende broer of zus van knooppunt s terug te keren, in die volgorde. Beide functies moeten een onderscheidende “NULL” kandidaat retourneren, als het gevraagde kind niet bestaat.
samen definiëren de functies root, first en next de set van partiële kandidaten en de potentiële zoekboom. Zij zouden zo moeten worden gekozen dat elke oplossing van P ergens in de boom voorkomt, en geen gedeeltelijke kandidaat meer dan eens voorkomt. Bovendien moeten zij een efficiënt en effectief afwijzingsvoorschrift erkennen.
vroeg stoppen variantsEdit
de pseudo-code hierboven roept uitvoer aan voor alle kandidaten die een oplossing zijn voor de gegeven instantie P. Het algoritme kan worden gewijzigd om te stoppen na het vinden van de eerste oplossing, of een bepaald aantal oplossingen; of na het testen van een bepaald aantal partiële kandidaten, of na het Besteden van een bepaalde hoeveelheid CPU-tijd.