Алгоритм создания команды по предпочтениям игрока

Я делаю клиент для подбора игроков, который объединяет 10 человек в две команды:

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

Затем из самых сильных отношений в этом наборе формируются две команды.

Как бы вы создали алгоритм, решающий эту задачу?

Пример:

Given players [a, b, c, d, e, f, g, h, i, j], '->' meaning a preference pick.

a -> b (weight: 4)
a -> c (weight: 3)
a -> d (weight: 2)
a -> e (weight: 1)

b -> d (weight: 4)
b -> h (weight: 3)
b -> a (weight: 2)
...and so on

Эта проблема кажется простой на первый взгляд (в конце концов, это всего лишь клиент для подбора партнеров), но, поразмыслив над этим некоторое время, кажется, что нужно учитывать довольно много отношений.

Изменить (вставлено из комментария): В идеале я бы избегал грубого подхода к масштабированию до более крупных игр, в которых требуется 100 игроков и 25 команд, где выбор предпочтительных товарищей по команде будет осуществляться с помощью функции поиска. Я понимаю, что эта система может быть не самой лучшей для своей цели, однако это интересная проблема, и я хотел бы найти эффективное решение, попутно чему-то научившись.


sorting partition-problem algorithm math
person SlickJava    schedule 09.06.2018    source источник
comment
SlickJava, можете ли вы поделиться фрагментом кода, где оспариваются?   -  person z atef    schedule 09.06.2018
comment
@zee, что ты имеешь в виду? Я разрабатываю систему подбора партнеров, и это была система создания команды, предложенная одним из моих пользователей, но я, кажется, не могу понять, как точно сформировать алгоритм, который эффективно учитывает все отношения.   -  person SlickJava    schedule 09.06.2018
comment
Учитывая эти крошечные числа: сделайте это методом грубой силы! В любом случае это (вероятно) NP-трудно, и с этими числами это небольшое пространство поиска (‹ = 30240; с большим количеством симметрий используется еще меньше).   -  person sascha    schedule 09.06.2018
comment
Вы пишете о 10 игроках, но в вашем примерном списке всего 9 символов, от a до i. Вам нужно добавить j, чтобы получить 10. И я согласен, что грубая сила должна хорошо работать на такой небольшой проблеме. И следует уточнить: вы хотите две команды, по пять человек в каждой? Я вычисляю только 252 возможности (комбинаторные 10 выбирают 5).   -  person Rory Daulton    schedule 09.06.2018
comment
(1) Вы не говорите, каков критерий предпочтения одного раздела другому. (2) Есть 10!/5!(10-5)! = возможно 252 раздела; перечислить их и максимизировать таинственный критерий предпочтения, указанный в пункте (1).   -  person AlexP    schedule 09.06.2018

Ответы (2)


arrow_upward
0
arrow_downward

Сначала оговорка.

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

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

Теперь перейдем к случаю, когда вы собираетесь весело провести время, изучая идею. Во-первых, для разделения десяти элементов на две группы по пять, существует просто select(10,5 )=252 возможности, поэтому, если системе не нужно делать это миллионы раз в секунду, вы можете просто подсчитать некоторый балл для всех из них и выбрать лучший. Возможно, самый простой способ — рассмотреть все 2^{10} = 1024 способа сформировать подмножество из 10 элементов, а затем изучить те, где размер подмножества равен 5. Но может быть и лучше, подробнее, доступные инструменты, в зависимости от языка или фреймворка . Комбинация 10-выберите-5 — это одна группа, не взятые предметы — это другая группа.

Итак, каков будет счет комбинации? Теперь смотрим на наши предпочтения.

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

  2. Точно так же для каждого неудовлетворенного предпочтения мы можем добавить штраф в зависимости от его веса.

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

  4. Еще одна вещь, которую следует учитывать, — это баланс команды. Поскольку единственными данными пока являются предпочтения (которые вполне могут оказаться недостаточными), дисбаланс означает, что у одной команды удовлетворены многие из их предпочтений, а у другой лишь немногие, если они вообще есть. Таким образом, мы добавляем еще один штраф в зависимости от абсолютной разницы (сумма удовлетворенности первой команды) и (сумма удовлетворенности второй команды).

  5. Конечно, могут быть и другие факторы, которые нужно учитывать...

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

person Gassa    schedule 09.06.2018
comment
В идеале я бы избегал грубого подхода к масштабированию для более крупных игр, в которых требуется 100 игроков и 25 команд, где выбор предпочтительных товарищей по команде будет осуществляться с помощью функции поиска. Я понимаю, что эта система может быть не самой лучшей для своей цели, однако это интересная проблема, и я хотел бы найти эффективное решение, попутно чему-то научившись. - person SlickJava; 09.06.2018
comment
@SlickJava Возможно, для некоторых критериев оценки алгоритм максимальный поток с минимальной стоимостью найдет оптимальное решение за полиномиальное время. Но если вам нужны большие размеры, укажите это в вопросе или, может быть, даже задайте отдельный вопрос. Этот ответ касается того, что содержит вопрос на момент написания. - person Gassa; 09.06.2018

arrow_upward
0
arrow_downward

Я бы подумал о способе сопоставить предложенные команды с выбором людей, например, сопоставить предложенные команды с весами.

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

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

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

Если вы включаете в качестве отправной точки все выборы или выборы, основанные на приоритете ABCDE... и затем приоритете BCDE... и затем приоритете CDEF... тогда у вас есть свойство, что если кто-то отправит идеальный выбор, ваш алгоритм распознает его как таковой .

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

person mcdowella    schedule 10.06.2018
comment
Я думаю, что имитация отжига будет работать лучше, чем восхождение на холм. - person qwr; 30.10.2018