Материал: 1997
качестве ТУ задаются также «точки» на транспортной сети, которые позволяют адекватно описывать геометрию ТС. Как правило, ОП в прямом и обратном направлениях, расположенных на разных сторонах улицы, принимаются за один узел, а в отдельных случаях допускается к одному узлу относить 3 и даже 4 близлежащие ОП.
формированный фрагмент графа ТС представить в таблице Excel со Сследующими столбцами:
ИУ – номер исходного узла; НУ – назван е узла;
1 |
У – первый смежный узел; |
и |
|
2 |
У – второй смежный узел; |
3 |
У, …– трет й смежный узел, остальные смежные узлы |
1 ДД – дл на ре ра до первого смежного узла; 2 ДД – дл на ре ра до второго смежного узла;
плекс АРМбА«МАРС», в частности его закладку «Ввод данных расчеты» + «Транспортная сеть» (рис.Д5), в которой можно увидеть граф ТС, а также номер и название транспортного узла. Кроме того для ориентации
3 ДД, … – дл на ре ра до третьего смежного узла, и остальных
смежных узлов.
Задан е 2. Поставить в соответствие основным улицам города граф транспортной сети (ТС) (нанести на графе основные улицы в раз-
ных районах города). Варианты заданий приведены в приложении 1.
Указания к выполнению задания 2.
Для выполнения данного задания использовать программный ком-
на территории г.Омска используется электронная карта-справочник Омска – 2 ГИС.
Задание 3. Описать через узлы графа ТС путь между двумя заданными вершинами графа, привести названияИтранспортных узлов, а также дать перечень улиц, по которым проходит выбранный вами путь. Варианты для выполнения задания приведены в таблице 2.
Для выполнения задания использовать программный комплекс АРМ
«МАРС», закладку «Ввод данных и расчеты»+»Транспортная сеть».
11
С |
|
|
|
|||
и |
|
|
|
|||
|
|
бА |
|
|
||
|
|
|
Р с. 5. Закладку «Ввод данных расчеты» + «Транспортная сеть» |
|||
|
|
|
Исходные данные для задания 2 |
Таблица 2 |
||
|
Номер |
|
|
Транспортная связь |
|
|
|
варианта |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
Исилькульский тракт – Сыропятский тракт |
|
|
|
|
2 |
|
|
Д |
|
|
|
|
Русско-полянский тракт – Пушкинский тракт |
|
|
||
|
3 |
|
Тюкалинский тракт – МЧС-9 |
|
|
|
|
4 |
|
пл. Ленина – Красноярский тракт |
|
|
|
|
5 |
|
СКК им. Блинова – старая Московка |
|
|
|
|
6 |
|
М-н Голубой огонек – Осташково |
|
|
|
|
14 |
|
Ленинградский мост – пос. Рыбачий;СибАДИ– Мега. |
|
||
|
7 |
|
Дом Туриста – Романенко |
|
|
|
|
8 |
|
Главпочтамт – Гашека |
|
|
|
|
9 |
|
ж/д вокзал – пос. Черемушки |
|
|
|
|
10 |
|
з-д Баранова – пос. Светлый |
|
|
|
|
11 |
|
пл. Ленина – пос. Загородный |
|
|
|
|
12 |
|
М-н Голубой огонек – Пушкино |
|
|
|
|
13 |
|
Дом Туриста – пос. Степной |
|
|
|
|
|
|
|
|
|
|
15 |
|
СибАДИ – з-д СК, Ленинградский мост – Большая островка |
|
|
||
Указания к выполнению задания 3.
Если, например, необходимо описать путь по ТС от транспортного узла 420 – Трикотажная фабрика до транспортного узла 738 – ПКиО 30
12
лет ВЛКСМ через узлы графа ТС, привести названия транспортных уз-
лов (рис. 6). |
|
|
|
|
|
То используя программный |
комплекс АРМ «МАРС», закладку |
||
«Ввод данных и расчеты»+»Транспортная сеть»+»Граф ТС» описыва- |
||||
ется номерами узлов графа путь следования из транспортного узла 420 в |
||||
738 |
транспортный узел по любой траектории по желанию студента. |
|||
С |
|
|
|
|
и |
ул. Депутатская |
|
||
|
|
|
||
|
бА |
|
||
|
ул. Подгорная |
|
|
|
|
Жукова . М |
|
|
Хмельницкого |
|
.ул |
|
ул. Масленникова |
|
|
|
|
|
|
|
|
Д |
||
|
|
|
|
. Б |
|
|
|
|
. ул |
|
|
|
И |
|
|
Рис. 6. Фрагмент графа транспортной сети |
|||
420 |
– Трикотажная фабрика |
|
|
|
419 |
– Школа (Депутатская) |
|
|
|
418без названия |
|
|
|
|
417 |
– Депутатская |
|
|
|
416 |
– без названия |
|
|
|
415 |
– без названия |
|
|
|
414 |
– ДОСААФ (Подгорная) |
|
|
|
13
413 – без названия
……
742 – без названия
741 – 20 лет РККА
739 – без названия |
|
|
738 – ПКиО 30 лет ВЛКСМ. |
||
С |
|
|
Контрольные вопросы: |
||
1. |
Дать определен |
е графа транспортной сети. |
2. |
Дать определен |
е дерева графа. |
сети |
||
3. |
Дать определен |
е транспортного узла в рассматриваемой модели |
транспортной |
города. |
|
4. |
Дать определен |
е смежного транспортного узла. |
|
|
Ла ораторная работа №4 |
|
Построение дерева кратчайших путей |
|
|
Цель ла ораторной ра оты – определение кратчайшего транс- |
|
портных связей между транспортными узлами модели транспортной се- |
||
ти городабс использованием дерева кратчайших путей. |
||
|
Алгоритм построения дерева кратчайших путей |
|
|
|
Д |
|
|
(алгоритм ейсктры). |
|
Суть методаАсостоит в последовательном наращивании деревьев |
|
кратчайших путей, начиная с дерева состоящего из одной вершины. За |
||
шаг работы алгоритма, количество дуг дерева будут увеличиваться на |
||
единицу, все дерево строится за n-1 шагов (n – это число вершин графа). |
||
|
|
И |
|
Дерево, которое получается на каждом шаге, называется текущим. |
|
На каждом шаге рассматриваются вершины, соседние с текущим деревом. Вершина к называется соседней с текущим деревом, если имеется дуга, связывающая эту вершину с деревом. При просмотре соседних вершин они сначала получают временную пометку (пометка – пара цифр, первая из которых является расстоянием от исходной вершины до рассматриваемой, вторая – номер соседней вершины с рассматриваемой на пути от исходной вершины до нее). Постоянную пометку получает та вершина, которая имеет минимальный потенциал среди все вершин, соседних с текущем деревом.
Просмотр вершины i на итерации q это вычисление потенциалов соседних с ней вершин j следующим образом:
14
|
|
|
|
|
|
Liq min(Lj(q 1);Li(q 1) |
аij ), |
|
|
(1) |
|
||||||||||
|
где Lj(q 1) – текущее значение потенциала, определенное на предыду- |
||||||||||||||||||||
|
|
|
|
щем шаге (если вершина рассматривается впервые, то зна- |
|||||||||||||||||
|
|
|
|
чение потенциала принимается равным + ); |
|
|
|
||||||||||||||
С |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
Li(q 1) |
– значение потенциала предыдущей (i-ой) вершины, |
|||||||||||||||||||
|
|
|
|
включенной в дерево кратчайших путей; |
|
|
|
||||||||||||||
|
аij – расстоян е по транспортной сети от рассматриваемой |
||||||||||||||||||||
|
|
верш ны до соседней. |
|
|
|
|
|
|
|
|
Таблица 3 |
||||||||||
построения |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
Постоянную пометку получает вершина, которая имеет мини- |
||||||||||||||||||||
|
мальный потенц ал среди соседних с текущим деревом: |
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
Liq |
minLiq |
|
|
|
|
|
|
|
(2) |
|
||||
|
По |
бА |
|
|
путей |
заполняется |
|||||||||||||||
|
|
мере |
|
|
|
|
дерева кратчайших |
|
|||||||||||||
|
табл ца 3. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Компактная запись дерева кратчайших путей |
|
|
|
|||||||||||||
|
|
|
|
|
|
|
из вершины s во все другие |
|
|
|
|
|
|||||||||
|
Номер |
|
|
s |
|
1 |
|
|
2 |
|
|
|
3 |
|
|
… |
|
n |
|
||
|
вершины |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Расстояние |
|
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Номер со- |
|
|
|
|
|
|
|
Д |
|
|
||||||||||
|
седней |
|
|
- |
|
|
|
|
|
|
|
||||||||||
|
вершины |
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Таблица позволяет получить любой путь из вершины s до любой |
||||||||||||||||||||
|
другой вершины графа. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
Пример построения дерева кратчайших путей |
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
4 |
|
|
|
|
|
|
И |
|||||||||
|
|
|
|
|
1 |
|
|
|
2 |
|
3 |
|
|
4 |
3 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
7 |
|
5 |
2 |
|
|
4 |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|||||
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
1 |
3 |
|
|
|
|||
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
6 |
6 |
|
|
|
|
|
|
|||
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|||
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
9 |
|
|
7 |
|
|
10 |
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Рис. 7. Граф транспортной сети, с указанием длин ребер графа. |
|||||||||||||||||||
15