Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 20 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

22
Пункт
0
6 позволяет найти концевые дуги кратчайших маршрутов
(таких маршрутов может быть более одного). Чтобы выявить кратчайший
маршрут необходимо момент прибытия каждого из множества
t
I
лидеров
привести к
единой (относительно момента старта первой группы
0=
c
k
T ) системе отсчёта времени, при этом наименьшее время и
обозначит собой концевую дугу очередного кратчайшего маршрута (
0
6):
}.1{}{},4{}{)},4;1{(330)(min
114.
1
}1{
==⇒=+=+
∈
ijcT
ii
i
Поскольку на первом шаге старт произведен только из УИ
1
A , то
лидер этой группы и определит первый кратчайший маршрут, самый
короткий из всего множества, записанный в строке
1=
t
(табл. 9).
Согласно
0
7 сам кратчайший маршрут будет получен путём
достраивания его недостающей части слева от концевой дуги
(1;4):
.4;1)4;1(1,...,1);(,...,
111
0
4,1
=∪=∪= jiik
μ
Длина построенного кратчайшего маршрута
1
0
kj
L при единичной
скорости движения гонцов численно равна моменту прибытия лидера на
концевую вершину
4
A кратчайшего маршрута
0
4,1
μ
.
Конечные результаты фиксируются в памяти ЭВМ, а при «ручных»
расчётах записываются в табл. 3.
Если номер 3=
l
искомой вершины содержится среди номеров
концевых вершин
}{
t
j найденных кратчайших маршрутов ( +
0
8), то
выводятся и записываются полученные результаты (
0
11 ), процесс
заканчивается. В противном случае (
−
0
8) производится пересчет текущих
величин (
0
9) и делается переход к очередной итерации (
0
10 ).
Согласно пункту
0
9 вначале уточняются множество номеров вершин
j
A , к которым ещё не построены кратчайшие маршруты, и множество
номеров вершин, от которых проведен старт групп:
}.4;1{}4{}1{ },6,5,3,2{}4{\}6,5,4,3,2{
22
=∪=== IG

Страницы