Евклидов кратчайший путь - Euclidean shortest path

Пример кратчайшего пути в трехмерном евклидовом пространстве

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

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

В трех (и более) измерениях проблема заключается в NP-жесткий в общем случае^[1] но существуют эффективные алгоритмы аппроксимации, которые работают за полиномиальное время, основанные на идее поиска подходящей выборки точек на краях препятствия и выполнения вычисления графа видимости с использованием этих точек выборки.

Есть много результатов по вычислению кратчайших путей, которые остаются на многогранной поверхности. Даны две точки s и t, скажем, на поверхности выпуклый многогранник, проблема состоит в том, чтобы вычислить кратчайший путь, который никогда не покидает поверхность и соединяет s с t. Это обобщение проблемы из 2-мерного, но оно намного проще, чем 3-мерная задача.

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

Смотрите также

• Задача кратчайшего пути

Заметки

1. Дж. Кэнни и Дж. Х. Рейф "[https://www.researchgate.net/profile/John_Canny2/publication/4355151_New_lower_bound_techniques_for_robot_motion_planning_problems/links/5581e03708ae6cf036c16ff3/New-lower-bound-techniques-mofor-robotz-problems-for-dfbot Новые методы нижних оценок для задач планирования движения роботов] ", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp.49-60.

использованная литература

• Александров Людмил; Махешвари, Анил; Сак, Йорг (2005), "Определение приближенных кратчайших путей на взвешенных многогранных поверхностях", Журнал ACM, 52: 25–53, Дои:10.1145/1044731.1044733.
• Чан Йи-Джен; Митчелл, Джозеф С. Б. (1999), "Двухточечные евклидовы запросы кратчайшего пути на плоскости", Proc. 10-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 1999), стр. 215–224.
• Чхве, Джунсу; Селлен, Юрген; Яп, Чи-Кенг (1994), "Приближенный евклидов кратчайший путь в 3-м пространстве", Proc. 10-й симпозиум ACM по вычислительной геометрии, стр. 41–48, Дои:10.1145/177424.177501, ISBN  0-89791-648-4.
• Хершбергер, Джон; Сури, Субхаш (1999), «Оптимальный алгоритм для евклидовых кратчайших путей на плоскости», SIAM Журнал по вычислениям, 28 (6): 2215–2256, CiteSeerX  10.1.1.47.2037, Дои:10.1137 / S0097539795289604.
• Капур, С .; Махешвари, С. Н. (1988), "Эффективные алгоритмы решения евклидовых кратчайших путей и задач видимости с многоугольными препятствиями", Proc. 4-й симпозиум ACM по вычислительной геометрии, стр. 172–182, Дои:10.1145/73393.73411, ISBN  0-89791-270-5.
• Капур, С .; Maheshwari, S.N .; Митчелл, Джозеф С. Б. (1997), «Эффективный алгоритм для евклидовых кратчайших путей среди многоугольных препятствий на плоскости», Дискретная и вычислительная геометрия, 18 (4): 377–383, Дои:10.1007 / PL00009323.
• Лантье, Марк; Махешвари, Анил; Мешок, Йорг (2001), «Аппроксимация кратчайших на взвешенных многогранных поверхностях», Алгоритмика, стр. 527–562.
• Ли, Д. Т.; Препарата, Ф. (1984), «Евклидовы кратчайшие пути при наличии прямолинейных преград», Сети, 14 (3): 393–410, Дои:10.1002 / нетто.3230140304.
• Ли, Фаджи; Клетт, Рейнхард (2011), Евклидовы кратчайшие пути: точные или приблизительные алгоритмы, Springer-Verlag, Дои:10.1007/978-1-4471-2256-2, ISBN  978-1-4471-2255-5.
• Самуил, Давид; Туссен, Годфрид Т. (1990), «Вычисление внешнего геодезического диаметра простого многоугольника», Вычисление, 44 (1): 1–19, Дои:10.1007 / BF02247961.
• Туссен, Годфрид Т. (1989), «Вычисление геодезических свойств внутри простого многоугольника» (PDF), Revue d'Intelligence Artificielle, 3 (2): 9–42.

внешние ссылки

• Реализация алгоритма евклидова кратчайшего пути в KernelCAD программного обеспечения