Симметричные разреженные матрицы
, Диагонализация
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [18.232.179.37] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Симметричные разреженные матрицы
, Диагонализация
|
Сообщ.
#1
,
|
|
 |
Дана симметричная разреженная матрица. Если переставить i-ую и j-ую строку, а также i-й и j-й столбец, то матрица останется симметричной. Нужно при помощи таких перестановок собрать ненулевые элементы матрицы возле главной диагонали. Пусть m[i] - это номер первого ненулевого элемента i-й строки. Тогда нужно максимизировать сумму m[i] по всем строкам.
|
|
Сообщ.
#2
,
|
|
|
Как я понимаю, матрица квадратная, верно?
Думаю, если выложить пример (скажем, матрицу 5х5) с решением, будет проще понять суть происходящего... |
|
Сообщ.
#3
,
|
|
|
|
Матрица квадратная.
Пример. Было: х00х0 0х000 00х00 х00х0 0000х Меняем местами первую и последнюю строки и столбцы. Стало: х0000 0х000 00х00 000хх 000хх Ненулевые элементы приближены к главной диагонали. |
|
|
Сообщ.
#4
,
|
|
|
Ну тут обычная пошаговая оптимизация.
Просто берём и опускаем все строки, у которых единичный элемент начинается раньше, чем у нижележащей. То есть в данном случае - сначала опускаем строку 4, меняя её со строкой 5, получаем х000x 0х000 00х00 000х0 х000x Закончив с горизонталями, делаем то же с вертикалями. Т.е. меняем вертикали 1 и 4, получаем х0000 0х000 00х00 000хх 000хх |
|
Сообщ.
#5
,
|
|
|
|
Цитата Akina @ Ну тут обычная пошаговая оптимизация. Просто берём и опускаем все строки, у которых единичный элемент начинается раньше, чем у нижележащей. Не понял идею. У первой строки первый элемент ненулевой. Но это не значит, что её надо опускать. |
|
|
Сообщ.
#6
,
|
|
|
Цитата prografix @ У первой строки первый элемент ненулевой. Он на главной диагонали. |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0219 ] [ 15 queries used ] [ Generated: 2.10.23, 00:37 GMT ]