Реализация алгоритма 1-Steiner

Данная работа посвящена реализации и оптимизации алгоритма 1-Steiner построения дерева Штейнера для заданного множества точек на плоскости. Программа принимает набор исходных координат и генерирует граф с добавленными точками Штейнера, минимизируя суммарную стоимость (длину) связей.

Сборка и запуск

Проект использует C++23 и собирается с помощью CMake. Управление зависимостями происходит автоматически через CMake Package Manager (CPM), устанавливать их вручную не требуется.

Требования

• CMake
• Git
• Компилятор с поддержкой C++23 (gcc 14.1+, clang 18.0+, MSVC 17.10+ и т.д.)
• Система сборки, поддерживаемая CMake (ninja, make и т.д.)

Установка

Linux / macOS:

git clone git@github.com:Iprime111/steiner.git
cd steiner
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build .

Windows:

git clone git@github.com:Iprime111/steiner.git
cd steiner
mkdir build && cd build
cmake .. -G "Visual Studio 18 2026" -A x64
cmake --build . --config Release

(Пример сборки для Visual Studio 18 2026 и x86_64)

Независимо от системы, при использовании вышеописанных примеров конфигурации, итоговый исполняемый файл будет расположен в папке build.

Использование

В базовом варианте достаточно передать программе только входной файл. В этом случае по умолчанию применяется неоптимизированная (base) версия алгоритма.

Пример запуска из директории build:

./steiner input.json

Если флаг выходного файла не указан, результат будет автоматически сохранен в той же директории, что и входной файл, под именем <имя_входного_файла>_out.json (в данном примере это будет файл ./input_out.json).

Аргументы командной строки

Для детальной настройки параметров выполнения предусмотрены следующие флаги:

Флаг	Назначение	Комментарий
-i, --input <путь>	Путь к входному файлу в формате JSON	Допускается передача первым аргументом без флага
-o, --output <путь>	Путь для сохранения итогового графа	Если не указан, файл создается автоматически с суффиксом _out.json.
-t, --time	Замер времени выполнения алгоритма	Операции ввода-вывода файлов исключаются из подсчета
-r, --repeat <число>	Количество итераций выполнения алгоритма	Используется для усреднения результатов и повышения точности замеров
-v, --verify	Верификацию графа, полученного на выходе	Проверяет соответствие кол-ва ребер/вершин и степени вершины точек Штейнера
-m	Оптимизированная (batched) реализация алгоритма	Без этого флага используется базовая реализация

Описание алгоритма

Алгоритм 1-Steiner предназначен для поиска оптимального дерева, соединяющего все заданные точки (терминалы), с возможностью добавления новых вспомогательных узлов (точек Штейнера). Добавление таких узлов позволяет сократить общую длину всех ребер в дереве по сравнению с обычным минимальным остовным деревом (MST).

Базовая версия (base)

Классическая реализация алгоритма работает путем жадного перебора. Для каждой потенциальной позиции новой точки Штейнера (определяется по сетке Ханана) алгоритм пересчитывает минимальное остовное дерево и оценивает выгоду. Данный подход гарантирует хорошие результаты, но явялется достаточно медленным.

Пакетная версия (batched)

Пакетный (batched) алгоритм является оптимизированной модификацией и работает следующим образом:

1. На каждой итерации все кандидаты в точки Штейнера сортируются по потенциально получаемой выгоде (сокращению итоговой стоимости дерева) при добавлении в дерево.
2. Для каждой из таких точек составляется список затронутых вершин. Для этого применяется простая эвристика: выбираются только те узлы, которые были бы напрямую связаны ребром с данной точкой Штейнера при добавлении только ее одной в MST.
3. Затем применяется жадный отбор: выбирается максимальное количество кандидатов с наибольшей выгодой так, чтобы множества их затронутых вершин не пересекались.
4. Все отобранные кандидаты попадают в один пакет (batch) и применяются к графу одновременно.

Важно отметить, что на практике применение данной эвристики не дает ухудшения стоимости финального дерева более 2% по сравнению с базовой версией, однако кардинально сокращает количество перерасчетов MST. При этом некоторых случаях такая эвристика дает улучшение итогового результата.

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

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

