соответствие элементов групп

[AndreyL]

Друзья!

Возникла такая задача: есть две группы по $n$ элементов в каждой. Между каждым $i$-м эелементом первой группы и каждым $j$-м элементом второй группы назначена мера сходства-различия. Фактически это матрица $n$-на-$n$. Нужно каждому элементу первой группы сопоставить элемент второй группы, причем так, чтобы сопоставлялись максимально похожие элементы. Это сопоставление должно быть взаимно однозначным: каждому элементу первой группы соответствует только один элемент второй группы, каждому элементу второй группы соответствует только один элемент первой группы.
По идее тут нужно оптимизировать некоторую функцию от мер реализованных связей, например, сумму.
Подскажите, пожалуйста, существуют ли какие-то методы решения такой задачи за разумное время?

[iancaple]

Так это "задача о назначениях", о ней много в сети есть

[AndreyL]

iancaple в сообщении #1068008 писал(а):

Так это "задача о назначениях", о ней много в сети есть

Спасибо! Нашел в сети Венгерский алгоритм, сейчас потестирую.

[provincialka]

Маленькое занудство. Слово "группа" для математиков имеет вполне определенный смысл, который не имелся в виду в данном вопросе. Сначала это немного сбило с толку
С точки зрения математики тут не "группы", а "множества" элементов.

[AndreyL]

provincialka в сообщении #1068018 писал(а):

Маленькое занудство. Слово "группа" для математиков имеет вполне определенный смысл, который не имелся в виду в данном вопросе. Сначала это немного сбило с толку
С точки зрения математики тут не "группы", а "множества" элементов.

Прошу прощения - не силен в математической терминологии (да и самой математике не очень).

А за "задачу о назначениях" еще раз большое СПАСИБО! Погонял Венгерский алгоритм - решение абсолютно правильное (для проверки использовал все перестановки) и довольно быстрое. Этого и следовало ожидать, но проверить все равно надо было.