Алгоритм Round Robin с добавлением и удалением людей
Хорошо, в этом codepen я уже нашел алгоритм планирования турниров Round Robin: https://codepen.io/Piconey/pen/mwPamw
var players = [
{
playerName: 'Person 1',
},
{
playerName: 'Person 2',
},
{
playerName: 'Person 3',
},
{
playerName: 'Person 4',
},
{
playerName: 'Person 5',
},
{
playerName: 'Person 6',
},
{
playerName: 'Person 7',
},
{
playerName: 'Person 8',
},
{
playerName: 'Person 9',
},
{
playerName: 'Person 10',
},
{
playerName: 'Person 11',
},
{
playerName: 'Person 12',
},
{
playerName: 'Person 13',
},
{
playerName: 'Person 14',
},
{
playerName: 'Person 15',
},
{
playerName: 'Person 16',
},
];
var numberOfRounds = players.length - 1;
function generateRounds() {
for(i = 0; i < numberOfRounds; i++) {
document.write('<h1 class = "round">'+'Round ' + (i+1) + '</h1>');
for (var j = 0; j < players.length / 2; j++) {
document.write('<div class = "match">' + players[j].playerName + " - " + players[players.length - 1 - j].playerName +'</div>');
}
players.splice(1, 0, players[15]);
players.pop();
}
}
generateRounds();
Я использую его для быстрых свиданий, даже если вы можете встречаться со всеми.
Моя проблема: После каждого раунда новые люди могут присоединиться к событию или покинуть его (если им станет скучно ;)
Примечание: опоздавшим не нужно встречаться со всеми, потому что они уже пропустили x раундов. Примечание 2. Если уходит много людей, было бы неплохо ограничить количество раундов, чтобы людям не приходилось так долго ждать между свиданиями.
Ааа, да, это то, что я пытался объяснить, но не смог ;-) Если присоединяется новый человек, добавляется только один раунд. Это будет опоздавший, поэтому, вероятно, более логично, если это произойдет после 1, 2 или 3 раунда.
В вашем конкретном случае. Скоростное свидание уже закончилось, так что он опоздал. Но если он был на один раунд раньше, нужно добавить новый раунд, и у него есть 2 даты.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 1
Для задачи двустороннего сопоставления, такой как быстрые свидания между отдельными группами мужчин и женщин, вы можете использовать алгоритм максимального потока.
Построить график в 4 слоя:
- Исходный узел S
- Один узел для каждого человека
- Один узел для каждой женщины
- Узел стока T
- Полностью соедините слои 1 и 2 с граничной емкостью 1.
- Полностью соедините слои 2 и 3 с граничной емкостью 1.
- Полностью соедините слои 3 и 4 с краевой емкостью 1.
Когда человек добавлен, добавьте его как новый узел на уровне 2 или 3 и полностью соедините его с соседними слоями, как указано выше.
Когда человек удаляется, удалите его узлы в слоях 2 и 3 и все ребра из его узла.
В каждом раунде используйте алгоритм максимального потока для определения ваших пар. После раунда установите емкость ребер уровня 2-> уровня 3, участвующих в сопряжении, на 0. Это предотвратит повторное сопоставление тех же двух людей в последующих раундах.
Эвристика: вы можете изменить алгоритм максимального потока, чтобы объединить в пары людей с наименьшим количеством дат или с наибольшим количеством просиженных раундов, поэтому, если существует нечетное количество людей, ни самый новый человек, ни один и тот же человек не будут просиживать раунды.
Расширения: вы можете реализовать настройки, чтобы ограничить набор потенциальных совпадений, отфильтровав набор ребер, добавленных между слоями 2 и 3.
Время: примерно O(n^3) за раунд
Некоторый пакет максимального потока javascript на github, никогда не пробовал, так что удачи: https://github.com/orcaman/flownetwork
Для задачи сопоставления всех и каждого вы должны заменить алгоритм максимального потока более сложным алгоритмом Блоссома.
Как и максимальный поток, этот алгоритм итеративно уточняет совпадения, находя увеличивающие пути, а затем изменяя текущий набор совпадений.
Вход для этого алгоритма:
- Добавить узел для каждого человека
- Полностью соединить все узлы
Как и в двудольном случае, в конце каждого раунда удаляйте все ребра, соответствующие совпадениям в предыдущих раундах, предотвращая сопоставление тех же двух людей.
Когда новый человек присоединяется, добавьте узел и полностью соедините его с другими людьми.
Когда человек уходит, удалите его узел и все связанные ребра.
Алгоритм Blossom лучше описан здесь https://en.wikipedia.org/wiki/Blossom_algorithm
Быстрый поиск показывает несколько реализаций javascript этого алгоритма, ваш пробег может отличаться.
Ого, это звучит сложно (я уже потерял вас из-за упоминания исходного узла S). Может быть, я должен забыть об этом и быть проще...
Ха-ха-ха :D Да, это было немного перебором! Как насчет: выстроить 8 столов со стульями на каждом конце, разделить группы на мужчин и женщин, каждый раунд мужчины сдвигают по одному влево (с закруглением). Чтобы кто-то мог присоединиться, он должен занять свободное место. Если двое уходят группой, пропустите их столик. Если один человек уйдет, надеюсь, кто-то присоединится :D
Привет @dhakim, отличный ответ, спасибо. Как вы думаете, мы можем использовать npmjs.com/package/… для достижения этой цели? И если да, можете ли вы привести пример использования? Я изо всех сил пытаюсь извлечь пары после каждого раунда.
@David'G' Форд Фулкерсон должен работать, да. Я никогда не использовал пакет, хотя. Библиотека должна иметь возможность выводить график с назначенным максимальным потоком. Затем вы просто исследуете ребра, которым он назначил поток, те ребра, которые пересекаются между людьми и имеют назначенный поток, являются парами, которые он выбрал. Вы удаляете эти пары из своего начального графика перед следующим раундом, предотвращая их повторное сопоставление в будущих раундах.
@dhakim Мне удалось это сделать, но у меня проблемы с дублированием. Алгоритм возвращает обе стороны пары. Пример: если используются следующие элементы: A, B, C, D я получаю пары [[A, B], [B, A], [C, D], [D, C]] вместо просто [[A, B], [C, D]]. В настоящее время я вручную фильтрую результаты, чтобы удалить дубликаты, но столкнулся с проблемами при использовании 6 участников. У 1 участника 2 разные пары. Пример: за A, B, C, D, E & F я получаю [[A, B], [C, D], [B, E], [E, A], [D, F], [F, C]]. Как видите, A используется в двух разных парах. Любая идея о том, как я могу установить края?
Максимальный поток ограничит поток через каждое ребро. Если ребро от источника к A ограничено потоком 1, не более 1 потока может выйти из A. Какой поток назначен на ребра [A,B] и [A,E]? Какой поток назначен ребру [S, A]? Я предполагаю, что один из ребер просто установлен неправильно.
@DavidG О, также убедитесь, что алгоритм максимального потока настроен на использование целочисленных потоков. В противном случае он мог бы сделать что-то глупое, например разделить поток пополам по краям.
@dhakim Я использую целочисленные потоки. Кроме того, я использовал ваши указания, и все ребра имеют мощность 1. Когда раунд заканчивается, я устанавливаю емкость на 0. [A,B] и [E,A] имеют емкость 1. [S,A] иметь вместимость 1. Я дважды проверил. Я могу предположить, что проблема в том, что у меня 2 слоя и, возможно, они установлены неправильно. В том смысле, что в первом слое A есть 1, B есть 2 и т. д., а для создания второго слоя A есть 7, B есть 8 и т. д. И алгоритм не знает, что 1 и 7 одинаковы, и поэтому дублирование.
Есть ли другой способ создать слои вместо создания дополнительных узлов?
@DavidG Ха, упс! Я думаю, что моя конструкция неверна! Это может быть конструкция для сопоставления мужчин и женщин. Если вы поместите всех мужчин в слой 2, а всех женщин в слой 3, это должно работать для системы быстрых свиданий, но не для турнира «все для всех». Позвольте мне немного подумать и обновить ответ.
@dhakim Это будет потрясающе!! Вот краткий пример CodeSandbox, чтобы продемонстрировать, что я сейчас делаю, возможно, он вам поможет: В моем реальном коде я использую генераторы для каждого раунда, помощники и т. д. Если вам нужно, я даже могу предоставить полный исходный код, но я думаю, что вы поняли идею: D
Давайте продолжим обсуждение в чате.
С n людьми требуется n-1 раундов, чтобы каждый встречался со всеми остальными. Таким образом, с 16 людьми требуется 15 раундов. Допустим, новый человек присоединяется сразу после 15-го раунда. Тогда всем нужно встречаться с новым человеком, а новый человек должен встречаться со всеми, но раундов не осталось (есть ли?). Независимо от того, с кем встречается новый человек, 14 человек ничего не делают или повторяют свидания. Что вы хотите, чтобы произошло в этом сценарии?