상호 쌍이있는 헝가리 알고리즘?

Question

다음 헝가리어 알고리즘 구현을 사용하려고합니다 : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm.

이 알고리즘을 수정하여 세트를 자체적으로 페어링 할 수 있기를 바랍니다. 즉, "b"에 "a"가 지정되면 "a"에도 "b"가 할당됩니다. 내가 가진 유일한 아이디어는 다음을 변경하는 것입니다. 다음

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; 
    } 

알고리즘은 항상 짝 상호있는 경로를 확인하는 그래서. 그러나, 나는 이것이 틀렸다는 것을 오히려 확신합니다. 코드는 대개 segfault입니다.

if (max_match == n)을 if (max_match >= n-1)과 같은 더 가혹한 제약 조건으로 변경하여 문제를 해결해 보았습니다. 그래야 알고리즘이 하위 완벽하게 일치하는 콘텐츠가됩니다. 이것은 때로는 효과가 있으며 때가되면 원하는대로 상호 쌍을 생성하지만 일부 꼭지점은 쌍을 이루지 않게됩니다. 여전히 세분화 오류가 있습니다.

이 문제를 해결할 방법이 있습니까? 이에 대한 다른 적합한 알고리즘이 있습니까?

Answer 1

나는 당신이 원하는 것이 이진파가 아닌 그래프의 최대 일치 버전이라고 생각한다. 알고리즘은 http://en.wikipedia.org/wiki/Blossom_algorithm에 있으며 가장 마지막 단락에서는 가중치에 대해 설명합니다. 최소 비용 매칭을 원하지만 모든 최대 매칭의 모서리 수가 동일하므로 각 링크의 비용을 무효화하거나 매우 큰 상수에서 비용을 뺀 경우 최소값을 최대 값으로 변경하십시오.

일반적인 최대 문제는 충분히 일정합니다. 헝가리어 알고리즘을 사용하면 문제가 너무 복잡해지기 때문에 헝가리어 알고리즘을 사용하는 데 문제가있을 것이라고 생각합니다.

Answer 2

"정상적인"헝가리 알고리즘의 양쪽에서 같은 세트를 사용하고 각 요소의 페어링에 "무한"을 할당 할 수없는 이유는 모르겠습니다. 그러면 최대 페어링을 제공하고 아무도 자신과 일치하지 않는다고 보장합니다.

Answer 3

이 문제를 최적의 비회 전성 검색이라고합니다. 고전적인 참고 자료는 DERIGS, U. (1988)입니다. 최단 경로 기법을 사용하여 비동 진성 일치 문제를 해결합니다. 실용 신안 연보 13, 225-261. 작은 세트의 경우 간단한 방법으로도 충분할 수 있습니다. 참조 : https://gis.stackexchange.com/questions/179559/how-to-group-10k-points-into-closest-pairs 문제를 해결하는 R 패키지 nbp 일치가 있습니다.

덧붙여 두 가지 단순한 일치 알고리즘을 사용하고 자신과 페어링하는 데 많은 페널티를 가하는 경우 일관되게 페어링을 얻지 못합니다. 그 이유는보다 최적의 배치가 A와 B ', B와 쌍을 이루고 C'와 C가 A '와 쌍을 이룰 수 있다는 것입니다.