LINUX.ORG.RU

В продолжение темы о кратчайших путях


0

0

Начало тут http://www.linux.org.ru/forum/development/4973047
Waterlaz предложил алогритм дейкстры для пары (точка, ребро): я считаю, что эффективно разбить плоскость на такие пары нельзя, поэтому и реализовать никак

Волновой уже делал, там непонятно как определять сложность перехода, потому что всё поле покрывается стопкой цифр, а обратный кратчайший путь приходится искать по ним. (Lee algorithm)

Алгоритм Hightower: невозможно найти описание :( IEEE всё загородила

Есть ещё A*, но у него странная реализация, которую сложно видоизменить для выбора приоритетов. Например путь всегда получается лесенкой. Он хорош для непрерывных пространств без ограничений

Что придумать то? // сорри много букв


Что придумать то? // сорри много букв

Уважаемый, вы строите эту «лесенку», а потом убирает лишние углы:

        |              |
   _____|              |
  |         ==>        |
  |                    |
__|               _____|

думаю алгоритм оптимизации то вы таки придумаете сами? Чтоб вы не заморачивались подскажу что кратчайший длина и у оптимизированного и у неоптимизирвоанного пути одинакова, потмоу если вы не даете углам «вес» рассчете путей у вас будет получаться лесенка.

wfrr ★★☆
()
Ответ на: комментарий от wfrr

Вот не надо, а. Задача не простая ни разу, Убрать лесенку, с учётом препятствий - это опять надо искать путь

jreznot
() автор топика
Ответ на: комментарий от jreznot

Кто хочет ищет способы, кто не хочет - препятствия.

wfrr ★★☆
()

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

Построим следующий граф: вершиной являются три числа <x, y, d> - координаты x и y узла сетки и направление, с которого мы пришли в эту вершину(например, север = 0, восток = 1, юг = 2, запад = 3). Вершины соединяются ребрами двух типов: <x0, y0, d>-<x1, y1, d> весом 0 (при этом переход из (x0, y0) в смежный узел (x1, y1) должен осуществляться по направлению d) и <x, y, d0>-<x, y, d1> весом 1 (остаемся в том же узле, но меняем направление). Теперь нам осталось только найти кратчайший путь в данном графе. Самая лучшая реализация поиска кратчайшего пути в таком графе (в литературе даже встречается специальное название для них: 0-1-граф) - волна на деке. Когда переходим в вершину по ребру с весом 0, пихаем ее в начало очереди. Когда по ребру с весом 1 - в конец очереди. Несложно доказать, что в таком графе расстояние от начального узла до конечного равно количеству поворотов.

sweiss
()

Прошу прощения, что не ответил в предыдущей теме - не было времени выйти в интернет.

Ссылка на описание алгоритма Maze, с различными его модификациями, в том числе есть что-то о Hightower:

http://www.eecs.northwestern.edu/~haizhou/357/lec6.pdf

SSN
()

> Есть ещё A*, но у него странная реализация, которую сложно видоизменить для выбора приоритетов.

A* очень просто адаптируется для любых приоритетов. Надо только правильным образом построить эвристическую функцию.

SSN
()
Ответ на: комментарий от jreznot

Вот не надо, а. Задача не простая ни разу, Убрать лесенку, с учётом препятствий - это опять надо искать путь.

Как правило задачи на решение конфликтов при трассировке решаются за счёт изменения приоритетов областям, в которых происходит конфликт с последующей перетрассировкой. Цикл продолжается до тех пор, пока за счёт приоритетов конфликтующие неты не будут перекинуты из области, в которой происходит конфликт, или пока не будет превышен лимит итераций ( = трассировка невозможна).

SSN
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.