Самостоятельная команда

Команда, состоящая из 100 членов, должна быть собрана из пула из 1000 претендентов. Каждый претендент получает возможность выбрать 99 других заявителей, которых он/она хотел бы иметь в качестве товарищей по команде.Самостоятельная команда

Каждая возможная команда получает оценку, которая измеряет, насколько она удовлетворяет предпочтениям партнера по команде своих членов. Если Лиза находится в команде, и 11 человек из списка желаний Lisas также находятся в команде, команда получает 11 очков за Лизу. Очки для всех участников складываются. Теоретический максимум любой возможной команды может составить 99 * 100. Минимум равен 0.

Теперь мы хотим найти команду с наивысшим результатом. Попытка перебора этой проблемы путем вычисления оценки для каждой возможной комбинации (≈ 10^140) не является вариантом.

Есть ли уловкий алгоритм, который займет ярлык к лучшему ответу или нужно будет решить алгоритм, который найдет хороший ответ?

источник

2013-02-11 oivvio

Интересный вопрос. Я уверен, что есть способы улучшить поиск грубой силы для детерминированного решения по C (1000 100), но я подозреваю, что они в лучшем случае улучшают геометрические характеристики. Для приемлемого решения, я думаю, вам придётся прибегнуть к эвристике. – RBarryYoung

Похож на проблему с собственными значениями для меня. Google для «итерации мощности» – wildplasser

Этот клиентский проект запущен. [Уравнение Куратрона] (http://curatroneq.com) - это платформа Сааса для краудсорсинга художественного кураторского процесса. – oivvio

Вы можете попробовать алгоритм hill climbing. Начните с члена, который является «популярным» (чаще всего выбирается другими участниками), и постепенно добавляйте новых членов, которые больше всего выигрывают в команде. Это, к сожалению, не гарантируется, чтобы найти лучшее решение, но оно, вероятно, найдет хорошие. Чтобы улучшить решение, вы можете попробовать simulated annealing.

источник

2013-02-11 22:36:11 ckb

Если я правильно понимаю проблему, оценка рассчитывается как 99 (от человека, выбирающего его команду - так как все они должны быть в его списке) + сумма остальных 99 членов команды подсчитывает претендентов по их списку желаний, которые в команде. Вы уже знаете теоретический максимальный балл команды, поэтому я не понимаю, зачем вам нужно проходить все комбинации. Итерация через все 1000 команд, чтобы найти лучший результат, должна быть относительно тривиальной. 1000 команд * 100 членов команды легко разрешимы. –

Боб: Есть более 1000 команд. Есть 1000!/900! команды (1000 способов выбора члена команды №1, 999 способов выбора члена команды № 2 и т. д.) –

Я думаю, что если бы вы могли эффективно решить эту проблему, вы могли бы эффективно решить http://en.wikipedia.org/wiki/Clique_problem - там, где есть связь между двумя узлами, поместите каждый узел в список узлов, с которыми хочет работать другой. Глядя на статью, я думаю, вам будет трудно найти даже гарантированное хорошее приближение, если у вашей проблемы не есть какая-то особая структура.

источник

2013-02-12 05:27:48 mcdowella

Хороший улов. Я согласен, это очень похоже на существенный супер-набор проблемы Clique. Учитывая, что проблема Клики * очень * неразрешима, мы, вероятно, можем быть уверены, что эта проблема слишком (или, скорее всего, еще сложнее). Таким образом, очень маловероятно иметь приемлемое детерминированное решение. – RBarryYoung

ответ

Смежные вопросы