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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

23
потребность в более простых эвристических методах, являющихся, по су ществу, методами
"проб и ошибок".
Задача распределения потока информации по линиям связи с целью увеличения пропуск-
ной способности является примером задачи, которая допускает аналитическое решение. Неко-
торые из аналитических методов оптимизации построены на больших упрощениях, например,
сведении нелинейной задачи к линейной.
Какова бы ни была задача, часто наилучшими методами ее решения являются эвристиче-
ские. Например, программа может генерировать топологии с улучшенными свойствами, поль-
зуясь некоторыми "разумными" соображениями, вместо того чтобы использовать алгоритм с
доказанной сходимостью к оптимуму. Такая программа может многократно "улучшать" потоки
в сети без какой-либо гарантии оптимальности результата. Чтобы достаточно полно охватить
возможные случаи, вводятся случайные изменения, и тогда одно из "наилучших решений" мо-
жет оказаться близким к оптимуму. В эвристическом алгоритме решения задачи оптимизации
случайным образом выбираются начальные точки, число которых должно быть достаточно
большим. Результаты, полученные для различных начальных точек, сравниваются между собой.
Наилучший из них выбирается в качестве истинного решения задачи.
2.2. Структурный синтез и оптимизация топологии
2.2.1. Регулярные графы
Одним из методов построения топологических структур сетей с заданными свойствами
является синтез графов с помощью известных математических операций. На рис. 8 приведен
граф, построенный таким путем. Обычно такие графы обладают некоторой регулярностью, т.е.
все их узлы равноправны в смысле топологии сети.
Рис. 8. Граф Петерсона
Граф Петерсона, изображенный на рис. 8, состоит из 10 узлов и 15 линий со связностью
3. Степень каждого узла также равна трем, и, следовательно, связность этого графа максималь-
на. Говорят, что такой граф имеет максимальную связность. Другое свойство оптимальности 
потребность в более простых эвристических методах, являющихся, по существу, методами
"проб и ошибок".
      Задача распределения потока информации по линиям связи с целью увеличения пропуск-
ной способности является примером задачи, которая допускает аналитическое решение. Неко-
торые из аналитических методов оптимизации построены на больших упрощениях, например,
сведении нелинейной задачи к линейной.
      Какова бы ни была задача, часто наилучшими методами ее решения являются эвристиче-
ские. Например, программа может генерировать топологии с улучшенными свойствами, поль-
зуясь некоторыми "разумными" соображениями, вместо того чтобы использовать алгоритм с
доказанной сходимостью к оптимуму. Такая программа может многократно "улучшать" потоки
в сети без какой-либо гарантии оптимальности результата. Чтобы достаточно полно охватить
возможные случаи, вводятся случайные изменения, и тогда одно из "наилучших решений" мо-
жет оказаться близким к оптимуму. В эвристическом алгоритме решения задачи оптимизации
случайным образом выбираются начальные точки, число которых должно быть достаточно
большим. Результаты, полученные для различных начальных точек, сравниваются между собой.
Наилучший из них выбирается в качестве истинного решения задачи.

      2.2. Структурный синтез и оптимизация топологии

      2.2.1. Регулярные графы

      Одним из методов построения топологических структур сетей с заданными свойствами
является синтез графов с помощью известных математических операций. На рис. 8 приведен
граф, построенный таким путем. Обычно такие графы обладают некоторой регулярностью, т.е.
все их узлы равноправны в смысле топологии сети.




      Рис. 8. Граф Петерсона

      Граф Петерсона, изображенный на рис. 8, состоит из 10 узлов и 15 линий со связностью
3. Степень каждого узла также равна трем, и, следовательно, связность этого графа максималь-
на. Говорят, что такой граф имеет максимальную связность. Другое свойство оптимальности
                                                23

Страницы