2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 соответствие элементов групп
Сообщение29.10.2015, 11:25 
Друзья!

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

 
 
 
 Re: соответствие элементов групп
Сообщение29.10.2015, 13:21 
Аватара пользователя
Так это "задача о назначениях", о ней много в сети есть

 
 
 
 Re: соответствие элементов групп
Сообщение29.10.2015, 13:36 
iancaple в сообщении #1068008 писал(а):
Так это "задача о назначениях", о ней много в сети есть
Спасибо! Нашел в сети Венгерский алгоритм, сейчас потестирую.

 
 
 
 Re: соответствие элементов групп
Сообщение29.10.2015, 13:42 
Аватара пользователя
Маленькое занудство. Слово "группа" для математиков имеет вполне определенный смысл, который не имелся в виду в данном вопросе. Сначала это немного сбило с толку :-(
С точки зрения математики тут не "группы", а "множества" элементов.

 
 
 
 Re: соответствие элементов групп
Сообщение29.10.2015, 15:23 
provincialka в сообщении #1068018 писал(а):
Маленькое занудство. Слово "группа" для математиков имеет вполне определенный смысл, который не имелся в виду в данном вопросе. Сначала это немного сбило с толку :-(
С точки зрения математики тут не "группы", а "множества" элементов.
Прошу прощения - не силен в математической терминологии (да и самой математике не очень).

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group