- •Введение
- •1. Методы решения комбинаторных задач
- •1.1. Понятие об оценке эффективности алгоритмов и программ
- •1.2. Понятие комбинаторной задачи
- •1.3. Примеры комбинаторных задач
- •1.4. Организация исчерпывающего перебора
- •1.5. Сокращение перебора
- •1.6. Метод ветвей и границ
- •1.7. Метод динамического программирования
- •1.8. Метод a-b-отсечений для позиционных игр с полной информацией
- •1.9. Приближенные и эвристические методы решения задач комбинаторной оптимизации
- •2. Элементы теории сложности вычислений
- •2.1. Основные понятия и проблемы теории сложности вычислений
- •2.2. Полиномиальная сводимость задач
- •2.3. Недетерминированные машины Тьюринга и np-задачи
- •2.5. Теорема Кука
- •2.6. Примеры np-полных задач
- •2.6. Псевдополиномиальные задачи
- •2.7. Практическое значение результатов теории сложности вычислений
- •Литература
- •Дроздов Сергей Николаевич Комбинаторные задачи и элементы теории вычислительной сложности
1.5. Сокращение перебора
Следует отметить, что исчерпывающий перебор далеко не всегда означает перебор буквально всех планов задачи. В большинстве конкретных задач удается сократить перебор, оставив без рассмотрения некоторые множества планов. Перечислим некоторые случаи, когда это удается сделать.
Иногда уже после выбора нескольких первых значений 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;
В сущности, изменение свелось к более ранней проверке условия допустимости плана, за счет которой можно ожидать некоторого сокращения перебора.