III Международная студенческая научная конференция Студенческий научный форум - 2011

Алгоритм построения минимального остовного дерева предполагает соединение всех узлов сети с помощью путей наименьшей длины. Типичной задачей, для решения которой необходим такой алгоритм, является создание (прокетирование) сети дорог с твёрдым покрытием, соединяющих населённые пункты в сельской местности, где дороги, соединяющие два каих-либо пункта, могут проходить через другие населённые пункты. Наиболее экономичный проект дорожной системы должен минимизировать общую длину дорог с твёрдым покрытием, при этом желаемый результат можно получить с помощью алгоритма построения минимального остовного дерева.

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

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

В соответствии с рассматриваемой методикой спроектирована сеть трубопроводов минимальной длины  км, соединяющая приёмный пункт со всеми добывающими платформами.

Код для цитирования: Скопировать