Monthly Archives: Май 2011

Графы-5: паросочетания

Определения

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

Максимальным называется паросочетание, к которому нельзя добавить ни одного ребра из множества рёбер графа, или, что то же самое, максимальное паросочетание не является подмножеством никакого другого паросочетания.

Наибольшим называется паросочетание, содержащее наибольшее число рёбер. Наибольшее паросочетание является максимальным, обратное неверно.

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

Оптимальным называется наибольшее паросочетание в графе с заданными весами рёбер, минимизирующее суммарный вес входящих в паросочетание рёбер.

Алгоритмы

Введённые определения позволяют поставить следующие задачи.

  1. Построить некоторое наибольшее паросочетание.
  2. Проверить, существует ли полное паросочетание.
  3. Построить оптимальное паросочетание для заданных весов рёбер.

Для простоты ограничимся рассмотрением двудольных графов.

Двудольным графом называется граф, вершины которого можно разделить на два непересекающихся множества X и Y таких, что все рёбра графа будут иметь вид (x, y), где x принадлежит X, а yY. Множества X и Y называются долями графа.

Добавим к графу две вспомогательные вершины s и t. Соединим s с каждой вершиной из X, и каждую вершину из Y соединим с вершиной t. Зададим всем рёбрам единичную пропускную способность и будем искать целочисленный максимальный поток (максимальный 0-1-поток) из s в t на построенной таким образом сети. Рёбра с единичным потоком составят некоторое из наибольших паросочетаний. Поэтому задачу 1 можно решить с помощью алгоритма построения максимального потока. Построив же некоторое наибольшее паросочетание не сложно проверить его на полноту, решив и задачу 2.

Кроме алгоритмов построения максимального потока существует адаптация алгоритма Форда-Фалкерсона к задаче построения наибольшего паросочетания, известная как алгоритм Хопкрофта-Карпа. Для решения задачи 2, а именно определения отсутствия полного паросочетания без построения наибольшего паросочетания, также существуют специальные алгоритмы (например, алгоритм Куна). Для решения задачи 3 существует алгоритм Куна-Манкреса, также известный как венгерский алгоритм.

Пример реализации

Возьмём часть кода до строки 506 и поместим её в файл Graph4.h. Для использования алгоритмов построения максимального потока в качестве алгоритмов поиска наибольшего паросочетания нам понадобится три элемента: а) функция, формирующая матрицу пропускных способностей, б) функция-обёртка алгоритма построения максимального потока, в) функция, «извлекающая» паросочетание из матрицы потока.

Первая и третья функции названы prepareBipartiteForMaxFlow и matchingFromFlow соответственно. Размеры долей графа передаются как константы X и Y. Для представления паросочетания используется вектор индексов, отображающий индекс вершины из доли X (от 0 до X — 1) в индекс вершины из доли Y (от 0 до Y), при этом фиктивное значение Y используется, чтобы показать, что вершина не насыщена.

Собственно привязка осуществляется тривиальной функцией fullMatching, которая использует вспомогательную структуру-шаблон FullMatching<class MaxFlowWrapper>, функцию-член find которого и вызывает (так сделано из-за того, что в C++ нельзя определять специализации функций-шаблонов).

Класс, переданный в качестве параметра MaxFlowWrapper, уже «переадресует» вызов конкретному алгоритму построения максимального потока или решает задачу самостоятельно.

Определены следующие классы, подходящие в качестве параметра MaxFlowWrapper: три обёртки алгоритмов из Graph4.h EdmondsKarpMaxFlow, PreflowPushingMaxFlow и PushRelabelMaxFlow, а также реализация алгоритма Хопкрофта-Карпа HopcroftKarp.

Итак, код реализации и теста: codepad.

Реклама

AV-2: AstarVis

Введение

На основе кода BY-1 и в качестве продолжения идей AV-1 был разработан визуализатор алгоритма A*. Архив содержит проект Visual C++ 2010 со всем исходным кодом и библиотекой FreeGLUT, готовый к использованию «как есть». В архив также включены откомпилированный exe и html-документация, сгенерированная системой Doxygen/Graphviz по комментариям в исходном коде.

Управление

  • ESC выход;
  • SPACE/ENTER новый ландшафт;
  • стрелки/WASDXZ управление камерой;
  • 0123456789 выбор множителя эвристики (соответственно от 0 до 9) с перерасчётом А*-пути, если нужно;
  • G показывать рёбра графа;
  • P показывать пути, полученные алгоритмами Дейкстры и А*.

Цвета

Про структуру графа, отражающего ландшафт, рассказано в следующем разделе «Ландшафт».

Предварительная заливка ландшафта вычисляется функцией Scene::prepareColors и состоит из синей и красной компонент. Красная компонента возрастает по мере приближения к целевой вершине, оставаясь при этом всегда меньше единицы. Синяя компонента возрастает по мере приближения к начальной вершине (эти вершины находятся в противоположных углах).

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

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

Рёбра графа изображаются отрезками жёлто-оранжевого цвета. Путь, построенный алгоритмом Дейкстры, изображается линией жёлто-зелёного цвета, А*-путь — линией светло-синего цвета.

Ландшафт

Ландшафт генерируется как карта высот сложением псевдослучайных чисел, «холмов» и «кратеров» (вычисляемых как сдвинутая и повёрнутая обратная квадратичная форма координат узла, точнее см. код классов Hill и Ring в HeightMap.h).

