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

Дана матрица единиц и нолей. Надо выбрать в ней такую комбинацию столбцов и строк, чтобы максимизировать отношение числа клеток с "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".
  • Вопрос задан
  • 260 просмотров
Пригласить эксперта
Ответы на вопрос 1
Labunsky
@Labunsky
Я есть на хабре
Не тестировал, но как-то так:
1. Считаем сумму всех значений матрицы N, а так же сумму для каждой строки и столбца M[] и соотношение 1 к 0 Z;
2. Вычитаем из N минимальное значение среди M: N -= min(M).;
3. "Убираем" строку или столбец соответсвующую min(M) из матрицы: вычитаем из каждого столбца или строки (соответственно) значения на пересечении и параллельно обновляем Z;
4. Сравниваем Z с предыдущим значением. Если оно стало больше - вернуться к шагу 2. Если меньше - комбинация найдена (неудаленые строки и столбцы).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ВЫМПЕЛ Москва
от 100 000 до 200 000 руб.
cyber eye control Санкт-Петербург
До 150 000 руб.