Файл: Цой, С. Синтез оптимальных сетей в системе управления горными предприятиями.pdf

Г л а в а II

МЕТОДЫ ПОИСКА ЭКСТРЕМАЛЬНЫХ ПУТЕЙ НА ЛЮБОМ ГРАФЕ

Как уже указывалось, в основе сетевого моделирования лежит сетевой график, представляющий собой графическую схему, состоящую из кружков, соединенных линиями со стрелками. Подобный подход к описанию различных явле­ ний встречается не только в сфере экономики, но и в дру­ гих областях (например, при моделировании электрических, транспортных, вентиляционных, гидравлических и других сетей). При этом сетевая модель может состоять из графов самых разнообразных видов. Например, современное угле­ добывающее производство как в период строительства или реконструкции предприятий, так и в период их эксплуата­ ционной деятельности представляет ряд сложных систем взаимосвязанных работ и событий, которые могут изобра­ жаться топологически сложными графами с контурами. В дальнейшем графы анализируются и рассчитываются с помощью известных методов.

Решение большого круга практических задач часто свя­ зано с необходимостью определения на графах экстремаль­ ных путей. Известно много различных методов для решения подобных задач. В основном они предназначены для поиска экстремальных путей на ориентированных графах без конту­ ров. На практике же часто требуется находить экстремальные пути на любом графе. В общем случае это может быть муль­ тиграф, у которого две вершины соединены произвольным количеством противоположно ориентированных дуг. Поиск максимального или минимального пути при этом сводится к установлению цепочки дуг, в которой ни одна вершина че встречается дважды. Имеющимися методами данную задачу решить нельзя. Возникает необходимость разработки обще­ го метода, позволяющего находить экстремальные пути на любом графе: ориентированном, смешанном и неориентиро­ ванном, с контурами или без них.

29

§ 1. КРИТИЧЕСКИЙ ОБЗОР МЕТОДОВ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ

Как в отечественной, так и зарубежной литературе в на­ стоящее время описаны различные методы поиска экстре­ мальных путей (цепей). Наиболее распространенные из них можно разделить на два класса: индексные и матричные.

В основу индексных методов положен принцип индек­ сации, т. е. присвоения вершинам графа некоторых индек­ сов, значения которых изменяются в процессе решения. Эти величины при реализации алгоритма представляют собой длину пути от фиксированной до рассматриваемой вершины. Индексными можно считать методы Л. Р. Форда [61], Му­ ра [68], метод произвольного дерева [22] и другие [5, 7, 22].

Все матричные методы связаны с построением матрицы смежности весов, элементами которой являются веса соот­ ветствующих дуг или ребер. Экстремальные пути находят­ ся последовательным преобразованием исходной матрицы смежности. К матричным относятся методы А. Шимбела [69], Ж. Оттермана [23], индексно-матричный [52], В. А. Паршикова [39] и другие [23, 26, 27]. Названные методы с примерами детально изложены в третьей главе монографии «Прикладная теория графов» [53], поэтому ограничимся только их кратким описанием.

Индексные методы

Наиболее распространенные методы определения макси­ мальных путей на ориентированном графе (критические пу­ ти)— алгоритмы, описанные в работах [27, 53, 55]. Если нумерация сети произвольная, то в качестве основного ис­ пользуется алгоритм Л. Р. Форда [27, 61]. С помощью мето­ да Форда на графе можно найти путь минимальной длины

ритм установления кратчайших путей состоит в присвоении

определяются пути минимальной длины как для неориен­ тированных, так и для смешанных и ориентированных гра­ фов, с контурами или без них. Основные преимущества этого метода — его простота и довольно быстрая сходимость про­ цесса вычислений. Вместе с тем указанным методом невоз­ можно найти максимальные пути на неориентированном и ориентированном графах с контурами. Поэтому им нельзя воспользоваться при решении задач, поставленных в гла­

30

ве I. Однако идея метода Форда положена в основу различ­ ных алгоритмов при определении длины критического пу­ ти. Множество других методов, разработанных как совет­ скими, так и зарубежными исследователями, являются, по существу, модификацией метода Форда.

Метод отыскания максимального пути с помощью про­ извольного дерева [52, 53] и индексный метод [53] также основаны на идее присвоения вершинам индексов и различа­ ются лишь способами их присвоения. Основное преимущест­ во этих методов заключается в том, что они достаточно про­ сто могут реализоваться даже на малых ЭВМ с быстродейст­ вием порядка 5000 операций в секунду и объемом оператив­ ной памяти до 4000 ячеек. Максимальное время счета для

при их использовании приходится затрагивать ряд других алгоритмов (например, алгоритм построения первоначаль­ ного дерева, с помощью которого производится индексация).

Близок к рассмотренным и метод Веллмана — Калаба [64], основанный на идее динамического программирования. Здесь последовательно вычисляются значения длины макси­ мального пути от мажоранты до всех остальных вершин, от­ стоящих от конечной на одну операцию (дугу), затем на две и т. д. Метод обеспечивает довольно быструю сходимость — за (N— 2) итерации, где N — количество вершин на графе. Как и все предыдущие методы, алгоритм Веллмана — Калаба не решает задачи поиска максимальных путей на ориенти­ рованных графах с контурами.

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

Матричные методы

Экстремальные пути на графе могут находиться с по­ мощью матричных методов. Решение задачи в этом случае может быть получено с помощью матрицы смежности весов А , элементами a которой являются веса дуг иц. Если вер­ шины i и j графа дугой не связаны, то соответствующий эле­ мент матрицы a,ij обозначается знаком оо. К наиболее из­ вестным относятся методы А. Е. Шимбела [69] и И. Е. Оттермана [23]. Для установления кратчайшего пути между двумя любыми вершинами Шимбел предложил процесс ум­ ножения (возведения в степень Т = 1, 2, . . . , N — 1) исход-

31

ной матрицы смежности. При умножении используются специальные операции над элементами ац .

Перемножение матриц заканчивается, когда AF = А !Г+ 1

представляют минимальные пути между i-й и j'-й вершина­ ми графа. Преимущество данного метода по сравнению с индексными заключается в том, что при решении получают­ ся минимальные пути между двумя любыми вершинами. Кроме того, метод Шимбела может применяться при нахож­ дении минимальных путей (цепей) между узлами и для не­ ориентированных графов. Но вместе с тем следует отметить, что алгоритм Шимбела громоздок, а объем вычислений рез­ ко возрастает с увеличением количества вершин на графе. Трудность ручного счета очевидна, так как приходится иметь дело с матрицами, каждый элемент которых обраба­ тывается. Уже при iV>10 вычисления желательно прово­ дить на ЭВМ. Основным «неприятным» моментом при реали­ зации матричного метода на ЭВМ является необходимость выделения большого объема памяти для хранения элементов матриц.

В отличие от метода Шимбела метод Оттермана [23] по­ зволяет найти не только величины первых кратчайших пу­ тей, но и отыскать вторые, третьи и т. д. k-e по длине ми­ нимальные пути между вершинами. Сложность и большой объем вычислений затрудняют использование метода Оттер­ мана для ручного счета даже на графах незначительных размеров, поэтому на практике его целесообразно реализо­ вать на ЭВМ.

С точки зрения численной реализации огромное преи­ мущество по сравнению с изложенными имеет метод В. А. Паршикова [39], предназначенный для определения на графе только кратчайших путей.

Идея метода заключается в преобразовании исходной матрицы смежности, т. е. в замене каждого из ее элементов akj на сумму двух других, меньшую по величине (если это возможно). Другими словами, непосредственная связь меж­ ду узлами k и j заменяется путем, длина которого меньше по величине веса akj. Основное преимущество рассматривае­

мого метода — простота алгоритма вычислений. Дальнейшей модификацией матричного и индексного

методов является индексно-матричный метод [52, 53]. В ка­ честве исходной информации применяется матрица смеж­ ности весов. Алгоритм нахождения экстремальных путей от фиксированного узла до всех остальных состоит в пере­ счете индексов (аналогично индексным методам). Метод

32