В двух измерениях задача может быть решена за полиномиальное время в модели вычислений, позволяющей складывать и сравнивать действительные числа, несмотря на теоретические трудности, связанные с числовой точностью, необходимой для выполнения таких вычислений. Эти алгоритмы основаны на двух разных принципах: либо выполнение алгоритма кратчайшего пути, такого как алгоритм Дейкстры, на графе видимости, полученном из препятствий, либо (в подходе, называемом непрерывным методом Дейкстры ) распространение волнового фронта от одной из точек до встречи с другой.
Более высокие измерения
В трех (и более) измерениях задача в общем случае является NP-трудной [1], но существуют эффективные алгоритмы аппроксимации, которые работают за полиномиальное время, основанные на идее поиска подходящей выборки точек на краях препятствия и выполнения расчета графа видимости с использованием этих точек выборки.
Существует множество результатов по вычислению кратчайших путей, которые остаются на многогранной поверхности. Если даны две точки s и t, скажем, на поверхности выпуклого многогранника , задача состоит в вычислении кратчайшего пути, который никогда не покидает поверхность и соединяет s с t. Это обобщение задачи из 2-мерного пространства, но оно намного проще, чем 3-мерная задача.
Варианты
Существуют вариации этой задачи, где препятствия взвешены , т. е. можно пройти через препятствие, но это влечет за собой дополнительные затраты на прохождение препятствия. Стандартная задача — это особый случай, когда препятствия имеют бесконечный вес. Это называется в литературе задачей взвешенной области .
^
J. Canny и JH Reif, «Новые методы нижних границ для задач планирования движения робота», Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, стр. 49-60.
Ссылки
Александров, Людмил; Махешвари, Анил; Сак, Йорг (2005), «Определение приближенных кратчайших путей на взвешенных многогранных поверхностях», Журнал ACM , 52 : 25–53, doi : 10.1145/1044731.1044733, S2CID 697658.
Чан, И-Джен; Митчелл, Джозеф СБ (1999), «Запросы на кратчайший путь по двум точкам Евклида на плоскости», Труды 10-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA 1999), Ассоциация вычислительной техники, стр. 215–224, ISBN 9780898714340.
Капур, С.; Махешвари, С. Н.; Митчелл, Джозеф С. Б. (1997), «Эффективный алгоритм для евклидовых кратчайших путей среди многоугольных препятствий на плоскости», Дискретная и вычислительная геометрия , 18 (4): 377–383, doi : 10.1007/PL00009323.
Лантье, Марк; Махешвари, Анил; Сак, Йорг-Рюдигер (2001), «Аппроксимация кратчайших путей на взвешенных многогранных поверхностях», Algorithmica , стр. 527–562.
Ли, Д.Т .; Препарата, Ф.П. (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.
