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

UptoLike

34
вей, соединенных последовательно или параллельно. Дальнейшее продвижение в анализе
сложных сетей возможно с использованием метода "разложения" относительно одной ветви.
0 1 2 0 1 2
0 0 1 2 0 0 0 2
1 1 2 2 1 0 1 2
2 2 2 2 2 2 2 2
а) б)
Рис. 12. Результирующие состояния последовательных и параллельных комбинаций вет-
вей: а - последовательная; б - параллельная
В этом методе выбирается некоторая ветвь, и дальнейший расчет вероятностей ведется
тремя различными путями в зависимости от того, в каком из трех состояний находится данная
ветвь.Если ветвь находится в состоянии 2, никаких дальнейших расчетов не требуется, так как
сеть несвязна. Если ветвь находится в состоянии 1, ее можно удалить из сети, а оставшуюся
часть сети можно подвергнуть дальнейшему упрощению путем выделения параллельно-
последовательных ветвей. В состоянии 0 два терминала ветви соединены надежно. Эти два узла
графа можно объединить, и при удачном результате продолжить упрощение путем выделения
параллельно-последовательных ветвей. Успех этой процедуры зависит от удачного выбора вет-
ви, вокруг которой упрощается сеть. В больших сетях к процедуре разложения приходиться
обращаться многократно, причем каждый раз число дальнейших расчетов удваивается.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Сформулируйте наиболее употребительные критерии оптимизации сетей.
2. Какие исходные данные используются при постановке и решении сетевых оптимиза-
ционных задач?
3. Что такое топологические ограничения?
4. Каковы особенности решения реальных задач оптимизации?
5. Какие основные подходы применяются при решении оптимизационных задач?
6. Чем обусловлена сложность комбинаторных задач?
7. В чем преимущество эвристических методов решения?
8. Чем примечателен граф Петерсона?
9. Почему вероятность применения регулярных графов при проектировании больших се-
тей невелика?
10. Опишите способ, с помощью которого можно исследовать различные топологии сети
и накапливать локально-оптимальные варианты.
11. Как работает алгоритм Прима?
12. В чем состоит сущность метода насыщения сечения?
13. Почему иерархические сети более экономичны?
14. Каковы особенности построения сетей с концентрирующими узлами?
15. В чем состоит сущность алгоритма Форда-Фалкерсона?
16. В чем проблема многокритериальности задачи выбора пропускных способностей?
17. Что такое метод девиации потока?
18. Какова сущность метода исключения ветвей при выпуклой функции стоимости?
19. Какие инженерные решения по оценке надежности сети Вам известны?
вей, соединенных последовательно или параллельно. Дальнейшее продвижение в анализе
сложных сетей возможно с использованием метода "разложения" относительно одной ветви.

              0         1         2                           0         1          2
     0        0         1         2                  0        0         0          2
     1        1         2         2                  1        0         1          2
     2        2         2         2                  2        2         2          2

                        а)                                              б)

        Рис. 12. Результирующие состояния последовательных и параллельных комбинаций вет-
вей: а - последовательная; б - параллельная

      В этом методе выбирается некоторая ветвь, и дальнейший расчет вероятностей ведется
тремя различными путями в зависимости от того, в каком из трех состояний находится данная
ветвь.Если ветвь находится в состоянии 2, никаких дальнейших расчетов не требуется, так как
сеть несвязна. Если ветвь находится в состоянии 1, ее можно удалить из сети, а оставшуюся
часть сети можно подвергнуть дальнейшему упрощению путем выделения параллельно-
последовательных ветвей. В состоянии 0 два терминала ветви соединены надежно. Эти два узла
графа можно объединить, и при удачном результате продолжить упрощение путем выделения
параллельно-последовательных ветвей. Успех этой процедуры зависит от удачного выбора вет-
ви, вокруг которой упрощается сеть. В больших сетях к процедуре разложения приходиться
обращаться многократно, причем каждый раз число дальнейших расчетов удваивается.

      КОНТРОЛЬНЫЕ ВОПРОСЫ

       1. Сформулируйте наиболее употребительные критерии оптимизации сетей.
       2. Какие исходные данные используются при постановке и решении сетевых оптимиза-
ционных задач?
       3. Что такое топологические ограничения?
       4. Каковы особенности решения реальных задач оптимизации?
       5. Какие основные подходы применяются при решении оптимизационных задач?
       6. Чем обусловлена сложность комбинаторных задач?
       7. В чем преимущество эвристических методов решения?
       8. Чем примечателен граф Петерсона?
       9. Почему вероятность применения регулярных графов при проектировании больших се-
тей невелика?
       10. Опишите способ, с помощью которого можно исследовать различные топологии сети
и накапливать локально-оптимальные варианты.
       11. Как работает алгоритм Прима?
       12. В чем состоит сущность метода насыщения сечения?
       13. Почему иерархические сети более экономичны?
       14. Каковы особенности построения сетей с концентрирующими узлами?
       15. В чем состоит сущность алгоритма Форда-Фалкерсона?
       16. В чем проблема многокритериальности задачи выбора пропускных способностей?
       17. Что такое метод девиации потока?
       18. Какова сущность метода исключения ветвей при выпуклой функции стоимости?
       19. Какие инженерные решения по оценке надежности сети Вам известны?



                                               34