Поиск по базе сайта:
Модель Пусть пункты маршрута заданы … Вычисление icon

Модель Пусть пункты маршрута заданы … Вычисление




Скачати 21.57 Kb.
НазваМодель Пусть пункты маршрута заданы … Вычисление
ЗАДАЧА
Дата конвертації10.07.2013
Розмір21.57 Kb.
ТипЗадача

УДК 681.142.2

И.О. Автор


ЗАДАЧА


Рассматриваются модели транспортных сетей в виде графовых структур. Обсуждаются особенности применения известных алгоритмов для вычисления кратчайших путей и маршрутов, и их модификации для уменьшения трудоемкости. Исследуется потенциальная погрешность приближенных алгоритмов решения ЗК в случае несимметричных расстояний.


Задачи вычисления кратчайших путей и маршрутов являются типичными для ряда геоинформационных приложений [1].


^ Модель


Пусть пункты маршрута заданы …


Вычисление


Алгоритм Дейкстры реализует просмотр графа в ширину, начиная с некоторой заданной вершины ^ A. В процессе работы он приписывает метку для каждой из вершин графа, которая вычисляется как длина кратчайшего пути от вершины A до этой вершины.


Алгоритм 1.

1. Создается множество S = {A}, вершине A приписывается окончательная метка, равная нулю.

2. Создается множество W из вершин, смежных A, каждой из этих вершин приписывается метка, равная длине ребра от вершины до A.

3. Цикл, пока не все вершины вошли в множество S.

3.1. Из множества W выбор вершины u с наименьшей меткой p и перемещение ее в множество S.

3.2. Цикл по вершинам, смежным с u.

3.2.1. Если очередная вершина v не входит ни в S, ни в W, то перемещение ее в множество W, приписывание ей метки pq, где q – длина ребра между u и v.

3.2.2. Если очередная вершина v входит в W и ее метка rpq, то приписывание ей метки p + q.

Конец алгоритма


Если требуется одновременно вычислять кратчайшие пути, то на предварительном этапе необходимо сформировать общую таблицу ссылок размером n × n элементов. После этого в оперативном режиме можно будет быстро сформировать таблицу ссылок для дополнительных вершин (размером m × m элементов), как дополнение для m строк общей таблицы ссылок.


Вычисление кратчайших путей

для уточненной модели


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


ЛИТЕРАТУРА


1. Кошкарев А.В., Тикунов В.С. Геоинформатика. М.: Картгеоцентр-Геоиздат, 1993.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

Статья представлена кафедрой теоретических основ информатики факультета информатики Томского государственного университета, поступила в научную редакцию 30 апреля 2003 г.





Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації