Ниже — практический рецепт: сначала — геометрическая модель, затем пошагово два подхода (аналитико‑геометрический и дискретно‑численный) и в конце — сравнение и рекомендации по применению.

1) Геометрическая модель задачи

Плоская область Ω разбивается на подрегионы Ωk (город, пойма, дорога, река и т.п.). Каждому региону присвоена «стоимость прокладки» wk (стоимость за единицу длины). Река/дорога могут быть:
областью с очень высокой стоимостью (если разрешён переход в любом месте, но дорого), илизапрещённой областью (∞ стоимость), но с ограниченными местами перехода — мосты/туннели, которые задаются как узлы перехода с отдельными ценами.Три терминала (города) — точки A, B, C в Ω, которые нужно соединить сетью кабеля минимальной суммарной стоимости (интеграл веса вдоль проводов).Стоимость сети = суммарный интеграл по всем веткам ∑ ∫ wk(s) ds. Для кусочно‑постоянного wk это сумма длин отдельных отрезков в каждом регионе, умноженная на соответствующий wk.Разрешённые топологии сети (для трёх терминалов): либо «Steiner‑топология» с одним Steiner‑узлом S, соединяющим все три точки, либо «MST‑топология» (две из точек напрямую связаны, третья к ним подсоединяется). Оптимальная топология нужно проверить обе.

Формальные локальные условия оптимальности

Внутри однородного региона (константное w) ветки оптимального Steiner‑решения выходят из Steiner‑точки под углами, удовлетворяющими векторному условию:
∑i wi * ui = 0,
где ui — единичные векторы от Steiner‑точки к трём концам. При равных весах wi это даёт углы 120°.При пересечении границы между регионами с весами w1 и w2 путь минимальной стоимости подчиняется закону «рефракции» (аналог Снелла):
w1 sin θ1 = w2 sin θ2,
где θi — угол ветки с нормалью к границе в соответствующем регионе. Это следует из вариационного принципа (минимизации суммарной стоимости при варьировании точки пересечения).Если регион запрещён (∞ стоимость), переход допустим только в специально заданных точках (мосты) — это превращает задачу части в дискретную.

2) Шаги применения геометрической модели (аналитико‑геометрический подход)
Подходит если границы простые, веса кусочно‑постоянные и вы хотите получить аналитические/полуаналитические условия.

Шаг 1. Картирование и классификация

Нанесите координаты A, B, C и границы регионов. Определите веса wk и места/способы пересечения реки/дороги (разрешённые точки или свободный переход).

Шаг 2. Выбор топологий

Рассмотрите две топологии: с одним Steiner‑узлом S и без него (MST). Для каждой найдите локальные условия.

Шаг 3. Аналитическое построение оптимальных отрезков внутри регионов

Если линия соединяет два пункта и лежит в одном регионе — это прямой отрезок.Если оптимальная ветка пересекает границу между регионами — найдите точку пересечения x на границе, удовлетворяющую закону Снелла: w1 sinθ1 = w2 sinθ2. На практике это решается численно: параметризуйте точку пересечения и минимизируйте сумму w1 |segment1| + w2 |segment2|.

Шаг 4. Поиск Steiner‑точки S (если предполагается)

Поставьте уравнение баланса сил: wA (S−A)/|S−A| + wB (S−B)/|S−B| + wC * (S−C)/|S−C| = 0,
где wi — веса вдоль соответствующей ветки (для ветки пересекающей разные регионы вес является локальным коэффициентом в уравнении силы; практично использовать длину в единицах «стоимости», т.е. каждая ветка рассматривается как последовательность прямых сегментов с соответствующими wk).Решение этого в общем случае требует итерации: начинайте с S0 (например, центр масс в «стоимостном» смысле) и итеративно обновляйте S по правилу коррекции (метод Ньютона или градиентного спуска) до выполнения векторного баланса и условия Снелла на границах, если ветки пересекают границы.

Шаг 5. Сравнение с MST‑решением

Вычислите суммарную стоимость полученной Steiner‑сети и сравните с наилучшей «деревянной» топологией (две прямые + одна ветка). Выберите минимальную.

Пример применения закона Снелла (маленький иллюстративный расчёт)

Пусть A и B по разные стороны границы, w1=1 (лево), w2=2 (право). Пусть граница — прямая y=0, A=(−a,h), B=(b,−h). Параметризуйте точку пересечения x на y=0: X=(x,0). Стоимость:
L(x) = w1 sqrt((x+a)^2 + h^2) + w2 sqrt((b−x)^2 + h^2).
Минимизируйте L(x) (производная = 0) — получите w1 sinθ1 = w2 sinθ2. Решается численно (одна переменная).

3) Практический дискретно‑численный подход (рекомендую для реальных карт)
Когда карта сложная (нерегулярные границы, множественные препятствия, неоднородности), удобней переходить к дискретизации и численным алгоритмам.

Вариант A — графовый (прост и надёжен)
Шаги:

