Постановка задачи

Даны на плоскости две фиксированные точки S (start) и T (target) и множество препятствий, каждое препятствие — отрезок (замкнутый, непроницаемый). Требуется найти путь минимальной длины из S в T, не пересекающий внутренностей препятствий (может касаться краёв или проходить через концы отрезков при условии допустимости касания).В частых вариантах препятствия образуют набор непересекающихся отрезков, или же образуют замкнутые многоугольные препятствия (многоугольники); также могут быть пересечения отрезков (сложная полигональная среда).

Классы подходов и их идеи
1) Чисто геометрические конструкции

Метод отражения. Для одного (или нескольких) прямолинейных барьеров: сверкнуть точку T относительно прямой, содержащей отрезок, и провести прямую S — отражённая T; точка пересечения с отрезком даёт точку касания минимального пути. Работает для одной прямой стены и в ряде простых конфигураций, когда короткий путь содержит одно касание к прямой.Правило «вершин» для полигональной среды: теорема «коротчайший путь среди многоугольников» — кратчайший путь можно представить ломаной, вершины которой — либо S и T, либо вершины препятствий (концы отрезков). То есть максимальные точки поворота находятся в вершинах препятствий (или в касательных точках, которые на отрезках совпадают с концами в случае жёстких отрезков).Построение видимости (visibility). Строят граф видимости: узлы — S, T и все концы отрезков; ребро между двумя узлами существует, если отрезок между ними не пересекает препятствий. Тогда кратчайший путь — кратчайший путь в этом графе (взвешенном длинами ребер).

Плюсы / минусы геометрических методов

Плюсы: точные, даёт доказуемую оптимальность (при корректном построении), хорошо для небольшого числа препятствий; отражение — красивый учебный пример.Минусы: ручные построения ограничены по числу препятствий; видимостьный граф в худшем случае имеет O(n^2) ребер (n — число концов отрезков), вычисление видимости требует аккуратных алгоритмов; трудно учесть нетривиальные касательные точки для криволинейных препятствий.

2) Графовые и дискретизационные алгоритмы (алгоритмы поиска на графе)

Видимостьный граф + Dijkstra/A. Построить все видимые пары вершин → получается граф; затем кратчайший путь по графу. A с эвристикой (евклидово расстояние) ускоряет поиск.Дискретизация на сетке (решётка): моделирование пространства в виде сетки клеток (проходимые/заблокированные) и поиск кратчайшего пути графовыми методами (BFS, Dijkstra, A*, Jump Point Search). Подходит для большого количества мелких препятствий или когда среда представлена растрово.Сэмплинг-методы: PRM (probabilistic roadmap), RRT (rapidly-exploring random tree) — строят случайный граф/дерево конфигураций, соединяют образцы в свободном пространстве, ищут путь в этом графе. Хороши для высокоразмерных задач и ограничений движения (роботика).Алгоритмы для полигональной среды: после триангуляции можно получить сокращённую структуру и применить funnel-алгоритм (если маршрут ограничен конвейером треугольников, shortest path в простом многоугольнике можно получить линейно после построения пути по диагоналям).

Плюсы / минусы графовых методов

Плюсы: алгоритмическая универсальность, хорошо подходят для реализации на компьютере, A*/PRM/RRT — практичны в робототехнике, можно учитывать дополнительные ограничения (динамика, размеры робота).Минусы: дискретизация даёт приближение (погрешность контролируется размерами ячеек/числом точек), видимостьный граф в худшем случае квадратичен по ребрам; PRM/RRT — вероятностные: дают приближённый или вероятно-достоверный результат, могут требовать много семплов в плотных средах.

3) Методы вариационного исчисления и непрерывные численные методы

Формулировка как задача вариационного исчисления: минимизация длины L[γ] = ∫ |γ'(t)| dt при ограничении γ(t) ∈ Ω_free (область без препятствий). Это задача с неравенствами (ограничение, препятствия) — приводит к задачам с контактными (свободными) границами.Уравнения Эйлера — Лагранжа в свободных участках дают прямые (в евклидовой метрике), а на стыках с препятствием возникают условия касания (закон отражения при гладких стенках).Численные PDE-подходы: решение уравнения Эйконала |∇T(x)| = 1 с заданными барьерами (T — время/расстояние до источника). Fast Marching Method / Fast Sweeping дают карту расстояний и геодезические линии — извлечение пути делается по спуску по градиенту карты расстояний.Оптимизация траектории: представить путь как набор узлов и минимизировать суммарную длину с добавлением штрафов за пересечение препятствий (barrier/penalty methods), а затем выполнять численную оптимизацию (градиент, SQP). Также «elastic band» и «string pulling» — итеративное сглаживание и натяжение ломаной.

