Лекция 14 Задача Штейнера

Кратчайшие расстояния. Потоки в сетях

Задача Штейнера

Следующая задача известна в теории графов под названием задачи Штейнера: на плоскости заданы n точек; нужно соединить их отрезками прямых таким образом, чтобы суммарная длина отрезков была наименьшей.

В процессе поиска решения разрешено вводить новые точки; длина отрезка, соединяющего две заданные точки, не обязательно понимается геометрически – это может быть какая – то цена прохождения из точки в точку. Задача Штейнера называется также транспортной задачей и интерпретируется как задача прокладки дорог (трубопроводов, линий и т.п.) наименьшей длины.

Графовая интерпретация задачи Штейнера: дан граф G₀ = (V₀,Æ) без рёбер. Требуется найти древесный граф G(V, E), V₀ÍV, такой, что сумма весов его рёбер была наименьшей.

Пример точного решения задачи

Эффективного алгоритма решения задачи Штейнера не существует. Однако известны эффективные алгоритмы, точно решающие некоторые приближения задачи Штейнера.