Как оптимизировать поиск комбинации строк и столбцов в матрице? Дана матрица единиц и нолей. Надо выбрать в ней такую комбинацию столбцов и строк, чтобы максимизировать отношение числа клеток с "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".
Как оптимизировать поиск комбинации строк и столбцов в матрице? Дана матрица единиц и нолей. Надо выбрать в ней такую комбинацию столбцов и строк, чтобы максимизировать отношение числа клеток с "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".
Например, тут строки (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".
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения данной задачи можно воспользоваться жадным алгоритмом, который будет пошагово выбирать строки и столбцы, максимизируя отношение числа клеток с "1" к числу клеток с "0".
Шаги алгоритма:
Создать пустое множество для выбранных строк и столбцов.Начать итерации: на каждом шаге выбирать строку или столбец, который максимально увеличивает отношение числа клеток с "1" к числу клеток с "0". Добавить выбранные строки и столбцы в множество.Продолжать шаг 2 до тех пор, пока не увеличивается отношение числа клеток с "1" к числу клеток с "0" или пока не будет достигнуто максимальное число строк и столбцов.Чтобы найти комбинацию без единого "0", можно воспользоваться алгоритмом поиска клики в графе. Для каждой строки создать вершину графа, соединить вершины ребрами, если строки не имеют "0" на одинаковых позициях. Затем найти максимальную клику в полученном графе, что и будет сочетанием строк и столбцов без единого "0".
Также для оптимизации алгоритма можно использовать методы динамического программирования или эволюционные алгоритмы, которые позволят быстрее находить оптимальные решения на больших объемах данных.