Проблема Евклидова кратчайшего пути - это проблема вычислительной геометрии : по заданному набору многогранных препятствий в евклидовом пространстве и двум точкам найти кратчайший путь между точками, который не пересекает ни одно из препятствий.
В двух измерениях проблема может быть решена за полиномиальное время в модели вычислений, допускающей сложение и сравнение действительных чисел, несмотря на теоретические трудности, связанные с числовой точностью, необходимой для выполнения таких вычислений. Эти алгоритмы основаны на двух разных принципах: либо выполнение алгоритма кратчайшего пути, такого как алгоритм Дейкстры, на графе видимости, полученного из препятствий, либо (в подходе, называемом непрерывным методом Дейкстры ) распространение волнового фронта от одной из точек до тех пор, пока он не встретит Другие.
В трех (и более) измерениях проблема NP-трудна в общем случае [1], но существуют эффективные алгоритмы аппроксимации, которые работают за полиномиальное время, основанные на идее поиска подходящей выборки точек на краях препятствия и выполнения расчет графика видимости с использованием этих точек выборки.
Есть много результатов по вычислению кратчайших путей, которые остаются на многогранной поверхности. Для двух точек s и t, скажем, на поверхности выпуклого многогранника , проблема состоит в том, чтобы вычислить кратчайший путь, который никогда не покидает поверхность и соединяет s с t. Это обобщение проблемы из 2-мерной задачи, но она намного проще, чем 3-мерная задача.
Кроме того, существуют варианты этой задачи, в которых препятствия взвешиваются , т. Е. Можно преодолеть препятствие, но преодоление препятствия требует дополнительных затрат. Стандартная задача - это частный случай, когда препятствия имеют бесконечный вес. В литературе это называется проблемой взвешенного региона .
См. Также [ править ]
Заметки [ править ]
- ↑ Дж. Кэнни и Дж. Х. Рейф, "[ https://www.researchgate.net/profile/John_Canny2/publication/4355151_New_lower_bound_techniques_for_robot_motion_planning_problems/links/5581e03708technae6cf036c16ffmobound-problems-plan-bot- pdf Новые методы оценки снизу для задач планирования движения роботов // Тр. 28-го Анну. IEEE Sympos. Нашел. Comput. Sci., 1987, с. 49-60.
Ссылки [ править ]
- Александров Людмил; Махешвари, Анил; Мешок, Йорг (2005), «Определение приблизительных путей кратчайших в весовых многогранных поверхностях», Журнал ACM , 52 : 25-53, DOI : 10,1145 / 1044731,1044733.
- Чан, Йи-Джен; Митчелл, Джозеф С.Б. (1999), "Двухточечные евклидовы запросы кратчайшего пути на плоскости", Proc. 10-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 1999) , стр. 215–224..
- Чхве, Джунсу; Селлен, Юрген; Яп, Чи-Кенг (1994), "Приближенный евклидов кратчайший путь в 3-м пространстве", Proc. 10 - ый ACM симпозиум по вычислительной геометрии ., Стр 41-48, DOI : 10,1145 / 177424,177501 , ISBN 0-89791-648-4.
- Хершбергер, Джон; Сури, Субхаш (1999), "Оптимальный алгоритм для евклидовых кратчайших путей на плоскости", SIAM Journal on Computing , 28 (6): 2215–2256, CiteSeerX 10.1.1.47.2037 , doi : 10.1137 / S0097539795289604.
- Капур, С .; Махешвари, С. Н. (1988), "Эффективные алгоритмы для решения задач кратчайшего евклидова пути и видимости с многоугольными препятствиями", Proc. Четвёртая ACM симпозиум по вычислительной геометрии . С. 172-182, DOI : 10,1145 / 73393,73411 , ISBN 0-89791-270-5.
- Капур, С .; Махешвари, С. Н.; Митчелл, Джозеф С. Б. (1997), «Эффективный алгоритм евклидовых кратчайших путей между полигональными препятствиями на плоскости», Дискретные и Вычислительная геометрия , 18 (4): 377-383, DOI : 10.1007 / PL00009323.
- Лантье, Марк; Махешвари, Анил; Сак, Йорг (2001), "Аппроксимация кратчайших путей на взвешенных многогранных поверхностях" , Algorithmica , стр. 527–562.
- Ли, Д.Т .; Препарата, Ф. (1984), "евклидовы кратчайшие пути в присутствии прямолинейных барьеров", сети , 14 (3): 393-410, DOI : 10.1002 / net.3230140304.
- Ли, Фаджи; Клетт, Рейнхард (2011), Евклидовы кратчайшие пути: точные или приблизительные алгоритмы , Springer-Verlag , DOI : 10.1007 / 978-1-4471-2256-2 , ISBN 978-1-4471-2255-5.
- Самуил, Давид; Туссен, Годфрид Т. (1990), «Вычисление внешнего геодезического диаметра простого многоугольника» , Computing , 44 (1): 1–19, doi : 10.1007 / BF02247961.
- Туссен, Годфрид Т. (1989), «Вычисление геодезических свойств внутри простого многоугольника» (PDF) , Revue d'Intelligence Artificielle , 3 (2): 9–42.
Внешние ссылки [ править ]
- Реализация алгоритма евклидова кратчайшего пути в программе KernelCAD
