Главная  Переработка нефти и газа 

Скачать эту книгу

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 [ 41 ] 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

(11.10)

где /(/-опт) - стоимость оптимального пути (или путей).

Опыт применения алгоритмов Ли и АУП показал их достаточно высокую эффективность при поиске оптимальных трасс между двумя точками - начальной и конечной. При поиске оптимальных трасс с отводами или конфигурации трубопроводной системы возникают трудности, связанные с практической реализацией названных алгоритмов.

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

3. Алгоритм поиска кратчайшего пути на неориентированном графе

Рассмотрим алгоритм, предложенный Дийкстрой. Этот алгоритм, по-нашему мнению, наиболее подходящ для поиска оптимальных трасс трубопроводов.

Поиск осуществляется на сетке с дугами произвольного очертания, которые образуют неориентированный граф с верщи-памп в узлах Ni, Nj. Каждой дуге Л,-,- поставлена в соответствие длина lij. Если пара узлов Ni, Nj не связана дугой, то lij = oo. Величины Uj могут быть любыми; ограничения по максимуму на степень вершин графа отсутствуют.

В процессе поиска кратчайшего пути из узла Ns в узел Ni будем искать кратчайшие пути в каждую вершину Л,- ЦФз), которая связана с N кратчайшим путем, т. е. дерево графа.

После построения дерева каждая кратчайшая цепь будет состоять из дуг дерева. В начале поиска все дуги неориентированной сетки считаются хордами, т. е. не принадлежащими дереву. В процессе поиска число ветвей дерева постепенно увеличивается от О до п- 1 {п - число узлов сетки).

Рассмотрим далее алгоритм построения дерева графа.

Полагаем, что узел Ns принадлежит искомому дереву и найдено т. ветвей дерева (/п = 0, 1, ..., п - 2). Длину кратчайшей цепи из узла Ns в узел Ni обозначим Li, а длину такой цепи, содержащей кро.ме ветвей дерева не более одной хорды,- Lst- Если все цепи из Ns в Nt содержат на некотором шаге алгоритма больше одной хорды, то полагаем Lsi = оо. Величина Lst изменяется по мере увеличения т. Кроме того,

1st > Lst.

Предположим, что в ходе алгоритма построена часть искомого дерева и имеется узел Nt, не принадлежащий этому дереву. Если есть дуга Ац или дуга Ati (где iV, - некоторый узел

построенного дерева), то узел Nt не принадлежит этому дереву. Тогда цепь L\i из узла Ns в узел Nt содержит только ветви дерева и, следовательно, Lsi = Lsi. Из определения Lst следует

Lsi = min(Ls,- + /fi),

где минимум берется по всем узлам построенного дерева.

Обозначим Nf соседний с построенным деревом узел, который обладает минимальной величиной Lst, а Nj - узел дерева, па котором достигается этот минимум:

Ср = min (L,.- + Up) = Lsi + lif. (11.11)

В этом случае Lsf = Lsf, а дуга Ajf должна принадлежать искомому дереву.

Алгоритм представляет собой 4 шага. Шаг 0. Полагаем, что узел Ns принадлежит дереву: Lss = 0; для соседних с Ns узлов Lst = lst; Для остальных Ls( = oo. Шаг L Полагаем Ls = mm Lst, где -все узлы, соседние с текущим деревом. Дуга Ajt включается в число ветвей дерева. Шаг 2. Если число ветвей дерева равно п- I, то поиск прекращаем, если нет - переходим к шагу 3.

Шаг 3. Lst = mm(Lst, L,,f + f<) - переходим к шагу 1.

§ II.4. МЕТОДЫ ПОИСКА ПО АЛГОРИТМАМ ЛИ И АУП

1. Поиск между двумя точками без учета расстановки перекачивающих станций Имеем сетку произвольной формы. Упорядочиваем ее, как было описано в § 11.2, и оцениваем все дуги сетки (кроме фиктивных) значениями критерия w. Составляем таблицу исход-Таблица 11.1

Исходные данные

-if"

Рис. 11.4. Поиск оптимального пути:

а - основного; б - основного и кратных

НЫХ данных (табл. 11.1) для сетки, изображенной на рнс. 11.4, а.

Поиск осуществляем с помощью двух списков и и и, в которые записываем координаты точки, а также направление входа в этот узел. На первом шаге записываем в список и (1) точку А (1,4) с w = 0 (направление входа в начальную точку безразлично), определяем для А соседние узловые точки с соответствующими характеристиками, заносим в список v (1). Направление входа в узел О может иметь четыре значения, которые условно обозначаем О, 1/4, 1/2, 3/4. Причем Э = 0 - это направленне, определяемое осью х, а отсчет угла осуществляется против часовой стрелки. Определяем в v (1) точку с минимальным значением w и переносим эту точку в список и (2). Далее в список v (2) помещаем все соседние с пей точки и их характеристики. В результате получаем список и (2) и список V (2).

Список и (2)

Список V (2)

Из списка V на каждом шаге вычеркиваем точки, совпадающие по координатам с перенесенной в список и точкой, но имеющие большие значения w.

В результате второго шага получаем

Этот процесс продолжается до тех пор, пока конечная точка яе окажется в списке и. Приводим окончательный список.

По направлению входа Э в точки последнего списка и восстанавливаем оптимальный путь

е=3,4 о 3 4 о 3,4 о о

X, у 1,4--1,3---2,3--v2,2---3,2---3,1---4,1---

-»-5,1-»-6,17,18,1.

Как видно из последнего списка и, этому пути соответствует минимальное значение суммы чисел, оценивающих дуги, при прохождении точки А (1,4) в точку К (8,1), равное 36,4; то же значение получим, если просуммируем стоимости всех дуг оптимального пути.

Список и (последний)

2. Поиск кратных трасс

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

Рассмотрим поиск оптимальной и кратных трасс на сетке, изображенной на рис. 11.4,6. Условные стоимости строительства трубопроводов вдоль каждой из дуг приведены на рисунке на всех дугах. Начальная точка А (1,1), конечная - /((4,3). Нч первом щаге в списке и (1) записываем начальную точку А с координатами (1,1), а в списке и(1)-соседние точки с координатами (1,2) и (2,1) с соответствующими стоимостями w и направлениями входа Э

Список и (1) Список V (1)

На втором шаге из списка v (1) переносим в список и (2) путь наименьшей стоимости с данными w и О - путь из узла (1,1) в узел (1,2). Из списка v (1) эту точку вычеркиваем. В список v (2) заносим точки, являющиеся соседними с точкой 1,2.

Список и (2)

Список V (2)

Результаты третьего, четвертого, пятого и последнего - тридцать седьмого шагов приведены в списках и(3), у(3); u(4), i(4); u(5), у(5); u(37).

Список и (3)

Список и (3)

Заказ № 1690