Симметричные разреженные матрицы , Диагонализация

[prografix]

Дана симметричная разреженная матрица. Если переставить i-ую и j-ую строку, а также i-й и j-й столбец, то матрица останется симметричной. Нужно при помощи таких перестановок собрать ненулевые элементы матрицы возле главной диагонали. Пусть m[i] - это номер первого ненулевого элемента i-й строки. Тогда нужно максимизировать сумму m[i] по всем строкам.

[Akina]

Как я понимаю, матрица квадратная, верно?
Думаю, если выложить пример (скажем, матрицу 5х5) с решением, будет проще понять суть происходящего...

[prografix]

Матрица квадратная.
Пример.
Было:
х00х0
0х000
00х00
х00х0
0000х
Меняем местами первую и последнюю строки и столбцы.
Стало:
х0000
0х000
00х00
000хх
000хх

Ненулевые элементы приближены к главной диагонали.

Сообщение отредактировано: prografix - 04.09.23, 09:53

[Akina]

Ну тут обычная пошаговая оптимизация.
Просто берём и опускаем все строки, у которых единичный элемент начинается раньше, чем у нижележащей.
То есть в данном случае - сначала опускаем строку 4, меняя её со строкой 5, получаем
х000x
0х000
00х00
000х0
х000x
Закончив с горизонталями, делаем то же с вертикалями. Т.е. меняем вертикали 1 и 4, получаем
х0000
0х000
00х00
000хх
000хх

[prografix]

Цитата Akina @ 04.09.23, 15:06

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

Не понял идею. У первой строки первый элемент ненулевой. Но это не значит, что её надо опускать.

[Akina]

Цитата prografix @ 05.09.23, 09:22

У первой строки первый элемент ненулевой.

Он на главной диагонали.

[prografix]

Я так и не понял, как должен работать алгоритм, который предложил Akina, но придумал, как упростить постановку задачи.
Дана квадратная матрица с нулями и единицами. Нужно переставить у неё столбцы так, чтобы сумма лидирующих нулей по всем строкам была максимальной.
Лидирующие нули - это нули до первой единицы.
Например, в строке 10101 лидирующих нулей - ноль, в строке 00101 лидирующих нулей - два.
Понятно, что можно сделать полный перебор всех перестановок столбцов, но нужен более быстрый алгоритм.

[Majestio]

Цитата prografix @ 05.11.23, 10:02

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

Посмотри ответ ChatGPT, может быть поможет

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Функция для подсчета суммы лидирующих нулей в строке
int countLeadingZeros(const vector<int>& row) {
    int count = 0;
    for (int i = 0; i < row.size(); i++) {
        if (row[i] == 0) {
            count++;
        } else {
            break;
        }
    }
    return count;
}
 
// Функция для перестановки столбцов в матрице
void permuteColumns(vector<vector<int>>& matrix) {
    // Создаем вектор пар (сумма лидирующих нулей, индекс столбца)
    vector<pair<int, int>> sums;
    for (int i = 0; i < matrix[0].size(); i++) {
        int sum = 0;
        for (int j = 0; j < matrix.size(); j++) {
            sum += countLeadingZeros(matrix[j]);
        }
        sums.push_back(make_pair(sum, i));
        // Переставляем столбцы в порядке убывания суммы лидирующих нулей
        sort(sums.rbegin(), sums.rend());
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                swap(matrix[i][j], matrix[i][sums[j].second]);
            }
        }
    }
}
 
