Java: Question de conception - paires minimales entre les ensembles

Question

J'ai deux ensembles d'objets Animal. La distance entre les animaux est définie en utilisant un algorithme spécifique qui regarde leurs traits. J'essaye de concevoir une méthode pour trouver la paire des deux ensembles (un de chaque) qui minimise la distance.

Une idée que j'avais: créer une classe Tuple paramétrée pour coupler Animals. Créez un PriorityQueue avec un comparateur pour trier Tuple<Animal> en fonction de la distance entre les deux membres. Ensuite, choisissez la première paire du PriorityQueue.

Est-ce une bonne conception, ou est-ce un gaspillage? Je crois qu'il fonctionnerait en O (m + n), où m et n sont les tailles de chaque collection.

Si Tuple est une classe paramétrée, comment cela fonctionne-t-il pour utiliser un comparateur sur celui-ci qui ne fonctionne que sur Animal? Je souhaite utiliser cette méthode findMinimalPair pour créer un arbre couvrant minimisant les distances d'un graphique de Animal objets. Que se passe-t-il si je fais cela en continuant à faire sauter les paires du PriorityQueue, en vérifiant que chaque paire contient toujours un membre de chaque collection?

Voici un exemple de base. Voici les distances:

 A0  A1  A2  A3 
A0 0  20  33  8 
A1 20  0  102 73 
A2 33  102 0  6 
A3 8  73  6  99 

On suppose que les collections sont:

A0

A1, A2, A3

ici serait l'ordre de tri de tuples, par distance:

(A0, A3) - 8 
(A0, A1) - 20 
(A0, A2) - 33 

Nous voyons donc que A3 est le plus proche. A3 est ensuite déplacé dans la première collection:

A0, A3

A1, A2

Encore une fois, nous vérifions pour une paire minimale:

(A3, A2) - 6 
(A0, A1) - 20 
(A0, A2) - 33 
(A3, A1) - 73 

maintenant A2 est prise. Regarde comment ça marche?

C'est ce que j'ai fini par faire. Commentaires?

Answer 1

En fait, vous devrez créer m * n tuples pour avoir tous les tuples possibles, ce qui prendra O (mn). Vous devez trier la liste des tuples qui prennent au minimum O (mn * log (mn)), donc la complexité est O (mn * log (mn)) - même avec la file d'attente prioritaire (vous aurez des insertions mn, avec O (log (mn)) complexité par chacun).

EDIT

Je viens de voir une erreur dans la solution ci-dessus - Si vous voulez juste trouver la paire minimale, la complexité réelle est O (mn) car vous avez besoin d'un chemin sur toutes les paires. Si vous voulez avoir une liste de toutes les paires triées par leur distance pour avoir le spanning tree minimum, alors c'est O (mn * log (mn)).En tout cas, ce n'est pas O (m + n)

Answer 2

Ma suggestion est que vous utilisiez les tuples qui vous donneront O (n.m) (pas O (n + m)). Et puis utilisez l'algorithme de tri de seau bucket sort où chaque seau sera un tuple .. donc vous obtiendrez O (n.m) sur votre problème. (d'après ce que j'ai compris de votre problème, vous pouvez utiliser le tri par seau, sinon vous devrez utiliser un algorithme O (nlogn)

Answer 3

Si vous voulez trouver les distances entre tous les tuples possibles entre l'ensemble 1 et l'ensemble 2, pense que vous pourriez être bloqué avec des boucles imbriquées, résultant en O (m * n). Je ne pense pas qu'il y ait moyen d'obtenir O (m + n). Si je me souviens bien, vous avez besoin d'un graphique complet avant de pouvoir trouver son arbre recouvrant minimum. Il semble que le graphique aura des bords O (V^2) (puisqu'il y a une distance entre chaque paire d'animaux), donc si vous utilisez l'algorithme de Prim pour trouver des arbres couvrant minimum, vous pouvez utiliser la liste de tas et d'adjacences de Fibonacci (qui est O (E + V log (V))).

http://en.wikipedia.org/wiki/Prim%27s_algorithm