Евклидов кратчайший путь
Евклидова задача о кратчайшем пути — это задача вычислительной геометрии : для заданного набора многогранных препятствий в евклидовом пространстве и двух точек найти кратчайший путь между точками, который не пересекает ни одно из препятствий.
Два измерения [ править ]
В двух измерениях проблема может быть решена за полиномиальное время в модели вычислений, позволяющей складывать и сравнивать действительные числа, несмотря на теоретические трудности, связанные с числовой точностью, необходимой для выполнения таких вычислений. Эти алгоритмы основаны на двух разных принципах: либо выполнение алгоритма кратчайшего пути, такого как алгоритм Дейкстры, на графе видимости, полученном из препятствий, либо (в подходе, называемом непрерывным методом Дейкстры ) распространение волнового фронта от одной из точек до тех пор, пока он не встретит другой.
Высшие измерения [ править ]
В трех измерениях (и выше) задача NP-трудна : в общем случае [1] но существуют эффективные алгоритмы аппроксимации, которые работают за полиномиальное время и основаны на идее поиска подходящей выборки точек на краях препятствия и выполнения расчета графика видимости с использованием этих точек выборки.
Имеется множество результатов по вычислению кратчайших путей, остающихся на многогранной поверхности. Даны две точки s и t, скажем, на поверхностиВ выпуклом многограннике задача состоит в том, чтобы вычислить кратчайший путь, который никогда не покидает поверхность и соединяет s с t. Это обобщение двумерной проблемы, но оно намного проще, чем трехмерная задача.
Варианты [ править ]
Существуют варианты этой задачи, где препятствия имеют вес , т. е. можно пройти через препятствие, но при этом возникаетдополнительная плата за преодоление препятствия. Стандартная задача — это частный случай, когда препятствия имеют бесконечный вес. Это называется проблемой взвешенного региона в литературе .
См. также [ править ]
- Задача о кратчайшем пути в графе ребер и вершин
- Планирование пути под любым углом в пространстве сетки
Примечания [ править ]
- ^ Дж. Кэнни и Дж. Х. Рейф, « Новые методы нижней границы для задач планирования движения роботов », Proc. 28-е число. Симпозиумы IEEE. Найденный. Вычислить. наук, 1987, с.49-60.
Ссылки [ править ]
- Александров, Людмил; Махешвари, Анил; Сак, Йорг (2005), «Определение приблизительных кратчайших путей на взвешенных многогранных поверхностях», Журнал ACM , 52 : 25–53, doi : 10.1145/1044731.1044733 , S2CID 697658 .
- Чан, И-Джен; Митчелл, Джозеф С.Б. (1999), «Двухточечные евклидовы запросы о кратчайшем пути на плоскости», Proc. 10-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 1999) , Ассоциация вычислительной техники, стр. 215–224, ISBN 9780898714340 .
- Чхве, Джунсу; Селлен, Юрген; Яп, Чи-Кенг (1994), «Приблизительный евклидов кратчайший путь в трехмерном пространстве», Proc. 10-й симпозиум ACM по вычислительной геометрии , стр. 41–48, doi : 10.1145/177424.177501 , ISBN 0-89791-648-4 , S2CID 69747 .
- Хершбергер, Джон; Сури, Субхаш (1999), «Оптимальный алгоритм для евклидовых кратчайших путей на плоскости», SIAM Journal on Computing , 28 (6): 2215–2256, CiteSeerX 10.1.1.47.2037 , doi : 10.1137/S0097539795289604 .
- Капур, С.; Махешвари, С.Н. (1988), "Эффективные алгоритмы для решения евклидовых задач кратчайшего пути и видимости с многоугольными препятствиями", Proc. 4-й симпозиум ACM по вычислительной геометрии , стр. 172–182, doi : 10.1145/73393.73411 , ISBN 0-89791-270-5 , S2CID 9599057 .
- Капур, С.; Махешвари, С.Н.; Митчелл, Джозеф С.Б. (1997), «Эффективный алгоритм поиска кратчайших евклидовых путей среди многоугольных препятствий на плоскости», Discrete & Computational Geometry , 18 (4): 377–383, doi : 10.1007/PL00009323 .
- Лантье, Марк; Махешвари, Анил; Сак, Йорг-Рюдигер (2001), «Аппроксимация кратчайших путей на взвешенных многогранных поверхностях» , Algorithmica , стр. 527–562 .
- Ли, DT ; Препарата, Ф.П. (1984), «Евклидовы кратчайшие пути при наличии прямолинейных барьеров», Networks , 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 , S2CID 31450333 .
- Туссен, Годфрид Т. (1989), «Вычисление геодезических свойств внутри простого многоугольника» (PDF) , Revue d'Intelligence Artificielle , 3 (2): 9–42 .
Внешние ссылки [ править ]
- Реализация алгоритма евклидова кратчайшего пути в Digital Geometric Kernel программном обеспечении
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |
 | Эта посвященная геометрии, статья, незавершена . Вы можете помочь Википедии, расширив ее . |