В.П. Степанов, П.В. Степанов
6
Рис. 2.
Граф возможных трасс прокладки ОК
Нахождение всех близких к оптимальному трасс прокладки ОК
позволяет реализовать многовариантное проектирование и, учитывая
дополнительные неформализованные требования, выбрать реальный
вариант проекта трассы для внедрения. В качестве дополнительных
требований могут служить количество изгибов на оптимальной трас-
се, возможность выполнения работ на трассе, пересечение трубопро-
водов или дорог и т. п.
Алгоритм решения.
Алгоритм решения задачи состоит из двух
этапов. Определение минимального по длине трассы прокладки ОК
R
ij
сводится к решению известной задачи кратчайшего пути на графе.
Для этого применяют известный алгоритм [4], основанный на расста-
новке пометок на вершинах графа. Для определения множества всех