Триангулируйте/разбейте область Ω на сетку (регулярный квадратный грид или триангуляция Delaunay) с узлами Vij.Каждому ребру присвойте вес = длина ребра × средний wk на ребре. Заблокируйте ребра, которые проходят через запрещённые зоны.Включите специальные узлы/рёбра для мостов (если переходы разрешены только там).Найдите кратчайшие пути (по сумме весов) между каждой парой терминалов (Dijkstra / A*).Получите metric closure: граф терминалов+возможные Steiner‑узлы (можно включить как кандидатов сеточные узлы). Постройте минимальное Steiner‑дерево на графе с использованием эвристик (например, MST на metric closure, затем локальные улучшения, или алгоритм для Steiner tree (обзор: Kou‑Markowsky‑Berman алгоритм)).Для улучшения ответов можно разрешить добавление Steiner‑узлов как произвольных сеточных узлов и повторно оптимизировать (реверсификация).

Вариант B — континуально‑волновой (для точных геодезических расстояний)

Используйте Fast Marching Method (FMM) или алгоритм «continuous Dijkstra» на сетке, где скорость c(x)=1/w(x). FMM вычисляет функцию расстояния в «стоимостных» единицах от точки до всех точек в области.Вычислите «distance map» от каждого терминала, затем найдите точку S где суммарная стоимость dA(S)+dB(S)+dC(S) минимальна (поиск минимумa на сетке). Это даёт приближение оптимального Steiner‑узла.После нахождения S получите конкретные пути — трассы по градиенту карт расстояния (trace back).Это даёт качественное решение с контролем разрешения сетки.

4) Пошаговый пример рабочего процесса (рекомендация для инженера)

Подготовка данных: получить карту зон и задать wk; отметить мосты как специальные узлы.Выбор сетки: начать с грубой сетки для быстрого поиска топологии, затем локально уточнить сетку вблизи найденной трассы.Запуск FMM от A, B, C. На грубой сетке найти S* = argmin (dA + dB + dC).Из S* восстановить пути к A,B,C; подсчитать стоимость.Локальная оптимизация: вокруг S* запустить оптимизатор (Nelder‑Mead / L-BFGS) минимизируя суммарную стоимость, используя точную интерполяцию весов и законы пересечения границ (при пересечениях применять условия Снелла как мягкое ограничение).Проверка альтернативных топологий: вычислить стоимость «двух‑в‑ряд» (MST) и сравнить.Итеративное уточнение сетки до достижения требуемой точности.

5) Сравнение геометрического и численного подходов

Геометрический (аналитический) подход
Плюсы:

Даёт физическую интуицию (условия Снелла, 120° при равных весах).Возможность получить точные решения в простых конфигурациях и доказать оптимальность.Быстрое решение для кусочно‑постоянных и простых границ.

Минусы:

Сильно усложняется при сложных границах, множественных препятствиях, неравномерных wk.Трудно обобщить на большие сети (много терминалов).Требует ручной аналитической работы и решения нелинейных уравнений.

Численный (дискретный/FMM/графовый) подход
Плюсы:

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

Минусы:

Результат зависит от дискретизации (точность vs время).Может требоваться тонкая настройка (сетка, эвристики для Steiner).Меньше аналитического понимания, требуется верификация качества решения.

6) Практические рекомендации и инструменты

Для небольших практических задач с простыми границами: попытайтесь сначала геометрически/аналитически — используйте закон Снелла и условие баланса в Steiner‑точке. Это даст хорошую проверку.Для реальных карт используйте численные методы: FMM (C++/Python библиотеки), Dijkstra/A* на взвешенной сетке, QGIS для подготовки карты и экспорта весов.Инструменты: QGIS (обработка карт), scipy.optimize / NLopt (локальная оптимизация), Fast Marching Library (C++), scikit‑image или pyAMG для сеток, NetworkX / Steiner tree библиотеки для графовых эвристик.Тонкая настройка: уточняйте сетку вдоль границ и вокруг найденной трассы; тестируйте чувствительность решения при варьировании wk; учтите практические ограничения (запрет на изгибы под малыми радиусами, минимальные расстояния до построек и т.п.).

7) Примерный псевдокод (грубая схема алгоритма на основе FMM)

Считать карту весов w(x) и координаты A,B,C; задать список мостов/переходов.Дискретизировать область (сеткой или триангуляцией).Для каждого терминала Ti запустить FMM, получить картu расстояний di(x).Найти S* = argmin_x (dA(x)+dB(x)+dC(x)) на сетке.Восстановить трассы TA,TB,TC от S* к A,B,C по градиенту карт di.Локально оптимизировать положение S (необязательный continuous шаг) для тонкой настройки.Сравнить с MST: найти кратчайшие пути между парами терминалов и составить MST; выбрать лучшее.

Итог

Модель: кусочно‑постоянные веса по регионам + запрещённые зоны/мосты — формализуется как минимизация интеграла стоимости по сети.Геометрические законы (Снелл, баланс сил в Steiner‑точке) дают мощные условия оптимальности и полезны для простых случаев и в качестве проверки.Для практических карт предпочтителен численный подход (FMM/дискретизация + локальная оптимизация), с последующей верификацией геометрическими соображениями.

Если хотите, могу:

Сделать конкретный числовой пример (с координатами A,B,C, картой регионов и числами wk) и показать полный расчёт (анализ Снелла и/или решение на сетке), илиПодготовить код‑шаблон на Python (использующий библиотеку scikit‑image/heapq для Dijkstra и/или FMM), который вы сможете запустить на вашей карте.