Определение проблемы и ссылки
Для простого графа (ненаправленный, без ребер, без ребер) a , соответствующий
является подмножеством ребер таким образом, что никакие два из них не попадают в одну и ту же вершину.
A совершенное сопоставление - это такое, в котором все вершины инцидентны ребру
сопоставление, что-то невозможное, если существует нечетное количество вершин.
В более общем случае мы можем запросить максимальное совпадение (максимально возможное количество
ребра в совпадении) или для максимального совпадения (совпадения, к которому не более
края могут быть добавлены).
Если положительные реальные «веса» присвоены ребрам, мы можем обобщить
проблема запросить максимально взвешенное соответствие , которое максимизирует
сумма весов ребер. Точная задача максимального соответствия может быть
решается за O (nm log (n)) время, где n - число вершин, а m -
количество ребер
Обратите внимание, что максимально взвешенное соответствие не обязательно должно быть идеальным соответствием. За
Пример:
*--1--*--3--*--1--*
имеет только одно идеальное соответствие, общий вес которого равен 2, и максимум
взвешенное совпадение с общим весом 3.
Обсуждение и дальнейшие ссылки на точные и приблизительные решения
они, и из минимально взвешенной проблемы идеального соответствия, могут быть найдены
в этих статьях:
«Алгоритм простого приближения для взвешенной задачи согласования»
Дрейк, Доратха Э. и Хугарди, Стефан (2002)
Реализация взвешенных соответствий O (nm log n) Сила структур данных
Мельхорн, Курт и Шефер, Гвидо (2000)
Вычисление идеального соответствия минимального веса
Кук, Уильям и Роэ, Андре (1997)
Аппроксимация максимального веса в почти линейное время
Дуань, Ран и Петти, Сет (2010)
Алгоритм простого приближения Дрейка и Хагарди
Алгоритм первого приближения Дрейка-Хугарди использует идею
растущих путей, используя локально самый тяжелый край в каждой встреченной вершине. Это
имеет «коэффициент производительности» 1/2 как жадный алгоритм, но линейный
временная сложность числа ребер (жадный алгоритм использует
самый тяжелый край в мире и требует больших временных затрат, чтобы найти это).
Основная задача реализации - определить структуры данных, которые поддерживают
шаги их алгоритма эффективно.
Идея алгоритма PathGrowing:
Given: a simple undirected graph G with weighted edges
(0) Define two sets of edges L and R, initially empty.
(1) While the set of edges of G is not empty, do:
(2) Choose arbitrary vertex v to which an edge is incident.
(3) While v has incident edges, do:
(4) Choose heaviest edge {u,v} incident to v.
(5) Add edge {u,v} to L or R in alternating fashion.
(6) Remove vertex v (and its incident edges) from G.
(7) Let u take the role of v.
(8) Repeat 3.
(9) Repeat 1.
Return L or R, whichever has the greater total weight.
Структуры данных для представления графика и вывода
Поскольку «множество» не является в каком-либо непосредственном смысле структурой данных C, мы
необходимо решить, какие контейнеры для ребер и вершин будут
подойдет этот алгоритм. Критические операции - удаление вершин
и падающие ребра таким образом, что позволяет нам найти, если какие-либо ребра
слева и сравнить веса оставшихся ребер, инцидентных
заданная вершина.
Края должны быть доступны для поиска, но только для того, чтобы увидеть, остались ли еще.
Сначала думают о простом связанном списке ребер, без каких-либо специальных
упорядоченность. Но этот список также необходимо поддерживать по существу
случайные удаления. Это предполагает двусвязный список (обратные ссылки как
так же, как вперед на каждом узле), так что удаление края может быть сделано
исправляя ссылки, чтобы пропустить любой «удаленный» узел. Краевые веса
также может храниться в той же структуре.
Далее нам нужна возможность сканировать все (оставшиеся) ребра,
данная вершина. Мы можем сделать это, создав связанный список для каждой вершины
из (указателей) инцидентных ребер. Я буду предполагать, что вершины имеют
были предварительно обработаны до порядковых значений, которые могут быть использованы в качестве индекса в
массив указателей на эти связанные списки.
Наконец, нам нужно представить наборы ребер L и R, один из которых
быть возвращены в качестве приблизительного максимального соответствия. Наши требования
должны иметь возможность добавлять ребра к любому набору и иметь возможность суммировать
изданиеGe веса для них обоих.Связанные списки с динамически размещенными узлами могут служить этой цели, возможно, сохраняя указатели на граничные узлы в исходных двусвязных списках, поскольку атрибут веса будет сохраняться там даже после того, как ребро будет «удалено» из-за манипуляции ссылками.* Такие связанные и двусвязные списки могут создаваться во времени, пропорциональном количеству ребер, поскольку записи двусвязных списков могут быть выделены для привязанных к вершинам ссылок на входе.Имея в виду такой дизайн, мы можем проанализировать усилия, необходимые для каждого шага алгоритма.
(продолжение следует)