Проблема с маршрутом сторожа

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

См. также

Задача художественной галереи , которая аналогичным образом предполагает просмотр всех точек заданной области, но с несколькими стационарными сторожами.

Ссылки

^ Перейти обратно: ^а ^б Чин, Вэй-Пан; Нтафос, Симеон (1988), «Оптимальные маршруты сторожа», Information Processing Letters , 28 (1): 39–44, doi : 10.1016/0020-0190(88)90141-X , MR 0947253 .
^ Карлссон, С.; Йонссон, Х.; Нильссон, Б.Дж. (1999), «Нахождение кратчайшего маршрута сторожа в простом многоугольнике», Discrete and Computational Geometry , 22 (3): 377–402, doi : 10.1007/PL00009467 , MR 1706598 .
^ Тан, Сюэхоу (2001), «Быстрое вычисление кратчайших маршрутов сторожа в простых многоугольниках», Information Processing Letters , 77 (1): 27–33, doi : 10.1016/S0020-0190(00)00146-0 , MR 1813864 .
^ Митчелл, Джозеф С.Б. (2013), «Приближение маршрутов сторожа», Труды двадцать четвертого ежегодного симпозиума ACM – SIAM по дискретным алгоритмам (SODA '13) , SIAM, стр. 844–855, doi : 10.1137/1.9781611973105.60 , ISBN 978-1-611972-51-1 .

Эта посвященная геометрии, статья, незавершена . Вы можете помочь Википедии, расширив ее .

[cn88-1] Перейти обратно: ^а ^б Чин, Вэй-Пан; Нтафос, Симеон (1988), «Оптимальные маршруты сторожа», Information Processing Letters , 28 (1): 39–44, doi : 10.1016/0020-0190(88)90141-X , MR 0947253 .

[2] Карлссон, С.; Йонссон, Х.; Нильссон, Б.Дж. (1999), «Нахождение кратчайшего маршрута сторожа в простом многоугольнике», Discrete and Computational Geometry , 22 (3): 377–402, doi : 10.1007/PL00009467 , MR 1706598 .

[3] Тан, Сюэхоу (2001), «Быстрое вычисление кратчайших маршрутов сторожа в простых многоугольниках», Information Processing Letters , 77 (1): 27–33, doi : 10.1016/S0020-0190(00)00146-0 , MR 1813864 .

[4] Митчелл, Джозеф С.Б. (2013), «Приближение маршрутов сторожа», Труды двадцать четвертого ежегодного симпозиума ACM – SIAM по дискретным алгоритмам (SODA '13) , SIAM, стр. 844–855, doi : 10.1137/1.9781611973105.60 , ISBN 978-1-611972-51-1 .

[1]

[2]

[3]

[4]