1.4. Организация исчерпывающего перебора

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

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

Наиболее часто для организации перебора планов используется схема, известная как перебор с возвратами.

Перебор планов задачи можно представить как обход дерева перебора, показанного на рис.1.1. Для упрощения рисунка принято, что множество допустимых значений каждой переменнойx_iсостоит из целых чисел от 1 доm_i. Каждая ветвь дерева соответствует плану задачи. Рисунок соответствует задаче с фиксированной размерностьюn. Для задачи с нефиксированной размерностью ветви дерева могут иметь неодинаковую длину.

Рис.1.1

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

Размер дерева перебора может быть очень большим. Пусть для простоты все m_i = m, тогда число всех планов (не обязательно допустимых) равноmⁿ. Приняв довольно скромное значениеm = 10, легко видеть, что приn  3дерево можно обойти даже вручную, при значенияхnот4до7-8с задачей без труда справится компьютер, но уже для значенийnпримерно от11-12и выше трудно рассчитывать на выполнение перебора с использованием любой существующей техники. Действительно, ведь в данном примере увеличение размерности задачи всего лишь на 1 приводит к увеличению времени решения в 10 раз. Это явление, когда комбинаторная задача для малой размерности решается запросто, но при увеличении размерности быстро становится практически неразрешимой, получило названиекомбинаторного взрыва.

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

Запишем общую схему перебора с возвратами в виде программы на псевдокоде. Чтобы не привязываться жестко к какому-либо конкретному виду множеств допустимых значений Ui, введем несколько абстрактных функций доступа к элементам этих множеств. ПустьFirst(U)– первый элемент множестваU,Last(U)– его последний элемент,Next(U, x)– элемент, следующий в множествеUза элементомx, а значениеNext(U, Last(U))равно константеNoValue. МножествоUiбудем записывать в программе какU[i]. Как известно, задачи обхода дерева удобнее всего программировать с помощью рекурсии. Определим рекурсивную процедуруCompleteSearch(k), которая решает комбинаторную задачу с параметромpи функцией ограниченийG(X,p)при условии, что значения переменныхx₁,x₂, …,x_kзафиксированы.

procedure CompleteSearch(k: Integer);

begin

if(первые k переменных составляют полный план) then begin

if G(X,p) then begin

Обработать полученный план X в соответствии

с типом задачи A, B или C;

end;

end

else begin

k:=k+1;

X[k]:=First(U[k]);

repeat

CompleteSearch(k);

X[k]:=Next(U[k],X[k]);

until X[k]=NoValue;

end;

end;

В основной программе вызов рекурсивной процедуры (после выполнения необходимых инициализаций) будет выглядеть так:

CompleteSearch(0);

Поясним фрагменты процедуры, записанные неформально. Условие «первые kпеременных составляют полный план» для задачи с фиксированной размерностьюnозначает простоk = n. Если размерность не фиксирована, то должно быть какое-то правило, позволяющее отличать полный план от частичного. Например, при поиске пути в графе из вершиныAв вершинуBплан полный, если он соединяет точкиAиB.

Обработка полученного плана в соответствии с типом задачи означает следующее:

• Для задачи типа A(поиск): следует прекратить поиск, поскольку найден допустимый план. Это можно запрограммировать, введя булевскую переменную со значением «план найден», проверка которой должна приводить к досрочному выходу из процедуры.

• Для задачи типа B(перечисление): нужно зафиксировать найденный план (например, напечатать его или записать в файл) и продолжить работу.

• Для задачи типа C(оптимизация): следует запоминать наилучшее из найденных значений целевой функции (его обычно называютрекордом) и для каждого полученного допустимого планаXсравнивать значениеF(X)с рекордом, корректируя при необходимости рекорд.