Венгерский алгоритм с взаимными парами?
Я пытаюсь использовать следующую реализацию венгерского алгоритма: http://community.topcoder.com/tc?module=Static&d1 = учебники&d2 = венгерский алгоритм.
Я хотел бы изменить этот алгоритм, чтобы я мог связать набор с самим собой. То есть, если «a» назначено на «b», «b» также назначено на «a». Единственная идея, которая у меня возникла, — это изменить следующее.
for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
{
yx[cy] = cx;
xy[cx] = cy;
}
К следующему:
for (int cx = x, cy = y, ty; cx != -2; cx = prv[cx], cy = ty)
{
yx[cy] = cx; yx[cx]=cy;
xy[cx] = cy; xy[cy]=cx;
}
Так что алгоритм всегда проверяет пути, где пары являются взаимными. Тем не менее, я уверен, что это неправильно — код, как правило, segfaults.
Я попытался исправить проблему, изменив if (max_match == n) к более слабому ограничению, как if (max_match >= n-1), так что алгоритм удовлетворен суб-идеальным соответствием. Иногда это работает, а когда это происходит, создается несколько взаимных пар, как я и хотел, но некоторые вершины остаются непарными. И все еще есть ошибки сегментации.
Итак, есть ли способ решить эту проблему? Есть ли другие более подходящие алгоритмы для этого?
Решение
Я думаю, что вам нужна версия максимального соответствия для графа, который не является двудольным. Для этого описан алгоритм http://en.wikipedia.org/wiki/Blossom_algorithm, и самый последний параграф говорит о взвешенном случае. Вы хотите соответствие минимальной стоимости, но каждое максимальное соответствие имеет одинаковое количество ребер, поэтому, если вы отмените стоимость каждой ссылки или вычтете затраты из какой-то очень большой константы, вы превратите минимум в максимум.
Общая максимальная проблема достаточно постоянна, поэтому я думаю, что вам будет трудно заставить венгерский алгоритм сделать это, потому что, если бы вы могли сделать это с помощью венгерского алгоритма, люди не сочли бы общую проблему настолько сложной.
Другие решения
Я не знаю, почему вы не можете просто использовать один и тот же набор с обеих сторон «нормального» венгерского алгоритма и назначить «бесконечность» для спаривания каждого элемента с самим собой. Это даст вам максимальное сопряжение и гарантирует, что ни один человек не сравнится с самим собой.
Задача называется оптимальным двудольным соответствием. Классическая ссылка:
DERIGS, U. (1988). Решение двудольных проблем сопоставления методами кратчайшего пути. Анналы исследования операций 13, 225–261.
Для небольших множеств более подходящими могут быть более простые методы. Увидеть:
https://gis.stackexchange.com/questions/179559/how-to-group-10k-points-into-closest-pairs
Существует пакет R nbpMatching, который решает проблему.
Между прочим, если вы попытаетесь просто использовать алгоритм двустороннего сопоставления и наложите тяжелый штраф на спаривание с самим собой, вы не получите спаривание последовательно. Причина заключается в том, что более оптимальной компоновкой может быть А в паре с В ‘, В в паре с С’ и С в паре с А ‘или подобные подобные компоновки.