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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

28
средних скоростей
ij
v передвижения по каждому участку
ij
c , то,
вычислив матрицу времен
ij
ττ
=
(
ijijij
vc /
=
τ
) и применив
рассмотренный метод (рис. 2) для каждой пары ),(
j
k
, получим маршрут
0
,
lk
μ
, кратчайший по времени.
7. Эстафетный метод не потребует существенных изменений, если
вместо кратчайшего строить наиболее длинный маршрут (
критический
путь
), что необходимо при сетевых методах планирования. В алгоритме
(рис. 2) в пунктах
0
4,
0
6 потребуется min заменить на max, при этом
согласно
0
9
появление циклов исключается.
8. При машинной реализации алгоритма эстафетного метода (рис. 2)
время задержки (расстояние отставания)
c
i
T
(табл. 2) целесообразно
добавлять ко всем элементам
ij
c i -й строки, сохранившимся к
t
-му шагу
процесса (
∈i
t
i
G ).
Примечание. Статистическая обработка всего семейства
кратчайших маршрутов (табл. 9) позволяет решать ряд практических
вопросов, связанных с проектированием и функционированием сетей
передачи данных (СПД): оптимизация топологической структуры
СПД, задачи маршрутизации информационных потоков,
обоснование пропускных способностей линий связи и узлов
коммутации [3, 8, 6] и др.
Перейдем к рассмотрению другого класса задач построения
кратчайшего пути на графе
при некотором дополнительном условии:
кратчайший маршрут
lk ,
μ
должен пройти через все вершины графа хотя
бы один раз
(или только один раз – гамильтонов путь или гамильтонов
цикл).
3. КЛАССИЧЕСКАЯ ЗАДАЧА КОММИВОЯЖЕРА
И ЕЕ РЕШЕНИЕ МЕТОДОМ РАСШИРЕНИЯ ЦИКЛА
3.1. Постановка классической задачи коммивояжёра ( 1=
ϕ
)
Классическая задача коммивояжера хорошо известна по многим
источникам [1, 2, 12, 5] и проста по своей содержательной постановке.
В классической задаче коммивояжера полагается, что коммивояжер,
выходя из пункта
k
A , по кратчайшему пути должен посетить каждый
пункт
ровно один раз и возвратиться в исходный пункт. Подобная
жесткость требования может представлять математический интерес,

Страницы