Правильная ссылка на эту страницу
http://az-design.ru/Support/DataBase/DBTree2/6200.shtml

Транспортные задачи

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

       Практически все транспортные задачи сводятся к поиску маршрута, который отвечает некоторым условиям. Как правило в учебниках просто говорится "поиск минимальной длины пути на ненаправленном графе", без описания самого графа. Потом выясняется, что для получения самого минимального маршрута требуется матрица N*N точек, где N - количество узлов в графе. Таким образом наиболее популярные алгоритмы для нахождения минимального пути — Дейкстры, Форда-Белмана, Левита, Флойда-Уоршолла — используют графы следующего типа:


Рис.5-3 Типовой граф для рассмотрения транспортных задач

       На самом деле в большинстве реальных задач граф направленный и выглядит так:


Рис.5-4 Типовой направленный граф для рассмотрения транспортных задач

       И это уже вызывает ряд проблем. Во-первых, вес ребра в одном направлении и вес ребра в обратном направлении могут отличаться. Во-вторых, возникают многочисленные циклы и многие оптимизации вышеназванных алгоритмов перестают работать.
       Реальные же задачи, например, поиск маршрута для такси, нужно рассматривать на графах следующего вида:


Рис.5-5 Реальная модель транспортной системы

       Во-первых, узел разделен на две части, и далеко не всегда между этими частями есть переход. Вспомните, для того чтобы к дому на противоположной стороне улицы требуется доехать до перекрестка, развернуться и проехать назад.
       Во-вторых, несколько вершин могут находится на одном пути, и следовательно, находясь в текущей вершине, невозможно принять решение о следующей вершине, так как сумма ребер еще не известна. Что также не нравится многим аглоритмам.
       И, наконец, все алгоритмы, разработанные математиками, основаны на просмотре матриц, в которых перечислены вершины. В процедурных языках легче построить циклы перебирающие массивы, чем перебирать пары чисел, которые определяют ребра.
       Предлагаемый алгоритм в принципе близок к алгоритму Форда-Беллмана, но реализован на SQL и хранимых процедурах. В качестве примера используется опять схема метрополитена г.Москвы, но с ограничениями реальной модели транспортной системы. Каждая линия имеет два пути — в прямом и обратном направлении. В качестве примера, переход с прямого на обратное направление (и наоборот) возможен только на станциях пересадок и конечных станциях. Таким образом, станции пересадок играют роль перекрестков на улицах. Вся схема хранится в 2 таблицах — MTops и MLines, а для заполнения этих таблиц используется скрипт Metro2.txt.
       Таблица MTops используется для хранения вершин. Столбцы TInp, TOut, Note — справочные и в работе алгоритма не используются.

Create table MTops
   (Code     AZInt32 not null primary key,
    Name     AZTitle,   -- наименование станции
    TInp     AZInt32D0, -- количество входящих путей
    TOut     AZInt32D0, -- количество исходящих путей
    Note     AZNotes);
Commit;
Insert into MTops(Code) values (0);
Commit;

       Таблица MLines используется для хранения ребер и их весов. Триггеры, которые подсчитывают сколько ребер входит и выходит из вершины, также в работе алгоритма не используются.

Create table MLines
   (LBeg      AZInt32 references MTops on update cascade on delete cascade,
    LEnd      AZInt32 references MTops on update cascade on delete cascade,
    LSize     AZInt32D0, -- вес ребра, например, длина пути в сек.
Primary key(LBeg,LEnd));
Commit;

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

Create table MRoad
   (Start     AZInt32 references MTops on update cascade on delete cascade,
    Fin       AZInt32 references MTops on update cascade on delete cascade,
    Step      AZInt32,
    Total     AZInt32D0);
Commit;

       Для поиска маршрута используется процедура SearchMin2Roads.

SET TERM !! ;
CREATE PROCEDURE SearchMin2Roads (Start Integer, Fin Integer, Step Integer, Total Integer)
 as
DECLARE VARIABLE  TCnt Integer;
DECLARE VARIABLE  MLin Integer;
DECLARE VARIABLE  TStr Integer;
DECLARE VARIABLE  TFin Integer;
DECLARE VARIABLE  Totl Integer;
DECLARE VARIABLE  CTot Integer;
BEGIN
Insert into MRoad(Start,Fin,Total,Step) values(:Start,:Start,0,0);
Select Count(*) from MLines into :MLin;
Totl = 2147483647;
TCnt = 1;
While ((TCnt>0) and (Step<=MLin)) do begin
   TCnt = 0;
   For Select distinct ml.LBeg,ml.LEnd,(ml.lSize+mr.Total) as CTotal from MLines as ml
       join MRoad as mr on ml.LBeg=mr.Fin
       where mr.Step=:Step
         and (ml.lSize+mr.Total) <= :Totl -- новый путь меньше найденного
       into :TStr,:TFin,:CTot
       do begin
          TCnt = TCnt + 1;
          IF (CTot<Totl) then begin
             If ((TFin=Fin) and (Totl>CTot)) then Totl = CTot; -- новая найденная длина
             Insert into MRoad(Start,Fin,Total,Step)
             values(:TStr,:TFin,:CTot,:Step+1);
          end
       end
   Step = Step + 1;
