Comments 4
То есть сначала делаете развесовку по некоторой эвристике и потом через очереди с приоритетом восстанавливаете? Не вижу каких-то принципиально новых подходов.
Не понятно на каких ограничениях все это работает - это может быть произвольный граф или оно на метричском пространстве обязательно должно быть, то есть расстояние между точками можно посчитать.
Какие ограничения на графы? Подойдёт ли n-конечная звезда или звезда Давида, например, в категорию валидных проблем? Подходит ли оно только для плоских графов или для произвольной мерности тоже подойдёт?
Хорошее замечание. Чтобы метод не "заблудился" в сложных топологиях (как упомянутые вами звезды), алгоритм работает в два этапа:
Аналитический (Генплан): На этом шаге строится топологический каркас. Мы находим "входы" и "выходы" из локальных скоплений точек, выявляем тупиковые зоны и определяем общее направление графа.
Геометрический (Шампур): Когда стратегический маршрут понятен, "Шампур" нанизывает на вектор движения выделенные узлы Генплана. Его задача — произвести "зачистку" периферийного шума и оставить только физически валидный коридор.
Таким образом, это не просто эвристика поиска, а тандем: топологический анализ гарантирует правильность маршрута (отсутствие тупиков), а геометрическая зачистка обеспечивает итоговую чистоту и скорость финальной трассировки. Это применимо к произвольной мерности, пока пространство остается метрическим. Другими словами «Шампур» — это не просто «слепой» геометрический луч, а высокоуровневый зачистик, который работает по уже размеченной «карте высот» или топологии.
Что касается топологий типа Звезды Давида или n-конечных звезд — они не являются критической сложностью для метода. Куда интереснее (и сложнее) ведут себя "злые" спирали или фрактальные лабиринты, где вектор цели может быть направлен в одну сторону, а физический проход — в противоположную.
Но именно для этого мы используем Генплан. Он заранее "маркирует" топологию, поэтому Шампур не пытается засасывать точки из соседних лучей звезды, даже если они находятся близко в пространстве. Он работает только с тем сегментом, который Генплан признал валидным путем к выходу. Звезду Давида, если будет интерес у аудитории, можем разобрать в следующих кейсах, но функционально она проще уже реализованных нами проходов через плотные облака со сложной периферией
А можете показать как будет обходиться мёртвая петля? То бишь топология какого-нибудь такого вида
Шампур не пытается засасывать точки из соседних лучей звезды,
меня больше интересует как ведёт себя алгоритм в точках самопересечения. То есть корректнее было спросить за n-граммы, а не просто звёзды. Ну всякие симметричные ветвления.
Ну и всякие вариаци, когда вот эти же примеры как-нибудь искажены твистером в разных направлениях.
Мне кажется, мы ходим по кругу. Как я уже говорил в ответе на ваш первый комментарий — топологическая связность в "Генплане" первична.
Попробую объяснить на пальцах: "Мертвая петля" или "Твистер" страшны только для слепого геометрического алгоритма, который ищет просто ближайшую точку. У нас же:
Если две ветки графа пересекаются или идут рядом, Генплан понимает, что это разные ветки (у них разная история связей).
"Шампур" — это не пылесос, который тянет всё подряд. Он забирает только те точки, которые санкционированы Генпланом для текущего участка. Самопересечение для него — это просто место, где одна ветка прошла "над" другой без потери логической нити.
Повторюсь: для алгоритма нет разницы, звезда это, n-грамма или фрактал. Это всё — просто набор условий и ограничений. Сделаем, не проблема — был бы заказчик с конкретными данными. Мы фокусируемся на прикладных задачах, а не на теоретических парадоксах.
На ваш взгляд, в каких реальных задачах (кроме чистой теории) вам встречались такие топологии, которые не смог переварить ни один инженерный метод?
Как решить TSP для 10 000 точек БЕЗ прыжков: метод «Динамического Шампура» с инерцией