В.П. Степанов, П.В. Степанов
8
Шаг 6. Если все пометки всех вершин постоянные, т. е.
B
=
A
, то
на этом определение оптимальной трассы кабеля завершается.
После этого происходит восстановление трассы прокладки кабеля.
На втором этапе алгоритма
задается допустимое значение от-
клонения от оптимального значения
E
. На первом этапе, в отличие от
алгоритма Дейкстры, для каждой вершины в зависимости от мощно-
сти множества
V
(
s
) вычисляются по формуле (1) и запоминается не
одно, а ряд значений пометок. Затем для каждой вершины отбрасы-
ваются те значения пометок, для которых выполняется соотношение
(
)
( )
( )
0
,
,
0, 2, ...,
1
sj
k
p p E s V d j
V s
> + ∈ =
−
.
(3)
В случае дальнейшего получения вариантов трасс прокладки из
таких значений пометок их значения будут только возрастать.
Такой подход успешно применяется для поиска оптимального по
длине и близких к нему маршрутов проезда на дорожной сети боль-
шой протяженности [6].
Программная реализация алгоритма.
Алгоритм решения задачи
реализован в виде клиент-серверного приложения с использованием
программного интерфейса электронной карты Google Maps [7]. В ка-
честве сервера используется web-сервер Apache с предустановлен-
ным языком PHP 5-й версии. Клиентская часть реализована на
HTML5 с применением языка JavaScript. Обработка запросов на по-
иск решения осуществляется на сервере. Для хранения данных графа
и полученных трасс используется база данных.
Работа с web-приложением происходит через систему меню с ис-
пользованием мыши. После загрузки электронной карты с помощью
указателя мыши назначаются вершины графа возможных трасс про-
кладки. Затем указываются соединения вершин графа между собой
для кабельной канализации и соответствующие длины участков. На
карте помечаются начальная и конечная вершины для прокладки оп-
тического кабеля. Имеется возможность оперативного изменения ха-
рактеристик вершин и ребер графа на электронной карте.
В программе реализованы два алгоритма — Дейкстры и нахожде-
ния всех
E
, близких к минимальной по длине трасс прокладки кабеля.
Полученные минимальная по длине и все близкие к ней варианты
трасс прокладки ОК между двумя вершинами графа выделяются на
карте различными цветами.
С помощью разработанной программы проведены расчеты для
района города с 85 вершинами и 123 ребрами. Для поиска близких к
минимальной трассе решений между точками 1 и 25 параметр
E
зада-
вался равным 50 м. На рис. 3 приведен пример представления резуль-
татов поиска трасс кабеля между двумя точками для заданного райо-
на. Для этих точек получены трасса прокладки кабеля минимальной
