<<
>>

Минимизация сети

Задача минимизации сети состоит в нахождении ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину.

На ребрах, соединяющих узлы 1, 2, 3, указаны длины.

Узел 3 соединен с узлами 1 и 2 минимальной длиной 4 + 6 = 10. Если соединить узлы 1 и 2, то возникает цикл и получающаяся сеть не будет минимальной. Отсутствие циклов в минимальной сети дало ей название "минимальное дерево–остов".

Алгоритм решения

Начнем с любого узла и соединим его с ближайшим узлом сети. Соединенные два узла образуют связное множество, а остальные — несвязное. Далее в несвязном множестве выберем узел, который расположен ближе других к любому из узлов связного множества. Скорректируем связное и несвязное множества и будем повторять процесс до тех пор, пока в связное множество не попадут все узлы сети. В случае одинаково удаленных узлов выберем любой из них, что указывает на неоднозначность (альтернативность) "минимального дерева–остова".

Пример. Телевизионная фирма планирует создание кабельной сети для обслуживания 5 районов–новостроек. Числа на ребрах указывают длину кабеля. Узел 1 — телевизионный центр. Отсутствие ребра между двумя узлами означает, что соединение соответствующих новостроек либо связано с большими затратами, либо невозможно.

Найти такое соединение кабелем районов–новостроек, чтобы длина его была минимальной.

Решение. Минимальная длина кабеля: 1 + 3 + 4 + 3 + 5 = 16.

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

Построить сеть трубопровода, соединяющего все скважины с приемным пунктом и имеющего минимальную общую длину труб.

Решение. Минимальная длина труб: 5 + 6 + 4 + 3 + 7 + 5 + 6 + 5 = 41.

Нахождение кратчайшего пути

Задача состоит в нахождении связанных между собой дорог на транспортной сети, которые в совокупности имеют минимальную длину от исходного пункта до пункта назначения.

Введем обозначения:

dij — расстояние на сети между смежными узлами i и j;

Uj — кратчайшее расстояние между узлами i и j, U1 = 0.

Формула для вычисления Uj:

Из формулы следует, что кратчайшее расстояние Uj до узла j можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного дугой с узлом j. Процедура завершается, когда получено Ui последнего звена.

Определить кратчайшее расстояние между узлами 1 и 7.

Решение. Найдем минимальные расстояния:

Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут: 1–2–5–7.

Задача замены автомобильного парка

Фирма по прокату автомобилей планирует замену автомобильного парка на очередные 5 лет. Автомобиль должен проработать не менее 1 года, прежде чем фирма поставит вопрос о его замене. На рисунке приведены стоимости замены автомобилей (усл. ед.), зависящие от времени замены и количества лет, в течение которых автомобиль находился в эксплуатации.

Определить план замены автомобилей, обеспечивающий при этом минимальные расходы.

Решение. Найдем минимальные расстояния:

Кратчайший путь 1–2–5 со стоимостью 12,1 усл. ед. Это означает, что каждый автомобиль заменяется через 2 года, а через 5 — списывается.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Минимизация сети:

  1. 2.3. Методика расчета характеристик перевозочного процесса доставки нефтепродуктов в сети «Нефтебаза - АЗС» с использованием принципа «точно-во-время»
  2. 2.2 Алгоритм обучения нейронной сети для ускоренной сходимости обучения
  3. 2.2.1 Алгоритм обратного распространения ошибки
  4. 3.2.2 Минимизация ресурсных требований к программной реализации
  5. 1.3.1 Эластичные нейронные сети
  6. 2.2.3. Сравнение МСП, RBF и СНРБ-сетей.
  7. 2.1. Сети с упорядоченными событиями
  8. 3.1. Разработка и реализация организационной структуры имидж-системы и мониторинга имиджа вуза
  9. ПРИЛОЖЕНИЯ
  10. Специфика менеджмента веб-проектов
  11. Резюме
  12. Современное состояние индустрии Питания: проблемы и перспективы развития на региональном уровне
  13. Минимизация сети
  14. Глава 7. Социальная ответственность
  15. Основы оценки стоимости предприятия [бизнеса)
  16. сро как институт сетевых структур горизонтального типа
  17. ИСПОЛЬЗОВАНИЕ ОБУЧЕНИЯ
  18. ВВЕДЕНИЕ