Алгоритм: устранение игроков, у которых больше нет шансов на победу в турнире
Я работал над алгоритмом для этой задачи, но не могу понять. Проблема ниже:
В турнире с участием X игроков каждый игрок делает ставку на исходы баскетбольных матчей НБА.
За угадывание правильного исхода матча игрок получает 3 очка, за угадывание MVP матча — 1 очко, за оба неверных — 0 очков.
Алгоритм должен быть в состоянии определить, не может ли определенный игрок занять первое место в этой игре со ставками.
Например, предположим, что в лиге всего 30 игр, поэтому максимальное количество очков, которое игрок может получить за правильное угадывание, составляет (3+1)*30=120.
В таблице ниже вы можете увидеть игроков X, Y и Z. Игрок X правильно угадал уже 20 матчей, поэтому у него 80 очков. У игроков Y и Z по 26 и 15 очков, а поскольку осталось всего 10 матчей, даже если они правильно угадают все оставшиеся 10, этого будет недостаточно, чтобы занять первое место. Поэтому алгоритм определил, что они выбывают из игры.
Задача на выбывание бейсбола кажется наиболее похожей на эту задачу, но это не совсем она.
Как мне построить редукцию задачи о максимальном потоке, чтобы она соответствовала этой задаче?
Спасибо.
Игроки делают ставки перед каждым матчем, и мы знаем, что их ставки да.
Мы знаем только ставки на следующий матч? или мы знаем ставки на следующий матч, один за другим и так далее?
Ответы 1
Я не понимаю, почему вы смотрите на очень сложные алгоритмы максимального потока. Это может понадобиться для очень сложных вещей (особенно когда пары приводят к результатам с нулевой суммой, а порядок / оставшиеся пары начинают иметь значение -> !намного! сложнее провести анализ наихудшего случая).
Может быть, проблема с бейсболом, о которой вы упоминаете, является одной из таких (не проверял). Но ваш вариант использования звучит тривиально.
1. Get current leader score LS
2. Get remaining matches N
3. For each player P
4. Get current player score PS
5. Eliminate iff PS + 3 * N < LS
(assumes parallel progress: standings always synced to all players P have played M games
-> easy to generalize though)
Это просто. Учитывая ваше описание, ничто не мешает нам предположить наихудшую производительность любого другого игрока, иначе говоря, это допустимый сценарий, при котором каждый другой игрок ошибается для всех предстоящих предположений -> счет S игрока P может оставаться на уровне S для всех оставшихся игр.
Все может быстро измениться на NP-сложные проблемы принятия решений, когда есть более сложные побочные ограничения (например, статистические распределения/ожидания).
Что такое ввод? Делают ли игроки ставки заранее на все матчи сезона? Знаем ли мы их ставки?