Плюсы / минусы вариационных и непрерывных методов

Плюсы: подходят для гладких обобщений, позволяют учитывать непрерывные ограничения, хорошо работают в областях большого размера и для получения поля расстояний ( полезно для многократных запросов ). Fast marching — быстрый, устойчивый способ получить расстояние.Минусы: сложнее математически (метод свободных границ, контактные условия), численные методы требуют сеток/дискретизации, возможны артефакты и необходимость постобработки для извлечения «точного» пути; оптимизация с штрафами может застревать в локальных минимумах.

Сравнение и рекомендации по применимости

Учебная (школьная) практика:

Простые геометрические задачи (отражение, доказательство про вершины): отлично подходят для иллюстрации методов минимума и свойств коротких путей, стимулируют геометрические рассуждения.Построение видимости и ручной поиск кратчайшего пути в примерах с небольшим числом отрезков — хорошая олимпиадная/курсовая тема.Дискретный подход на сетке + A* — доступен при подготовке в информатике; просто реализуется и демонстрирует практические алгоритмы поиска пути.Вариационные методы и PDE — требуют более высокого уровня (университет): можно показать идею fast marching в демонстрации, но полный математический аппарат не обязателен.

Прикладная практика (робототехника, GIS, CAD):

Небольшое число препятствий, точные решения: видимостьный граф + Dijkstra/A* — предпочтителен (точный, быстрый, доказуемый).Много препятствий, плотная среда, необходимость быстрого ответа на регулярные запросы: построить карту расстояний (Fast Marching / Eikonal) и извлекать путь — экономно при многократных запросах.Реал-тайм роботы, высокие размеры состояния или динамические ограничения: sampling-based planners (PRM, RRT, RRT*) и их варианты, дополненные локальными планировщиками и сглаживанием.Динамическая среда (движущиеся препятствия): D, D Lite (динамическая версия A*) или алгоритмы перезапрошения маршрута.Для задач, где требуется оптимальность и корректность — использовать алгоритмы из вычислительной геометрии (видимость, funnel), для приближённости и скорости — дискретизация/A*/sampling.

Сложность и ресурсы

Видимостьный граф: в худшем случае O(n^2) рёбер; построение видимости наивно — O(n^3) проверок, оптимизировано — O(n^2 log n) или с использованием секционных структур быстрее для специальных случаев.Dijkstra/A*: O(E + V log V) с бинарной кучи; для видимостьного графа это ~ O(n^2 log n).Fast Marching на сетке M узлов: O(M log M) или O(M) при специальных реализациях; погрешность ограничена шагом сетки.PRM/RRT: время зависит от числа семплов k и плотности среды; нет жёсткой гарантии оптимальности (RRT* даёт асимптотическую оптимальность).

Практические замечания и «подводные камни»

Короткий путь может касаться крайних точек отрезков — нужно включать концы отрезков в набор кандидатных точек.При касании (скольжение по краю) короткий путь может содержать участок вдоль отрезка; такой путь корректно получается в видимости/graph-подходе если разрешено проходить по краям.Потенциальные поля (gradient-based, навигационные функции) просты, но склонны к ловушкам локальных минимумов.Обработка пограничных/вырожденных случаев (S или T на препятствии, пересекающиеся отрезки) требует спец. обработки.Если робот имеет ненулевой радиус, нужно «увеличить» (морфологически расширить) препятствия на радиус робота и решать задачу для точки.

Краткие рекомендации выбора метода по задачам

Небольшой n, требуется точность: visibility graph + Dijkstra/A* (или funnel при связности полигонов).Плотная/большая среда, многократные запросы: fast marching/Eikonal для карты расстояний + извлечение пути.Реал-тайм навигация робота с динамикой/нехолономией: sampling-based planners (RRT*, kinodynamic RRT), с последующей оптимизацией пути.Школьные упражнения: отражение, показ свойств через небольшие примеры; реализация A* на сетке для практики программирования.

Заключение
Существует несколько взаимодополняющих подходов: геометрические методы дают точные теоретические решения и полезны в математическом образовании; графовые/дискретные алгоритмы (видимость, A*, PRM/RRT) — основной инструмент в практических приложениях; вариационные и PDE-подходы (fast marching, оптимизация) удобны для вычисления карт расстояний и для численных решений в больших средах. Выбор зависит от размера и структуры задач, требований к точности и времени, а также от того, доступен ли вычислительный инструмент (программа) или требуется ручная геометрическая постройка.

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

показать конкретный пример построения графа видимости и алгоритма A* для нескольких отрезков (с иллюстрацией шагов),описать детально алгоритм funnel и как из треугольной разбивки извлечь оптимальный путь,привести пример реализации Fast Marching и извлечения пути на сетке.