IV Международная студенческая научная конференция Студенческий научный форум - 2012

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

Среди всех алгоритмов, отвечающих за работу спутниковых навигаторов, ярко выделяются два базовых. Первый позволяет определить положение приемника по сигналам со спутника GPS, а второй - определить кратчайший путь из точки А в точку Б. Существуют и другие, определяющие визуальное отображение маршрута, но они не столь важны.

Используя данные только с одного спутника, устройство GPS определяет свое положение на поверхности виртуальной сферы с центром на этом спутнике. В таких данных полезной информации крайне мало.

Анализ данных с двух спутников дает область пересечения двух сфер с центрами на каждом спутнике. Пытаясь представить пересечение двух сфер геометрически, можно выделить три возможных случая: сферы не пересекаются вообще, сферы пересекаются в одной точке (возможно только при касании сфер), либо сферы пересекаются в виде окружности. Чтобы было легче представить это, сопоставьте мысленно сферы с мыльными пузырями. Но информации для позиционирования и в этом случае недостаточно.

Так, для определения своей позиции GPS устройство использует, по меньшей мере, четыре различных спутника. Спутники GPS расположены над Землей, таким образом, что из любой точки Земли одновременно видно их около 10 (если, конечно, не мешает рельеф или другие непрозрачные для радиоволн препятствия). Нетрудно догадаться, что такое расположение является достаточным для определения позиции. Положение приемника, вычисляемое по данным только GPS спутников, рассчитывается с точностью до 15 м.

Пусть у нас есть изображение со спутника (Рис. 2. Московский государственный областной социально-гуманитарный институт. г. Коломна), для быстроты работы устройству проще воспринимать векторную карту, которая представляет собой набор объектов (в основном дорог), которые отображаются на дисплее навигатора. Благодаря этому можно учитывать ориентацию и положение устройства в текущий момент времени. По изображению со спутника строим векторную карту.

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

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

Для поиска минимального пути используем модификацию алгоритма Дейкстры, суть которого сводится к следующему: в начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния объявляются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив меток заполняется нулями. Затем запускается основной цикл. На каждом шаге цикла мы ищем вершину с минимальным расстоянием и меткой равной нулю. Затем мы устанавливаем в ней метку в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается, когда метки всех вершин становятся равны 1, либо когда у всех вершин c метками 0 d[i]→∞. Последний случай возможен тогда и только тогда, когда граф G не связан.

Без помощи вычислительной техники решать задачу не имеет смысла, поэтому приведем основную часть реализации алгоритма программой, в которой выделим 3 части:

1) считывание матрицы весов из файла:

procedure ReadFileGraph(var  a:graph);

var       i,j:integer; filename:string; f:text;

begin

filename:=´ss.txt´; Assign (f,filename); reset(f); Read(f,N);

For i:=1 to n do for j:=1 to n do  read(f,a[i,j]); close(f);

end;

2) алгоритм Дейкстры нахождения кратчайшего пути:

procedure Deikstr(n:integer; W:graph; u1,u2:integer;

var length:integer; var Weight:real; var Path: array of integer);

var       i,k,j:integer;     GM:real;         d,m:array[1..nn] of real;

 p:array[1..nn] of integer;        t:integer;        dd,min:real;

begin

  GM:=10000;

  length:=0;

  if u1<>u2 then

  begin

    i:=1;

    repeat

      d[i]:=GM; p[i]:=0; m[i]:=0; i:=i+1

    until not(i<=n);

    d[u1]:=0; t:=u1;

    while length=0 do

    begin

      i:=1;

      repeat

        if w[t,i]<GM then

        begin

          dd:=d[t]+w[t,i];

          if d[i]>dd then begin d[i]:=dd; p[i]:=t  end;

        end;

        i:=i+1

      until not(i<=n);

      Min:=GM; i:=1; k:=0;

      repeat

        if m[i]=0 then

        begin

          if d[i]<min then begin min:=d[i]; k:=i  end;

        end;

        i:=i+1

      until not(i<=n);

      if k<>0  then  begin

        m[k]:=1; t:=k;

        if t=u2 then begin length:=1; end;

      end else begin  length:=-1 end;

    end;

    if length=1 then

    begin

      Path[1]:=u2;  length:=2; j:=u2;

      repeat

        Path[length]:=P[j]; j:=P[j]; length:=length+1

      until not(j<>u1);

      i:=1;  k:=trunc(length/2);

      repeat

        t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1

      until not(i<=k);

      length:=length-1

    end;

    Weight:=d[u2]

  end;

end;

3) ввод параметров поиска и получение результата:

Begin

  clrscr;

readfilegraph(G);

 for i:=1 to n do 

 begin

  for l:=1 to n do if G[i,l]=10000 then

                write(´  -  ´) else write({´  ´,}G[i,l]:5{,´  ´});

  writeln;

 end;

 write(´u1 = ´); readln(u1);

 write(´u2 = ´); readln(u2);

 Deikstr(n,G,u1,u2, L,w,path);

 writeln(´w=´,w:1:2);    

 write(path[1]);

 for i:=2 to l do write(´ - ´,path[i]);

 readkey;

End.

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

Код для цитирования: Скопировать