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

Question

Пытаюсь написать алгоритм, но я не знаю много теории графов, поэтому все, что у меня есть в моем арсенале сейчас, это ветвление и связывание и генетический алгоритм. Не очень надежный, но я здесь, чтобы учиться.

Вот моя проблема: У нас есть набор из n детей, которые будут разбиты на k команд, по L игроков на команду. Каждый ребенок просит максимум 3 друзей сыграть в их команде. Каждому ребенку гарантируется, что один из его запросов будет выполнен.

Я хочу максимизировать набор команд, чтобы мы максимально увеличивали количество выполненных запросов, с учетом ограничений по L игроков на команду, и у каждого ребенка есть хотя бы один выполненный запрос.

Какой тип алгоритма мне следует изучить при исследовании? Я предполагаю, что это какое-то применение теории графов, где каждый игрок является узлом, а каждый запрос - ребром ... но это все, что касается моих знаний о графике.

Answer 1

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

Это предполагает, что не будет количества подграфов (то есть две группы игроков, которые запрашивают друг друга, но ни одной из другой группы).По крайней мере, запустив Prim's, вы можете сузить поле, с которым игрок в паре с какими друзьями.