Карта высот представляет собой набор отсчётов (двумерный массив чисел), заданных в узлах прямоугольной сетки (лежащей в плоскости 0xy), используемыми как высоты (координаты по оси 0z) некоторого ландшафта в этих узлах. Карту высот представляет класс HeightMap.

Карта высот может быть изображена как набор полосок треугольников. Каждая четвёрка соседних узлов (ограничивающих ячейку сетки в плоскости 0xy) задаёт два треугольника. При этом дублируются вершины всех рядов кроме двух крайних. Нормали к этим треугольникам можно вычислить, например, используя векторное произведение разностей пар их вершин. Полоски треугольников строит и отображает класс Terrain.

Чтобы рассчитывать пути на ландшафте, нужно отождествить элементы графа с некоторыми элементами ландшафта. В простейшем случае можно считать вершинами графа вершины треугольников, а рёбрами графа — рёбра треугольников, проецирующиеся на 0xy в отрезки, параллельные осям 0x и 0y.

В данном случае было решено немного усложнить построение графа, так как удобно отождествить вершины графа с самими треугольниками, а рёбрами соединять те треугольники, что имеют общее ребро или общую вершину при «прямом» угле (этот угол является прямым в проекции на плоскость 0xy). Удобство состоит в том, что в этом варианте состояние вершин можно показывать цветом треугольника. Вершина графа размещается в «центре» треугольника (точке пересечения медиан). Расчётом координат вершин, стоимости переходов между вершинами и составлением списков смежности занимается класс TerrainGraph.

Связывание визуализации с алгоритмом А*

Класс TerrainGraph может быть использован непосредственно как вектор списков смежности благодаря перегруженному оператору [ ]. Веса рёбер и оценка расстояний (эвристика) рассчитываются с помощью функции-члена estimatePrice. Функторы-адапторы WeightsForGraph и HeuristicForGraph представляют граф соответственно в виде матрицы весов рёбер и эвристики для алгоритма А*.

Визуализатор использует три типа событий:

  1. OpenedEvent для события размещения вершины в очереди с приоритетом (открытое множество).
  2. ClosedEvent для события извлечения вершины из очереди.
  3. PathEvent для пометки очередной вершины в пути, построенном алгоритмом А*.

События последнего типа генерируются в последнем цикле в функции Scene::makeApath. События первых двух типов генерируются и помещаются в очередь объектом класса AstarDemo, передаваемом функции astar в качестве последнего параметра (класс AstarDemo выступает в роли модели параметра шаблона DemoPolicy).

UPDATE. 2013.01.25. Более новый вариант расположен здесь (в составе AV Orchid).

Графы-2x: алгоритм поиска пути A*

Введение

Ранее приводился алгоритм Дейкстры поиска кратчайших путей от заданной вершины до всех остальных вершин графа с неотрицательными весами рёбер. Существует алгоритм (алгоритм A*), развивающий идею алгоритма Дейкстры для ускорения поиска пути между двумя заданными вершинами графа, если известна оценка длины кратчайшего пути между любыми двумя вершинами, называемая «эвристикой». Алгоритм этот довольно популярен и используется в робототехнике и играх.

Реализация

Была написана реализация, отталкивающаяся от тех же принципов, что и ранее созданная реализация алгоритма Дейкстры. Итак, функция-шаблон, реализующая алгоритм А*, принимает следующие параметры (слова в кавычках, описывают поведение объектов, а не реальное представление их в памяти):

  • (вывод) ссылку на «массив» предшественников Pr, после выполнения алгоритма Pr[v] == u, если вершина с индексом v стоит сразу за вершиной с индексом u на искомом пути;
  • (ввод) ссылку на «матрицу» весов рёбер графа;
  • (ввод) ссылку на «массив» наборов смежности, каждый набор должен представлять собой STL-последовательность с input-итератором;
  • (ввод) индексы начальной и конечной (целевой) вершин искомого пути;
  • (ввод) количество вершин графа;
  • (ввод) эвристика, реализованная как бинарный функтор, принимающий два индекса вершин графа и возвращающий оценку расстояния;
  • (ввод, опционально) политика демонстрации работы алгоритма, предназначенная для визуализации (подробнее в AV-2).

Функция возвращает истину, если путь был найден, ложь в противном случае.

Основное отличие алгоритма поиска A* от алгоритма Дейкстры состоит в том, что при выборе ещё не пройденных вершин приоритет отдаётся тем вершинам, которые минимизируют сумму веса уже известного на момент пути (хранится в массиве gscore) и оценки остатка пути до целевой вершины. Эти суммы хранятся в массиве fscore, который используется компаратором ByArrayComparator при сравнении индексов вершин, помещаемых в объект openset (имеющий тип std::set<unsigned, ByArrayComparator<(…)>>).

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

Эта очередь называется «открытым множеством» (openset). Вершины, извлечённые из открытого множества, попадают в «закрытое множество» (closedset), после чего они уже не могут попасть в открытое множество.

Известно, что если эвристика даёт оценку кратчайшего пути снизу ( такая эвристика называется «допустимой» ), то алгоритм поиска A* находит кратчайший путь. В частности, эвристика может всегда возвращать 0, в этом случае алгоритм А* будет эквивалентен алгоритму Дейкстры с остановом при достижении целевой вершины.

С другой стороны, алгоритм А* позволяет ускорить процесс поиска с возможной потерей оптимальности результирующего пути. Известно, что если эвристика даёт оценку кратчайшего пути, которая не больше, чем в q раз превосходит вес реального кратчайшего пути, то алгоритм А* находит путь веса не более, чем в q раз большего, чем кратчайший путь (субоптимальное решение).

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