алгоритм сопоставления

Question

Я пишу приложение, которое делит совокупность пользователей на пары с целью совместного выполнения задачи.Каждый пользователь может указать различные предпочтения своего партнера, например,

• пол
• язык
• возраст
• местоположение (обычно в пределах X миль / километров)откуда живет пользователь)

В идеале я бы хотел, чтобы пользователь мог указать, является ли каждое из этих предпочтений «хорошим» или «обязательным», например «Я хотел бы»Предпочитаю, чтобы меня подбирали носителем английского языка, но я не должен совпадать с женщиной ".

Моя цель - максимально повысить общее среднее качество матчей.Например, предположим, что в системе 4 пользователя, A, B, C, D. Эти пользователи могут быть сопоставлены тремя способами:

Option 1     Match Score
A-B           5
C-D           4
---
Average       4.5

Option 2     Match Score
A-C           2
B-D           3
---
Average       2.5

Option 3     Match Score
A-D           1
B-C           9
---
Average       5

Так что в этом надуманном примере будет выбран третий вариантпотому что он имеет самое высокое общее качество совпадения, хотя A и D. не очень хорошо сопоставлены.

Существует ли алгоритм, который может помочь мне:

• вычислить "«оценки совпадений», показанные выше
• , выберите пары, которые максимизируют среднюю оценку совпадений (при соблюдении абсолютных ограничений каждого пользователя)

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

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

Наконец, эта система вычисления результатов матчей имаксимизация общего среднего - это просто эвристика, которую я придумал сам.Если есть намного лучший способ для расчета пар, пожалуйста, дайте мне знать.

Обновление

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

Answer 1

Какие алгоритмы максимального соответствия вы рассматривали?Сначала я читаю ваш вопрос слишком поспешно: кажется, вы не обязательно ограничиваетесь двудольным графом.Это кажется сложнее.

Answer 2

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

Answer 3

Чтобы найти максимальное совпадение в произвольном графе, существует взвешенный вариант алгоритма сопоставления Эдмонда:

http://en.wikipedia.org/wiki/Edmonds's_matching_algorithm#Weighted_matching

См. Сноски там.

Answer 4

Судя по всему, ваша проблема не состоит из двух частей, поэтому мне кажется, что вы ищете соответствие максимального веса в общем графике. Я не завидую задаче написания этого, так как алгоритм сокращения расцвета Эдмонда нелегко понять или реализовать эффективно. Существуют реализации этого алгоритма, одним из таких примеров является библиотека C ++ LEMON (http://lemon.cs.elte.hu/trac/lemon).. Если вы хотите сопоставить максимальный вес с максимальным количеством элементов, вам придется использовать алгоритм сопоставления максимального веса и добавить большой вес (сумма всех весов) к каждому ребру, чтобы сделать максимальную мощность множества в качестве первого приоритета.

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

Answer 5

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

Для вашего приложения вы должны установить предпочтения человека в качестве ожидаемых данных и каждого другого человека, которого высравните с измеренными данными.Вы хотели бы отфильтровать «измеренные данные», чтобы исключить такие случаи, как «не должны совпадать с женщинами», которые вы упоминаете в исходном вопросе, перед выполнением сравнения.

Другой вариант - использованиеАлгоритм хи-квадрат.