Trouver le 2x2 la plus optimale des correspondances entre les collections hétérogènes

Question

J'ai un problème:

J'ai une classe A et classe B, dont les objets par exemple peuvent être inspectés programatically être semblables ou différents les uns des autres dans différentes les montants. Par exemple, ils peuvent correspondre parfaitement, ou être très différents (même si les classes sont différentes, elles peuvent toujours représenter la même information et être notées identiques.)

Maintenant, étant donné deux collections, une de A et une de B , quelle serait la meilleure façon de jumeler les As et les Bs de manière à ce qu'ils soient mieux adaptés, en laissant certains orphelins si la collection est plus grande que l'autre ou si certains As ou Bs sont simplement trop différents pour être appariés ? Ma première tentative a été de créer un tableau à deux dimensions, où chaque cellule était le «score» du match (0 = parfait, avec des nombres plus élevés étant pire) et récursif à travers chaque chemin à la recherche du score accumulé le plus bas. Cela fonctionne et les résultats sont parfaits, mais il est horriblement lent.

Des idées sur des algorithmes plus efficaces?

Dans le cas où vous vous poseriez la question, ma classe A représente un canal d'entrée de mixage audio, et mon B représente l'état persistant de la même chose (appelé une scène). Le problème que j'essaie de résoudre est de savoir comment importer une scène dans une table de mixage existante, où la scène (B) pourrait être légèrement, voire très différente de l'une des voies existantes (A). Je ne veux pas juste ajouter des canaux (A) si je peux légèrement modifier pour correspondre. Par exemple, je pourrais pourrais ajouter un insert d'effet au A afin de correspondre parfaitement avec le B et éviter d'avoir à ajouter une autre A.

Mike

Answer 1

Cela ressemble à un problème de correspondance bipartites et peut probablement être résolu avec une solution standard max-flow/mincut en utilisant la métrique de similarité pour les bords de pondération.

This maybe helpful

Answer 2

Je n'ai pas un algorithme, une simple suggestion générale. Vous pourriez essayer des possibilités d'échantillonnage aléatoire jusqu'à ce que vous ayez passé le plus de temps possible et que vous ayez choisi la meilleure option que vous ayez trouvée en cours de route. Cette approche ne trouve généralement pas la solution optimale, mais elle est généralement très facile à programmer. Et selon le problème, il peut se rapprocher suffisamment pour un optimum. Vous pourriez expérimenter et voir comment la qualité s'améliore à mesure que le nombre d'échantillons aléatoires augmente. Si vous avez de la chance, un petit nombre d'échantillons peut suffire.

Answer 3

Je le ferais heuristiquement.

Commencez par collecter un ensemble de correspondances exactes.

Ensuite, ayez un seuil et collectez des correspondances mieux que ce seuil.

Augmentez le seuil et répétez jusqu'à ce que l'un ou les deux ensembles soient épuisés.

Vous disposez maintenant d'une correspondance d'essai qui n'est peut-être pas la meilleure.

Exécutez un grand nombre de cycles de recuit simulé, dans lequel vous permutez aléatoirement des liens correspondants, et les gardez ou non basé sur une probabilité qui dépend de leurs coûts respectifs.

Ceci vous permet d'explorer l'espace correspondant, et s'il y a de meilleurs correspondances à proximité, il devrait les trouver.