Построение минимального дерева Штейнера в евклидовой плоскости

Условие:

Даны три точки в евклидовой плоскости с координатами A(x1,y1), B(x2,y2) и C(x3​,y3​). Необходимо построить минимальное дерево, соединяющее эти точки с минимальной общей длиной рёбер.

Разрешается добавление одной дополнительной точки S(xs,ys)(точки Штейнера), которая может уменьшить суммарную длину соединяющих отрезков.

Требования:

1. Найти координаты точки S, которая минимизирует сумму расстояний от неё до заданных точек.
2. Визуализировать полученное дерево с помощью библиотеки SFML.
3. Вывести терминальные точки (красным), точку Штейнера (синим) и соединяющие рёбра (жёлтым).

Формат входных данных:

На вход подаются три пары вещественных чисел (x1,y1), (x2,y2), (x3,y3) — координаты заданных точек.

Формат выходных данных:

Программа должна:

• Вычислить координаты точки Штейнера S(xs,ys).
• Вывести общую длину построенного дерева.
• Открыть графическое окно с визуализацией результата.

Пример работы программы:

Входные данные:

Выходные данные:

Порядок решения задачи о минимальном дереве Штейнера

Шаг 1: Определение входных данных

Заданы три точки A(x1,y1), B(x2,y2) и C(x3,y3) в евклидовой плоскости. Нужно найти минимальное дерево, соединяющее их, с возможностью добавления одной точки Штейнера S(xs,ys), которая минимизирует сумму расстояний.

Шаг 2: Поиск точки Штейнера

Метод градиентного спуска применяется для нахождения оптимальной точки S.

1. Начальная точка

• Используем центр масс терминальных точек в качестве начальной точки

2. Минимизация суммы расстояний

• Вычисляем сумму расстояний от текущего положения S до всех терминалов:

• Двигаемся в направлениях вверх, вниз, влево и вправо с некоторым шагом Δ, уменьшая его, когда не находим лучшего положения.
• Останавливаемся, когда шаг становится меньше заданной точности.

Шаг 3: Визуализация графа (SFML)

После нахождения S(xs,ys), строим дерево:

1. Рисуем точки:

• Красные круги для терминальных точек A,B,C.
• Синяя точка для найденной точки Штейнера.

1. Рисуем рёбра:

• Жёлтые линии от точки S к каждой из терминальных точек.

1. Отображение в окне SFML

• Создаём окно SFML.
• Отображаем точки и соединяющие линии.
• Обновляем экран.

Шаг 4: Вывод результатов

1. Вывод координат точки Штейнера
2. Вывод длинны минимального дерева
3. Графическое представление:

- Красные точки — исходные точки

- Синяя точка — точка Штейнера

- Жёлтые линии — минимальное дерево

Код программы

Итог

Метод использует градиентный спуск для поиска точки Штейнера и SFML для визуализации. Это позволяет эффективно решать задачу и демонстрировать результат в графическом окне.

Скачать код