Венгерский алгоритм с взаимными парами?

Я пытаюсь использовать следующую реализацию венгерского алгоритма: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm.

Я хотел бы изменить этот алгоритм, чтобы я мог связать набор с самим собой. То есть, если "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), так что алгоритм удовлетворен суб-идеальным соответствием. Иногда это работает, а когда это происходит, создается несколько взаимных пар, как я и хотел, но некоторые вершины остаются непарными. И все еще есть ошибки сегментации.

Итак, есть ли способ решить эту проблему? Есть ли другие более подходящие алгоритмы для этого?

Источник

3 ответа

Решение

Я думаю, что вам нужна версия максимального соответствия для графа, который не является двудольным. Для этого есть алгоритм, описанный по адресу 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, который решает проблему.

Между прочим, если вы попытаетесь просто использовать алгоритм двустороннего сопоставления и наложите серьезное наказание на спаривание с самим собой, вы не всегда получите спаривание. Причина заключается в том, что более оптимальной компоновкой может быть А в паре с В ', В в паре с С' и С в паре с А 'или подобные подобные компоновки.

Источник
Другие вопросы по тегам