backtracking algoritmen nummererer et sett med delvise kandidater som i prinsippet kan fullføres på ulike måter for å gi alle mulige løsninger på det gitte problemet. Fullførelsen gjøres trinnvis, ved en sekvens av kandidatutvidelsestrinn.
Konseptuelt er de delvise kandidatene representert som noder av en trestruktur, det potensielle søketreet. Hver partiell kandidat er forelder til kandidatene som avviger fra det ved et enkelt forlengelsestrinn; bladene på treet er de delvise kandidatene som ikke kan utvides lenger.
backtracking algoritmen krysser dette søketreet rekursivt, fra roten ned, i dybde-første rekkefølge. Ved hver node c kontrollerer algoritmen om c kan fullføres til en gyldig løsning. Hvis det ikke kan, blir hele undertreet rotfestet ved c hoppet over (beskåret). Ellers sjekker algoritmen (1) om c selv er en gyldig løsning, og i så fall rapporterer den til brukeren; og (2) rekursivt oppregner alle undertrær av c. de to testene og barna til hver node er definert av brukergitte prosedyrer.
derfor er det faktiske søketreet som krysses av algoritmen bare en del av det potensielle treet. Den totale kostnaden for algoritmen er antall noder av det faktiske treet ganger kostnaden for å skaffe og behandle hver node. Dette faktum bør vurderes når du velger det potensielle søketreet og implementerer beskjæringstesten.
PseudocodeEdit
for å kunne bruke backtracking til en bestemt klasse av problemer, må man gi dataene P For den spesielle forekomsten av problemet som skal løses, og seks prosessuelle parametere, root, reject, accept, first, next og output. Disse prosedyrene bør ta forekomstdataene P Som en parameter og bør gjøre følgende:
- root (P): returner den delvise kandidaten ved roten av søketreet.
- avvis (P,c): returner sant bare hvis den delvise kandidaten c ikke er verdt å fullføre.
- godta (P, c): returner sant hvis c er en løsning Av P, og falsk ellers.
- først (P,c): generer den første utvidelsen av kandidat c.
- neste (P, s): generer den neste alternative utvidelsen av en kandidat, etter utvidelsen s.
- utdata(P,c): bruk løsningen c Av P, som passer til søknaden.
backtracking algoritmen reduserer problemet til call backtrack (root(p)), der backtrack er følgende rekursive prosedyre:
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)
brukerbetraktningrediger
avvisningsprosedyren skal være en boolsk funksjon som returnerer sann bare hvis Det er sikkert at ingen mulig forlengelse av c er en gyldig løsning For P. hvis prosedyren ikke kan komme til en bestemt konklusjon, bør den returnere false. Et feil sant resultat kan føre til at bt-prosedyren går glipp av noen gyldige løsninger. Prosedyren kan anta at reject (P,t) returnerte false for hver stamfar t av c i søketreet.
på den annen side er effektiviteten til backtracking algoritmen avhengig av å avvise retur sant for kandidater som er så nær roten som mulig. Hvis avvis alltid returnerer false, vil algoritmen fortsatt finne alle løsninger, men det vil tilsvare et brute-force-søk.
godta-prosedyren skal returnere sant hvis c er en komplett og gyldig løsning For problemforekomsten P, og falsk ellers. Det kan anta at den delvise kandidaten c og alle dens forfedre i treet har bestått avvisningstesten.
den generelle pseudokoden ovenfor antar ikke at de gyldige løsningene alltid er blader av det potensielle søketreet. Med andre ord innrømmer det muligheten for at en gyldig løsning For P kan utvides ytterligere for å gi andre gyldige løsninger.
de første og neste prosedyrene brukes av backtracking-algoritmen for å oppregne barna til en node c i treet, det vil si kandidatene som avviger fra c ved et enkelt utvidelsestrinn. Anropet først (P,c) skal gi det første barnet av c, i noen rekkefølge; og samtalen neste (P,s) skal returnere neste søsken av node s, i den rekkefølgen. Begge funksjonene skal returnere en særegen» NULL » kandidat, hvis det forespurte barnet ikke eksisterer.
sammen definerer rot -, første-og neste-funksjonene settet med delvise kandidater og det potensielle søketreet. De bør velges slik at Hver løsning Av P forekommer et sted i treet, og ingen delvis kandidat oppstår mer enn en gang. Videre bør de innrømme et effektivt og effektivt avvise predikat.
tidlig stopp variantsEdit
pseudokoden ovenfor vil kalle utdata for alle kandidater som er en løsning på den gitte forekomsten P. algoritmen kan endres for å stoppe etter å ha funnet den første løsningen, eller et spesifisert antall løsninger; eller etter å ha testet et spesifisert antall delkandidater, eller etter å ha brukt en gitt MENGDE CPU-tid.