Основные алгоритмы

Алгоритм Ли

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

Алгоритм представляет собой 4 шага.

Шаг 0. Полагаем, что узел N_s принадлежит дереву; L_ss = 0; для соседних с N_s узлов L_st = l_st; для остальных L_st = oo.

Шаг 1. Полагаем L_s = minL'_st = L_Sj + l_jF, где N_t — все узлы, соседние с текущим деревом. Дуга A_jt включается в число ветвей дерева.

Шаг 2. Если число ветвей дерева п=1, то конец поиска; если нет— перейти к шагу 3.

Шаг 3. L'_st t= rnin(L'_sj, L_sF + l_Ft) —перейти к шагу 1.

Выбор оптимальной трассы и кратных трасс на сетке между двумя точками

Поиск оптимальной трассы

Рассмотрим поиск оптимальной трассы на сетке прямоуголь­ной формы без диагоналей (рис. 3.5, а). Допустим, что стои­мость строительства трубопровода вдоль каждой их дуг сетки оценена каким-либо условным числом w. Эти числа-стоимости приведены в табл. 3.1, а номера дуг указаны на рис. 3.5, а. Поиск оптимальной трассы будем осуществлять в соответст­вии с алгоритмом, основная идея которого заключается в сле­дующем. Процесс поиска многошаговый. На первом шаге вво­дим в рассмотрение все возможные пути из начальной точки Л, имеющей координату (1,4), и продолжаем путь, имеющий наименьшую стоимость. На каждом последующем шаге опреде­ляем стоимость всех построенных к этому моменту путей от начальной точки и оставляем тот из них, который имеет наи­меньшую стоимость. Продолжаем на следующем шаге именно

этот путь, достраивая его во всех допускаемых сеткой направ­лениях на одну дугу. Получаем несколько новых путей. Из всех путей (с учетом отброшенных ранее) опять продолжаем наи­более перспективный путь до тех пор, пока в рассмотрение не попадет конечная точка. Решение заканчиваем отысканием та­кой трассы между начальной и конечной точками, для которой полный критерий оптимальности будет наименьшим. Решение проводим с помощью двух списков и и v, в которые записываем координаты х, у точки (или узла), а также направление входа в этот узел 8. На первом шаге записываем в список u (1) точку A (1,4) с w = 0 (направление входа в начальную точку безраз­лично), определяем для А соседние узловые точки и с соответ­ствующими характеристиками заносим в список v (1). Направ­ление входа в узел 9 может иметь четыре значения, которые условно обозначаем 0, 1/4, 1/2, 3/4. Причем O = 0 — это направле-

ние, определяемое осью х, а отсчет угла осуществляется про­тив часовой стрелки. Определяем в v(\) точку с минимальным значением w и переносим эту точку в список v (2). Далее в спи­сок 0(2) помещаем все соседние с ней точки и их характери­стики. В результате получаем список u (2) и список v (2).

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

Продолжаем заполнение списков. В результате второго шага получаем

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

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

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

Рассмотрим поиск оптимальной и кратных трасс на сетке, изображенный на рис. 3.5, 6. Условные стоимости строитель­ства трубопровода вдоль каждой из дуг приведены на рисунке на всех дугах. Начальная точка — A(1, 1), конечная — K(3, 4). Как и в предыдущем примере, поиск ведем с помощью спис­ков и и v. На первом шаге в списке u (1) записываем началь­ную точку А с координатами (1,1), а в списке v (1) —соседние точки с координатами (1,2) и (2,1) с соответствующими стои­мостями w и направлениями входа O.

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

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

Восстановление оптимального пути проводим по последнему списку u (37). Как видно, точка K достигнута двумя равноцен­ными путями с w=10, оба с направлением входа 0 = 1/4. По этому направлению ближайшим узлом обоих путей является точка 4,2. Здесь один путь уходит по направлению O =1/4 в точку 4,1, а другой — по направлению 6 = 0 в узел 3,2. Даль­нейшее движение путей понятно из списка u (37). Для нагляд­ности каждый из путей имеет свой индекс. Таким образом, имеем следующие два одинаковых по стоимости пути с w =10:

Если продолжать рассматривать пути, то уже на следую­щем шаге находим путь с w =14, это путь второй кратности. Восстанавливая его по направлениям входа, находим траекто­рию пути:

На рис. 3.5, б этот путь изображен пунктиром. Таким образом можно получить и все остальные пути, которые будут иметь большую кратность.

Поиск оптимальной трассы на прямоугольной сетке с диагоналями

Такая сетка изображена на рис. 3,2, б. Как видно из предыду­щих примеров, при составлении списков и и v каждую дугу характеризуют две величины — стоимость w и угол входа 6. При прямоугольной сетке углы 0 отсчитываются от направле­ния х против часовой стрелки. В случае сетки с диагоналями отсчет 8 ведется также от оси х против часовой стрелки, но значения следующие: 0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8- Если в прямо­угольной сетке без диагоналей каждая точак может иметь лишь 3 соседних точки, то при сетке с диагоналями — 7. Если отбросить из рассмотрения пути назад как заведомо беспер­спективные, то сетка с диагоналями будет допускать 5 направ­лений. Следовательно, при сетке с диагоналями каждая точка в списке и может иметь по 5 соседних точек, заносимых в спи­сок v. Это и является основным отличием поиска оптимального пути на сетке с диагоналями от сетки без диагоналей.