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

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

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

              Он на главной диагонали.
              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
              0 пользователей:


              Рейтинг@Mail.ru
              [ Script execution time: 0,0219 ]   [ 15 queries used ]   [ Generated: 2.10.23, 00:37 GMT ]