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
- ^ 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.
Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.
