Задача о гладиаторах

Суть проблемы:
Есть два набора бойцов:
В первой m человек
Во второй n человек

Необходимо выбрать из каждого набора 2 команды по p (p < m) и q (q < n) человек соответственно.
Таких, бой между которыми будет самым зрелищным (биться будет каждый из первой команды с каждым из второй). необходимо вернуть индексы бойцов в каждой команде.

Примеры:
m = 5, n = 5, p = 3, q = 3.

Первый набор - 1 2 3 4 5
Второй набор - A B C D E

Пример 1.
На пересечении - "зрелищность" боя.
В ответ ожидается:
Первая команда, бойцы: 1,2,3
Вторая команда, бойцы: A,B,C

Пример 2.
Та же самая таблица, но с изменённым порядком строк и столбцов (так проблема более наглядна).
В ответ ожидается:
Первая команда, бойцы: 1,3,5
Вторая команда, бойцы: A,C,E

Собственно суть вопроса не в просьбе написать алгоритм, а в возможных подсказках в плане оптимизации или подходах к решению этой задачи, т.к. m и n могут быть довольно большими.
Может есть похожие задачи, с решениями не требующими полного перебора.
Возможно есть подходы находящие не самое оптимальное решение (может генетический алгоритм), но работающие относительно быстро.
Возможно есть какой-то способ уменьшить изначальные наборы.

Думаю над проблемой довольно долго, глаз "замылился".

0

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

1

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

1

А если так:

• подсчитаем рейтинг бойцов команды А как сумму баллов соответствующей строки/столбца матрицы;
• выберем p бойцов команды А с наивысшим рейтингом;
• подсчитаем рейтинг бойцов команды В как сумму баллов встреч с уже выбранными бойцами команды А;
• выберем q бойцов команды В с наивысшим рейтингом;

Кажется, готово?

1

Спасибо за ответ.
Вариант, похоже, не плохой.

Но есть кейсы, когда может выдать не самый хороший результат.
Наример:

в данном случае, если "фиксировать" бойцов из группы (A-E), алгоритм отработает корректно.
но если сперва выбирать из группы (1-5)
после первоначального отсеивания получим:
т.к. сумма в столбцах 4 и 5 - больше, чем 1 - 3

После второго:
Вероятно "улучшением" алгоритма будет выбор лучшего из 2-х решений - (1) с фиксацией по строкам и (2) по столбцам.

Пока писал ответ, придумал вариант (который "ломает") в том числе предложенное улучшение:
В данном случае в любом случае вернётся набор из 6 (т.к. сумма по столбцам и по строкам будет больше и 7 не попадут ни в один из наборов).

Тем не менее - учитывая что нам не всегда нужен лучший вариант, а важен баланс между скоростью и результатом. Решение имеет право на жизнь.

0

Свести задачу к задаче целочисленного линейного программирования (ЦЛП).
Для каждого боя заводим целочисленную переменную, которая будет принимать 0 (бой не состоится) или 1 (состоится).
Эти переменные x[1,1], ..., x[m,1], x[1,2], ..., x[m,n] - матрица, оптимизируемые целочисленные решения.
Накладываются ограничения:
x[i, j] >= 0
x[i, j] <= 1
x[i, j] - целое
sum(x[i,1], ..., x[i, n]) = p
sum(x[1, j], ..., x[m, j]) = q
sum(A[1,1]*x[1,1], ..., A[m,n]*x[m,n]) = max

Это типичная ЗЦЛП. Решается точно и влёт.

A[i,j] - матрица зрелищности боёв.

Добавлено через 11 минут
Но тут прочитал, что ЗЦЛП является NP-полной. ((
Но алгоритмы-решатели есть, надо их использовать.

0

Сообщение от Mikhaylo Накладываются ограничения: x[i, j] >= 0 x[i, j] <= 1 x[i, j] - целое

Можно записать тут единственное ограничение x[i, j]*(1-x[i, j])=0 - станет возможным последующее применение алгоритмов гладкой оптимизации.
Если кому не очевидно - то потребуется всего лишь трансформация подобного и других (не стал их включать в цитату) критериев вида z=const в критерии вида (z-const)²->min, и последующая сборка их в единую дифференцируемую функцию из кучи слагаемых ("штрафных слагаемых" вдобавок к основному максимизируемому критерию).

0

Сообщение от azizoff Вариант, похоже, не плохой. Но есть кейсы, когда может выдать не самый хороший результат.

Выбор в качестве рейтинга суммы баллов по строке/столбцу это просто первое, что в голову пришло.
Можно, наверно, поэкспериментировать и с другими функциями.

0

Если задачу свести к целочисленному линейному программированию, что уже написали, то решение будет находится быстро.
Для малых задач можно использовать полный перебор, количество вариантов: кол-во сочетаний p по m помноженное на количество сочетаний q по n (для стартовой задачи - 225 вариантов). Может быть получится применить метод ветвей и границ для сокращения расчетов

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

Добавлено через 1 минуту
azizoff, Вы можете приложить задачу с реальными данными большой размерностью?

1

На самом деле - данная задача не совсем академическая (приведена к такому виду для простоты понимания), а вполне требующая решения на практике, за разумное время.
В реальности m и n могут быть трехзначными и четырёхзначными. (от сотен до тысяч)
p и q до сотни.

0

Сообщение от azizoff В реальности m и n могут быть трехзначными и четырёхзначными. (от сотен до тысяч) p и q до сотни.

Повторю вопрос, Вы можете приложить реальные данные?
Можно конечно придумать их генератором случайных чисел, но лучше все таки протестировать реальные данные

0

m-ch, приложил полноразмерный пример (таблица "зрелищностей").
Ожидаемые p = 13 и q = 13.

Вложения

table.xlsx (55.0 Кб, 14 просмотров)

0

Посмотрите такое решение, не обязательно оно будет оптимальным, но считает относительно быстро на текущих данных

Вложения

Максимизация.zip (273.1 Кб, 6 просмотров)

1

m-ch, Спасибо! Наглядное решение, пошел изучать макрос.

0

Как можно улучшить решение:
Можно стартовое решение не находить жадным алгоритмом, а взять любое: взять столбцы и строки просто по порядку, по сортировке суммы по столбцам и строкам или просто случайным образом (метод Монте-Карла).
Затем улучшать решение, до тех пор, пока не найдем локальный максимум.
Также можно транспонировать исходную матрицу и поменять порядок перебора строк и столбцов.

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

0

Нашел у себя в коде небольшую ошибку, выкладываю с исправлениями
Описанную выше методику не реализовывал

Вложения

Максимизация.rar (316.8 Кб, 3 просмотров)

1

Дополнил решение "медленным" алгоритмом, по сути, это тот же алгоритм, но используется перебор всех n столбцов в качестве стартового решения, из множества n решений выбирается лучшее.
Получилось чуть лучше, но решает значительно дольше

Вложения

Максимизация2.rar (263.2 Кб, 3 просмотров)

1