Организация исчерпывающего перебора
В отличие от большинства задач «непрерывной» математики, где первым шагом в анализе задачи должно быть исследование условий существования решения, для комбинаторных задач решение всегда существует, поскольку множество планов конечно. Полный перебор всех планов позволяет наверняка решить задачу. Другое дело, что для этого может понадобиться неприемлемо большое время. Только поэтому и существует разветвленная теория комбинаторных задач, основная цель которой – разработка и анализ эффективных, т.е. достаточно быстрых алгоритмов для различных частных типов комбинаторных задач. Тем не менее перебор планов остается наиболее универсальным методом решения. Если он не всегда пригоден для практических целей, то очень полезен для исследования задач, для сравнения с приближенными алгоритмами и т.п.
Как правило, удается избежать рассмотрения всех возможных планов задачи, отсечь некоторые множества планов как явно бесперспективные для поиска решения. Мы будем говорить, что конкретный алгоритм выполняет исчерпывающий перебор, если можно гарантировать, что не пропущен ни один план, который мог бы повлиять на результат.
Наиболее часто для организации перебора планов используется схема, известная как перебор с возвратами.
Перебор планов задачи можно представить как обход дерева перебора, показанного на рис.1.1. Для упрощения рисунка принято, что множество допустимых значений каждой переменной xi состоит из целых чисел от 1 до mi. Каждая ветвь дерева соответствует плану задачи. Рисунок соответствует задаче с фиксированной размерностью n. Для задачи с нефиксированной размерностью ветви дерева могут иметь неодинаковую длину.
Рис.1.1
Для задачи поиска обход дерева можно прекратить, как только найдена ветвь, представляющая допустимый план задачи. Для задач перечисления и оптимизации перебор следует продолжать до получения всех допустимых планов.
Размер дерева перебора может быть очень большим. Пусть для простоты все mi = m, тогда число всех планов (не обязательно допустимых) равно mn. Приняв довольно скромное значение 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) при условии, что значения переменных x1, x2, …, xk зафиксированы.
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) с рекордом, корректируя при необходимости рекорд.
Сокращение перебора
Следует отметить, что исчерпывающий перебор далеко не всегда означает перебор буквально всех планов задачи. В большинстве конкретных задач удается сократить перебор, оставив без рассмотрения некоторые множества планов. Перечислим некоторые случаи, когда это удается сделать.
· Иногда уже после выбора нескольких первых значений xiвыясняется, что на данной ветви дерева перебора не может быть допустимых планов. Например, коммивояжер раньше времени вернулся в исходный город, рюкзак переполнен первым же товаром, при раскраске графа две смежные вершины оказались одного цвета. Во всех этих случаях нет смысла достраивать план до полного, лучше уже не будет.
· Похожая ситуация иногда возникает в задачах оптимизации. Каждый построенный план задачи должен сравниваться с текущим рекордом. Иногда удается, не дожидаясь построения полного плана, сравнить с рекордом и на основании этого сравнения отвергнуть частичный план. Например, для задачи о коммивояжере текущий рекорд составляет 500 единиц длины, а очередной строящийся план начинается с путей длиной 200 и 350 единиц. Нет смысла достраивать такой план, потому что короче он уже не станет.
· В задаче поиска иногда возникает ситуация, когда удачный выбор нескольких первых переменных гарантирует, что план будет допустим при любых значениях оставшихся переменных. Например, в задаче о тождественной истинности ДНФ может оказаться, что первое же значение x1 = 0 обращает в нуль все элементарные конъюнкции.
· В задаче оптимизации иногда удается построить допустимый план, относительно которого можно с уверенностью сказать, что он оптимален, потому что лучшего просто не бывает. Например, если в задаче о коммивояжере удалось построить такой замкнутый маршрут, в котором путь из каждого города ведет в ближайший к нему город, то этот маршрут, очевидно, является кратчайшим и дальнейший перебор не имеет смысла.
Все соображения, подобные приведенным выше, следует учитывать при разработке программы перебора планов для конкретной задачи. Если приемы сокращения перебора и не позволят справиться с проблемой комбинаторного взрыва, то во всяком случае они могут увеличить размерность решаемых задач хотя бы на 1-2 единицы, что уже неплохо.
Как изменится программа при учете возможностей сокращения перебора? Рассмотрим для примера сокращение за счет отбрасывания частичных планов, которые не могут привести к допустимым планам. Предполагается, что мы умеем проверять допустимость частичных планов. Пусть G(X,p,k) = 0, если для фиксированных x1, x2, …, xk и любых xk+1, xk+2, …, xn план будет заведомо недопустим, и G(X,p,k) = 1, если при некоторых значениях xk+1, xk+2, …, xn допустимый план существует или, во всяком случае, может существовать. Тогда вместо ранее описанной процедуры CompleteSearch можно использовать процедуру ReducedSearch, модифицированную следующим образом:
procedure ReducedSearch(k: Integer);
begin
if G(X,p,k) then begin
if(первые k переменных составляют полный план) then
begin
Обработать полученный план X в соответствии
с типом задачи A, B или C;
end
else begin
k:=k+1;
X[k]:=First(U[k]);
repeat
ReducedSearch(k);
X[k]:=Next(U[k],X[k]);
until X[k]=NoValue;
end;
end;
end;
В сущности, изменение свелось к более ранней проверке условия допустимости плана, за счет которой можно ожидать некоторого сокращения перебора.
Метод ветвей и границ
В ряде задач оптимизации удается добиться более существенного сокращения перебора, используя подход, известный как метод ветвей и границ. Заметим сразу, что этот метод не выходит за рамки хорошо организованного исчерпывающего перебора, а потому, с одной стороны, наверняка находит оптимальный план, но с другой, не позволяет надеяться на волшебное ускорение работы. Тем не менее этот метод позволил решать ряд практических задач оптимизации, которые ранее считались безнадежно трудоемкими.
Метод ветвей и границ представляет собой не конкретный алгоритм, а скорее подход к рассмотрению задачи, с помощью которого (но и при учете специфики конкретной задачи) иногда удается построить эффективные алгоритмы. Рассмотрим, в чем заключается этот подход.
Пусть U - множество всех допустимых планов задачи оптимизации и F(X) - целевая функция, подлежащая минимизации. Разделим каким-то образом множество U на два непересекающихся подмножества U0и U1. При этом постараемся провести разделение так, чтобы множество U0было «поменьше и получше», т.е. с наибольшей вероятностью содержало искомый оптимальный план и при этом было невелико по мощности. Практически разделение можно выполнить, например, так: выбрать какое-то «наиболее перспективное» значение одной из переменных и отнести к U0все планы с этим значением переменной. Далее аналогичным образом разделим U0на два множества U00и U01, затем разделим U00на U000и U001и т.д. На некотором шаге придем к множеству, содержащему только один план. Чтобы не плодить индексы, предположим, что это произошло на четвертом шаге: U0000= {X0}. Результат разделения множеств показан на рис.1.2. Получен некоторый допустимый план X0. Не является ли он оптимальным?
Рис.1.2
Пусть имеется какая-то достаточно просто вычисляемая функция j(W), дающая оценку снизу для любого подмножества W U, т.е. j(W) F(X) для любогоX W.[3] Оценка не обязательно должна быть точной, т.е. на самом деле, возможно, минимум F(X) приX W больше, чем оценка j(W). Однако чем она точнее, тем лучше будет работать алгоритм.
Вычислим значение целевой функции F(X0) и сравним его с оценкой j(U0001). Если F(X0) j(U0001), то план X0 является лучшим среди всего подмножества U000. Мы выяснили это, не выполняя перебора планов из U0001. В этом случае следует подняться по дереву и вычислить оценку U001. Если, на наше счастье, F(X0) j(U001), то план X0 является лучшим на подмножестве U00и т.д.
Что, если на каком-то шаге подъема по дереву оценка j(W) не позволит отсечь очередное подмножество без рассмотрения? Пусть, например, F(X0) > j(U01). Тогда следует разделить U01на U010и U011, U010на U0100и U0111и т.д., то есть выполнить спуск еще по одной ветви дерева. При этом будет получен другой план, назовем его X1. После этого следует запомнить лучший из двух планов в качестве рекорда и в дальнейшем использовать его для сравнения с нижними оценками множеств.
Работа алгоритма будет завершена тогда, когда каждое из построенных подмножеств будет либо состоять из одного элемента, для которого можно вычислить целевую функцию, либо будет исключено из рассмотрения на основании сравнения нижней оценки целевой функции на множестве с текущим рекордом.
Итак, применение метода ветвей и границ к задаче комбинаторной оптимизации предполагает выполнение следующих операций:
· Последовательное разделение множества планов задачи на непересекающиеся подмножества.
· Подсчет оценок снизу для всех подмножеств планов.
· После того, как в результате разделения получен хотя бы один допустимый план задачи, сравнение целевой функции для рекордного плана с нижними оценками подмножеств и отбрасывание тех подмножеств, которые заведомо не могут улучшить рекорд.
В самом худшем случае, если нижняя оценка не позволит исключить ни одно подмножество, алгоритм сведется к полному перебору всех планов задачи. Однако если при разработке алгоритма удалось придумать удачный способ разбиения множества и построить достаточно хорошую нижнюю оценку, то число рассмотренных планов может быть значительно уменьшено. Трудно оценить это уменьшение количественно, однако на основании опыта применения метода ветвей и границ принято считать, что число рассмотренных планов обычно примерно равно квадратному корню из их общего количества. Учитывая экспоненциальный характер роста числа планов в зависимости от размерности задачи, можно сделать вывод, что метод ветвей и границ при его успешном применении позволяет примерно вдвое увеличить размерность задач, которые могут быть решены за то же время.
Не существует общих правил для разбиения множеств и построения оценок. Алгоритмы для конкретных задач должны строиться индивидуально, на основании учета особенностей задачи.
Рассмотрим пример применения метода ветвей и границ для решения задачи о коммивояжере. Соответствующий алгоритм разработан группой авторов и называется алгоритмом Литл, Мерти, Суини и Карел. Шаги алгоритма будут показаны на конкретном числовом примере.
Пусть дана задача о коммивояжере с 5 городами и несимметричной матрицей расстояний A, показанной в табл.1.1. Для такой малой размерности задачу проще всего было бы решить полным перебором маршрутов, однако при большей размерности алгоритм ветвей и границ работает значительно быстрее.
Таблица 1.1
| A | ji | |||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| jj | j = 47 |
На каждом шаге алгоритма предварительно выполняется операция приведения матрицы, которая заключается в следующем. Пусть ji – минимальное расстояние в i-той строке матрицы. Выпишем значение ji в дополнительном столбце справа и вычтем его из всех элементов строки. Затем выполним такую же операцию со столбцами матрицы. Подсчитаем сумму всех ji. В данном примере суммарное значение j = 47. Получившаяся после приведения матрица A¢ показана в табл.1.2.
Таблица 1.2
| A¢ | |||||
| ¥ | |||||
| 0 (15) | ¥ | ||||
| ¥ | 0 (2) | ||||
| ¥ | 0 (3) | ||||
| 0 (12) | 0 (2) | ¥ |
В чем смысл выполненной операции? Вычитая одно и то же число из всех элементов строки (т.е. из всех расстояний от данного города до других городов), мы уменьшаем на это число длину всех возможных маршрутов коммивояжера, поскольку каждый допустимый маршрут ровно один раз проходит через каждый город. Величина j показывает, на сколько длина приведенного маршрута меньше длины исходного. Ясно, что после приведения кратчайший маршрут останется кратчайшим. Зато теперь можно легко получить оценку снизу для всего множества маршрутов исходной задачи. Поскольку для приведенной матрицы кратчайший маршрут не может иметь длину меньше 0, то для исходной матрицы кратчайший маршрут имеет длину не менее j.
Теперь следует продумать способ разделения множества маршрутов. Выберем один из элементов матрицы aij, определяющий расстояние от города i до города j, и разделим все множество маршрутов на две неравные части: те маршруты, которые включают путь из i в j (U0), и те, которые не включают этот путь (U1). Чтобы меньшее множество U0 было более перспективным, надо выбрать такой элемент aij, который с наибольшей вероятностью входит в оптимальный маршрут. В качестве такого элемента разумно выбрать один из нулевых элементов матрицы A¢, однако какой именно? Вероятно, тот, отказ от которого приведет к наибольшим потерям. Как можно подсчитать потери, связанные с отказом от использования пути из города i в город j? Во-первых, из города i все равно придется куда-то ехать, поэтому в суммарную длину маршрута вместо слагаемого aij = 0 войдет некоторый элемент i-той строки aik, где k ¹ j. Минимальное по i-той строке значение aik дает оценку связанных с этим потерь. Во-вторых, в город j надо будет откуда-то приехать, и минимальное по столбцу значение arj, где r ¹ i, даст оценку потерь от того, что коммивояжер приехал не из города i. Общая оценка потерь dij равна сумме оценок по строке и по столбцу.
В табл.1.2 возле каждого нулевого элемента матрицы в скобках показаны величины dij – оценки потерь в случае неиспользования данного пути в маршруте коммивояжера. Как видно из таблицы, наибольшее значение оценки d21 = 15. Исходя из этого, выберем в качестве U0 множество всех маршрутов, в которых используется путь из города 2 в город 1, тогда U1 будет содержать все остальные маршруты. Нижняя оценка целевой функции для множества U1 будет равна j1 = j + d21 = 62.
Чтобы продолжить построение наиболее перспективного плана, рассмотрим множество U0. Для определения остальных путей маршрута построим матрицу A0 путем вычеркивания из матрицы A¢ строки 2 и столбца 1, поскольку они уже использованы. Кроме того, так как использован путь 2 ® 1, то нельзя использовать путь 1 ® 2, поэтому положим a12 = ¥. Получившаяся матрица показана в табл.1.3.
Таблица 1.3
| A0 | ji | ||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| ¥ | |||||
| jj | j = 3 |
Выполним описанную выше операцию приведения и получим матрицу A0¢ (табл.1.4). Поскольку величина приведения j = 3, можно сделать вывод, что нижняя оценка множества U0 будет равна j0 = 47 + 3 = 50.
Таблица 1.4
| A0¢ | ||||
| ¥ | 0 (1) | |||
| ¥ | 0 (2) | |||
| ¥ | 0 (18) | |||
| 0 (13) | 0 (13) | 0 (1) | ¥ |
Как и на предыдущем шаге, получим оценки потерь для всех нулевых элементов матрицы dij. Максимальное значение имеет d45 = 18. Выберем в качестве U00 множество маршрутов из U0, включающих путь 4 ® 5, тогда U01 – маршруты, которые включают путь 2 ® 1, но не включают 4 ® 5. Имеем нижнюю оценку j01 = j0 + d45 = 50 + 18 = 68.
Для множества U00 построим матрицу A00, вычеркнув из A0¢ строку 4 и столбец 5 и положив a54 = ¥. Матрица показана в табл.1.5.
Таблица 1.5
| A00 | ji | |||
| ¥ | ||||
| ¥ | ||||
| ¥ | ||||
| jj | j = 3 |
В табл.1.6 показана приведенная матрица A00¢. Нижняя оценка множества U00 будет равна j00 = 50 + 3 = 53.
Таблица 1.6
| A00¢ | |||
| ¥ | 0 (12) | ||
| ¥ | 0 (11) | ||
| 0 (11) | 0 (12) | 0 (0) |
Два нулевых элемента имеют одинаковые оценки потерь: d14 = d53 = 12. Возьмем любой из них[4], например, a14. Для множества U001 (всех маршрутов из U00, не включающих путь 1 ® 4), получаем нижнюю оценку j001 = j00 + d14 = 53 + 12 = 65.
Чтобы ускорить дело, обратим внимание, что мы уже включили в строящийся маршрут пути 2 ® 1, 4 ® 5 и 1 ® 4, что составляет цепочку 2 ® 1 ® 4 ® 5. Ее можно единственным образом достроить до замкнутого маршрута, включив город 3 (другими словами, множество U000 состоит из единственного элемента). Тогда, если для порядка начать с города 1, получается маршрут: 1 ® 4 ® 5 ® 3 ® 2 ® 1. Длину этого маршрута можно подсчитать разными способами, например, добавив к оценке j00 = 53 длины путей a53 = 0 и a32 = 11, а можно и просто суммировать длины всех пяти путей из исходной матрицы. В любом случае получается число f000 = 64, которое будет первым рекордом при решении данной задачи.
Является ли данный рекордный маршрут оптимальным? Попробуем для ответа на этот вопрос использовать имеющиеся нижние оценки множеств. Оценка j001 = 65, и это значит, что в множестве U001 все маршруты, по крайней мере, на 1 длиннее, чем полученный рекорд, поэтому множество U001 можно не рассматривать. Тем более бесперспективно множество U01, для которого j01 = 68. Однако для множества U1 нижняя оценка j1 = 62, а это значит, что множество вполне может содержать маршрут с длиной, меньшей чем 64. Придется для U1 вновь выполнять процедуру разделения, строить нижние оценки и искать новый рекордный маршрут.
Вспомним, что множество U1 состоит из всех маршрутов, не использующих путь 2 ® 1. Чтобы отразить это условие, достаточно в приведенной матрице A¢ положить элемент a21 = ¥. Полученная матрица A1 показана в табл.1.7.
Таблица 1.7
| A1 | ji | |||||
| ¥ | ||||||
| ¥ | ¥ | |||||
| ¥ | ||||||
| ¥ | ||||||
| ¥ | ||||||
| jj | j = 15 |
После приведения получится матрица A1¢ (табл.1.8). Нижняя оценка для U1, как уже говорилось выше, j1 = 62.
Таблица 1.8
| A1¢ | |||||
| ¥ | 0 (3) | ||||
| ¥ | ¥ | 0 (8) | |||
| ¥ | 0 (2) | ||||
| 0 (12) | ¥ | 0 (0) | |||
| 0 (0) | 0 (2) | ¥ |
Выбираем нулевой элемент с максимальной оценкой d41 = 12. Получим два множества: U10 – маршруты, которые не включают путь 2 ® 1, но включают 4 ® 1, и U11 – маршруты, которые не включают ни путь 2 ® 1, ни путь 4 ® 1. Нижняя оценка j11 = j1 + d41 = 62 + 12 = 74, т.е. множество U11 можно отбросить сразу – оно содержит маршруты, заведомо худшие, чем текущий рекорд.
Матрица A10 для множества U10 показана в табл.1.9.
Таблица 1.9
| A10 | ji | ||||
| 0 (3) | ¥ | ||||
| ¥ | 0 (8) | ||||
| ¥ | 0 (4) | ||||
| 0 (0) | 0 (2) | ¥ | |||
| jj | j = 0 |
Приведение ничего не дает, поэтому нижняя оценка j10 = j1 = 62 и сразу можно вычислять оценки нулевых элементов. Выбираем d23 = 8. Для множества U101 оценка j101 = j10 + d23 = 62 + 8 = 70, значит, множество U101 также можно не рассматривать. Множество U100 содержит маршруты, которые не включают путь 2 ® 1, но включают 4 ® 1 и 2 ® 3. Матрица A100 показана в табл.1.10.
Таблица 1.10
| A100 | ji | |||
| 0 (3) | ¥ | |||
| ¥ | 0 (4) | |||
| 0 (3) | ¥ | |||
| jj | j = 0 |
Приведение ничего не дает, нижняя оценка j100 = j10 = 62. Вычисляем оценки нулевых элементов и выбираем d35 = 8. Для множества U1001 оценка j1001 = j100 + d35 = 62 + 4 = 66, поэтому U1001 не рассматриваем. Множество U1000 содержит маршруты, которые включают 4 ® 1, 2 ® 3 и 3 ® 5. Единственный маршрут, который можно достроить (множество U1000), выглядит так: 1 ® 2 ® 3 ® 5 ® 4 ® 1. Длина этого маршрута f1000 = 62, что лучше, чем прежний рекорд!
Поскольку все нерассмотренные множества были забракованы с помощью сравнения их нижних оценок с рекордом, перебор можно считать законченным, и текущий рекордный маршрут является кратчайшим маршрутом коммивояжера для данной задачи. Интересно отметить, что при решении задачи были полностью построены только два маршрута (всего для задачи с пятью городами возможны 24 разных маршрута).
На рис.1.3 показан просмотренный фрагмент дерева перебора. Рисунок позволяет более наглядно убедиться, что проведенный поиск действительно был исчерпывающим. Жирными стрелками выделены те ветви дерева перебора, которые были рассмотрены до конца.
Рис.1.3