Задача об охране картинной галереи на клетчатой плоскости
Abstract
В данной работе рассматривается задача об охране картинной галереи в случае, когда план галереи представляет собой ортогональный многоугольник с вершинами в узлах целочисленной решетки. Проводится точная оценка на число охранников, а также разрабатывается жадный алгоритм расстановки охранников. Для реализации алгоритма выбран язык программирования Python.
References
2. Chvatal V. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. – 1975. – Vol. 18. – P. 39-41.
3. Fisk S. A short proof of Chvatal's watchman theorem // Journal of Combinatorial Theory, Series B. – 1978. – Vol. 24, no. 3. – P. 374.
4. Берг М., Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения. - М. : ДМК Пресс, 2017. - 438 с.
1. Авторы сохраняют за собой права на авторство своей работы и предоставляют журналу право первой публикации этой работы с правом после публикации распространять работу на условиях лицензии Creative Commons Attribution License, которая позволяет другим лицам свободно распространять опубликованную работу с обязательной ссылокой на авторов оригинальной работы и оригинальную публикацию в этом журнале.
2. Авторы сохраняют право заключать отдельные договора на неэксклюзивное распространение работы в том виде, в котором она была опубликована этим журналом (например, размещать работу в электронном архиве учреждения или публиковать в составе монографии), с условием сохраниения ссылки на оригинальную публикацию в этом журнале. с. Политика журнала разрешает и поощряет размещение авторами в сети Интернет (например в институтском хранилище или на персональном сайте) рукописи работы как до ее подачи в редакцию, так и во время ее редакционной обработки, так как это способствует продуктивной научной дискуссии и положительно сказывается на оперативности и динамике цитирования статьи
