Данные –
m строк по
n коэффициентов.
Найти в этих данных такой набор из столбцов и строк, который бы максимизировал сумму коэффициентов, попавших в это пересечение.
Ответом будут номера выбранных столбцов и строк.
Подскажите, пожалуйста, алгоритм (хотя бы название, куда копать).
Упрощённый случай
Коэффициенты принимают значения 0 или 1.
Найти такой набор столбцов и строк, в котором одни единицы.
Допустим, число столбцов в
k=2 раза весомее числа строк. Т.е. 6 столбцов и 4 строки (6*2 + 4) лучше, чем 4 столбца и 6 строк (4*2 + 6). Пример. Тут матрица описывает граф двунаправленных связей между некими объектами 0..5. Поэтому симметрия отн. диагонали:
...0 1 2 3 4 5
0 [1,1,1,0,0,0]
1 [1,1,0,1,1,0]
2 [1,0,1,0,0,0]
3 [0,1,0,1,1,0]
4 [0,1,0,1,1,0]
5 [0,0,0,0,0,1]
Тут
клика в столбцах==строках [0,1] и крупнее – в [1,3,4] – вот последняя и была искомой.
Реальный вариант, сложнее
Ячейка в каждом столбце может иметь лишь одно из двух значений – это отрицательное или положительное число: – «награда» за наличие признака, или «штраф» за его отсутствие. Они несимметричны отн. нуля: «награда» небольшая, «штраф» большой. Одинаковые в рамках одного столбца. Разные в разных столбцах. Коэффициент
k тоже будем варьировать для получения разных результатов.
Похоже ли это на какую-то типовую задачу из machine learning и прототипирования в Matlab/Octave или Python?
Средний
