Метод перебора с возвратом (backtracking) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых любят демонстрировать этот подход, являются обход конем доски N×N [Вирт 89, гл.3], расстановка N ферзей на доске N×N [Шень 95, гл.3; Окулов 98, п.2.1.2] и задача коммивояжера [Кристофидес 78, п.10.6]. Решаемые методом перебора с возвратом задачи, как правило, принадлежат одному из трех классов - требуется либо найти произвольное из решений, либо перечислить все возможные решения, либо найти решение, оптимальное по заданному критерию

Основной принцип, на котором базируется рассматриваемый метод, состоит в следующем. Рассмотрим, для определенности, задачу P₀ оптимизационного типа. Разобьем задачу P₀ на некоторое число подзадач P₁,...,P_k, представляющих в целом всю задачу P₀. Далее пытаемся по очереди разрешить каждую из этих подзадач. Под термином "разрешить" мы подразумеваем:

• либо показать, что подзадача P_i не является допустимой;

• либо показать, что решать задачу Р_i не имеет смысла, поскольку значение оптимального решения для P_i, заведомо хуже, чем для наилучшего из ранее найденных решений;

• либо определить оптимальное решение задачи Р_i, если эта задача настолько проста, что оптимальное решение находится очевидным образом;

• либо разбить задачу Р_i на подзадачи Р_i1, ...,Р_is и рекурсивно перейти к рассмотрению задачи Р_i1

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

Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P₁ исходной задачи P₀, в то время как оптимальное решение Р₀ находится в другой подзадаче Р_i. В этом случае полезно использовать метод локальной оптимизации [Романовский 99, п.7.12]. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются "близкие" к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное (см., например, задачу 2.1). Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга

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

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

Использовать стандартную процедуру GetTime в данном случае нерационально, т.к. она осуществляет преобразование времени из внутреннего формата в общепринятый и за счет этого работает долго. Гораздо эффективнее напрямую обращаться к 4-байтному числу, расположенному по адресу $0000:$046С, в котором хранится текущее значение таймера. Это значение увеличивается на единицу каждые 55 миллисекунд, то есть примерно 18.2 раза в секунду. Для реализации отсечения по времени заводится переменная с непосредственным указанием адреса и переменная, в которой хранится время окончания работы:

Var Timer : Longint Absolute $0:$046C;
      BreakTime : Longint;

В начале работы программы снимается текущее показание таймера и вычисляется время, когда программа должна завершить свою работу:

BreakTime:=Timer+Round(T/55*1000)-5;

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

If Timer>=BreakTime Then
    выдать наилучшее из найденных решений и завершить работу;