Redigerer Tilbakesporing

'''Tilbakesporing''' eller '''bactracking''' er en generell [[algoritme]] for å finne alle (eller noen) løsninger på enkelte [[beregningsproblem]]er, 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.<ref>{{cite book | title = [[The Art of Computer Programming]] | author = Donald E. Knuth | publisher = Addison-Wesley | year = 1968}}</ref><ref>{{cite web | url=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms | year=1999 | last=Gurari | first=Eitan | archive-url=https://web.archive.org/web/20070317015632/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128 | archive-date=17 March 2007 | tittel=Arkivert kopi | besøksdato=15. januar 2007 | arkivurl=https://web.archive.org/web/20070317015632/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html | arkivdato=17. mars 2007 | url-status=død | accessdate=15. januar 2007 | archiveurl=https://web.archive.org/web/20070317015632/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html | archivedate=17. mars 2007 | url-status=dead }} {{Kilde www |url=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html |tittel=Arkivert kopi |besøksdato=2016-08-06 |arkiv-dato=2007-03-17 |arkiv-url=https://web.archive.org/web/20070317015632/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html |url-status=yes }}</ref>

Det klassiske lærebok-eksempelet på dette er [[8-dronningproblemet]], som søker etter alle kombinasjoner av åtte [[dronning (sjakk)|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==
<references/>

{{stubb}}

{{Autoritetsdata}}

[[Kategori:Søkealgoritmer]]