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

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

В том случае, когда исходная задача определяется одним параметром N, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение F_k задачи размерности k для всех k, меньших N, и хотим получить решение для k, равного N. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N. В частности, зная решения задач F ₀, F ₁, …, F_s, вычисляем в цикле решения F _s+1, F _s+2 и т.д. до искомого решения F_N.

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

Перебор с возвратом

Метод перебора с возвратом (backtracking) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых обычно демонстрируется этот подход, являются обход конем доски размером N ´ N, расстановка N ферзей на доске N ´ N и задача коммивояжера.

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

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

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

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

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

· либо разбить задачу P_i на подзадачи P_{i 1}, …, P_is и рекурсивно перейти к рассмотрению задачи P_{i 1}.

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

Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P ₁ исходной задачи P ₀, в то время как оптимальное решение P ₀ находится в другой подзадаче P_i. В этом случае полезно использовать метод локальной оптимизации. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга.

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

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

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

Алгоритмы на графах

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

При решении задач на графы полезно знать, что эти задачи относятся к одному из двух больших классов задач. Первый класс составляют задачи, которые решаются эффективно, т.е. за время, полиномиальное от длины входных данных, и про такие задачи говорят, что они принадлежат P -классу. Ко второму классу относятся, так называемые, NP-полные задачи и те задачи, к которым они сводятся (они не менее сложные и потому называются NP-трудными). Все NP -полные задачи эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся специалистами задач, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Однако, несмотря на огромное число эмпирических свидетельств, эта гипотеза (называемая «P ¹ NP») до сих пор остается недоказанной.

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

Итак, пусть задан граф с двумя выделенными вершинами s и t, которые мы будем называть начальной и конечной, и нам необходимо найти кратчайший путь из s в t. Суть алгоритма состоит в том, чтобы пометить сначала меткой 1 те вершины графа, которые находятся на расстоянии одного ребра от вершины s, затем меткой 2 те вершины, которые отстоят от s на расстояние двух ребер, и т.д. При этом на очередном шаге k мы помечаем те и только те вершины, которые еще не были помечены и которые связаны ребром с какой-либо вершиной, имеющей метку k –1. Рано или поздно описанный алгоритм остановится, поскольку окажутся помеченными все вершины, достижимые из начальной. Если при этом вершина t останется непомеченной, то путей из s в t не существует. В противном случае метка вершины t равна длине кратчайшего такого пути.

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

Следует также отметить, что некоторые графы могут быть естественным образом заданы множеством своих вершин { u } и итератором f (u), который для каждой вершины u перечисляет все соседние ей вершины графа (такого рода итераторы называются перечислителями). В этом случае нет никакой необходимости в хранении самих ребер графа — обрабатывая вершину u, алгоритм просто вызывает перечислитель f (u) и помещает все вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение «построим граф всех возможных состояний», употребляемое при решении различных задач, означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель. Описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин.

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

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

Наиболее часто встречаются следующие задачи второго класса:

· Гамильтонов путь и задача коммивояжера;

· максимальное независимое множество;

· минимальное доминирующее множество;

· раскраска графа в минимальное число цветов.

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