backtracking-algoritmen räknar upp en uppsättning partiella kandidater som i princip kan slutföras på olika sätt för att ge alla möjliga lösningar på det givna problemet. Slutförandet görs stegvis genom en sekvens av kandidatförlängningssteg.
konceptuellt representeras de partiella kandidaterna som noderna i en trädstruktur, det potentiella sökträdet. Varje delkandidat är förälder till kandidaterna som skiljer sig från det med ett enda förlängningssteg; trädets löv är de partiella kandidaterna som inte kan förlängas ytterligare.
bakåtspårningsalgoritmen korsar detta sökträd rekursivt, från roten ner, i djup-första ordningen. Vid varje nod C kontrollerar algoritmen om c kan slutföras till en giltig lösning. Om det inte kan hoppas hela underträdet rotat vid c (beskärs). Annars kontrollerar algoritmen (1) om c själv är en giltig lösning och rapporterar i så fall den till användaren; och (2) räknar upp alla underträd av c. de två testerna och barnen i varje nod definieras av användargivna procedurer.
därför är det faktiska sökträdet som korsas av algoritmen bara en del av det potentiella trädet. Den totala kostnaden för algoritmen är antalet noder i det faktiska trädet gånger kostnaden för att erhålla och bearbeta varje nod. Detta faktum bör beaktas när man väljer det potentiella sökträdet och genomför beskärningstestet.
PseudocodeEdit
för att kunna tillämpa backtracking på en specifik klass av problem måste man tillhandahålla data P för den specifika förekomsten av problemet som ska lösas och sex procedurparametrar, rot, avvisa, acceptera, först, nästa och utgång. Dessa procedurer bör ta instansdata P som en parameter och bör göra följande:
- root (P): returnera den partiella kandidaten vid roten av sökträdet.
- avvisa(P,c): returnera true endast om den partiella kandidaten c inte är värd att slutföra.
- Acceptera (P, c): returnera true om c är en lösning av P, och false annars.
- första(P,c): generera den första förlängningen av kandidat c.
- nästa(P,s): generera nästa alternativa förlängning av en kandidat, efter förlängningen s.
- utgång(P,c): använd lösningen c av P, beroende på applikationen.
backtracking-algoritmen reducerar problemet till anropets backtrack(root (P)), där backtrack är följande rekursiva procedur:
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)
usage considerationsEdit
reject-proceduren bör vara en boolesk värderad funktion som returnerar true endast om det är säkert att ingen möjlig förlängning av c är en giltig lösning för P. om proceduren inte kan nå en bestämd slutsats bör den returnera false. Ett felaktigt sant resultat kan leda till att BT-proceduren missar några giltiga lösningar. Förfarandet kan anta att avvisa (P,t) returnerade falskt för varje förfader t till c i sökträdet.
å andra sidan beror effektiviteten i backtracking-algoritmen på reject returning true för kandidater som är så nära roten som möjligt. Om reject alltid returnerar false, kommer algoritmen fortfarande att hitta alla lösningar, men det kommer att motsvara en brute-force-sökning.
accept-proceduren ska returnera true om c är en fullständig och giltig lösning för probleminstansen P, och false annars. Det kan antas att den partiella kandidaten c och alla dess förfäder i trädet har klarat avvisningstestet.
den allmänna pseudokoden ovan förutsätter inte att de giltiga lösningarna alltid är löv av det potentiella sökträdet. Med andra ord medger det möjligheten att en giltig lösning för P kan utvidgas ytterligare för att ge andra giltiga lösningar.
de första och nästa procedurerna används av backtracking-algoritmen för att räkna upp barnen i en nod c i trädet, det vill säga kandidaterna som skiljer sig från c med ett enda förlängningssteg. Samtalet först (P,c) bör ge det första barnet av c, i viss ordning; och samtalet nästa (P,s) ska returnera nästa syskon av nod s, i den ordningen. Båda funktionerna ska returnera en distinkt” NULL ” – kandidat, om det begärda barnet inte existerar.
tillsammans definierar funktionerna rot, första och nästa uppsättningen partiella kandidater och det potentiella sökträdet. De bör väljas så att varje lösning av P inträffar någonstans i trädet, och ingen partiell kandidat inträffar mer än en gång. Dessutom bör de erkänna ett effektivt och effektivt avvisa predikat.
tidig stoppvariantsedit
pseudokoden ovan kommer att ringa ut för alla kandidater som är en lösning på den givna instansen P. algoritmen kan modifieras för att stoppa efter att ha hittat den första lösningen, eller ett visst antal lösningar; eller efter att ha testat ett visst antal partiella kandidater, eller efter att ha spenderat en viss mängd CPU-tid.