Эффективный алгоритм поиска пути, избегающий zigzag's

Question

Я разрабатываю программное обеспечение, которое соединяет объекты с проводами. Эта проводка имеет правило, что эти провода не могут проходить на других объектах, и диагональное перемещение не принимается.

Все кратчайшие пути алгоритмы, которые я знаю (A *, Дейкстра и т.д.) найти этот тип путей:

Я не хочу ненужных зигзагов во втором скриншоте. Как достичь этой цели?

Примечание: Любой, кто хочет попробовать алгоритмы, может использовать приложение this.

Другое примечание: Это точная ситуация, в которой я не хочу. Он находит путь зигзага вместо того, чтобы «идти вправо, пока вы не достигнете позиции х цели, идите вверх, пока не достигнете позиции y цели», которая имеет одинаковую стоимость с зигзагообразным.

Answer 1

Ваш текущий алгоритм находит кратчайший путь, Pmin, но улучшенный алгоритм должен найти кратчайший путь, который принимает минимальное количество оборотов (Pmin, Tmin). Общее решение требует, чтобы вы работали с парой чисел вместо одного числа. Если вновь найденный Pnew меньше текущего Pmin ИЛИ если он равен, но Tnew меньше Tmin, тогда возьмите (Pnew, Tnew) как новый минимальный путь.

Если плата достаточно мала, вы все равно можете использовать один номер, который вы используете в настоящее время, но это число должно быть составным номером C = P * N + T, где N - достаточно большое и достаточно небольшое постоянное число. Он должен быть больше, чем максимально возможный T для этой платы, что составляет почти общее количество плиток в доске. Он также должен быть достаточно мал, чтобы не было целочисленного переполнения, когда алгоритм обрабатывает самый большой путь на доске, что также является общим количеством плиток в доске. Так N должен удовлетворять эти два термина (B является общим количеством плиток в доске):

N > B 
B * N < INT_MAX 

Если B больше, чем SQRT(INT_MAX) то эта система является неразрешимой, и вы должны пойти с парой значений. N должно быть SQRT(INT_MAX), которое для 2 is 2 .

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

Answer 2

Интуитивно вы можете сделать это, предоставив вашему агенту «импульс».

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

Answer 3

Я не знаком с поисковыми алгоритмами конкретно, но это был бы лучший программный подход, псевдонимый ниже.

объектов мы используем:

vertex { //generic x,y coordinate 
    int x; 
    int y; 
} 
vertices[3]; //3 vertices: 0, 1, 2 (0 is start, 1 is mid, 2 is end); 

И наш алгоритм, который зависит от наиболее эффективного пути уже нашли, не имея странность как ¯ | _ | ¯

boolean hasObstacles = false; 

int increment = 0; 
//there's some other ways to set this up, but this should make the most sense to explaining which way we need to go 
if(vertices[0].x < vertices[2].x) 
    increment = 1; 
else 
    increment = -1; 

for(int i = vertices[0].x; i != vertices[2].x; i = i + increment) { 
    //check for collision at coordinate (i, vertices[0].y), set hasObstacles to true if collision 
} 

if(vertices[0].y < vertices[2].y) 
    increment = 1; 
else 
    increment = -1; 

for(int i = vertices[0].y; i != vertices[2].y; i = i + increment) { 
    //check for collision at coordinate (vertices[2].x, i), set hasObstacles to true if collision 
} 

if(!hasObstacles) { 
    //we can remove these 3 vertices and add this point to our list of vertices. 
    vertex corner = new vertex(vertices[2].x, vertices[0].y) // relocation of point 
} 

Скан должен прогрессировать одну вершину вовремя. Если 3 вершины заменены одной вершиной, следующее сканирование должно использовать эту новую вершину как 0.

Answer 4

Прямо сейчас ваш алгоритм отвечает на вопрос «какие квадраты проходят оптимальный путь?» У вашего графика есть узел для каждого квадрата и край для каждой пары смежных квадратов.

Изменить его на «где оптимальный путь пересекает границы между квадратами?»

Ваш график изменится:

• узлов графа: середину каждого ребра между соседними квадратами + старт + финиш.
• Графические края: на каждом квадрате они соединяют каждую пару квадратных ребер.

И теперь вы можете по-разному рассчитывать соединения противоположных квадратных краев и соединений соседних квадратных краев. Увеличение веса до второго уменьшит количество зигзагов.

Answer 5

Ваша проблема нетривиальна, поскольку, например,если вы жадно заходите так далеко, как можете вверх или направо, то вы можете столкнуться с плотным лабиринтом предметов, для которых требуется безумный путь зигзага, а если вы остановились перед плотным лабиринтом, вы могли бы изменить направлений меньше, по существу, обходя лабиринт. И вы можете столкнуться с этой дилеммой в любом месте по пути, а не только в начале. Один из способов решения этой проблемы - использовать Dijkstra и определить сетку местоположений, к которым вы можете путешествовать, а затем определить переход на 2 шага вперед вместо 1 шага. Определить расстояние между двумя связанными точками сетки очень мало, если движение чисто горизонтально или чисто вертикально в одном ориентированном направлении и очень велико, если движение меняет направление в середине. Затем, предполагая, что длина пути от начала до конца четна, кратчайший путь от начала до конца в этой структуре с двойным перемещением - это путь, который минимизирует количество зигзага. Если длина пути от начала до конца является нечетной, то используйте точки сетки на одно место в горизонтальном и вертикальном направлениях, чтобы начать, а затем длина пути от начала до конца будет четной (хотя вам придется запускать поиск пути для обоих возможные измененные начальные позиции).

Answer 6

Используйте пару значений (удваивает, целые числа и т. Д.) Для расчета расстояния.

Первый - это расстояние, второе - количество оборотов.

Сортировка лексически, поэтому первое имеет значение больше, чем второе.

Это чище, чем «использовать штраф за повороты» как математически, так и программно.

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

Эвристика - это расстояние в Манхэттене, с поворотом, если вы не точно горизонтали или вертикально выровнены с целью.

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

Answer 7

Внутренний алгоритм оценивает множество возможных путей и выбирает самый короткий.

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

Answer 8

Все, что вам нужно, это немного изменить эвристику вашего алгоритма A *. Один на моей голове: если вам не нравятся эти повороты, вы можете просто наказывать каждый ход.

Таким образом, ваша эвристика будет зависеть от количества поворотов и расстояния Манхэттена до цели. Важно не забывать, что он не должен переоценивать расстояние до цели. Подробнее о том, как выбрать heuristic here.