5.6.1 Введение

Существует класс алгоритмов под на- званием backtracking algorithms, что в переводе значит «алгорит- мы с откатом назад». Как прави- ло, такие алгоритмы строятся на основе рекурсии. Эти алгоритмы отличаются тем, что ищут реше- ние методом проб и ошибок, пе- ребирая все или почти все вари- анты. Алгоритмы с возвратом можно назвать «лобовыми»; есть намного более продвинутые классы алгоритмов (ди- намическое программирование, «разделяй и властвуй», жадные алгоритмы). Т.е. когда приходится иметь дело с задачей поиска оптимального решения, когда невозможно применить ни один из известных методов, способных отыскать оптимальный вариант решения, и остается прибегнуть к последнему средству – полному перебору.

Такая ситуация возникает в следующих случаях:

• Поиск оптимума с полным перебором всех вариантов;

• Поиск любого решения с выходом при его отыскании;

• Поиск оптимального решения с оптимизацией полного перебора (отсечением вариантов, которые заведомо хуже найденного до этого момента оптимального ре- шения).