두 세트 사이에 요소를 매핑하는 알고리즘

Question

두 세트의 벡터 세트 A와 B 세트가 있습니다. 세트 A에는 100 개의 벡터가 있고 세트 B에는 50 개의 벡터가 포함되어 있습니다. 두 벡터 사이의 거리를 측정하는 자체 방식이 있습니다. 목표는 집합 A의 벡터를 거리가 특정 임계 값 내에있는 집합 B의 벡터에 매핑하는 것입니다. 이제 두 벡터 사이의 거리가 특정 임계 값 내에 있지 않으면 쌍을 이루지 않습니다. 매핑은 1 대 1입니다. 즉 집합 A의 벡터는 집합 B의 한 벡터에만 매핑 될 수 있으며 반대의 경우도 가능합니다.

결국 집합 A의 40 벡터가 집합 B의 40 벡터에 매핑 될 수 있습니다. 따라서 집합 A의 60 벡터는 집합 B의 벡터와 쌍을 이루지 않습니다. 따라서 집합 B의 벡터 10 개 또한 짝을 이루지 못하게 남겨둔다.

이제 집합 A의 벡터에 A1, A2, A3 ... A100, B1, B2, B3 ... 같은 벡터를 레이블하면 가장 효율적인 반복 방법은 무엇입니까? 두 세트를 통해이 페어링을합니다.

추가 설명이 필요한 경우 알려 주시기 바랍니다.

Answer 1

당신이해야 할 일은 A의 어떤 벡터가 B의 어떤 벡터와 쌍을 이룰 수 있는지 먼저 확인하는 것입니다. 이것은 O (n^2) 복잡도로 수행되며 2 개의 그래프를 만듭니다. 두 개의 꼭지점 파티션 - A의 벡터와 B의 벡터 그리고 A의 벡터가 B의 벡터와 쌍을 이룰 수있는 경우에만 가장자리가 있습니다. 그래프를 작성한 후에는 최대 2 부분 일치를 찾아야하며 일반적으로 흐름을 사용하여 완료되었습니다. 예를 들어 here을보십시오. 나는 개인적으로 흐름을 위해 Dinitz 알고리즘을 사용한다.

희망이 도움이됩니다.