Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 59 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v
2
=. . . . .
3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v
3
=. . . . .
4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v
4
=. . . . .
Ответ: наиболее выгодный . . . . . . путь.
2. Дан граф со взвешенными вершинами, в
котором в качестве характеристики
вершины указывается ее пропускная
способность. Определить какой из
перечисленных маршрутов имеет лучшую
среднюю пропускную способность.
1.
A → B → C → D
2.
A → F → G → D
3.
A → B → G → D
5.
A → F → G → E → D
Решение: Средняя пропускная способность маршрута определяется как суммарное
значение пропускной способности всех вершин, входящих в маршрут, деленное на
количество вершин этого пути, то есть p
n
= Σa
i
/ l
i.
1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..
p
1
= . . . . .
2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p
2
=. . . . .
3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p
3
=. . . . .
4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p
4
=. . . . .
Ответ: наиболее выгодный . . . . . . маршрут.
. .
5.4. Алгоритм Дейкстры поиска кратчайших путей в графе
Наиболее эффективный алгоритм решения задачи о кратчайшем пути
первоначально дал Дейкстра [ 5]. В общем случае этот метод основан на
приписывании вершинам временных пометок, причем пометка вершины дает
верхнюю границу длины пути от некоторой вершины
s
к рассматриваемой
вершине. Эти пометки постепенно уменьшаются с помощью некоторой
итерационной процедуры, и на каждом шаге итерации точно одна из временных
пометок становится постоянной. Последнее указывает на то, что пометка уже не
является верхней границей, а дает точную длину кратчайшего пути от
t к
рассматриваемой вершине. Рассмотрим подробнее этот алгоритм.
Дан граф G=(X, A, C) со взвешенными дугами. Обозначим
L (x
i
) пометку
вершины x
i
.
Рассмотрим алгоритм нахождения кратчайшего пути от вершины
s к
вершине
t графа и более общий случай: от вершины s ко всем вершинам графа.
Присвоение начальных значений
ШАГ 1. Положить
L(s)=0 и считать эту пометку постоянной. Для всех
вершин x
i
≠ S положить L(x
i
)= ∞ и считать эти пометки временными. За текущую
(0)
B C
D
E
G
F
A
(4) (5)
(0)
(6) (7)
(10) 
  2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v2 =. . . . .
  3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v3 =. . . . .
  4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. v4 =. . . . .
Ответ: наиболее выгодный . . . . . . путь.

2. Дан граф со взвешенными вершинами, в
котором в качестве характеристики                      B              C
вершины указывается ее пропускная                        (4)      (5)
способность. Определить какой из                 A
перечисленных маршрутов имеет лучшую                         (10)                D
среднюю пропускную способность.               (0)
                                                                             (0)
    1. A → B → C → D                                           G
    2. A → F → G → D                                 F
                                                       (6)          (7) E
    3. A → B → G → D
    5. A → F → G → E → D
Решение:      Средняя пропускная способность маршрута определяется как суммарное
значение пропускной способности всех вершин, входящих в маршрут, деленное на
количество вершин этого пути, то есть pn = Σai / li.

  1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p1= . . . . .
  2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p2 =. . . . .
  3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p3 =. . . . .
  4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. p4 =. . . . .
Ответ: наиболее выгодный . . . . . . маршрут.
  .                                                                                                         .
                 5.4. Алгоритм Дейкстры поиска кратчайших путей в графе
          Наиболее эффективный алгоритм решения задачи о кратчайшем пути
первоначально дал Дейкстра [ 5]. В общем случае этот метод основан на
приписывании вершинам временных пометок, причем пометка вершины дает
верхнюю границу длины пути от некоторой вершины s к рассматриваемой
вершине.           Эти        пометки          постепенно              уменьшаются                с   помощью   некоторой
итерационной процедуры, и на каждом шаге итерации точно одна из временных
пометок становится постоянной. Последнее указывает на то, что пометка уже не
является верхней границей, а дает точную длину кратчайшего пути от t                                                    к
рассматриваемой вершине. Рассмотрим подробнее этот алгоритм.
          Дан граф G=(X, A, C) со взвешенными дугами. Обозначим L (xi) пометку
вершины xi.
          Рассмотрим алгоритм нахождения кратчайшего пути от вершины s к
вершине t графа и более общий случай: от вершины s ко всем вершинам графа.
          Присвоение начальных значений
          ШАГ 1. Положить L(s)=0 и считать эту пометку постоянной. Для всех
вершин xi ≠ S положить L(xi)= ∞ и считать эти пометки временными. За текущую

Страницы