Проектирование реляционных баз данных. Ковалев А.В - 23 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

25
Выбрать
случайную
топологию
Отвергну ть
Проверить
связность
Принять
Генератор Конец Сохранить
локальных локальный
изменений оптимум
Отвергну ть
Проверить
связность
Принять
Выбор пропускных способностей
и распределение потоков
Нет Улучшились Да Принять
свойства сети? локальное
изменение
Рис. 9. Эвристический метод оптимизации топологии
2.2.3. Алгоритм Прима
В качестве примера эвристического метода приведем алгоритм Прима. Для связи средств
вычислительной техники в больших сетях традиционно применяется модемная техника, однако
качество и надежность получаемой системы передачи данных существенно зависят от выбора
каналов - выделенных или коммутируемых. Проектировщику такой распределенной системы
традиционно приходится разрешать дилемму между обеспечением требуемого качества сети и
ее стоимости, что связано со значительной разницей в оплате указанных каналов связи.
Пусть имеется множество территориально распределенных объектов X={x
i
}, характери-
зуемых: географическими координатами (a
i
,b
i
); объемом информации f
i
, генерируемой объек-
том. Предполагается, что одним из объектов является "центральный" (главный) узел, выделен-
ный в соответствии с некоторыми правилами - административными, территориальными и пр.
Пусть, кроме того, известны приведенные затраты C
пер,ij
на передачу информации от объ-
екта x
i
к объекту x
j
, зависящие от трафика f
ij
в данном направлении и длины линий связи l
ij
.
Требуется синтезировать структуру минимальной стоимости в классе древовидных структур
при ограничениях на максимальный трафик f
ij
в каждой ветви (f
ij
,d
max
), где f
ij
определяется как 
             Выбрать
             случайную
             топологию

                           Отвергнуть


             Проверить
             связность

                      Принять

             Генератор           Конец                      Сохранить
             локальных                                      локальный
             изменений                                      оптимум

         Отвергнуть

             Проверить
             связность

                      Принять

             Выбор пропускных способностей
             и распределение потоков


        Нет Улучшились           Да      Принять
            свойства сети?               локальное
                                         изменение


      Рис. 9. Эвристический метод оптимизации топологии

      2.2.3. Алгоритм Прима

      В качестве примера эвристического метода приведем алгоритм Прима. Для связи средств
вычислительной техники в больших сетях традиционно применяется модемная техника, однако
качество и надежность получаемой системы передачи данных существенно зависят от выбора
каналов - выделенных или коммутируемых. Проектировщику такой распределенной системы
традиционно приходится разрешать дилемму между обеспечением требуемого качества сети и
ее стоимости, что связано со значительной разницей в оплате указанных каналов связи.
      Пусть имеется множество территориально распределенных объектов X={x i}, характери-
зуемых: географическими координатами (ai,bi); объемом информации fi, генерируемой объек-
том. Предполагается, что одним из объектов является "центральный" (главный) узел, выделен-
ный в соответствии с некоторыми правилами - административными, территориальными и пр.
      Пусть, кроме того, известны приведенные затраты Cпер,ij на передачу информации от объ-
екта xi к объекту xj, зависящие от трафика fij в данном направлении и длины линий связи lij.
Требуется синтезировать структуру минимальной стоимости в классе древовидных структур
при ограничениях на максимальный трафик fij в каждой ветви (fij,dmax), где fij определяется как
                                                  25

Страницы