Система принимает на вход JSON файл со структурой, содержащей список вершин (node). Исходные вершины помечаются типом "t" (терминалы).

{
    "node": [
        {
            "name": "p1",
            "x": 90,
            "y": 75,
            "id": 1,
            "type": "t"
        },
        {
            "name": "p2",
            "x": 49,
            "y": 22,
            "id": 2,
            "type": "t"
        }
    ],
    "edge": []
}

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

В результирующем файле структура расширяется.

1. К существующим узлам добавляется массив инцидентных ребер (edges).
2. Добавляются вычисленные точки Штейнера (маркируются типом "s").
3. Массив edge заполняется описанием ребер графа (идентификатор и пара соединенных вершин).

Анализ производительности

Тестирование производилось на примерах, расположенных в папке examples данного репозитория. Все тесты выполнялись на Apple M4 pro (~4.51 GHz performance core, 192 Kb L1 cache, 16 Mb L2 cache), 16Gb RAM.

По результатам тестирования был проведен сравнительный анализ эффективности версий base и batched. Обе версии корректно строят деревья почти одинаковой стоимости (различие меньше 1%). Все измерения проводились при 10-кратном повторении алгоритма (-r 10) для минимизации погрешности.

Для измерения времени использовался std::chrono::high_resolution_clock из стандартной бибиотеки C++. Несмотря на то, что погрешность самого таймера крайне мала, наличие ОС, кэшей и прочих механизмов процессора вносит заметную погрешность в итоговые измерения. В задачи данной работы не входит точная оценка прироста производительности, поэтому погрешность была оценена сверху в 5%.

Сравнение метрик: Base vs Batched

Тест	Стоимость (Base / Batched)	Точки Штейнера (Base / Batched)	Время (Base / Batched), мс	Ускорение
0005	179 / 179	1 / 1	0.50 / 0.48	~1.0x
0006	179 / 179	2 / 2	1.16 / 1.25	~0.9x
0007	205 / 205	3 / 3	3.63 / 2.46	~1.5x
0008	202 / 202	2 / 2	3.46 / 2.26	~1.5x
0009	227 / 227	4 / 4	9.76 / 8.09	~1.2x
0010	267 / 267	4 / 4	14.8 / 8.6	~1.7x
0011	247 / 246	4 / 5	19.6 / 13.0	~1.5x
0012	274 / 274	5 / 5	35.4 / 23.7	~1.5x
0013	209 / 209	5 / 5	69.5 / 32.3	~2.1x
0014	297 / 297	4 / 4	43.7 / 26.2	~1.7x
0015	293 / 293	6 / 6	91.6 / 38.7	~2.4x
0016	261 / 261	6 / 6	109 / 65.0	~1.7x
0017	341 / 341	8 / 8	200 / 93.0	~2.1x
0018	337 / 337	8 / 8	244 / 125	~2.0x
0019	304 / 300	6 / 8	205 / 132	~1.5x
0020	332 / 332	6 / 6	248 / 149	~1.7x
0021	352 / 352	9 / 9	480 / 265	~1.8x
0022	345 / 349	10 / 9	647 / 174	~3.7x
0023	397 / 397	9 / 9	670 / 359	~1.8x
0024	355 / 352	8 / 10	675 / 331	~2.0x
0025	397 / 397	11 / 11	1142 / 399	~2.9x
0026	389 / 389	7 / 7	989 / 528	~1.9x
0027	392 / 392	10 / 10	1318 / 510	~2.6x
0028	409 / 407	7 / 8	1038 / 409	~2.5x
0029	366 / 365	12 / 13	2120 / 935	~2.3x
0030	432 / 432	13 / 14	2690 / 592	~4.5x

Выводы

1. Малые графы: На графах с низким количеством терминалов разница в производительности мала и во многом определяется накладными расходами на сортировку и фильтрацию кандидатов в batched версии. Прирост при этом может быть отрицательным или нулевым, как в тестах 0005 и 0006

2. Средние и большие графы: С ростом числа узлов базовая версия демонстрирует сильный рост времени работы. Оптимизация через пакетную обработку в некоторых случаях (тесты 0039, 0027 и т.д.) позволяет сократить время выполнения более чем в 2 раза, сохраняя при этом точность результата (отклонение по стоимости минимально).

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