Medida de distancia entre dos conjuntos de tamaño posiblemente diferente

Question

Tengo 2 conjuntos de enteros, A y B, no necesariamente del mismo tamaño. Para mis necesidades, tomo la distancia entre cada 2 elementos a y b (enteros) para que sea solo abs(a-b).

estoy definiendo la distancia entre los dos conjuntos como sigue:

1. Si los conjuntos son del mismo tamaño, minimizar la suma de las distancias de todos los pares [a, b] (a partir de A y B desde B), minimización sobre todas las posibles 'particiones de pares' (hay n! particiones posibles).
2. Si los conjuntos no son del mismo tamaño, digamos A de tamaño m y B de tamaño n, con m < n, luego minimice la distancia desde (1) sobre todos los subconjuntos de B que son de tamaño m.

Mi pregunta es, es el siguiente algoritmo (solo una suposición intuitiva) da la respuesta correcta, de acuerdo con la definición escrita anteriormente.

• construir una matriz de D de tamaño m X n, con D(i,j) = abs(A(i)-B(j))
• Encontrar el elemento más pequeño de D, acumularlo, y eliminar la fila y la columna de ese elemento. Acumule la siguiente entrada más pequeña y continúe acumulándose hasta que se eliminen todas las filas y columnas.

por ejemplo, si A={0,1,4} y B={3,4}, entonces D es (con los elementos por encima ya la izquierda):

3 4

03 4

12 3

41 0

Y la distancia es 0 + 2 = 2, procedente de emparejamiento con 44 y 3 con 1.

Answer 1

Tenga en cuenta que este problema se conoce a veces como el problema de esquís y esquiadores, donde tiene n esquís ym esquiadores de diferentes longitudes y alturas. El objetivo es hacer coincidir los esquís con los esquiadores para que la suma de las diferencias entre alturas y longitudes de esquí se minimice.

Para resolver el problema, puede usar una coincidencia bipartita de peso mínimo, que requiere O (n^3) tiempo.

Mejor aún, puede lograr O (n^2) tiempo con O (n) memoria adicional utilizando el algoritmo de programación dinámico simple a continuación.

De manera óptima, puede resolver el problema en tiempo lineal si los puntos ya están ordenados usando el algoritmo descrito en este paper.

O (n^2) dinámica algoritmo de programación:

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

después de cada iteración i del exterior for bucle anterior, opt[j] contiene la solución óptima a juego {A[0],..., A[i]} utilizando los elementos {B[0],..., B[j]}.

La exactitud de este algoritmo se basa en el hecho de que en cualquier coincidencia óptima si a1 se combina con b1, a2 se combina con b2, y a1 < a2, entonces b1 < = b2.

Answer 2

No, no es una mejor respuesta, por ejemplo: A: {3,7} y B: {0,4} que se elija: {(3,4), (0,7)} y distancia es 8 pero debe elegir {(3,0), (4,7)} en este caso la distancia es 6.

Answer 3

Su respuesta da una buena aproximación al mínimo, pero no necesariamente el mejor mínimo. Está siguiendo un enfoque "codicioso" que, en general, es mucho más fácil y ofrece buenos resultados, pero no puede garantizar la mejor respuesta.

Answer 4

Para obtener el nivel óptimo, resuelva el problema de asignación en D.

El problema de asignación encuentra una coincidencia perfecta en un gráfico bipartito de modo que se minimiza el peso total del borde, que se adapta perfectamente a su problema. También está en P.

EDIT para explicar cómo se relaciona el problema de OP en la asignación.

Para simplificar la explicación, amplíe el conjunto más pequeño con los elementos especiales e_k.

Deje A ser el conjunto de trabajadores, y B sea el conjunto de tareas (los contenidos son solo etiquetas).

Deje que el costo sea la distancia entre un elemento en A y B (es decir, una entrada de D). La distancia entre e_k y cualquier cosa es 0.

Luego, queremos encontrar una coincidencia perfecta de A y B (es decir, cada trabajador se corresponde con una tarea), de modo que el costo se reduce al mínimo. Este es el problema de asignación.