Дрейк и Hougardy находят простой алгоритм аппроксимации для задачи максимального взвешенного соответствия. Я думаю, что мое понимание академических работ выше моих возможностей, поэтому я ищу легкую реализацию, предпочтительную в php, c, javascript?
Определение проблемы и рекомендации
Учитывая простой график (неориентированный, без собственных ребер, без многогранников), сопоставление является подмножеством ребер, так что ни одна из них не попадает в одну и ту же вершину.
Идеальное совпадение – это то, в котором все вершины попадают в ребро соответствия, что невозможно, если существует нечетное число вершин. В более общем плане мы можем запросить максимальное совпадение (максимально возможное количество ребер в сопоставлении) или максимальное согласование (сопоставление, к которому нельзя добавить больше ребер).
Если положительным реальным «весам» присваиваются ребрам, мы можем обобщить проблему, чтобы спросить максимально-взвешенное соответствие , которое максимизирует сумму весов ребер. Точная задача с максимальным весовым соответствием может быть решена в O (nm log (n)) времени, где n – число вершин, а m – количество ребер.
Обратите внимание, что согласование с максимальным весом не должно быть идеальным совпадением. Например:
*--1--*--3--*--1--* имеет только одно идеальное соответствие, общий вес которого равен 2, и максимальное взвешенное соответствие с общим весом 3.
Обсуждение и дальнейшие ссылки для точных и приближенных решений этих задач и задачи минимального взвешенного совпадения можно найти в следующих статьях:
«Алгоритм простой аппроксимации для взвешенной задачи соответствия» Дрейк, Доратха Е. и Угардди, Стефан (2002)
Реализация O (nm log n) Взвешенные соответствия Сила структур данных Melhorn, Kurt and Schäfer, Guido (2000)
Вычисление минимального веса Perfect Matchings Cook, William and Rohe, André (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, один из которых должен быть возвращен как примерное совпадение максимумов. Наши требования состоят в том, чтобы иметь возможность добавлять ребра к любому набору и иметь возможность суммировать весы для них обоих. Связанные списки с динамически выделенными узлами могут служить этой цели, возможно, сохраняя указатели на граничные узлы в исходных двусвязных списках, поскольку атрибут веса по-прежнему сохраняется там, даже когда край становится «удаленным» путем манипуляции ссылками.
Такие связанные и двусвязные списки могут быть созданы во времени пропорционально количеству ребер, так как записи с двойной связью могут быть выделены на конкретные ссылки на входе. Имея такую конструкцию, мы можем анализировать усилия, требуемые каждым шагом алгоритма.
(продолжение следует)