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.[1][2]
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 rediger
- ^ Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.
- ^ Gurari, Eitan (1999). «CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms». Arkivert fra originalen 17. mars 2007. Besøkt 15. januar 2007. «Arkivert kopi». Arkivert fra originalen 17. mars 2007. Besøkt 6. august 2016.