Как проехать на метро?

Архангельский Андрей

       В примере VAZKompl было показано, как построить дерево на двух таблицах. Но так как дерево есть частный случай графа, то этим способом можно представить любой граф.
       Граф — это структура данных, состоящая из узлов, соединенныйх ребрами. Ребра могут быть направленными (допускать перемещения по ним только в одном направлении) и ненаправленными (допускать перемещение в обоих направлениях). Количество входящих в узел ребер называется его полустепенью входа (indegree), количество выходящих ребер называется его полустепенью выхода (outdegree). Множество ребер, позволяющих переместится от одного узла к другому, называется путем. Цикл — это путь, вовращающийся к узлу, от которого он начался, не пересекаясь сам с собой (напоминает букву О, но не цифру 8).
       Рекурсивно структурированными связями между данными являются либо деревья (иерархии), либо обобщенные направленные графы.
       Деревья характеризуются большим количеством специфических, очень полезных свойств.
       Например, дерево представляет собой граф без циклов. Это означает, что ни один путь не повернет сам на себя, поэтому, следуя по нему невозможно попасть в бесконечный цикл. Кроме того, всегда можно пройти от корня до любого другого узла дерева. Те случаи, когда в программе VAZKompl возникали бесконечные циклы, рассматривались как ошибки разработчика комплексов и должны быть исправлены.
       Но если используется обобщенный граф, например, схема линий метрополитена, то как в нем найти путь от одного узла к другому, используя вышеописанные приемы. Эта интересная задача может подсказать решения в других аналогичных задачах.
       Итак, для примера возьмем схему метрополитена г.Москвы и представим ее в БД в виде обобщенного графа и найдем путь между любыми двумя станциями.
       Для этого в одной таблице разместим станции, как узлы графа, а в другой связи между станциями, как ребра. При этом переходы между станциями на разных линиях также рассматриваются как связи.

Create table MStations
   (Code     AZInt32 not null primary key, -- код станции
    Line     AZInt32,                  -- линия, на которой находится станция
    Name     AZTitle,                  -- наименование станции
    Note     AZNotes);                 -- возможные комментарии
Commit;

Insert into MStations(Code,Line) values (0,0); Commit; Alter table MStations add foreign key (Line) references MStations on update cascade;

       Таблица MStations очень простая — всего четыре поля, которые описывают станцию. Поле Line введено просто для удобства отображения станций в форме для пользователя, т.е. сначала показывается список линий метро, а затем станции на выбранной линии. Так например, сделано на сайте московского метрополитена www.mosmetro.ru. Однако, в дальнейшем будет показано, как это поле может помошь в выборе более оптимального пути.

Create table MEdges
   (StLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    StRight     AZInt32 references MStations on update cascade 
                                             on delete cascade,
    RouteTime   Time,
    RouteNote   AZNotes,
Primary key(StLeft,StRight));
Commit;

       Таблица MEdges описывает связи между станциями. StLeft указывает на станцию, которая находится на левом конце ребра (перегона между станциями), а StRight — указывает на станцию, которая находится на правом конце ребра. Поле RouteTime определяет время нахождения в пути между этими станциями. Подобным образом можно добавить и другие описания ребра, например, расстояния между станциями и т.п.
       Для того чтобы заполнить эти таблицы используется скрипт MetroLines.txt.

Insert into MStations(Code,Line,Name) 
               values(1000,0,'Сокольническая линия');
Insert into MStations(Code,Line,Name)
               values(1041,1000,'Улица Подбельского');
Insert into MStations(Code,Line,Name)
               values(1042,1000,'Черкизовская');
Insert into MStations(Code,Line,Name)
               values(1043,1000,'Преображенская площадь');

       Так как коды станций присваиваются вручную, то заполнение таблицы MStations выполняется обычным операторм Insert.

Insert into MEdges(StLeft, StRight, RouteTime)
Select Lft.Code, Rgt.Code, '00:02:30' from MStations as Lft, MStations as Rgt
 where Lft.Name ='Улица Подбельского'
   and Rgt.Name='Черкизовская';

Insert into MEdges(StLeft, StRight, RouteTime)
Select Lft.Code, Rgt.Code, '00:02:30' from MStations as Lft, MStations as Rgt
 where Rgt.Name ='Улица Подбельского'
   and Lft.Name='Черкизовская';

       С одной стороны, по ребрам можно двигаться в обоих направлениях и это означает, что граф ненаправленный, но с другой стороны нахождение пути по ребру, у которого нет направления, проблематично. Поэтому представим этот граф как направленный, но между двумя вершинами есть два пути в разных направлениях. Это выгодно еще и потому, что переходы между станциями реально имеют разную длину в одну и в другую сторону, что и можно отобразить с помощью поля RouteTime. При заполнении этой таблицы время указывается примерное и одинаковое для всех ребер.
       Кроме этого, нам потребуется таблица для хранения найденного пути, которую назовем MRoutes:

