Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.07.2011, 16:40
Новичок

Отправить личное сообщение для maxfisher Посмотреть профиль Найти все сообщения от maxfisher
 
Регистрация: 25.06.2009
Сообщений: 24

Паросочетание
Есть N<30000 пользователей, у каждого пользователя есть K<8 интересов. Нужно разбить пользователей по парам за интересами, алгоритм должен быть быстрым и эффективным.

Другая подзадача: нужно для каждого пользователя предложить список более подходящих пользователей для него за интересами.

Как это решать?
  #2  
Старый 09.07.2011, 08:29
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Полагаю, подойдет алгоритм Эдмондса (не Эдмондса-Карпа!)
  #3  
Старый 09.07.2011, 15:33
Новичок

Отправить личное сообщение для maxfisher Посмотреть профиль Найти все сообщения от maxfisher
 
Регистрация: 25.06.2009
Сообщений: 24

?
Объясните пожалуйста поподробнее как мне использовать этот алгоритм?
  #4  
Старый 09.07.2011, 17:04
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Пользователи - узлы
Ребрами соединены пользователи с общими интересами
Указанный алгоритм найдет паросочетание - максимальное по количеству подмножество ребер, разбивающее пользователей на пары (и не пересекающееся по узлам). Идеальный случай - все пользователи разбиты на пары (реберное покрытие)
  #5  
Старый 09.07.2011, 19:49
Новичок

Отправить личное сообщение для maxfisher Посмотреть профиль Найти все сообщения от maxfisher
 
Регистрация: 25.06.2009
Сообщений: 24

этот алгоритм подойдет, но мне в принципе не нужно максимальное паросочетание. Меня устроит достаточно неплохое паросочетание, но алгоритм должен работать очень быстро.
  #6  
Старый 09.07.2011, 21:28
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

А сколько интересов всего?
Возможно, какой-либо вид кластеризации подойдет для первичного разбиения на небольшие группы.
  #7  
Старый 09.07.2011, 21:33
Новичок

Отправить личное сообщение для maxfisher Посмотреть профиль Найти все сообщения от maxfisher
 
Регистрация: 25.06.2009
Сообщений: 24

Сейчас есть около 50 стандартных интересов, но пользователи могут создавать свои собственные.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Паросочетание максимального веса в двудольном графе Shl Графы 2 23.10.2010 14:27
Наибольшее паросочетание Fredo Реализация, исходники, языки 1 02.05.2010 20:56
Паросочетание в недвудольном графе гость Графы 8 05.09.2008 20:43
Паросочетание максимального веса гость Графы 5 30.07.2007 11:40