Эффективность алгоритма поиска совпадений
Я разрабатываю приложение, которое помогает пользователю создавать игры, формируя лучшие команды.
Например, предположим, что 30 человек ждут в опросе, чтобы играть в баскетбол. В баскетбол играют 10 игроков (5 против 5). Из 30 человек, ожидающих, чтобы их выбрали, алгоритм выбирает наилучшую возможную комбинацию 5 против 5, чтобы играть друг против друга.
(Для этого алгоритм ищет комбинацию игроков с максимальной вероятностью ничьей. Это вычисляется с использованием двух количественных показателей, характеризующих каждого игрока: средний навык игрока и коэффициент достоверности предполагаемого рейтинга.)
Я хочу посмотреть, как быстро работает этот алгоритм.
Для этого нужно пройти все возможные комбинации игроков. Так что в этом случае общее количество комбинаций является C(30,10) правильно??
Можем ли мы сказать, что алгоритм равен O(n!), Где n - общее количество игроков, ожидающих игры?
Эта проблема NP-полная?? Если да, может ли кто-нибудь дать мне краткий способ объяснить, почему он является NP-полным (не полное доказательство, достаточно только веских аргументов).
Большое спасибо!:)
1 ответ
Неясно, как следует комбинировать средний навык и факторы достоверности, но, скорее всего, найти полиномиальное решение в обоих nа также k (количество игроков и количество игроков в команде) будет так же сложно, как и доказать P = NP.
Моя интуиция основана на том факте, что проблема суммы подмножеств NP-Hard, и текущая проблема кажется более сложной, чем она.
В нашем случае, даже для простого подхода, который бы игнорировал факторы доверия и просто суммировал навыки игрока, чтобы получить силу команды (1), это, кажется, NP-Complete.
Это потому, что даже если мы исправим одну команду, то есть знаем целевую сумму, NP будет сложно определить, есть ли другая команда с таким же счетом (2). Кроме того, отвечая на вопрос "есть ли равная команда?" это проще, чем ответить на вопрос "какой матч лучше для этой команды?".
Кроме того, найти наилучшее совпадение среди всех пар команд, вероятно, сложнее, чем найти наилучшее совпадение с одной фиксированной командой, поэтому это будет наглядной демонстрацией того, что данная задача сложнее, чем проблема с подмножеством сумм.
Примечания:
(1) Маловероятно, что учет факторов достоверности каким-либо образом упростит проблему (поскольку в конкретном случае, когда все они равны, мы все равно сталкиваемся с несоответствующими факторами достоверности).
(2) В задаче суммы подмножеств не делается никаких предположений о размере подмножества. Однако, если бы существовал известный алгоритм полиномиального времени, который нашел бы подмножество с суммой 0 за полиномиальное время для любого заданного размера, мы могли бы применить его для каждого возможного размера, и это привело бы к полиномиальному алгоритму для произвольного размера (который доказать P = NP).
(3) Значение 0 в ограничении суммы = 0 не является существенным. Это может быть любое произвольное значение. Например, поскольку мы зафиксировали размер, мы можем просто вычесть из всех элементов значение, равное targetSum / size, и теперь мы будем искать подмножество с суммой 0.
По поводу других вопросов:
Таким образом, в этом случае общее число комбинаций является правильным (C 30,10)?
Нет, на самом деле это C(30, 5) * C(25, 5) / 2, потому что сначала нам нужно выбрать 5 игроков для первой команды, а затем выбрать из остальных 5 игроков для второй команды. Деление на два выполняется потому, что в противном случае каждая пара будет учитываться дважды, и мы, вероятно, не хотим различать команды.
Можем ли мы сказать, что алгоритм равен O(n!), Где n - общее количество игроков, ожидающих игры?
Сложность перечисления методом грубой силы составляет O(n^2k / (k! * K!)), Где n - общее количество игроков, а k - размер команды. Таким образом, для маленьких k все в порядке. Подход является NP-полным, если мы рассмотрим оба n а также k в качестве переменных.
Сложность такая, потому что формула для комбинаций следующая:
C (n, k) = n * (n - 1) *.. * (n - k + 1) / (1 * 2 *.. * k),
и согласно предыдущему пункту, есть C(n, k) * C(n - k, k) / 2 возможностей.