Проблема с художественной галереей
-
Проблема охраны музея
- Задача охраны музея включает размещение охранников в вершинах многоугольника для наблюдения за всей территорией.
- Оптимальное количество охранников зависит от формы многоугольника и может быть вычислено с помощью алгоритмов аппроксимации.
-
Аппроксимация и сложность задачи
- Задача аппроксимации является NP-полной, но существуют эффективные алгоритмы для некоторых классов многоугольников.
- Для многоугольников с ограниченным числом вершин существуют алгоритмы с логарифмической аппроксимацией.
- Для неограниченных охранников сложность задачи возрастает.
-
Аппроксимация для простых многоугольников
- Для простых многоугольников существуют алгоритмы аппроксимации с постоянным коэффициентом.
- Для монотонных и слабо видимых с края многоугольников существуют полиномиальные алгоритмы аппроксимации.
- Для обычных простых многоугольников полностью разрешена гипотеза Гоша.
-
Трехмерная охрана
- В трехмерном пространстве установка охраны в вершинах не гарантирует полного наблюдения за объектом.
-
Дополнительные сведения
- В статье представлены ссылки на исходные данные и оптимальные решения для различных классов многоугольников.
Полный текст статьи: