Наименование узлов

Номер пункта	Наименование
1	«Дубровка»
2	Развилка дорог
3	Тупик
........................	.........................

5. Построить векторную карту дорожной сети в области, заданной студенту на предыдущем занятии.

6. По векторной карте найти длину отрезков сети дорог своей области карты.

7. Выполнить распечатку векторной карты совместно с растровым слоем. Распечатку привести в отчете.

8. Заполнить табл. 3.

Таблица 3

Характеристика отрезков дорожной сети

Номера узлов		Длина, см	Длина, км	Характеристика дороги
начала	конца			Тип покрытия	Ширина полосы	Кол-во полос	Ширина всей дороги
1	2	2	10.5	Асфальт	8	2	16
.......	.......	.......	.......	..............	.............	............	............

6. Построить граф дорожной сети (в тетради) с узлами в виде кружков с номерами и соединяющих их отрезков дорог (ребер графа) в виде прямых линий (см. рис. 2.)

Рис. 2. Граф дорожной сети

Защита отчета на следующем занятии Лабораторная работа № 2

(4 часа)

Изучение методов определения кратчайших расстояний между пунктами дорожной сети

Цель занятия: изучение методов определения кратчайших расстояний между пунктами дорожной сети

Теоретические сведения

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

Методы, разработанные для поиска кратчайших расстояний, используются также в случаях поиска маршрутов с минимальным временем доставки, например, при доставке скоропортящихся продуктов или пассажиров.

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

Условное изображение транспортной сети без учета масштаба называется графом. Если одно или несколько ребер графа изображаются стрелками, то такой граф называется ориентированным. Ребро со стрелкой означает, что соответствующий участок дороги имеет одностороннее движение.

Для густоразветвленной сети определение кратчайших расстояний является весьма трудоемкой задачей. При этом можно решать следующие типы задач:

• найти кратчайший путь от вершины U до вершины V;

• отыскать кратчайшие пути из вершины U до всех остальных вершин сети;

• найти кратчайшие пути между всеми вершинами сети (из каждой вершины до всех остальных вершин сети).

Алгоритмы поиска минимальных путей можно разделить на две основные группы:

• древовидные алгоритмы, которые отыскивают дерево минимальных расстояний (минимальные расстояния от одной вершины – корня дерева до всех остальных вершин);

• матричные алгоритмы, которые вычисляют всю матрицу минимальных расстояний.

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

При расчете матрицы минимальных расстояний графа

,

где V – конечное множество всех вершин (всего их N); H – конечное множество ребер (их количество M),

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

(1)

где c(u, v) – длина ребра между вершинами u и v.

При расчете дерева минимальных расстояний применяют различные модификации метода потенциалов, метод "метлы", динамическое программирование. При расчете всей матрицы минимальных расстояний используются методы Флойда, Данцига, Табори. Наиболее простой и удобный для реализации на ЭВМ – метод Флойда.

Метод потенциалов

Пусть задана транспортная сеть, вершины которой обозначим буквами от А до Л. Заданы расстояния между соседними вершинами сети.

Задача решается следующим образом:

• Шаг 1. Вершина, от которой требуется определить кратчайшие расстояния, называется начальной. Ей присваивается потенциал , где i – номер этой вершины (в нашем случае А).

• Шаг 2. Просматриваются все звенья, начальные вершины i которых имеют потенциалы , а конечные вершины j потенциалов не имеют. Определяется значение потенциалов конечных вершин по следующей формуле:

, (2)

где – длина звена (i-j), т.е. расстояние между вершинами i и j.

Из всех полученных потенциалов выбирается наименьший (т.к. определяются кратчайшие расстояния), и его значение присваивается соответствующей конечной вершине. Звено (i-j) помечается стрелкой.

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

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

П

Рис.1. Граф транспортной сети

ример. Дана сеть (рис. 1). Определим кратчайшие расстояния от вершины А до остальных вершин.

Шаг 1. Принимаем .

Шаг 2.

1. определяем звенья, для которых вершина А является начальной. Это АБ, АД, АЕ, АЗ. Вычисляем потенциалы конечных вершин этих звеньев по формуле (1)

2. выбирается наименьшее значение этих потенциалов

3. звено АД отмечается стрелкой. Вершине Д присваивается значение потенциала, равное 5 (показано в рамке на рис. 1).

Вновь повторяется шаг 2, но за начальную вершину принимается вершина Д, потенциал которой уже найден:

1. определим звенья, выходящие из Д, т.е. ДГ, ДЕ, ДЖ. Вычислим потенциалы

2. из полученных сейчас и из оставшихся от предыдущего этапа расчета потенциалов выбирается наименьшее значение

Это значение проставляется в квадрате у вершины Б, звено (АБ) отмечается стрелкой.

Вновь повторяется шаг 2, за начальную вершину принимается Б.

1. Звенья БВ, БГ

2. Для вершины Г было определено раньше значение , т.е.

которое принимается за окончательное.

3. Вершине Г присваивается потенциал равный 7, звено ДГ помечается стрелкой. Далее вершина Г задается как начальная и определяются потенциалы вершин В и Ж

Из всех оставшихся потенциалов и новых выбирается наименьшее

принимаемое за окончательное, т.е. на рис. 1 заключается в рамку. Ребро АЗ помечается стрелкой.

Вновь повторяется шаг 2, за начальную вершину теперь принимается вершина З. Определяются потенциалы вершин Е, Ж, И, К:

Из всех оставшихся и новых потенциалов выбирается наименьшее

которое принимается за окончательное. Ребро ДЕ помечается стрелкой.

Далее процесс повторяется.

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

Матричный метод Флойда

В компактном виде алгоритм можно представить следующим образом:

Шаг 0:

Шаг 1:

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

Далее вычислительная процедура включает проверку наличия прямого пути между узлами i и k. Если такой путь имеется, то расстояние между вершинами i и j принимается наименьшим из уже имеющегося в матрице значения и суммы расстояний и .