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

Реши гентическим алгоритмом

*генетическим

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

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

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

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

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

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

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

Построим следующий граф: вершиной являются три числа <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 - в конец очереди. Несложно доказать, что в таком графе расстояние от начального узла до конечного равно количеству поворотов.

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

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

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

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

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

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

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

Ещё ссылка:

http://users.ece.utexas.edu/~dpan/2008Fall_EE382V/notes/lecture18_gr.ppt