Create table MRoutes
   (Start        AZInt32 references MStations on update cascade
                                              on delete cascade,
    Finish       AZInt32 references MStations on update cascade
                                              on delete cascade,
    RouteStep    AZInt32,
    RouteNbr     AZInt32,
Primary key(Start,Finish,RouteNbr));
Commit;

       Таблица содержит последовательный набор ребер, который описывает путь от одной станции к другой. Поле RouteStep содержит номер шага, на котором получено ребро, а поле RouteNbr — содержит номер пути, по которому алгоритм выходит из узла.
       Прежде чем приступать к построению хранимой процедуры, оценим последовательность необходимых действий.
       Предположим, что нам ничего неизвестно о структуре графа.
       Возьмем точку начала маршрута (Start) и найдем все возможные пути из нее. Для того чтобы не было бесконечных циклов, поставим условием чтобы каждое ребро проходилось только один раз. Таким образом весь граф превратится в обычное дерево, на одной из ветвей которого есть точка конца маршрута (Finish). Если после этого к этому дереву применить процедуру поиска родителя от точки Finish, то получим маршрут в обратном порядке — от точки Finish до точки Start.

SET TERM !! ;
CREATE PROCEDURE SearchRoutes (Start Integer, Fin Integer, Step Integer)
 as
DECLARE VARIABLE  SNext Integer;
DECLARE VARIABLE  TNbr Integer;
BEGIN
   TNbr = 0;
   For Select StRight from MEdges
        where StLeft=:Start
          and StRight not in (Select Finish from MRoutes where Start=:Start)
         into :SNext
    do begin
          Step = Step + 1;
          TNbr = TNbr + 1;
          Insert into MRoutes(Start,Finish,RouteStep,RouteNbr)
                       values(:Start,:SNext,:Step,:TNbr);
          If (Start=Fin) then Exit;
          Execute procedure SearchRoutes(:SNext,:Fin,:Step);
      end
END !!
SET TERM ; !!
Commit;

       Для определенности считая, что маршрут начинается с левой точки ребра будет искать правые точки всех ребер, которые выходят из чтоки Start. Так как у нас каждое направление имеет свое ребро, то их одной точки как минимум два ребра выходят и два входят. При этом исключим те правые точки, которые уже есть в маршруте. Так выглядит основной запрос, на котором строится процедура SearchRoutes. Перебирая найденные точки, во-первых пронумеруем их с помощью переменной TNbr, и, во-вторых на каждой увеличим номер шага Step.
       Найденное ребро записываем в таблицу MRoutes как очередной шаг маршрута. Если точка в переменной Start уже оказалась конечной точкой Fin, то выходим из процедуры, чтобы не делать лишнюю работу. В противном случае используем найденную точку в качестве нового значения Start рекурсивно вызываем процедуру SearchRoutes.
       Для окончательного поиска маршрута используем процедуру GetRoutes, которая представляет собой чуть видоизмененную процедуру GetParent, которая была описана ранее.

SET TERM !! ;
create procedure GetRoutes (Beg integer, Fin Integer, bLev Integer)
                   returns (rStart Integer, rFin Integer, rLev Integer) as
begin
   for select Start from MRoutes where Finish=:Fin into :rStart
     do begin
        rFin = Fin;
        rLev = bLev - 1;
        suspend;
        for select rStart,rFin,rLev from GetRoutes(:Beg,:rStart,:rLev)
              into :rStart,:rFin,:rLev
          do begin 
             suspend;
             If (rStart=Beg) then Exit;
             end
        end
end!!
SET TERM ; !!
Commit;

       Разница заключается в двух мелочах:
       — место родителя (Parent) займет Beg, Start,rStart, а место потомка (Child) займет Fin, rFin.
       — так как из вершины выходит несколько ребер разной направленности, то при достижении корня дерева (начала маршрута) возникает бесконечный цикл с соседней вершиной. Чтобы предотвратить это используется условие — если достигнута начальная вершина, то завершить процедуру.
       Для демонстрации описанных алгоритмов используется небольшая программа Example10, которая по сути вызывает две вышеописанные процедуры и выполняет некоторые вспомогательные операции, поэтому исходные тексты здесть не приводятся. Но их можно найти на диске в каталогах Example10xxx.
       Работа программы показана ниже:


Рис.5-1 Выбор маршрута между двумя станциями метро без оптимизации

       Выбрав в раскрывающемся списке "ОТ" станцию, от которой начинается движение, и в списке "ДО" станцию, до которой нужно доехать, нажимаем на кнопку "Пуск" с красной надписью и в таблице получаем результат вышеописанных действий.
       Сразу видно, что полученный маршрут далек от идеального, но к нужной станции он привел. Это не удивительно. Нам ничего не было известно о графе, мы не отмечали пройденные маршруты камешками, как мальчик-с-пальчик, мы просто преобразовали обобщенный направленный граф в дерево и поднялись по одной из ветвей.
       Если к описанию графа добавить информацию о том, что узлы и ребра графа принадлежат к линиям, что линии могут иметь пересечения, и, что есть линия, которая пересекается с большинством других линий (кольцевая), то можно перед поиском маршрута оставить в пространстве поиска только те ребра, которые заведомо приведут к положительному результату. Для этого немного исправим таблицу MEdges:

