Задача оптимизации - векторное отображение

Question

A и B являются наборами N размерных векторов (N=10), |B|>=|A| (|A|=10^2, |B|=10^5).Мера подобия sim (a, b) является точечным произведением (обязательно).Задача следующая: для каждого вектора a в A найти вектор b в B, чтобы сумма сходств ss всех пар была максимальной.

Моя первая попытка была жаднойалгоритм:

1. найдите пару с наибольшим сходством и удалите эту пару из A, B
2. повторяйте (1) до тех пор, пока A не станет пустым

Нотакой жадный алгоритм в этом случае неоптимален:

a_1=[1, 0]
a_2=[.5, .4]

b_1=[1, 1]
b_2=[.9, 0]

sim(a_1,b_1)=1
sim(a_1,b_2)=.9
sim(a_2,b_1)=.9
sim(a_2, b_2)=.45

Алгоритм возвращает [a_1,b_1] и [a_2, b_2], ss=1.45, но оптимальное решение дает ss=1.8.

Есть ли эффективный алгоритм?Для решения этой проблемы?Спасибо

Answer 1

Это, по сути, проблема соответствия в взвешенном двудольном графе . Просто предположим, что весовая функция f является точечным произведением (|ab|).
Я не думаю, что специальная структура вашей весовой функции сильно упростит задачу, так что вы почти наверняка найдете максимальное совпадение.

Вы можете найти несколько основных алгоритмов для этой проблемы в этой статье в википедии . Хотя, на первый взгляд, они не кажутся жизнеспособными для ваших данных (V = 10^5, E = 10^7), я все равно буду их исследовать: некоторые из них могут позволить вам воспользоваться преимуществами «хромого» набора вершин, с одной частью на порядки меньше, чем у других.

Эта статья также представляется актуальной, хотя и не содержит никаких алгоритмов.

Не совсем решение, но надеюсь, что оно поможет.

Answer 2

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