Tilbakesporing

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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 | rediger kilde]

  1. ^ Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley. 
  2. ^ Gurari, Eitan (1999). «CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms». Arkivert fra originalen 17. mars 2007. Besøkt 15. januar 2007. 
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.