Create table MEdges
   (StLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    StRight     AZInt32 references MStations on update cascade
                                             on delete cascade,
    LnLeft      AZInt32 references MStations on update cascade
                                             on delete cascade,
    LnRight     AZInt32 references MStations on update cascade
                                             on delete cascade,
    RouteTime   Time,
    RouteNote   AZNotes,
    EdgeUse     AZInt32D0,
Primary key(StLeft,StRight));
Commit;

       В первую очередь добавленая информация о линиях, к которым принадлежит станция, — поля LnLeft, LnRight.
       Во-вторую очередь добавлено поле EdgeUse — использовать это ребро. По умолчанию значение этого поля 0, что запрещает его использовать в поиске.
       И, наконец, нужно немного исправить процедуру SearchRoutes:

SET TERM !! ;
CREATE PROCEDURE SearchRoutes (Start Integer, Fin Integer, Step Integer)
 as
DECLARE VARIABLE  SNext Integer;
DECLARE VARIABLE  TNbr Integer;
BEGIN
   TNbr = 0;
   For Select StRight from MEdges
        where StLeft=:Start and EdgeUse>0
          and StRight not in (Select Finish from MRoutes where Start=:Start)
         into :SNext
    do begin
          Step = Step + 1;
          TNbr = TNbr + 1;
          Insert into MRoutes(Start,Finish,RouteStep,RouteNbr)
                       values(:Start,:SNext,:Step,:TNbr);
          If (Start=Fin) then Exit;
          Execute procedure SearchRoutes(:SNext,:Fin,:Step);
      end
END !!
SET TERM ; !!
Commit;

       Добавив условие, что в поиске будут участвовать только ребра, у которых поле EdgeUse>0.
       Соответственно, нужно немного исправить скрипт, который заполняет таблицу MEdges:

Insert into MEdges(StLeft,LnLeft,StRight,LnRight,RouteTime)
Select Lft.Code,Lft.Line,Rgt.Code,Rgt.Line,'00:02:30'
  from MStations as Lft, MStations as Rgt
 where Lft.Name ='Улица Подбельского'
   and Rgt.Name='Черкизовская';

Insert into MEdges(StLeft,LnLeft,StRight,LnRight,RouteTime)
Select Lft.Code,Lft.Line,Rgt.Code,Rgt.Line,'00:02:30'
  from MStations as Lft, MStations as Rgt
 where Rgt.Name ='Улица Подбельского'
   and Lft.Name='Черкизовская';

       Теперь можно начинать поиск, предварительно подготовив для этого таблицу MEdges.
       1) Сначала установим значение EdgeUse всех ребер в 0.
       2) Включим в пространство поиска только те ребра, который относятся либо к начальной, либо к конечной станции:

Update MEdges Set EdgeUse=1
Where (LnLeft=:LnStart and LnRight=:LnStart)
    or (LnLeft=:LnFin and LnRight=:LnFin);

       где переменные LnStart и LnFin содержат коды линий, на которых находятся соответствующие станции.
       3) После чего нужно определить есть ли пересечения между линиями LnStart и LnFin для чего используется следующий запрос:

Select Count(*) as Cnt from MEdges
Where (LnLeft=:LnStart and LnRight=:LnFin)
    or (LnLeft=:LnStart and LnRight=:LnFin);

       И, если пересечения есть, т.е. переменная Cnt>0, то включаем в пространство поиска станции пересечения запросом:

Update MEdges set EdgeUse=2
Where (LnLeft=:LnStart and LnRight=:LnFin)
    or (LnLeft=:LnStart and LnRight=:LnFin);

       В противном случае добавляем в пространство поиска Кольцевую линию и все станции пересадок, которые к ней относятся:

Update MEdges set EdgeUse=2
Where (LnLeft=5000 or LnRight=5000);

       Для простоты примера код Кольцевой линии указан явно.
       После всех этих приготовлений опять выполняем две вышеописанные функции — SearchRoutes и GetRoutes — нажав кнопку "Пуск" с зеленой надписью. Результат показан на рисунке ниже:


Рис.5-2 Поиск маршрута между двумя станциями метро с оптимизацией

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

[an error occurred while processing this directive]

© 01.08.2009, Архангельский А.Г.

<<Пред. Оглавление
Об Авторе
Все персоны
Главная страница
След.>>



Поддержите культуру
ЯндексЯндекс. ДеньгиХочу такую же кнопку

Google
 
Web azdesign.ru az-libr.ru


Дата последнего изменения:
Wednesday, 23-Oct-2013 09:03:00 UTC