Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов. Оказалось, что многие проблемы теоретического и прикладного характера могут быть сформулированы в терминах графовых и сетевых моделей. Этим объясняется бурное развитие алгоритмической теории графов в последние десятилетия и то большое количество встречающихся на олимпиадах задач, в решении которых так или иначе используются алгоритмы на графах
Как правило, эти задачи относятся к одному из двух больших классов. Первый класс составляют те задачи, которые решаются эффективно, т.е. за время, полиномиальное от длины входных данных. (Про такие задачи говорят, что они принадлежат классу Р.) Ко второму классу относятся так называемые NP-полные задачи и те задачи, к которым они сводятся (они не менее сложные и потому называются NP-трудными [Емеличев 90, п.78]). Все NP-полные задачи эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся специалистами задач, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Однако, несмотря на огромное число эмпирических свидетельств, эта гипотеза (называемая "P≠NP") до сих пор остается недоказанной
Прекрасным введением в задачи первого класса могут служить главы 2 и 3 книги [Липский 88]. Глава 2 начинается с описания структур данных, предназначенных для представления графов в памяти компьютера, и влияния выбранной структуры данных на эффективность алгоритма. Далее объясняются такие фундаментальные алгоритмы, как поиск в глубину и ширину, отыскание компонент связности, построение остовного (стягивающего) дерева, построение эйлерова цикла (цикла, проходящего по каждому ребру ровно один раз).
Глава 3 рассказывает о нахождении кратчайших путей в графе - методы Форда-Беллмана, Дейкстры и Флойда. Приводится алгоритм топологической сортировки графа.
Пособие [Емеличев 90] может служить обстоятельным введением в математическую сторону теории графов. Дополнительно оно содержит главу с описанием базовых алгоритмов на графах. Также мы можем порекомендовать главу 5 [Ахо 79], главы 1, 2, 9 [Кристофидес 78], главу 3 [Окулов 98], главу 7 [Романовский 99] и главу 9 книги [Шень 95]
Здесь мы сочли нужным лишь вкратце упомянуть алгоритм обхода графа в ширину по той причине, что те или иные его модификации используются для нахождения кратчайших путей во многих задачах этой главы. Для простоты мы опишем его для случая неориентированных графов; изменения, которые необходимо внести для работы с ориентированными графами, достаточно очевидны. Более подробно о методе обхода в ширину можно прочитать в [Липский 88, п.2.3; Шень 95, п.9.2]
Итак, пусть задан граф с двумя выделенными вершинами s и t (которые мы будем называть начальной и конечной) и нам необходимо найти кратчайший путь из s в t. Суть алгоритма состоит в том, чтобы пометить сначала (меткой 1) те вершины графа, которые находятся на расстоянии одного ребра от вершины s, затем (меткой 2) те, которые отстоят от s на расстояние двух ребер, и т.д. При этом на очередном шаге k мы помечаем те и только те вершины, которые еще не были помечены и которые связаны ребром с какой-либо вершиной, имеющей метку k-1. Рано или поздно описанный алгоритм остановится, поскольку окажутся помечены все вершины, достижимые из начальной. Если при этом вершина t останется непомеченной, то путей из s в t не существует. В противном случае метка вершины t равна длине кратчайшего такого пути
Чтобы найти сам кратчайший путь (а не только его длину), необходимо при обходе в ширину для каждой обрабатываемой вершины v запоминать ту вершину и (помеченную на предыдущем шаге), из которой мы пришли в v. Восстановление пути начинается с конца: по последней вершине вспоминаем предпоследнюю, затем по ней - предпредпоследнюю и т.д. В результате мы получим вершины кратчайшего пути, записанные (увы!) в обратном порядке. Поэтому зачастую более выгодно начинать алгоритм обхода в ширину с конечной, а не с начальной вершины
Сделаем важное замечание. Некоторые графы могут быть естественным образом заданы множеством своих вершин {u} и итератором f(u), который для каждой вершины и перечисляет все соседние ей вершины графа (в этой главе мы будем называть такого рода итераторы перечислителями). В этом случае нет никакой необходимости в хранении самих ребер графа - обрабатывая вершину u, алгоритм просто вызывает перечислитель f(u) и помещает все непомеченные вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение "построим граф всех возможных состояний" в комментариях к задачам означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель
Кроме того, описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин
Некоторые из приведенных ниже задач для своего решения требуют построения наибольшего паросочетания в двудольном графе. Для этого можно применить известный алгоритм чередующихся цепочек [Романовский 99, п.7.9; Емеличев 90, п.77; Окулов 98, п.3.9.3]. Конечно, наибольшее паросочетание можно найти и с помощью алгоритма построения максимального потока во вспомогательной сети [Липский 88, п.4.3; Кормен 99, п.27.3], но этот способ более сложен в реализации
Перейдем теперь к обзору задач второго класса. Здесь активно используется метод перебора с возвратом. Поскольку этот метод был подробно разобран в главе 2, здесь мы ограничимся лишь кратким комментарием, а внимание сосредоточим на задачах, имеющих эффективные алгоритмы решения
Наиболее часто встречаются следующие задачи второго класса: Гамильтонов путь и задача коммивояжера Максимальное независимое множество Минимальное доминирующее множество Раскраска графа в минимальное число цветов
Формулировки приведенных задач и методы их решения (основанные на переборе с возвратом и использовании отсечений) содержатся в книгах [Кристофидес 78] и [Окулов 98]. Общая идея здесь нехитрая - следует отсекать те ветви дерева вариантов, которые заведомо не могут привести к решению, лучшему уже найденного. В этом случае часто бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма). Можно использовать эвристический подход и в целом - ограничить множество перебираемых вариантов, руководствуясь теми или иными разумными соображениями. Естественно, что при этом мы можем случайно отсечь ту часть дерева, где содержалось оптимальное решение, и полученное нами решение оптимальным не будет. Также, при программировании этих задач, следует предусмотреть возможность прерывания программы пользователем (или использовать отсечение по времени), выдавая наилучшее из найденных за отведенное время решений
|
