NP-СЛОЖНЫЕ И ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ

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

Рассматриваемые вопросы: основные принципы методов ветвей и границ, понятия сложности и сводимости задач.

Метод ветвей и границ

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

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

Перечислим основные этапы решения задачи методом МВГ.

1) Трансформация задачи (ТЗ). Исходную задачу заменяют другой задачей так, что множество решений исходной задачи содержится в множестве решений трансформированной задачи. Найти оптимальное решение трансформированной задачи значительно проще, чем решение исходной задачи.

2) Построение дерева решений. Множество решений ТЗ разбивают на подзадачи. Затем каждую подзадачу в свою очередь разбивают на подзадачи. В результате получается дерево решений. Процесс разбиения прекращается, если подзадача содержит не более одного решения исходной задачи, такая задача называется концевой. Если в результате работы МВГ будет построено полное дерево решений, то МВГ будет эквивалентен полному перебору, чем лучше работает МВГ, тем он дальше от полного перебора.

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

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

4) Получение верхней оценки. Любое решение исходной задачи называют верхней оценкой. Верхняя оценка больше (хуже) или равна оптимальному решению.

5) Отсечения. Если для подзадачи нижняя оценка получилась больше или равна верхней оценке, то эта подзадача заведомо не содержит решения лучше одного из уже найденных решений. Поэтому дальнейшее ее исследование не имеет смысла. Идущий от нее фрагмент дерева отсекается. Чем больше ветвей дерева отсекается, тем быстрее работает МВГ. А отсечения зависят как от качества нижних оценок, так и от качества верхней оценки (исходного размещения).

6) Ветвление. Чаще всего используется следующий способ ветвления:

- для подзадач верхнего уровня получают оценки снизу;

- подзадача с лучшей оценкой разбивается на подзадачи следующего уровня, и для них определяются оценки снизу;

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

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

Динамическое программирование

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

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

Вычислительное преимущество такого подхода состоит в том, что занимаются решением одномерных оптимизационных задач подзадач вместо большой n-мерной задачи, а затем собираем решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.

Этот метод имеет под собой достаточно серьезную научную основу, однако его суть вполне можно объяснить на простом примере чисел Фибоначчи.

Вычислить Af чисел в последовательности Фибоначчи: 1,1,2,3,5,8,..., где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.

Самый очевидный способ «решения» задачи состоит в написании рекурсивной функции примерно следующего вида:

function F(X: integer): longint; begin

if (X = 1) or (X = 2) then F := 1

else F := F(X-l) + F(X-2) end;

При этом на шестом-седьмом десятке программе перестанет хватать временных ресурсов самой современной вычислительной машины. Это происходит по следующим причинам.

Для вычисления, например, F (40) вначале вычисляется F (39) и F (38). Причем F (3 8) вычисляется заново, без использования значения, которое было вычислено, когда считалось F (39), т. е. значение функции при одном и том же значении аргумента считается много раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:

var D: array[1..100] of longint;

Сначала массив заполняется значениями, которые заведомо не могут быть значениями функции (чаще всего, это «-1», но вполне пригоден 0). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат.

Функция принимает следующий вид:

function F(X: integer): longint; begin

if D[X] =0 then

if (X=l) or (X=2) then D[X] := 1

else D[X] := F(X-l) + F(X-2); F := D[X]; end;

Этот подход динамического программирования называется подходом «сверху вниз». Он запоминает решенные задачи, но очередность реше­ния задач все равно контролирует рекурсия.

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

D[12] := 1; D[2] := 1; For i := 3 to N do

D[i] := D[i-1] + D[i-2];

Здесь использован подход «снизу вверх». Чаще всего, такой способ раза в три быстрее. Однако в ряде случаев такой метод приводит к необходимости решать большее количество подзадач, чем при рекурсии.

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

Таким образом, если алгоритм превышает отведенное ему время на тестах большого объема, то необходимо осуществлять доработку этого алгоритма.