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

Question

Я делаю клиента для поиска партнеров, который объединяет 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 команд, где выбор предпочитаемых товарищей по команде будет осуществляться с помощью функции поиска.Я понимаю, что эта система может быть не самой лучшей в своих целях, однако это интересная проблема, и я хотел бы найти эффективное решение, изучая что-то по пути.

Answer 1

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

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

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

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

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

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

Answer 2

Сначала отказ от ответственности.

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

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

---

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

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

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

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

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

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

5. Конечно, могут быть и другие вещис учетом ...

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