여러 벡터에서 동일하지 않은 요소를 찾는 방법은 무엇입니까?

Question

여러 벡터/집합이 주어지며, 각 벡터/집합은 하나의 벡터 내에서 서로 다른 여러 정수를 포함합니다. 이제 나는 요소 하나만 각 주어진 벡터/세트에서 추출하여 구성된 집합이 있는지 확인하려면 추출 번호가 동일하지 않은입니다. 주어진 예

는, A, B, C, D로 설정 :

a <- (1,3,5); 
b <- (3,6,8); 
c <- (2,3,4); 
d <- (2,4,6) 

I가 같은 세트를 찾을 수있다 (1, 8, 4, 6) 또는 (3, 6, 2, 4) ..... 사실, 나는 그 존재를 증명할 수있는 그러한 집합을 발견 할 필요가있다.

잔인한 힘 검색을 적용하면 최대 m^k 조합을 확인할 수 있습니다. 여기서 m은 주어진 세트의 크기, k는 주어진 세트의 수입니다.

더 세밀한 방법이 있습니까? 감사합니다.

Answer 1

당신은 양자 그래프의 일치로 문제를 재구성 할 수 있습니다

• 왼쪽의 노드가 당신의 집합입니다,
• 오른쪽의 노드가 세트에 나타나는 정수입니다.

"집합"노드와 "정수"노드 사이에 지정된 정수가 포함 된 경우 가장자리가 있습니다. 그런 다음이 bipartite 그래프에서 일치를 찾으려고합니다. 각 세트는 하나의 정수와 연결되며 정수는 두 번 사용되지 않습니다. 그러한 매칭을 찾는 간단한 알고리즘의 실행 시간은 O (| V || E |)이고, 여기서 | V | (m + 1) k보다 작고 | E | mk와 같습니다. 그래서 당신은 O (m^2 k^2)의 해답을 가지고 있습니다. 참조 : Matching in bipartite graphs. 이분 매칭

알고리즘 :

알고리즘 지향 그래프에서 작동한다. 처음에는 모든 가장자리가 왼쪽에서 오른쪽으로 향하게됩니다. 두 노드 사이의 가장자리가 오른쪽에서 왼쪽으로 향한 경우 두 노드가 일치하므로 처음에는 일치가 비어 있습니다. 알고리즘의 목표는 "경로 확대"(또는 교차 경로), 즉 크기를 증가시키는 경로를 찾는 것입니다.

증가 경로는 일치하지 않는 왼쪽 노드에서 시작하여 일치하지 않는 오른쪽 노드에서 끝나는 방향성 그래프의 경로입니다. 확대 경로가 생기면 경로를 따라 모든 가장자리를 뒤집어서 일치하는 크기를 증가시켜야합니다. 일치하는 항목에 속하지 않는 가장자리가 하나 더 있기 때문에 일치하는 항목의 크기가 커집니다.이 항목은 경로가 일치하는 항목에 속하지 않는 가장자리, 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로)

다음

당신은 증대시키는 경로를 찾는 방법은 다음과 같습니다.,

1. 모든 노드가 방문하지 않은 것으로 표시됩니다
당신이 방문하지 않은 타의 추종을 불허 왼쪽 노드를 선택
2. ,
3. 당신은 할 비교할 수없는 오른쪽 노드를 찾을 때까지 깊이있는 첫 번째 검색을 수행합니다 (그 다음에는 보강 경로가 있습니다). 일치하지 않는 오른쪽 노드를 찾을 수 없으면 2로 이동합니다.

추가 경로를 찾을 수없는 경우 일치가 최적입니다.

증가 경로를 찾는 것이 O (| E |)의 복잡성이며, 최대 일치의 크기가 k와 m으로 제한되기 때문에 최대 min (k, m) 배로 수행합니다. 따라서 문제는 복잡성이 O (mk min (m, k))가됩니다.

교정본에 대한 자세한 설명은 this reference 섹션 1을 참조하십시오.