Как оптимизировать поиск комбинации строк и столбцов в матрице?

Question

[Сергей Соколов]

Дана матрица единиц и нолей. Надо выбрать в ней такую комбинацию столбцов и строк, чтобы максимизировать отношение числа клеток с "1" к числу клеток с "0". При этом чем больше строк и столбцов участвует, тем лучше.

Например, тут строки (0,1,3) со столбцами (0,3,5) дают всего один "0" при восьми "1":

1 0 0 1 0 1
1 1 0 1 1 1
0 1 0 1 0 0
1 1 0 0 0 1

Как я понял, задача NP-полная, т.е. требуется полный перебор всех возможных сочетаний. Хочется находить такие максимальные выборки на довольно большом числе строк и столбцов: от тысяч до миллионов.

Какие есть алгоритмы, оптимизирующие этот перебор?

Как частный случай нужно искать сочетания вообще без единого "0".

Answer 1

[Labunsky]

Не тестировал, но как-то так:
1. Считаем сумму всех значений матрицы N, а так же сумму для каждой строки и столбца M[] и соотношение 1 к 0 Z;
2. Вычитаем из N минимальное значение среди M: N -= min(M).;
3. "Убираем" строку или столбец соответсвующую min(M) из матрицы: вычитаем из каждого столбца или строки (соответственно) значения на пересечении и параллельно обновляем Z;
4. Сравниваем Z с предыдущим значением. Если оно стало больше - вернуться к шагу 2. Если меньше - комбинация найдена (неудаленые строки и столбцы).

Comments

[Сергей Соколов]

Опасаюсь, что убирая строки/столбцы по признаку минимума выкинем нужные. Данные могут быть настолько «размазаны», что искомый максимум будет совсем небольшим и включать лишь 1% строк/столбцов.

[Labunsky]

Сергей Соколов: нужные мы в любом случае не выкинем - чтобы максимизировать отношение 1:0, нужно выкинуть максимально возможное количество нулей

Ведь очевидно, что 1_count/0_count будет расти только при уменьшении знаменателя - числитель увеличиться не может, так как исходное соотношение включает ВСЕ единицы в матрице

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