Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: подзадача для последовательной декомпозиции графа  (Прочитано 9142 раз)
0 Пользователей и 1 Гость смотрят эту тему.
cooler_3105
Гость
« : 14-02-2009 12:59 » 

Имеется матрица смежности упорядоченного ориентированного графа (например, размерностью 9*9). 1 соответствует наличию дуги, 0 - ее отсутствием. Нужно вычислить
С(2,1)
С(3,2), С(3,1)
С(4,3), С(4,2), С(4,1)
С(5,4), С(5,3), С(5,2)
...................
С(9,8), С(9,7), С(9,6)
Максимальное кол-во значений С в каждой строке дается в условии (в данном случае макс. кол-во = 3). Т.е. сначала считается одно значение (в нашем случае С(2,1)), потом - 2 (С(3,2), С(3,1)), и т.д. пока не дойдем до макс. кол-ва значений (С(4,3), С(4,2), С(4,1)), которое сохраняется до конца расчетов (С(9,8), С(9,7), С(9,6)).
С высчитывается по формуле: С(x,y) = количеству существующих ребер (i*j) при y<=i<x, j>=x. По матрице смежности
С(x,y) равняется сумме значений матрицы смежности в прямоугольнике шириной (x-y) и длиной до конца матрицы, левый верхний угол которого - ячейка (y,x).
В данном случае нужно явно использовать динамическое программирование. Вопрос в том, как оптимально использовать вычисления, проводимые ранее.
Это является подзадачей при последовательной декомпозиции графа.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 14-02-2009 13:04 » 

cooler_3105, расскажи, что уже придумал.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
cooler_3105
Гость
« Ответ #2 : 14-02-2009 13:20 » 

RXL, я думаю сначала надо вычислить первый столбец, т.е. С(2,1), С(3,2), С(4,3)...С(9,8). Это считается тривиально, С(х,у) = сумме строки матрицы смежности, начиная с элемента a[y][х].
Затем считаем второй стоблец: С(3,1), С(4,2)... С(9,7). Например С(3,1)=С(2,1)+С(3,2) (не забудем проверить элемент [1][2], если он 1, тогда из С(3,1) вычтем единицу). По мере счета второго столбца проверять придется больше элементов (они располагаются в матрице лесенкой).
Затм считаем следующий столбец: С(4,1) = С(4,2)+С(4,3).
Удобно нарисовать матрицу, так становится понятнее.
Записан
cooler_3105
Гость
« Ответ #3 : 21-02-2009 12:45 » new

Прошу модераторов закрыть тему, задача решена.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines