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

пути 1—>2->5—>3->4->6. При поиске этого пути не было об­ наружено ни одного контура.

Шаг 3. Поиск разветвлений пути от а до Ъ. Действия ша­ га 2 позволяют определить только один элементарный путь между вершинами а и Ь. Чтобы найти все остальные пути между а и Ь, рассмотрим разветвления предыдущего пути. Изложим действия этого шага на примере (рис. 2.1, табл.

2 . 1 ).

На шаге 2 установлен путь 1->-2->5-»-3-»-4->-6. Начнем отыскивать разветвление этого пути с конца, с предпослед­ ней вершины #5 = 4 (табл. 2.2). Путь от вершины Х\ = а до

#5 = 4 включительно считаем известным и ищем его продол­ жение так же, как на шаге 2 , с той лишь разницей, что в четвертом столбце таблицы 2 .1 из последней заполненной клетки выбираем не вершину 6, а вершину 1 , находящуюся на строку выше, чем #6 = 6. Другими словами, мы условно принимаем #6 за вершину контура и поступаем далее так же, как это делали на шаге 2 при появлении контура.

Согласно изложенному, для вершины # = 1 необходимо проверить условие существования контура. Первая верши­ на #i = l на отрезке пути 1->2->5—>~3->4 уже встречалась. Поэтому в четвертом столбце таблицы 2.1 исследуем верши­ ну 3, расположенную на строку выше, чем вершина 1. Вер­ шина 3 также не может служить очередным узлом второго пути, так как она уже была включена ранее в отрезок 1->-2->-3->-4 предыдущего пути. В четвертом столбце (табл. 2.1) все элементы уже рассмотрены. Это означает, что вто­ рой путь нельзя получить разветвлением от узла 4, поэтому попробуем найти ветвление от узла 3, предшествующего уз­ лу 4 в предыдущем (первом) пути (табл. 2.2).

Теперь, зная отрезок пути 1-»-2—>-5-»-3 , попытаемся опре­ делить разветвление от узла 3. При этом вершину 4 (табл. 2 .2 ) условно примем за вершину контура и повторим дейст­ вия шага 2. В третьем столбце таблицы 2.1 рассмотрим вер­ шину 2, которая находится на строку выше, чем вершина 4,

39

и проверим для нее условие контура. Вершина 2 в отрезке пути 1->2-»-5—»-3 уже есть, поэтому в третьем столбце на строку выше исследуем вершину х = 1 , которая в пути 1 —»- —>2->5— тоже имеется. Теперь остается проверить в треть­ ем столбце только вершину х= 5. Но вершина 5 в оставлен­ ной части пути также существует. Следовательно, от верши­ ны 3 разветвление найти нельзя. Теперь, считая известной часть пути 1—>-2—>-5, пробуем искать ветвление от вершины 5. Условно принимаем x^=S за вершину контура и в пятом столбце анализируем вершину 6, расположенную на строку выше, чем вершина 3. Вершина 6 может служить продолже­ нием пути 1-*-2->-5. Кроме того, она совпадает с вершиной

Таблица 2 • 3

Ь = 6 . Таким образом, определен второй путь 1->2->5-^6, по­ лученный ветвлением предыдущего (первого) пути. Длина этого пути 48 есть сумма длины 33 звена 1->2->5 и веса ду­ ги use, равного 15.

Второй путь помещен в таблице 2.3. Третий путь ищем ветвлением второго пути от вершины #з= 5. Весь процесс повторяем заново. Считаем известным отрезок пути 1—>-2—>-5. Принимаем условно Х4 = 6 за вершину контура и в пятом столбце таблицы 2 .1 рассматриваем вершину 2 , лежащую на строку выше, чем вершина контура 6. Вершина 2 в отрез­ ке пути 1—>-2—>-5 уже есть. Поскольку в пятом столбце выше вершины 2 ничего нет, то ветвление от узла невозможно. Попытаемся найти его от вершины 2.

Считаем установленным отрезок пути 1—>-2 и принимаем условно вершину 5 за вершину контура. Во втором столбце таблицы 2 .1 анализируем вершину, расположенную на стро­ ку выше, чем вершина 5. Такой вершиной будет а = 1 . По­ скольку в отрезке пути 1 - > 2 она уже есть, то во втором столб­ це возьмем вершину 3, находящуюся на строку выше пер­ вой. Вершина 3 может служить продолжением пути 1—>-2. Поэтому во втором столбце таблицы выбираем в правом нижнем углу клетки длину дуги Пгз, равнуюЮ, и суммируем с длиной звена 1—^2: 30+10 = 40.

Третий путь будем фиксировать в таблице 2.4. Вершину 3 поместим в строке R, а длину звена 1->-2->-3, равную 40,— в строке Д + 1. В нашем случае вершина 3, взятая из второ­

40

го столбца таблицы 2 .1 , не приводит к контуру, поэтому рассмотрим третий столбец и выберем в нем из последней заполненной клетки вершину 4 и вес дуги И34, равный 5.

Поскольку вершина 4 в найденный отрезок пути 1—>-2->3 не включена, то в таблице 2.4 в строку R заносим 4, а в строку — величину 4 0 + (— 5) = 35 как длину звена 1—>-2->-3->-4. Далее исследуем в четвертом столбце таблицы 2 .1 в последней заполненной клетке вершину 6, которая, очевидно, является замыкающей в третьем пути 1—>2->3—>- ->4->6. Длиной этого пути будет величина 105 (табл. 2.4). Четвертый путь следует определять разветвлением третьего

пути.

Продолжая аналогичный поиск, можно найти все осталь­ ные пути между выбранными вершинами а = 1 и Ъ= 6 :

а = 1 таблицы 2 .1 рассмотрены все элементы.

При определении всех путей графа сравнением можно найти путь максимальной или минимальной длины, или те

41

При соблюдении условий (2.1) длина установленного пути будет лежать в интервале [с, d].

Следует отметить, что в качестве вершин а и Ъмогут быть взяты любые из вершин графа и тем самым определены все возможные пути на графе. Если в шаге 1 при составлении таблицы 2 .1 учитывать только дуги, выходящие из каждой вершины, то с помощью изложенного алгоритма можно най­ ти пути, в которых движение осуществляется по направле­ нию стрелок. Предлагаемый нами метод позволяет опреде­ лять пути максимальной длины в любом мультиграфе. Этим методом можно воспользоваться, если какая-либо часть пу­ ти предварительно задана и для нее нужно найти продолже­ ние — экстремальный путь между вершинами а и b (имеет­ ся в виду, что в заданную часть вершины а и & не входят). Для такого случая ранее описанные методы не пригодны.

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

§ 3. РЕАЛИЗАЦИЯ АЛГОРИТМА НА ЭВМ

Информация о дугах графа задается неупорядоченным множеством кодов (строк), составляющих некоторое множе­ ство L :

Здесь i и j означают номера вершин, ai3 — вес дуги uijt на­ правленной от z-й вершины к j-й. При такой записи под каж­ дую из составляющих i, j, ai7может быть занято три деся­ тичных разряда (имеется в виду, что код (2 .2 ) помещен в одну 36-разрядную ячейку ЭВМ). Таким образом, каждая из составляющих (2 .2 ) может принимать максимальное зна­ чение, равное 999. Начальные условия задачи могут зада­ ваться одним из трех способов:

1)определение на графе между узлами а и Ъпутей (це­ пей) минимальной длины или всех путей и их длин;

2)нахождение на графе между узлами й и Ь пути мак­ симальной длины или всех путей и их длин;

3)установление на графе между узлами а и Ь всех пу­ тей (цепей), длина которых лежит в заданном интервале.

42