Алгоритм трассировки

[Procopus]

Подскажите, кто знает, алгоритм, или источник, где его можно поискать.
Задача такая - разрабатывается среда моделирования, что-то типа Simulink'а в матлабе, т.е. на поле есть блоки, которые имеют входы и выходы. Пользователь устанавливает связи между входами/выходами. Надо, чтобы эти связи рисовались в виде ломаных линий, ну как обычно это везде рисуется. Связи могут проходить по занятым блоками позициям, но только если нет пути обхода, или он слишком запутанный. Вообще требования по навороченности алгоритма такой трассировки не предъявляются, лишь бы соединял и обходил блоки. Пока что самое главные требования - простота и скорость.

[Alf]

Мне кажется, для такой задачи подойдет волновой алгоритм.

Весьма доступно он изложен здесь: http://iron.fire.usi.ru/modules.php?name=Pages&pa=showpage&pid=96

[Procopus]

Волновой пока не хочу использовать, с ним опыт уже есть - он самый простой, но и, наверное, самый трудоемкий в вычислительном плане, то есть при малом шаге сетки, большой протяженности соединений и большом их количестве (если таскается блок с несколькими входами) он будет тормозить. В той статье он рассматривается, как я понял, применительно к роботам, у них это можно делать аппаратно, действительно смоделировав распространение волны, программно с рекурсиями это очень долго.

[Alf]

...В той статье он рассматривается, как я понял, применительно к роботам, у них это можно делать аппаратно, действительно смоделировав распространение волны,

Чего-то я не понял... Это что за аппаратный имитатор волн к роботам прилагается и каким образом он работает? У робота на борту имеется некое вычислительно-управляющее устройство, в лучшем случае оно обладает производительностью хорошей персоналки (а то и поменьше).

В статье моделируется игрушечный робот, который ищет дорогу к цели, огибая препятствия. Никаких спецпроцессоров на нем не предполагается.

...программно с рекурсиями это очень долго.

Во-первых, не уверен, что действительно настолько уж долго. Не настолько обременителен механизм рекурсии.

Во-вторых, никто не заставляет пользоваться рекурсией, если именно она - источник всех бед. Вполне можно применить итерацию.

В-третьих, можно в разы ускорить работу программы, если подобрать подходящие эвристики. Например, если соединение должно идти из верхнего левого угла в середину листа, не следует пытаться провести его через правый нижний угол. Сужая допустимый коридор для соединения, мы можем избежать отслеживания волнового фронта в тех областях, где он нам не интересен.

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

[Procopus]

Чего-то я не понял... Это что за аппаратный имитатор волн к роботам прилагается и каким образом он работает? У робота на борту имеется некое вычислительно-управляющее устройство, в лучшем случае оно обладает производительностью хорошей персоналки (а то и поменьше).

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

Насчет рекурсий, да, погорячился, но стек все-равно использовать придется. По поводу эвристик - интересная идея, странно что упустил ее из внимания.

А вот интересно, какой алгоритм используется в Visio, Simulink'е и прочих программах, где оптимальность маршрута роли не играет, а надо просто провести его по-быстрому.

[Alf]

За всех не скажу, а вот в MS Visio используется алгоритм "как Бог на душу положит". Это весьма отчетливо видно при перемещениях блоков с большим количеством соединений на существенные расстояния. Количество пересечений линий при этом обычно превосходит все разумные пределы. Сталкивался с этим при попытке рисования диаграмм UML при помощи сего инструмента.

По поводу использования стека. Распространение волны наиболее очевидно моделировать древовидной структурой. Исходная точка у нас - корень дерева. Его дочерние вершины - точки, достижимые из исходной за один шаг. Второй уровень составляют вершины, достижимые на втором шаге, и т.д. Конечная вершина будет достигнута (если будет) на шаге N, после чего построение дерева можно прекратить. Затем задача сведется к поиску пути на дереве от корня к конечной вершине.

С использованием рекурсии наиболее естественно построить поиск "сначала вглубь", при помощи итерации - "сначала вширь". Предположим, что мы рисуем на листе размером 1мХ1м с сеткой 1мм (полагаю, что это сильно завышенные цифры, поскольку такое изображение при насыщенном расположении связей будет больше похоже на лист миллиметровки, чем на удобочитаемую диаграмму). Путь максимальной длины будет лежать по диагонали листа, т.е. 2000 ячеек сетки. Удвоим его для верности (предположим, что трасса сильно петляет), получим глубину рекурсии 4000 вызовов. Если даже каждый вызов отложит в стек 100 байт (что заведомо превышает реальную потребность, подробно процессы в стеке мы обсуждали в статье "Механизмы рекурсии"), получим глубину стека менее половины мегабайта. Сейчас, когда на рабочем месте секретаря редко стоит агрегат менее чем с 256М оперативной памяти, это не выходит за грани разумного.

[Procopus]

За всех не скажу, а вот в MS Visio используется алгоритм "как Бог на душу положит". Это весьма отчетливо видно при перемещениях блоков с большим количеством соединений на существенные расстояния. Количество пересечений линий при этом обычно превосходит все разумные пределы. ативной памяти, это не выходит за грани разумного.

Вот это мне как раз и нужно Чтобы быстро и просто, пересечения пока не сильно волнуют.

С древовидной структурой ИМХО слишком сложно, разве только для более сложного анализа, а так я думаю спользовать стек, куда буду помещать новые точки. Это будет тот же поиск вширь с итерациями над содержимым стека.
Да, еще думаю для уменьшения количества поворотов "штрафовать" маршруты за каждую смену направляния.
Поиск вглубь получится, если я для следующего распространения поиска буду выбирать ограниченное число точек, полученное на текущем шаге, а остальные складывать в стек про запас.

[Alf]

Вот это мне как раз и нужно Чтобы быстро и просто, пересечения пока не сильно волнуют.

Тогда незачем огород городить с трассировкой, достаточно вести прямую от точки А до точки В. Только вот эстетика такого решения явно хромать будет, а с ней и визуальное восприятие диаграммы.

С древовидной структурой ИМХО слишком сложно, разве только для более сложного анализа,

А на мой взгляд, как раз самое простое решение. Достаточно только поменять направление трассировки - от конечной точки к начальной, и тогда весь маршрут будет полностью детерминированным, на каждом шаге поднимаемся к родительской вершине, без вариантов. Да и построить дерево не так сложно.

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

А вот эта идея мне непонятна. Я планировал лишь неявное использование системного стека через рекурсивные механизмы, однако там никакие вольности с итерациями не получатся.

[npak]

Волновой алгоритм делается без рекурсии, с очередью.  В очередь ставим узлы сетки, которые находятся на границе. При выемке узла из очереди он обрабатывается -- в очередь ставятся соседи узла, если они ещё не обработаны.

Именно очередь гарантирует, что узлы сети обрабатываются по мере роста удаления от начала волны.  Если очередь заменить на стек, то получится алгоритм поиска в глубину, а не волна.

Оценка размера очереди -- порядка N, где N -- линейный размер сети (ширина или длина).  Время работы на просторном поле (с малым количеством препятствий) порядка L*L, где L -- расстояние между началом волны и целевой точкой.

[Serega]

На самом деле волна одно из лучших решений, почитай про A*, его в играх обычно используют, а уж они-то время точно экономят
и откуда ты взял рекурсию действительно не понятно