Tilbakesporing

Tilbakesporing eller bactracking er en generell algoritme for å finne alle (eller noen) løsninger på enkelte beregningsproblemer, deriblant problemer som tilfredsstiller begrensninger, som inkrementelt bygger opp kandidater til løsninger, og som forkaster enhver delvis kandidat c så snart som det oppdages at c ikke kan fullføre en gyldig løsning.

Det klassiske lærebok-eksempelet på dette er 8-dronningproblemet, som søker etter alle kombinasjoner av åtte sjakkdronninger på et standard sjakkbrett slik at ingen dronninger angriper hverandre. Delvise kandidater er kombinasjoner av k dronninger i de første k rekkene av brett, alle i forskjellige rekker og kolonner. Enhver delvis løsning som inneholder to gjensidig angripende dronninger kan forkastes.

Referanser

Søkealgoritmer