Оптимизация брекетов для турнира - PullRequest
Новая
       20

Оптимизация брекетов для турнира

2 голосов
/ 18 марта 2012

Я строю систему, которая будет создавать турнир на основе списка претендентов.

У претендентов есть свойства, которые могут помешать их поместить в скобки вместе, например, пол, вес,уровень квалификации и т. д.

В некоторых случаях это становится довольно сложным:

  • претендент может подняться на одну весовую категорию, но никогда не опускается
  • Пол может быть смешаннымопределенного возраста.

Каков будет хороший способ, чтобы эти люди попали в оптимальные скобки (например, размеры 4, 8, 16)?Есть ли известный алгоритм для этого без попытки всех перестановок?

1 Ответ

5 голосов
/ 18 марта 2012

Это называется проблемой удовлетворения ограничений (CSP).Один из самых простых и во многих случаях наиболее эффективных способов ее решения - это поиск методом "грубой силы" с возвратом.

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

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

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

AIMA имеет отличную главу о CSP: http://aima.cs.berkeley.edu/newchap05.pdf

...