МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 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. В этом случае полезно использовать метод локальной оптимизации. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга.
Для решения оптимизационных задач наряду с точными методами, обходящими все дерево вариантов и действительно определяющими экстремум, используются разнообразные приближенные и эвристические методы, в которых поиск тем или иным способом ограничивается. При этом, однако, нет гарантии, что полученное решение окажется оптимальным.
При программировании переборных задач обязательно нужно предусмотреть возможность прерывания программы пользователем, выдавая наилучшее из найденных на данный момент решений и завершая работу программы. В некоторых случаях следует использовать отсечение по времени.
Подытоживая сказанное, можно отметить, что наиболее важными техническими моментами при решении таких задач является правильная организация обхода дерева вариантов, умение хранить это дерево в памяти компьютера и умение завершать работу программы по истечению некоторого промежутка времени.
Алгоритмы на графах
Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такая формализация приводит нас к понятию графа и возможности использования теории графов для решения исходной задачи.
При решении задач на графы полезно знать, что эти задачи относятся к одному из двух больших классов задач. Первый класс составляют задачи, которые решаются эффективно, т.е. за время, полиномиальное от длины входных данных, и про такие задачи говорят, что они принадлежат P-классу. Ко второму классу относятся, так называемые, NP-полные задачи и те задачи, к которым они сводятся (они не менее сложные и потому называются NP-трудными). Все NP-полные задачи эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся специалистами задач, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Однако, несмотря на огромное число эмпирических свидетельств, эта гипотеза (называемая «P ¹ NP») до сих пор остается недоказанной.
Среди задач первого класса рассмотрим подробнее обхода графа в ширину, по той причине, что те или иные его модификации используются для нахождения кратчайших путей во многих задачах. Для простоты опишем его для случая неориентированного графа, так как изменения, которые необходимо внести для работы с ориентированными графами, достаточно очевидны.
Итак, пусть задан граф с двумя выделенными вершинами s и t, которые мы будем называть начальной и конечной, и нам необходимо найти кратчайший путь из s в t. Суть алгоритма состоит в том, чтобы пометить сначала меткой 1 те вершины графа, которые находятся на расстоянии одного ребра от вершины s, затем меткой 2 те вершины, которые отстоят от s на расстояние двух ребер, и т.д. При этом на очередном шаге k мы помечаем те и только те вершины, которые еще не были помечены и которые связаны ребром с какой-либо вершиной, имеющей метку k–1. Рано или поздно описанный алгоритм остановится, поскольку окажутся помеченными все вершины, достижимые из начальной. Если при этом вершина t останется непомеченной, то путей из s в t не существует. В противном случае метка вершины t равна длине кратчайшего такого пути.