Mesure de distance entre deux ensembles de taille éventuellement différente

Question

J'ai 2 ensembles d'entiers, A et B, pas nécessairement de la même taille. Pour mes besoins, je prends la distance entre chaque 2 éléments a et b (entiers) pour être juste abs(a-b).

Je définissant la distance entre les deux ensembles de la manière suivante:

1. Si les ensembles sont de la même taille, de minimiser la somme des distances de toutes les paires [a, b] (a partir de A et B à partir de B), minimisation sur toutes les 'partitions paires' possibles (il y a n partitions possibles).
2. Si les ensembles n'ont pas la même taille, disons A de taille m et B de taille n, avec m < n, puis minimisez la distance de (1) sur tous les sous-ensembles de B qui sont de taille m.

Ma question est, est l'algorithme suivant (juste une supposition intuitive) donne la bonne réponse, selon la définition écrite ci-dessus.

• construire une matrice D de taille m X n, avec D(i,j) = abs(A(i)-B(j))
• Trouver l'élément de D plus petit, accumulez, et supprimer la ligne et la colonne de cet élément. Accumulez la plus petite entrée suivante et continuez à accumuler jusqu'à ce que toutes les lignes et colonnes soient supprimées.

par exemple, si A={0,1,4} et B={3,4}, puis D est (avec les éléments ci-dessus et à gauche):

3 4

03 4

12 3

41 0

Et la distance est 0 + 2 = 2, venant de jumelage 4 avec 4 et 3 avec 1.

Answer 1

Notez que ce problème est appelé parfois le problème des skis et les skieurs, où vous avez n skis et m skieurs de longueurs et hauteurs différentes. L'objectif est de faire correspondre les skis avec les skieurs afin que la somme des différences entre les hauteurs et les longueurs de ski soit minimisée.

Pour résoudre le problème, vous pouvez utiliser la correspondance biparti de poids minimum, ce qui nécessite O (n^3) temps.

Mieux encore, vous pouvez obtenir O (n^2) temps avec O (n) de la mémoire supplémentaire en utilisant l'algorithme de programmation simple dynamique ci-dessous.

optimale, vous pouvez résoudre le problème dans le temps linéaire si les points sont déjà triés en utilisant l'algorithme décrit dans ce paper.

O (n^2) algorithme de programmation dynamique:

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

après chaque itération de la boucle i externe for ci-dessus, opt[j] contient la solution correspondant à {A[0],..., A[i]} en utilisant les éléments {B[0],..., B[j]}. L'exactitude de cet algorithme repose sur le fait que dans toute correspondance optimale si a1 correspond à b1, a2 est apparié avec b2, et a1 < a2, puis b1 < = b2.

Answer 2

Non Ce n'est pas une meilleure réponse, par exemple: A: {} et 3,7- B: {} 0,4 vous choisirez: {(3,4), (0,7)} et la distance est 8 mais vous devez choisir {(3,0), (4,7)} dans ce cas la distance est 6.

Answer 3

Votre réponse donne une bonne approximation du minimum, mais pas nécessairement le meilleur minimum. Vous suivez une approche "gourmande" qui est généralement beaucoup plus facile, et donne de bons résultats, mais ne peut garantir la meilleure réponse.

Answer 4

Afin d'obtenir le meilleur, résolvez le problème d'affectation sur D. Le problème d'affectation trouve une correspondance parfaite dans un graphique bipartite, de sorte que le poids total des bords est minimisé, ce qui correspond parfaitement à votre problème. C'est aussi dans P.

EDIT pour expliquer comment le problème de l'OP correspond à l'affectation.

Pour simplifier l'explication, étendent l'ensemble plus petit avec des éléments spéciaux e_k. Soit A l'ensemble des travailleurs, et B l'ensemble des tâches (le contenu n'est que des étiquettes).

Que le coût soit la distance entre un élément A et B (à savoir une entrée de D). La distance entre e_k et n'importe quoi est 0.

Ensuite, nous voulons trouver une correspondance parfaite de A et B (c'est-à-dire que chaque travailleur est associé à une tâche), de sorte que le coût soit minimisé. Ce est le problème d'affectation.