Бектрекинг

Бектрекинг (енгл. Backtracking) алгоритам или метод обрнуте претраге предстаља приступ грубе силе у тражењу решења где се испробавају све могуће комбинације. Постепено се граде кандидати за решење а одбацују се сви кандидати за које се испостави да не воде до тачног решења. Због сложености неких проблема, алгоритам се често споро извршава па се користе алгоритми пролагођенији за дати проблем, осим ако за проблем постоји добра хеуристика (интуитивнан начин налажења који често даје само приближно решење). Алгоритам пролазећи кроз све могуће ситуације даје прво решење, сва могућа решења, па и самим тим и оптимално решење.

Литература

• Brassard, Gilles; Bratley, Paul (1995). Fundamentals of Algorithmics. Prentice-Hall. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald R.; Stein, Cliff (1990). Introduction to Algorithms. McGraw-Hill. 
• Gurari, Eitan (1999). „Backtracking algorithms“. CIS 680: DATA STRUCTURES. 
• Knuth, Donald E. (1968). The Art of Computer Programming. Addison-Wesley. 

Спољашње везе

• HBmeyer.de, Interactive animation of a backtracking algorithm
• Sample Java Code, Sample code for backtracking of 8 Queens problem.