Нахождение наиболее оптимальных 2х2 совпадений между гетерогенными коллекциями

Question

У меня проблема:

У меня есть класс A и класс B, чьи объекты экземпляров можно проверять программно, чтобы они были похожи или отличались друг от друга в различных количествах. Например, они могут идеально совпадать или быть совершенно разными (даже если классы разные, они все равно могут представлять одну и ту же информацию и могут быть одинаковыми).

Теперь, учитывая две коллекции, одну из A и одну из B, что было бы лучшим способом объединить As и B таким образом, чтобы они лучше подходили друг другу, оставляя некоторых сирот, если любая коллекция больше другой или если некоторые из As или B просто слишком разные, чтобы их можно было сопоставить?

Моей первой попыткой было создание 2-мерного массива, в котором каждая ячейка представляла собой «оценку» совпадения (0 = идеально, с большими числами хуже) и повторялась по каждому пути в поисках наименьшего накопленного значения. Это работает, и результаты превосходны, но это ужасно медленно.

Есть идеи по более эффективным алгоритмам?

Если вам интересно, мой класс A представляет входной канал аудиомикшера, а мой B представляет его постоянное состояние (называемое сценой). Проблема, которую я пытаюсь решить, состоит в том, как импортировать сцену в существующий микшер, где сцена (B) может немного или даже сильно отличаться от любого из существующих каналов (A). Я не хочу просто добавлять каналы (A), если бы я мог немного изменить любой, чтобы соответствовать. Например, я мог бы добавить вставку эффекта к A, чтобы идеально соответствовать B и избежать необходимости добавления другого A.

Mike

Answer 1

Это звучит как проблема согласования двудольных и, вероятно, может быть решена с помощью стандартного решения max-flow / mincut с использованием метрики подобия для взвешивания ребер.

Это может быть полезно

Answer 2

Я бы сделал это эвристически.

Сначала соберите набор точных совпадений.

Тогда имейте порог и собирайте совпадения лучше, чем этот порог.

Расширьте порог и повторяйте, пока один или оба набора не будут исчерпаны.

Теперь у вас есть пробный матч, который может быть не самым лучшим.

Выполните много циклов имитации отжига, в которых вы случайным образом переставляете соответствующие ссылки и сохраняете их или нет, основываясь на вероятности, которая зависит от их соответствующих затрат.

Это позволяет вам исследовать подходящее место, и если поблизости есть лучшие совпадения, он должен их найти.

Answer 3

У меня нет алгоритма, только общее предложение. Вы можете использовать возможности случайной выборки, пока не потратите столько времени, сколько захотите, и выбрать лучший вариант, который вы нашли на этом пути. Такой подход обычно не находит оптимального решения, но его обычно очень легко программировать. И в зависимости от проблемы, она может быть достаточно близка к оптимальной. Вы можете поэкспериментировать и посмотреть, как улучшается качество по мере увеличения числа случайных выборок. Если вам повезет, достаточно небольшого количества образцов.