Для решения оптимизационных задач наряду с точными методами, обходящими все дерево вариантов и действительно определяющими экстремум, используются разнообразные приближенные и эвристические методы, в которых поиск тем или иным способом ограничивается. При этом, однако, нет гарантии, что полученное решение окажется оптимальным.
При программировании переборных задач обязательно нужно предусмотреть возможность прерывания программы пользователем, выдавая наилучшее из найденных на данный момент решений и завершая работу программы. В некоторых случаях следует использовать отсечение по времени.
Подытоживая сказанное, можно отметить, что наиболее важными техническими моментами при решении таких задач является правильная организация обхода дерева вариантов, умение хранить это дерево в памяти компьютера и умение завершать работу программы по истечению некоторого промежутка времени.
Алгоритмы на графах
Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такая формализация приводит нас к понятию графа и возможности использования теории графов для решения исходной задачи.
При решении задач на графы полезно знать, что эти задачи относятся к одному из двух больших классов задач. Первый класс составляют задачи, которые решаются эффективно, т.е. за время, полиномиальное от длины входных данных, и про такие задачи говорят, что они принадлежат 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) и помещает все вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение «построим граф всех возможных состояний», употребляемое при решении различных задач, означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель. Описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин.
Некоторые задачи для своего решения требуют построения наибольшего паросочетания в двудольном графе. Для этого можно применить известный алгоритм чередующихся цепочек. Конечно, наибольшее паросочетание можно найти и с помощью алгоритма построения максимального потока во вспомогательной сети, но этот способ более трудоемок.
При решении задач на графах второго класса широко используется метод перебора с возвратом. Поскольку этот метод был описан выше, ограничимся здесь лишь краткими комментариями.
Наиболее часто встречаются следующие задачи второго класса:
Формулировки приведенных задач и методы их решения (основанные на переборе с возвратом и использовании отсечений) содержатся в соответствующей литературе. Общая идея здесь достаточно простая — следует отсекать те ветви дерева вариантов, которые заведомо не могут привести к решению, лучшему уже найденного. В этом случае часто бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма). Можно использовать эвристический подход и в целом — ограничить множество перебираемых вариантов, руководствуясь теми или иными разумными соображениями. Естественно, что при этом мы можем случайно отсечь ту часть дерева, где содержалось оптимальное решение, и полученное нами решение оптимальным не будет. Также, при программировании этих задач, следует предусмотреть возможность прерывания программы пользователем (или использовать отсечение по времени), выдавая наилучшее из найденных за отведенное время решений.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 2)
Вычислительная геометрия
Геометрические задачи обычно редко встречаются при обучении школьников, поэтому основная часть школьников не представляет, как быстро и эффективно их решать. Но поскольку многие из них хорошо владеют школьным курсом геометрии, они, увидев геометрическую задачу, немедленно берутся за нее. Как правило, это приводит к плачевным результатам. Причина в том, что вычислительная геометрия имеет свою специфику и сильно отличается от школьной геометрии, на которую опирается.
Опишем основные геометрические объекты, используемые при программировании решений к задачам этого раздела:
В программах, решающих геометрические задачи, обычно используются вещественные числа. При проведении с ними операций необходимо учитывать погрешность вычислений, вызванную накоплением ошибок в последних разрядах. Это приводит к тому, что вещественные числа, как правило, нельзя сравнивать обычным образом — их нужно сравнивать с какой-то заданной точностью eps. Например, для выяснения, равно ли вещественное число a нулю вместо условия a=0 следует записать abs(a).
Также необходимо избегать ошибок, связанных с переполнением целых типов. Например, для вычисления расстояния между двумя целочисленными точками многие используют выражение
sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1).
Хотя полученный результат и будет вещественным, преобразование в вещественный тип из целого происходит только при извлечении корня, что делает возможным переполнение целого типа при предыдущих операциях вычитания, умножения и сложения.