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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

107
Выводы
1. Алгоритм (рис. 6, пункты
00
53
−
) исключает возможность
образования циклов при построении маршрута
0
,
lk
μ
, поэтому маршрут не
может содержать более чем n элементов.
2. Исключение возможности образования циклов не может ухудшить
решение: если критическая дуга находится только в цикле, то его
исключение улучшит решение; если критическая дуга вне цикла –
пропускная способность не изменится.
3. Наиболее известный и эффективный метод решения задачи о
пропускной способности сети –
метод Форда-Фалкерсона – основан на
использовании отрицательных плотностей потоков. В [14, с. 549]
приводится пример сети размера 4
=
n , при этом решение указанным
методом получается после выполнения 2 000 000 итераций. Метод
улучшения оценок (рис. 6; 8) позволяет получить оптимальное решение
указанного примера не более чем за две итерации (см. приложение).
Попытки найти подобный контрпример, характеризующий
неэффективную работу алгоритма улучшения оценок, оказались
безуспешными.
4. Метод и алгоритм решения не зависят от коэффициента полноты
матрицы
c ()10
≤
<
ϕ
. При построении маршрута по оценке
t
lk
,
π
(рис. 6,
0
3
) может быть использован алгоритм эстафетного метода (рис. 2), т.к.
наличие хотя бы одного маршрута от пункта
k
А
к пункту
l
А
гарантирует и
наличие кратчайшего для суммы весов
ji
c
,
дуг
0
,
),(
lk
ji
μ
∈ .
5. Определение пропускных способностей сетей проводилось с
допущением, что циркулирующие в них потоки близки к
детерминированным. Если потоки случайны и в узлах (вершинах)
производится их обработка (например, информационные потоки), то для
решения вопросов, связанных с пропускными способностями, возникает
необходимость привлекать теорию массового обслуживания [16, 15, 3] и
другие специальные методы.

Страницы