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

Question

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

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

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

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

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

Answer 1

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

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

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

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

AIMA имеет прекрасную главу о ППО: http://aima.cs.berkeley.edu/newchap05.pdf