end
END !!
SET TERM ; !!
Commit;

       Как работает эта процедура?
       Во-первых, устанавливаются начальные переменные:
       — записывается первый путь, у которого в качестве начальной и конечной точки используется точка старта и длина равна 0;
       — вычисляется количество ребер и записывается в переменную :MLin;
       — устанавливается минимальная длина найденного пути в "машинную бесконечность".
       Далее, в цикле выполняются следующие действия:
       — находятся все пути из конечных точек, которые были получены на предыдущем шаге, и вычисляется длина пути до новых конечных точек. При этом выбираются только те пути, для которых длина нового пути меньше найденного кратчайшего пути.
       — если найденный путь содержит точку финиша и длина пути до нее меньше найденного (:Totl), то переменной :Totl присваивается новая длина пути.
       — все найденные пути записываются в таблицу MRoad.
       Цикл останавливается в следующих случаях:
       — запрос вернул 0 строк. Это означает, что минимальный путь найден.
       — количество циклов (шагов) стало больше чем число ребер в графе. Это означает, что точки Start и Finish не соединены и решения нет.
       Результатом работы этой процедуры является массив всех путей из точки Start, среди которых есть и точка Finish.
       Для вывода кратчайшего маршрута используется такой же прием, как в предыдущих случаях, — из точки Finish находится маршрут с минимальной длиной до точки Start. Для этого используется процедура GetRoads2.

SET TERM !! ;
create procedure GetRoads2 (Beg integer, Fin Integer, bLev Integer)
                   returns (rStart Integer, rFin Integer, rLev Integer, rTotal Integer)
as
DECLARE VARIABLE  TFin Integer;
DECLARE VARIABLE  Totl Integer;
DECLARE VARIABLE  BCnt Integer;
DECLARE VARIABLE  ECnt Integer;
begin
   If (bLev=0) then begin
      Select Count(Start) from MRoad where Start=:Beg into :BCnt;
      Select Count(Fin) from MRoad where Fin=:Fin into :ECnt;
   end
   If ((bLev<>0) or ((BCnt>0) and (ECnt>0))) then begin
      Select Fin,Min(Total) as MTot from MRoad
       where Fin=:Fin group by Fin into :TFin,:Totl;
      For Select Start,Fin,Total from MRoad
           where Fin=:Fin and Total=:Totl into :rStart,:TFin,:rTotal
       do begin
          rFin = Fin;
          rLev = bLev - 1;
          suspend;
          for select rStart,rFin,rLev,rTotal from GetRoads2(:Beg,:rStart,:rLev)
                into :rStart,:rFin,:rLev,:rTotal
            do begin 
               suspend;
               If (rStart=Beg) then Exit;
               end
          end
   end
end!!
SET TERM ; !!
Commit;

       Несмотря на то, что процедура рекрсивная, в первом цикле выполняется проверка на допустимость исходных данных, т.е. точка Start должна находится в в списке начальных точек, а точка Finish должна находится в списке конечных. Точка Finish может быть в нескольких экземплярах, но это не мешает нахождению минимального пути. Это вводит некоторое ограничение на параметр bLev, который в первом вызове должен быть равен 0, но зато защищает от ошибок пользователя в случае если процедура вызвана не из приложения.
       Если все условия выполняются, то сначала находится текущая точка Fin, у которой минимальная длина общего пути. Для этой точки находится полный путь, который выводится в результат запроса, и формируются новые параметры для рекурсивного вызова этой же процедуры.
       Если достигнута точка Start {If (rStart=Beg) then Exit}, то выполняется выход из процедуры.
       Для демонстрации работы этих процедур написан пример, который находится в каталоге Example11. Нажатие кнопки "Пуск" последовательно вызывает обе вышеописанных процедуры:
       Первая находит все пути до конечной точки

+>>>qrExeProc.SQL:
EXECUTE PROCEDURE SearchMin2Roads (2038, 3035, 0, 0)
->>>

       Вторая находит в найденных путях кратчайший маршрут:

+>>>qrMRoad.SQL:
Select mt.Name,gr.* from GetRoads2(2038, 3035, 0) as gr
   join MTops as mt on mt.Code=gr.rFin
   order by gr.rLev asc


Рис.5-6 Работа программы Example11

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

<<Пред. Оглавление
Начало раздела
След.>>




Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:44 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/DataBase/DBTree2/6200.shtml