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.  Arkivert 17. mars 2007 hos Wayback Machine.
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.