Как называется этот алгоритм поиска пути?

введите здесь описание изображения

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

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


algorithm graph-algorithm
person Hosdgfag2    schedule 01.11.2015    source источник
comment
На картинке слева показан правильный путь. На картинке справа нет. Тогда речь идет не о конкретном алгоритме, а об изменении представления вашей среды (синие точки = стены, нет ограничений на переход от узла к узлу)   -  person Dese    schedule 01.11.2015
comment
Какова структура вашей карты (это вообще сетка?), как вы можете ходить (телепортироваться (с евклидовой стоимостью) в любой узел, если вы не проходите сквозь стену?)   -  person harold    schedule 01.11.2015

Ответы (2)


arrow_upward
3
arrow_downward

Поиск евклидовых кратчайших путей на основе дискретизации двумерной сетки проходимого пространства может быть выполнен с помощью Тета*.

Другой (более часто используемый) подход основан на стандартном 4- или 8-стороннем поиске пути (рисунок слева) с последующей оптимизацией «выдергивания строки». Наиболее распространенный алгоритм для этого известен как "Алгоритм воронки".

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

person Sneftel    schedule 01.11.2015
comment
Вы упомянули о других алгоритмах вытягивания строк, которые более подходят для выпуклых многоугольников; не могли бы вы назвать их? Это может быть полезно. - person legends2k; 27.10.2017
comment
@ legends2k Если вашу среду можно описать как полигональную декомпозицию, вы можете выполнить A * на гранях / ребрах самих полигонов, либо используя эвристику средней точки, либо (если вам требуется абсолютная оптимальность за счет значительного увеличения сложности) алгоритм Хершбергера описан в «Оптимальном алгоритме евклидовых кратчайших путей на плоскости». - person Sneftel; 20.02.2020

arrow_upward
0
arrow_downward

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

Для алгоритмического решения проверьте эти две ссылки:

  • Хершбергер, Джон; Сури, Субхаш (1999), «Оптимальный алгоритм для евклидовых кратчайших путей на плоскости», SIAM Journal on Computing 28 (6): 2215–2256, doi: 10.1137 / S0097539795289604.

  • Капур, С .; Махешвари, С.Н. (1988), «Эффективные алгоритмы для евклидовых задач поиска кратчайшего пути и видимости с многоугольными препятствиями», Proc. 4-й симпозиум ACM по вычислительной геометрии, стр. 172–182, doi: 10.1145/73393.73411, ISBN 0-89791-270-5.

person Yves Daoust    schedule 01.11.2015