Проблема маршрута сторожа - Watchman route problem
В Проблема сторожа является оптимизация проблема в вычислительная геометрия где цель состоит в том, чтобы вычислить кратчайший маршрут, который должен пройти сторож, чтобы охранять всю территорию с препятствиями, имея только карту местности. Задача состоит в том, чтобы убедиться, что сторож заглядывает за каждый угол, и определить наилучший порядок посещения углов. Проблема может быть решена в полиномиальное время когда охраняемая территория простой многоугольник.[1][2][3] Проблема в NP-жесткий для полигонов с отверстиями,[1] но может быть аппроксимирован за полиномиальное время решением, длина которого находится в пределах полилогарифмического коэффициента оптимальности.[4]
Смотрите также
- Проблема с картинной галереей, который аналогично включает просмотр всех точек данной области, но с несколькими стационарными сторожами
Рекомендации
- ^ а б Чин, Вэй-Пан; Нтафос, Симеон (1988), "Оптимальные маршруты сторожа", Письма об обработке информации, 28 (1): 39–44, Дои:10.1016 / 0020-0190 (88) 90141-X, МИСТЕР 0947253.
- ^ Carlsson, S .; Jonsson, H .; Нильссон, Б. Дж. (1999), "Поиск кратчайшего маршрута сторожа в простом многоугольнике", Дискретная и вычислительная геометрия, 22 (3): 377–402, Дои:10.1007 / PL00009467, МИСТЕР 1706598.
- ^ Тан, Сюэхо (2001), "Быстрое вычисление кратчайших маршрутов сторожа в простых многоугольниках", Письма об обработке информации, 77 (1): 27–33, Дои:10.1016 / S0020-0190 (00) 00146-0, МИСТЕР 1813864.
- ^ Митчелл, Джозеф С. Б. (2013), «Примерные сторожевые маршруты», Материалы двадцать четвертого ежегодного симпозиума ACM – SIAM по дискретным алгоритмам (SODA '13), SIAM, стр. 844–855, Дои:10.1137/1.9781611973105.60, ISBN 978-1-611972-51-1.
 | Этот связанные с геометрией статья - это заглушка. Вы можете помочь Википедии расширяя это. |