Дискретная математика. Громов Ю.Ю - 82 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

82
Метод динамического программирования использует важную осо-
бенность, которая заключается в следующем. Если последовательность
вершин
n
i
v
,
1−n
i
v
, ...,
1
i
v
, v
k
определяет кратчайший путь от вершины
n
i
v
до вершины v
k
, то последовательность вершин
1−n
i
v
,
2−n
i
v
, ...,
1
i
v
, v
k
оп-
ределяет кратчайший путь от вершины
1−n
i
v
до вершины v
k
. Следова-
тельно, для определения кратчайших путей вершины графа можно рас-
сматривать по шагам, учитывая на некотором j-м шаге (j = 1, 2, ..., n)
только те вершины, которые удалены от вершины v
k
на j дуг.
На первом шаге поставим в соответствие каждой вершине
1
x
v
, уда-
лённой от вершины v
k
на одну дугу, единственную дугу D(
1
x
v
) = (
1
x
v
, v
k
).
Вершине
1
x
v
соответствует расстояние L(
1
x
v
) = l(
1
x
v
, v
k
) от вершины
1
x
v
до вершины v
k
, которое равно в данном случае длине дуги D(
1
x
v
).
Для нашего примера D(v
13
) = (v
13
, v
k
), L(v
13
) = l
(v
13
, v
k
) = 2; D(v
14
) =
= (v
14
, v
k
), L(v
14
) = l
(v
14
, v
k
) = 1. На рисунке 46 дуги D(v
13
) и D(v
14
) выделе-
ны утолщённой линией, а значения расстояний L(v
13
) и L(v
14
) выступают в
качестве весов соответствующих вершин.
В общем случае, найдя D(
j
x
v
) и L(
j
x
v
) для каждой вершины
j
x
v
,
удалённой от вершины v
k
на j дуг ( j = 1, 2, ..., n – 1), определим расстоя-
ние L(
1+j
x
v
) и соответствующую ему дугу D(
1+j
x
v
) для каждой вершины
1+j
x
v
, удалённой от вершины v
k
на ( j + 1) дугу. При этом L(
1+j
x
v
) опре-
деляется по формуле L(
1+j
x
v
) = min {l (
1+j
x
v
,
j
x
v
) + L(
j
x
v
)} для всех дуг
вида (
1+j
x
v
,
j
x
v
), у которых
1+j
x
v
является начальной вершиной, а в ка-
честве D(
1+j
x
v
) выбирается дуга, на которой достигается этот минимум.
Рис. 46
ν
6
ν
3
ν
1
ν
0
ν
10
ν
7
ν
4
ν
2
ν
13
ν
11
ν
8
ν
5
ν
k
ν
14
ν
12
ν
9
1
5
7
2
1
3
5
2
2
2
4
1
0
4
1
3
3
2
4
5
4
2
8
2
L
(v
13
) = 2
L
(v
14
) = 1

Страницы