Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896706 Sun, 12 Nov 2023 15:05:16 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896706 Majestio, он не всегда будет оптимальным, всё же на практике показал хороший результат.
А теперь о том для чего это нужно.
Иногда мне приходится решать задачи с большим числом неизвестных методом наименьших квадратов. Получается система уравнений с симметричной и разреженной матрицей А с сотнями или тысячами строками ( столбцами ). Я решаю её путём LDLt разложения. Здесь L - это нижняя треугольная матрица, D - диагональная матрица, а Lt - это транспонированная матрица L. Этот метод асимптотически быстрее метода Гаусса в 2 раза. Я обнаружил, что лидирующие нули матрицы А сохраняются в матрице L, а значит эти элементы можно не вычислять. Если А сильно разрежена, то получается большая экономия в вычислениях. Поэтому я сделал специальную модификацию метода LDLt разложения, в которую поступает информация о матрице А без лидирующих нулей и вычисляется матрица L тоже без них. Назовём его, для примера, specLDLt. Понятно, что чем больше лидирующих нулей, тем быстрее будут вычисления, а этого можно добиться переставив неизвестные и уравнения. Обозначим алгоритм получения максимума лидирующих нулей через maxNull.
Мои опыты на реальных данных показали, что если число неизвестных меньше 200, то применение maxNull+specLDLt даёт небольшое ускорение, либо даже замедление по сравнению с просто specLDLt. С увеличением числа неизвестных эффективность предобработки растёт и для 1500 неизвестных сочетание maxNull+specLDLt было в 10 раз быстрее, чем просто specLDLt. А если сравнивать с обычным LDLt или методом Гаусса, то там разница в сотни раз.
Интересно, что тут встретились задачи из дискретной (maxNull) и непрерывной математики (specLDLt).]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896668 Thu, 09 Nov 2023 16:33:25 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896668 Majestio
Очень интересный и неожиданный пример!]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896614 Wed, 08 Nov 2023 17:57:32 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896614 Цитата 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

Т.е. если первый столбец берём с большим числом нулей - ничего путного не выйдет. Увы :no:]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896529 Mon, 06 Nov 2023 14:02:20 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896529 Цитата 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896526 Mon, 06 Nov 2023 05:22:05 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896526 Majestio
Спасибо. Значит ли это, что эту задачу уже кто-то решал?
Я придумал более оптимальный алгоритм.
Вначале выбираем столбец с минимальным числом единиц и делаем его первым. Если их несколько, то какой-то из них.
Далее строки в которых были единицы игнорируем. Находим столбец с минимальным числом единиц без учёта этих строк и делаем его следующим. И так далее.
Для исходной матрицы из поста выше получим:
0 0 1 1
0 0 0 1
1 0 1 0
0 1 1 1
Ответ получился лучше. У него два последних столбца переставлены по сравнению с результирующей матрицей из поста выше.]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896525 Sun, 05 Nov 2023 14:31:17 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896525 Цитата 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

]]> Majestio Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896524 Sun, 05 Nov 2023 10:02:22 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3896524 Akina, но придумал, как упростить постановку задачи.
Дана квадратная матрица с нулями и единицами. Нужно переставить у неё столбцы так, чтобы сумма лидирующих нулей по всем строкам была максимальной.
Лидирующие нули - это нули до первой единицы.
Например, в строке 10101 лидирующих нулей - ноль, в строке 00101 лидирующих нулей - два.
Понятно, что можно сделать полный перебор всех перестановок столбцов, но нужен более быстрый алгоритм.]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894636 Tue, 05 Sep 2023 17:17:52 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894636 Цитата prografix @ 05.09.23, 09:22

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

Он на главной диагонали.]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894605 Tue, 05 Sep 2023 09:22:02 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894605 Цитата Akina @ 04.09.23, 15:06

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

Не понял идею. У первой строки первый элемент ненулевой. Но это не значит, что её надо опускать.]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894574 Mon, 04 Sep 2023 15:06:39 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894574 Просто берём и опускаем все строки, у которых единичный элемент начинается раньше, чем у нижележащей.
То есть в данном случае - сначала опускаем строку 4, меняя её со строкой 5, получаем
х000x
0х000
00х00
000х0
х000x
Закончив с горизонталями, делаем то же с вертикалями. Т.е. меняем вертикали 1 и 4, получаем
х0000
0х000
00х00
000хх
000хх]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894550 Mon, 04 Sep 2023 09:50:35 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894550 Пример.
Было:
х00х0
0х000
00х00
х00х0
0000х
Меняем местами первую и последнюю строки и столбцы.
Стало:
х0000
0х000
00х00
000хх
000хх

Ненулевые элементы приближены к главной диагонали.]]> prografix Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894537 Mon, 04 Sep 2023 07:59:35 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894537 Думаю, если выложить пример (скажем, матрицу 5х5) с решением, будет проще понять суть происходящего...]]> Akina Алгоритмы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894535 Mon, 04 Sep 2023 06:36:27 +0000 Симметричные разреженные матрицы https://forum.sources.ru/index.php?showtopic=437623&view=findpost&p=3894535 prografix Алгоритмы