int main() {
    // Пример матрицы 4x4
    vector<vector<int>> matrix = {
        {1, 0, 1, 0},
        {1, 0, 0, 0},
        {0, 1, 1, 0},
        {1, 0, 1, 1}
    };
 
    // Вывод исходной матрицы
    cout << "Исходная матрица:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
 
    // Перестановка столбцов
    permuteColumns(matrix);
 
    // Вывод результирующей матрицы
    cout << "Результирующая матрица:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}

Исходная матрица:
1 0 1 0
1 0 0 0
0 1 1 0
1 0 1 1
Результирующая матрица:
0 0 1 1
0 0 1 0
1 0 0 1
0 1 1 1

[prografix]

Majestio
Спасибо. Значит ли это, что эту задачу уже кто-то решал?
Я придумал более оптимальный алгоритм.
Вначале выбираем столбец с минимальным числом единиц и делаем его первым. Если их несколько, то какой-то из них.
Далее строки в которых были единицы игнорируем. Находим столбец с минимальным числом единиц без учёта этих строк и делаем его следующим. И так далее.
Для исходной матрицы из поста выше получим:
0 0 1 1
0 0 0 1
1 0 1 0
0 1 1 1
Ответ получился лучше. У него два последних столбца переставлены по сравнению с результирующей матрицей из поста выше.

Сообщение отредактировано: prografix - 06.11.23, 05:22

[Majestio]

Цитата prografix @ 06.11.23, 05:22

Спасибо. Значит ли это, что эту задачу уже кто-то решал?

Не уверен, думаю ChatGPT это решает на основе большого множества частных алгоритмов.
И его решения не всегда бывают оптимальными, а иногда и вовсе бывают неправильными.
Но, как отправную точку - использовать можно часто.

Кстати, вот ещё вариант перестановки (но это чисто вручную)

Было:

A B C D
1 0 1 0
1 0 0 0
0 1 1 0
1 0 1 1

Стало:

D B C A
0 0 1 1
0 0 0 1
0 1 1 0
1 0 1 1


Добавлено 06.11.23, 14:25
Да, примерно твой алгоритм. Выбираются столбцы с максимальным числом нулей и ставятся от начала. Если очередной столбец имеет столько нулей, что и некоторые "неиспользованные" - из них выбирается тот, который больше прибавляет к общей сумме лидирующих нулей. Так получился мой вариант. Но я очень не уверен, что это "финальный" вариант алгоритма, а не частное решение для данных из моего примера. Тут х3

[Majestio]

Цитата Majestio @ 06.11.23, 14:02

Но я очень не уверен, что это "финальный" вариант алгоритма, а не частное решение для данных из моего примера. Тут х3

Да, алгоритм ошибочный! И вот я придумал пример это подтверждающий:


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

Т.е. если первый столбец берём с большим числом нулей - ничего путного не выйдет. Увы

[prografix]

Majestio
Очень интересный и неожиданный пример!

[prografix]

Я реализовал свой алгоритм из сообщения №9, и хотя, как показывает пример Majestio, он не всегда будет оптимальным, всё же на практике показал хороший результат.
А теперь о том для чего это нужно.
Иногда мне приходится решать задачи с большим числом неизвестных методом наименьших квадратов. Получается система уравнений с симметричной и разреженной матрицей А с сотнями или тысячами строками ( столбцами ). Я решаю её путём LDLt разложения. Здесь L - это нижняя треугольная матрица, D - диагональная матрица, а Lt - это транспонированная матрица L. Этот метод асимптотически быстрее метода Гаусса в 2 раза. Я обнаружил, что лидирующие нули матрицы А сохраняются в матрице L, а значит эти элементы можно не вычислять. Если А сильно разрежена, то получается большая экономия в вычислениях. Поэтому я сделал специальную модификацию метода LDLt разложения, в которую поступает информация о матрице А без лидирующих нулей и вычисляется матрица L тоже без них. Назовём его, для примера, specLDLt. Понятно, что чем больше лидирующих нулей, тем быстрее будут вычисления, а этого можно добиться переставив неизвестные и уравнения. Обозначим алгоритм получения максимума лидирующих нулей через maxNull.
Мои опыты на реальных данных показали, что если число неизвестных меньше 200, то применение maxNull+specLDLt даёт небольшое ускорение, либо даже замедление по сравнению с просто specLDLt. С увеличением числа неизвестных эффективность предобработки растёт и для 1500 неизвестных сочетание maxNull+specLDLt было в 10 раз быстрее, чем просто specLDLt. А если сравнивать с обычным LDLt или методом Гаусса, то там разница в сотни раз.
Интересно, что тут встретились задачи из дискретной (maxNull) и непрерывной математики (specLDLt).