Чтобы найти сам кратчайший путь (а не только его длину), необходимо при обходе в ширину для каждой обрабатываемой вершины v запоминать ту вершину u (помеченную на предыдущем шаге), из которой мы пришли в v. Восстановление пути начинается с конца: по последней вершине находим предпоследнюю, затем по ней — пред-предпоследнюю и т.д. В результате мы получим вершины кратчайшего пути, записанные в обратном порядке. Поэтому зачастую более выгодно начинать алгоритм обхода в ширину с конечной, а не с начальной вершины.
Следует также отметить, что некоторые графы могут быть естественным образом заданы множеством своих вершин {u} и итератором f(u), который для каждой вершины u перечисляет все соседние ей вершины графа (такого рода итераторы называются перечислителями). В этом случае нет никакой необходимости в хранении самих ребер графа — обрабатывая вершину u, алгоритм просто вызывает перечислитель f(u) и помещает все вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение «построим граф всех возможных состояний», употребляемое при решении различных задач, означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель. Описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин.
Некоторые задачи для своего решения требуют построения наибольшего паросочетания в двудольном графе. Для этого можно применить известный алгоритм чередующихся цепочек. Конечно, наибольшее паросочетание можно найти и с помощью алгоритма построения максимального потока во вспомогательной сети, но этот способ более трудоемок.
При решении задач на графах второго класса широко используется метод перебора с возвратом. Поскольку этот метод был описан выше, ограничимся здесь лишь краткими комментариями.
Наиболее часто встречаются следующие задачи второго класса:
Формулировки приведенных задач и методы их решения (основанные на переборе с возвратом и использовании отсечений) содержатся в соответствующей литературе. Общая идея здесь достаточно простая — следует отсекать те ветви дерева вариантов, которые заведомо не могут привести к решению, лучшему уже найденного. В этом случае часто бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма). Можно использовать эвристический подход и в целом — ограничить множество перебираемых вариантов, руководствуясь теми или иными разумными соображениями. Естественно, что при этом мы можем случайно отсечь ту часть дерева, где содержалось оптимальное решение, и полученное нами решение оптимальным не будет. Также, при программировании этих задач, следует предусмотреть возможность прерывания программы пользователем (или использовать отсечение по времени), выдавая наилучшее из найденных за отведенное время решений.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 1)
В.М.Кирюхин
За годы проведения олимпиад школьников по информатике было разработано и опубликовано в различных изданиях, в том числе и в интернете, достаточно большое количество задач. Наряду с этим, в последнее время решения всех задач, предлагавшихся на заключительном этапе всероссийских олимпиад школьников по информатике, печатаются в периодических изданиях, с которыми центральная методическая комиссия по информатике тесно сотрудничает. Тем не менее, полноценных методических изданий, способных оказать существенную помощь учителям и школьникам в подготовке к олимпиадам и систематизирующих весь накопленный опыт в решении олимпиадных задач по информатике нет.
Формат данной статьи не позволяет рассмотреть в полном объеме теорию и практику решения олимпиадных задач по информатике. Поэтому ограничимся здесь только методическими указаниями, которые будут полезными в понимании содержания олимпиадных задач и основных подходов к их решению.
Несмотря на то, что на олимпиадах по информатике предлагаются самые разнообразные задачи, тем не менее, можно выделить наиболее часто встречающиеся разделы информатики, которые необходимо знать, чтобы успешно выступать на этих олимпиадах. К таким основным разделам можно отнести:
Рассмотрим краткое содержание этих разделов и особенности использования присущих им подходов и методов при решении олимпиадных задач по информатике.
Динамическое программирование
Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач с меньшей размерностью и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. Преимущество динамического программирования заключается в том, что любая подзадача решается один раз, ее решение сохраняется и никогда не вычисляется заново.
В том случае, когда исходная задача определяется одним параметром N, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение Fk задачи размерности k для всех k, меньших N, и хотим получить решение для k, равного N. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N. В частности, зная решения задач F0, F1, …, Fs, вычисляем в цикле решения Fs+1, Fs+2 и т.д. до искомого решения FN.
Задачи, решение которых основано на использовании метода динамического программирования, зачастую требуют только правильного применения основной идеи этого метода. После этого нужна только аккуратная реализация алгоритма. Сложно выделить какие-то общие ошибки или проблемы, возникающие в таких задачах. Все же отметим, что часто «лобовое» применение принципа динамического программирования не укладывается в ограничения, например, по памяти (такие задачи требовательны к памяти, ведь мы экономим время работы, в том числе за счет хранения промежуточных результатов). Поэтому, возможно, потребуется аккуратная реализация хранения большого количества данных (динамическая память, структуры данных).
Перебор с возвратом
Метод перебора с возвратом (backtracking) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых обычно демонстрируется этот подход, являются обход конем доски размером N´N, расстановка N ферзей на доске N´N и задача коммивояжера.
Решаемые методом перебора с возвратом задачи, как правило, принадлежат одному из трех классов — требуется либо найти произвольное из решений, либо перечислить все возможные решения, либо найти решение, оптимальное по заданному критерию.
Основной принцип, на котором базируется рассматриваемый метод, состоит в следующем. Рассмотрим, для определенности, задачу P0 оптимизационного типа. Декомпозируем задачу P0 на некоторое число подзадач P1, …, Pk, представляющих в целом всю задачу P0. Далее попытаемся по очереди решить каждую из этих подзадач. Под решением подзадачи обычно подразумевается:
Смысл описанного разбиения задачи на некоторое число подзадач состоит в том, что или эти подзадачи проще разрешить, или они имеют меньшую размерность, или обладают какой-то дополнительной структурой, не присущей первоначальной задаче. Поскольку мы должны отсекать те ветви дерева решений, которые заведомо не могут содержать решения, лучшего уже найденного, то становится важным как можно раньше найти хорошее приближение к оптимальному решению. Поэтому бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма) и организовать перебор таким образом, чтобы наиболее «перспективные» варианты рассматривались первыми. Кроме того, можно найти несколько начальных решений с помощью различных эвристик, а затем выбрать из них наилучшее.
Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P1 исходной задачи P0, в то время как оптимальное решение P0 находится в другой подзадаче Pi. В этом случае полезно использовать метод локальной оптимизации. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга.