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

очень удобен как для ручного счета, так и для реализации на ЭВМ. Как и во всех предыдущих методах, предполагает­ ся, что исходный граф не содержит контуров.

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

A. Типы рассматриваемых графов. Все индексные мето­ ды, основанные на идее индексации вершин, применяются при определении максимального и минимального путей на сетевых графах, не содержащих контуров. Исключение со­ ставляет метод Форда, с помощью которого можно находить минимальные пути и на неориентированном графе.

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

Б. Объем вычислений. В индексных методах объем вы­ числений зависит от количества дуг на графе. Для графов с числом дуг около 20 можно применять алгоритмы вруч­ ную. В матричных методах на объем вычислений влияет число вершин графа, причем эта зависимость квадратичная. Если граф имеет свыше 10 вершин, то на практике анализ таких графов вручную затруднителен и необходимо исполь­ зовать ЭВМ.

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

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

инаглядности выполняемых операций. Процесс индексации

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

, Ниже представлен обобщенный алгоритм.

§2. НАХОЖДЕНИЕ ЭКСТРЕМАЛЬНЫХ ПУТЕЙ

ИПУТЕЙ ЗАДАННОЙ ДЛИНЫ НА ЛЮБОМ ГРАФЕ СЕТИ

Если рассматривается граф без учета ориентации, то предлагаемый алгоритм позволяет найти все возможные це пи графа, определить сумму числовых характеристик ребер для каждой цепи, выделить максимальную или минималь­ ную из полученных сумм, а также цепь с заданной длиной* Алгоритм можно также применять для установления экст­

а и Ь: например, цепь 1->-2->5->-3->4—ИЗ между узлами 1 и 6. Длина этой цепи, т. е. сумма весов ребер, будет равна 30+ 3+ 20 -f-5+ 7 0 = 128. Если теперь восстановим у всех вет­ вей графа прежнюю ориентацию, то в найденном пути от а = 1 до 6= 6 направления дуг будут различные. Условим­ ся под длиной такого пути подразумевать сумму числовых характеристик всех дуг рассматриваемой последовательно­ сти, причем для дуг, по которым проходим от а к 6 в направ­ лении стрелок, числовую характеристику будем брать со знаком «плюс», а для дуг, по которым проходим против на­ правления стрелок,— со знаком «минус». В нашем случае длина пути от 1 до 6 равна 78. Максимальным в этом случае может оказаться не обязательно путь, в котором веса всех дуг взяты со знаком «плюс». Например, максимальным пу­ тем от 1 до 6 на графе (рис. 2.1) будет 1->2-»-3->-4->-6 со зна­ чением L = 3 0+ 10 — 5+70 = 105.

Всегда можно построить граф, в максимальном пути ко­ торого содержится хоть одна дуга, движение по которой осу­ ществляется в обратном направлении и вес которой берется со знаком «минус». Действительно, пусть имеется произ­ вольный граф G(X, U), в котором по какому-либо алгоритму между вершинами А и В найден максимальный путь дли­ ны L (рис. 2.2), а веса всех дуг этого пути положительные

•• л

34

(со знаком «плюс»). Дополним множество дуг U графа тре­ мя дугами: щ, 112 , щ так, чтобы мажорантой нового графа стала вершина С. Допустим, что веса дуг щ, щ, иъ равны со­ ответственно нулю, I и £, где I — произвольное положитель­ ное число, а £ < /. Очевидно, максимальным путем от А до С нового графа будет путь, включающий максималь­ ный путь первоначального графа и дуги и2, из. Длина

этого пути будет равна L +

+Z— £, где L — длина мак­ симального пути первона­ чального графа от А до В. Вес дуги из взят со знаком «минус». Следовательно,

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

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

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

Рассмотрим вычислительный алгоритм, позволяющий решить поставленную задачу и найти на графе все пути, длина (сумма весов дуг) которых лежит в заданном интер­ вале [с, d\.

Сущность алгоритма заключается в том, что на графе рациональным способом перебираются все возможные цепочки между двумя любыми узлами a mb л для них опреде­ ляется сумма весов дуг, взятых с соответствующими знака­ ми. Алгоритм построения искомых путей разберем на кон­ кретном примере (рис. 2.1). Действие алгоритма можно пред­ ставить следующими основными шагами.

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

35

дуг — четыре, поэтому таблица 2 .1 будет иметь четыре строки. Так как на графе шесть вершин, то и столбцов тоже шесть: 1, 2, . . . , 6. Заполним первый столбец элементами.

Таблица 2. /

Из вершины 1 выходит три дуги, поэтому элементов в столбце 1 таблицы 2.1 будет три. При этом каждую клетку, расположенную на пересечении ;-го столбца и i-й строки в таблице 2.1, разбиваем на две половинки. В верхнем левом углу записываем номер вершины, с которой соединена ду­ гой вершина 1 , в нижнем правом углу — вес этой дуги со знаком «плюс», если дуга исходит из вершины 1 , и со зна­ ком «минус», если дуга оканчивается в вершине 1 .

Рассмотрим дугу и\з, которая связывает вершину 1 с вер­ шиной 3. Вес дуги равен двум. Так как дуга исходит из вершины 1 , то в нижнем правом углу клетки (1 ,1 ) записы­ ваем вес дуги со знаком «плюс», т. е. + 2 , а в верхнем левом углу — число 3 — номер вершины 3 (табл. 2.1). Аналогично заполняем все клетки таблицы 2 .1 относительно остальных вершин графа.

Шаг 2. Построение любого пути от а до Ъ(а и Ъ— две любые вершины графа). Искомый путь a = Xi—ке2—> -...

. . . х п = Ъ определяем по известному правилу с помощью построенной на предыдущем шаге таблицы 2 .1 (п — число вершин искомого пути, n ^ N ).

Предположим, что мы хотим начать поиск всех путей графа с первой вершины а = х i= l. Номер вершины Xi = 1 находится в первом столбце строки Iq. И з вершины 1 можно

36

ки). Условимся каждый раз брать в столбце вершину из последней заполненной клетки. Таким образом, попав в j-й столбец таблицы, будем выбирать в нем из последней запол­ ненной строки вершину х, номер которой указывает следу­ ющий столбец, в котором вновь берем следующую проме­ жуточную вершину искомого пути, и т. д. Этот процесс про­ должаем до тех пор, пока в качестве очередной вершины х не будет взята вершина х п = Ъ, являющаяся последним уз­ лом на пути от а до Ь. В этом случае путь а=Х\-+Х2- + .. .

. . . ~*хп = Ьсчитается найденным.

Для нашего примера определим первый путь от верши­

.£2= 2. Далее во втором столбце из последней заполненной клетки возьмем номер следующей вершины Хз= 5. Затем в пятом столбце таблицы отыщем номер вершины лг4= 3, пос­ ле чего попадем в третий столбец, где фиксируем jcs= 4, и,

Следует отметить, что при выборе в ;-м столбце таблицы очередного промежуточного узла х, смежного с j-м, можно вновь попасть в вершину х , которая вошла в найденный к данному моменту отрезок пути. То, что одна и та же вер­ шина х в пути встречается дважды, говорит о появлении контура. Это недопустимо, так как мы ищем только эле­ ментарные пути, в которые любая вершина и дуга графа могут входить не более одного раза. Чтобы избежать обра­ зования контуров в искомом пути, необходимо учитывать следующее условие.

Каждый раз, выбирая в j-м столбце из последней запол­ ненной клетки вершину х^, следует проверять, не встреча­ лась ли она в найденном уже отрезке пути. Если не встреча­ лась, то поиск продолжается, в противном случае в ;-м столб­ це нужно отыскать вершину х, номер которой расположен на строку выше, чем x k, и для нее вновь проверить условие появления контура. Если новая вершина х опять приведет к контуру, то в столбце j строкой выше рассмотрим следую­ щую вершину.

В процессе поиска может оказаться, что в j-м столбце нельзя выбрать ни одну из вершин х, смежных с j-й верши­ ной, так как все они вошли в определенный к данному мо­ менту отрезок пути. В этом случае необходимо вернуться в столбец i, из которого попали в j-й, и проанализировать в нем вершину Xi, номер которой записан на строку выше, чем номер вершины

37

Дальнейшее продолжение искомого пути осуществляем с вершины x t так, как указывалось выше. Для Xi проверя­ ем существование контура и либо переходим в лггй столбец и отыскиваем в нем вершину из последней заполненной клетки, либо (при наличии контура) анализируем вершину на строку выше, чем x t .

Для того чтобы было легче производить анализ на появ­ ление контура, а также фиксировать искомые пути и их дли­ ну, рассмотрим таблицу 2.2. Эта таблица состоит из двух строк: R и (-R-J-1) и содержит столько столбцов, сколько

Таблица 2. 2

. . . , х п искомого пути, а в (-R-j-l)-io — длину (сумму в е с о Е дуг) соответствующих звеньев пути:

а = Х1-^X2 , Х\-^Хзг+Хъу . . . , Xi~^X2~^. . .-+хп = Ъ.

Рассмотрим процесс подробнее на примере (рис. 2 .1 , табл. 2.1). Номер вершины х\, равный 1, помещаем в первый столбец строки R таблицы 2.2, а длину звена, состоящего из одной вершины х\, равную нулю,— в первый столбец стро­ ки (.R +l). Далее из последней заполненной клетки первого

санной в правом нижнем углу клетки, где зафиксирована вершина Х2 .т0+30 = 30. Величину 30 помещаем во второй столбец строки (Д + 1 ).

Далее во втором столбце таблицы 2.1 из последней за­ полненной клетки берем вершину х$= 5 и длину дуги Н25» равную + 3 . Номер вершины 5 в строке R таблицы 2.2 не встречался, поэтому в третий столбец строки R записываем 5, а в третий столбец (Д+1)-й строки — сумму, равную дли­

ную — 20. Номер вершины 3 в заполненных трех столбцах

38