backtracking-algoritmen opregner et sæt delvise kandidater, der i princippet kunne udfyldes på forskellige måder for at give alle mulige løsninger på det givne problem. Afslutningen udføres trinvist ved hjælp af en række kandidatudvidelsestrin.
konceptuelt er de delvise kandidater repræsenteret som knudepunkter i en træstruktur, det potentielle søgetræ. Hver delvis kandidat er forælder til de kandidater, der adskiller sig fra den med et enkelt forlængelsestrin; træets blade er de delvise kandidater, der ikke kan udvides yderligere.
backtracking-algoritmen krydser dette søgetræ rekursivt, fra roden ned, i dybden-første orden. Ved hver node C kontrollerer algoritmen, om c kan udfyldes til en gyldig løsning. Hvis det ikke kan, springes hele undertræet, der er rodfæstet ved c, over (beskæres). Ellers kontrollerer algoritmen (1), om c i sig selv er en gyldig løsning, og rapporterer den i så fald til brugeren; og (2) rekursivt opregner alle undertræer i c. de to tests og børnene i hver node er defineret af brugerdefinerede procedurer.
derfor er det egentlige søgetræ, der krydses af algoritmen, kun en del af det potentielle træ. De samlede omkostninger ved algoritmen er antallet af noder i det faktiske træ gange omkostningerne ved at opnå og behandle hver node. Denne kendsgerning bør overvejes, når du vælger det potentielle søgetræ og implementerer beskæringstesten.
PseudocodeEdit
for at anvende backtracking til en bestemt klasse af problemer skal man give dataene P for den særlige forekomst af det problem, der skal løses, og seks procedureparametre, rod, afvise, acceptere, først, næste og output. Disse procedurer skal tage forekomstdataene P som en parameter og skal gøre følgende:
- root (P): returner den delvise kandidat ved roden af søgetræet.
- Afvis(P,c): returner kun sandt, hvis den delvise kandidat c ikke er værd at gennemføre.
- acceptere (P, c): retur sandt, hvis c er en løsning af P, og falsk ellers.
- først (P, c): generer den første udvidelse af kandidat c.
- næste(P,s): generer den næste alternative udvidelse af en kandidat efter udvidelsen s.
- output(P, c): brug løsningen c af P,som det er relevant for applikationen.
backtracking-algoritmen reducerer problemet til call backtrack (root (P)), hvor backtrack er følgende rekursive procedure:
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)
brugsovervejelseredit
afvisningsproceduren skal være en boolsk-værdsat funktion, der kun Returnerer SAND, hvis det er sikkert, at ingen mulig udvidelse af c er en gyldig løsning for P. Hvis proceduren ikke kan nå en bestemt konklusion, skal den returnere falsk. Et forkert sandt resultat kan medføre, at bt-proceduren går glip af nogle gyldige løsninger. Proceduren kan antage, at Afvis (P,t) returneres falsk for hver forfader t af c i søgetræet.
på den anden side afhænger effektiviteten af backtracking-algoritmen af afvise returnering sandt for kandidater, der er så tæt på roden som muligt. Hvis Afvis altid returnerer FALSK, vil algoritmen stadig finde alle løsninger, men det svarer til en brute-force-søgning.
acceptproceduren skal returnere sand, hvis c er en komplet og gyldig løsning for problemforekomsten P og falsk ellers. Det kan antage, at den delvise kandidat c og alle dens forfædre i træet har bestået afvisningstesten.
den generelle pseudokode ovenfor antager ikke, at de gyldige løsninger altid er blade af det potentielle søgetræ. Med andre ord indrømmer det muligheden for, at en gyldig løsning til P kan udvides yderligere for at give andre gyldige løsninger.
de første og næste procedurer bruges af backtracking-algoritmen til at opregne børnene i en node c i træet, det vil sige kandidaterne, der adskiller sig fra c med et enkelt udvidelsestrin. Opkaldet først (P,c) skal give det første barn af c, i en eller anden rækkefølge; og opkaldet næste (P, s) skal returnere det næste søskende til node s, i den rækkefølge. Begge funktioner skal returnere en karakteristisk” NULL ” kandidat, hvis det ønskede barn ikke eksisterer.
tilsammen definerer funktionerne root, first og næste sættet af delvise kandidater og det potentielle søgetræ. De bør vælges således, at hver løsning af P forekommer et sted i træet, og ingen delvis kandidat forekommer mere end en gang. Desuden bør de indrømme et effektivt og effektivt afvise prædikat.
tidlig stopvarianterredit
pseudokoden ovenfor kalder output for alle kandidater, der er en løsning på den givne forekomst P. algoritmen kan ændres til at stoppe efter at have fundet den første løsning eller et specificeret antal løsninger; eller efter at have testet et bestemt antal delvise kandidater eller efter at have brugt en given mængde CPU-tid.