크기가 다른 두 세트 간의 거리 측정

Question

두 세트의 정수 A와 B가 있어야하며 크기가 같지 않아도됩니다. 필자의 필요에 따라 각 요소 2 개 a와 b (정수) 사이의 거리는 abs(a-b)이됩니다. 다음 I의 두 세트 사이의 거리를 정의하고

:

1. 세트는 동일한 크기 인 경우, 모든 쌍의 거리의 합을 최소화 [A, B] (A 및 B로부터 B에서), 모든 가능한 '쌍 파티션'에 대한 최소화 (n! 가능한 파티션이 있음).
2. 세트의 크기가 같지 않은 경우, 크기가 m이고 크기가 n 인 B가 m이 < 인 경우, 크기가 m 인 B의 모든 부분 집합과 (1)의 거리를 최소화하십시오.

제 질문은 위의 정의에 따라 올바른 대답을주는 알고리즘입니다 (직관적 인 생각).

• 는 D의 작은 요소를 찾아 D(i,j) = abs(A(i)-B(j))
• 가진 크기의 행렬 m X nD 구축을 축적하고, 그 행 및 열 요소의 삭제. 그 다음으로 작은 항목을 누적하고 모든 행과 열이 삭제 될 때까지 계속 누적하십시오.

예 A={0,1,4} 및 B={3,4} 있다면, D은 (왼쪽 위의 요소)이다

3 4

03 4

12 3

41 0

는 그리고 거리가 1와 4 및 3와 페어링 4에서 오는 0 + 2 = 2입니다.

Answer 1

이 문제는 때때로 스키와 스키어 문제로 불리는데, 길이가 다른 n 개의 스키와 m 개의 스키어가있는 점에 유의하십시오. 목표는 높이와 스키 길이의 차이의 합이 최소화되도록 스키와 스키를 맞추는 것입니다.

문제를 해결하려면 O (n^3) 시간이 필요한 최소 중량의 2 부분 일치를 사용할 수 있습니다.

아래의 간단한 동적 프로그래밍 알고리즘을 사용하면 O (n) 여분의 메모리로 O (n^2) 시간을 얻을 수 있습니다.

포인트가 이미 paper에 설명 된 알고리즘을 사용하여 정렬 된 경우 선형 시간으로 문제를 해결할 수 있습니다.

O (N^2) 동적 프로그래밍 알고리즘 : 상기 외측 for 루프의 각 반복 i 후

if (size(B) > size(A)) 
    swap(A, B); 
sort(A); 
sort(B); 
opt = array(size(B)); 
nopt = array(size(B)); 
for (i = 0; i < size(B); i++) 
    opt[i] = abs(A[0] - B[i]); 
for (i = 1; i < size(A); i++) { 
    fill(nopt, infinity); 
    for (j = 1; j < size(B); j++) { 
    nopt[j] = min(nopt[j - 1], opt[j - 1] + abs(A[i] - B[j])); 
    swap(opt, nopt); 
} 
return opt[size(B) - 1]; 

는 opt[j]는 요소 {B[0],..., B[j]}를 사용 {A[0],..., A[i]} 일치하는 최적의 솔루션을 포함한다.

이 알고리즘의 정확성은 a1이 b1과 일치하고 a2가 b2와 일치하고 a1이 < a2 인 경우 b1 < = b2와 일치하는 경우에 따라 달라집니다.

Answer 2

아니 그것은 예를 들어, 가장 좋은 대답이 아니다 : A : {3,7} 및 B : 당신이 선택하는 것입니다 {0,4} : {(3,4), (0,7)}이고 거리는 8이지만 {(3,0), (4,7)}을 선택해야합니다.이 경우 거리는 6입니다.

Answer 3

귀하의 답은 최소값에 대한 근사치를 제공하지만, 반드시 최소값 일 필요는 없습니다. 당신은 일반적으로 훨씬 더 쉽고 좋은 결과를주는 "욕심 많은"접근 방식을 따르고 있지만 최선의 답을 보장 할 수는 없습니다.

Answer 4

최적의 결과를 얻으려면 D에 할당 문제를 해결하십시오.

할당 문제는 전체 가장자리 가중치가 최소화되어 문제에 완벽하게 매핑되도록 이분 그래프에서 완벽한 일치를 찾습니다. 그것은 또한 P.에 있습니다.

EDIT 어떻게 OP 문제가 할당에 매핑되는지 설명합니다.

설명의 편의를 위해 작은 요소 집합을 특수 요소 e_k으로 확장하십시오.

A를 작업자 집합이라고하고 B를 작업 집합이라고합니다 (내용은 레이블 일뿐입니다).

비용을 A와 B의 요소 간 거리 (즉, D의 항목)로합니다. e_k과 무엇이든간에 거리는 0입니다.

그러면 우리는 비용이 최소화되도록 A와 B의 완벽한 일치 (즉 모든 작업자가 작업과 일치 함)를 찾고 싶습니다. 이 은 할당 문제 인입니다.