Поиск по сайту

АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНЫХ ПОКРЫТИЙ РАВНЫМИ КРУГАМИ НЕВЫПУКЛЫХ МНОГОУГОЛЬНИКОВ С НЕЕВКЛИДОВОЙ МЕТРИКОЙ

Казаков Александр Леонидович , Лемперт Анна Ананьевна , Нгуен Гуй Лием

2016 / Номер 5(112) 2016 [ ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ ]

Рассматривается задача о покрытии ограниченного множества на плоскости заданным количеством кругов равного радиуса. Разработан новый численный алгоритм, основанный на фундаментальных физических принципах Ферма и Гюйгенса, который позволяет решать рассмотренную задачу в случаях, когда покрываемое множество является невыпуклым и/или метрика, задающая расстояние между точками, не является евклидовой. Выполнена программная реализация алгоритма и проведен вычислительный эксперимент, который показал работоспособность предложенного подхода в общем случае и его высокую эффективность для решения задачи о покрытии выпуклого множества в евклидовой метрике при большом количестве (и малом радиусе) покрывающих кругов.

Ключевые слова:

покрытие равными кругами,неевклидова метрика,оптико-геометрический подход,оптимизация,численный метод,вычислительный эксперимент,coverage with equal circles,non-Euclidean metric,optical geometric approach,optimization,numerical method,computational experiment

Библиографический список:

Алдыноол Т.А., Ерзин А.И., Залюбовский В.В. Покрытие плоской области случайно распределенными сенсорами // Вестник Новосибирского государственного университета. Серия: Математика, механика, информатика. 2010. Т. 10. № 4. C. 7-25.
Астраков С.Н., Ерзин А.И. Сенсорные сети и покрытие полосы эллипсами // Вычислительные технологии. 2013. Т. 18. № 2. C. 3-11.
Астраков С.Н., Ерзин А.И., Залюбовский В.В. Сенсорные сети и покрытие плоскости кругами // Дискретный анализ и исследование операций. 2009. Т. 16. № 3. C. 3-19.
Брусов В.С., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журнал вычислительной математики и математической физики. 1971. Т. 11. № 2. С. 304-313.
Брусов В.С., Пиявский С.А. Двигательная установка малой тяги, универсальная для двумерного диапазона // Известия Академии наук СССР. Космические исследования. 1970. № 4. С. 542-546.
Брусов В.С., Пиявский С.А. Применение теории оптимальных покрытий к задачам выбора мощности двигателя малой тяги // Известия Академии наук СССР. Механика твердого тела. 1969. № 2. С. 10-14.
Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычислительной математики и математической физики. 2010. Т. 50. № 4. С. 757-769.
Казаков А.Л., Журавская М.А., Лемперт А.А. Вопросы сегментации логистических платформ в условиях становления региональной логистики // Транспорт Урала. 2010. № 4. С. 17-20.
Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. С. 50-57.
Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. С. 87-100.
Казаков А.Л., Лемперт А.А., Нгуен Г.Л. Оптимизация системы коммуникаций с учетом региональных особенностей: математическая модель и численный метод // Вестник ИрГТУ. 2014. № 12 (95). С. 17-22.
Кротов В.Ф., Пиявский С.А. Достаточные условия оптимальности в задачах об оптимальных покрытиях // Известия Академии наук СССР. Техническая кибернетика. 1968. № 2. С. 10-17.
Лебедев П.Д., Бухаров Д.С. Аппроксимация многоугольников наилучшими наборами кругов // Известия Иркутского государственного университета. Серия: Математика. 2013. № 3. С. 72-87.
Лебедев П.Д., Успенский А.А., Ушаков В.Н. Алгоритмы наилучшей аппроксимации плоских множеств объединениями кругов // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2013. Вып. 4. С. 88-99.
Можаев Г.В. Задача о непрерывном обзоре поверхности Земли и кинематически правильные спутниковые системы // Известия Академии наук СССР. Космические исследования. 1972. Т.10. № 6. С. 833-840.
Москаленский Е.Д. О нахождении точных решений двумерного уравнения эйконала для случая, когда фронт волны, распространяющейся в среде, является окружностью // Сибирский журнал вычислительной математики. 2014. Т. 17. № 4. С. 363-372.
Мухачева А.С. Простые эвристики для решения двумерной задачи максимального покрытия // Принятие решений в условиях неопределенности: межвузовский научный сборник. Вып. 2. Ч. 1. Уфа: Изд-во УГАТУ, 2005. С. 24-32.
О методе решения задачи оптимальной прокладки высокоскоростных железнодорожных магистралей с учетом региональных особенностей /А.Л. Казаков [и др.] // Транспорт: наука, техника, управление. 2012. № 2. С. 41-44.
Пиявский С.А. Об оптимизации сетей // Известия Академии наук СССР. Техническая кибернетика. 1968. № 1. С. 68-80.
Тахонов И.И. О некоторых задачах покрытия плоскости кругами // Дискретный анализ и исследование операций. 2014. Т. 21. № 1. C. 84-102.
Телицкий С.В., Филиппова А.С. Комплексный подход к решению задачи покрытия области заготовками неопределенных размеров // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2012. № 2 (145). С. 61-67.
Филиппова А.С., Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками // Информационные технологии. 2008. № 9 (145). С. 60-65.
Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы). Saarbrücken: LAP LAMBERT Academic Publishing, 2011. 124 с.
Balazs B., Endre P., Balazs L.L. Optimal circle covering problems and their applications // CEJOR. 2015. Vol. 23. C. 815-832.
Drezner Z. Facility location: A survey of applications and methods. NY: Springer-Verl. 1995. 571 p.
Heppes A. Covering a planar domain with sets of small diameter // Periodica Mathematica Hungarica. 2006. Vol. 53. P. 157-168.
Jandl H., Wieder К. A continuous set covering problem as a quasidifferentiale optimization problem // Optimization: A Journal of Mathematical Programming and Operations Research. 1988. Vol. 19. No. 6. P. 781-802.
Melissen J.B.M., Schuur P.C. Covering a rectangle with six and seven circles // Discrete Applied Mathematics. 2000. Vol. 99. P. 149-156.
Nurmela K.J. Ostergard P.R.J. Covering a square with up to 30 equal circles. Res. rept A62. Lab. Technol. Helsinki Univ. 2000. Р. 20.
Nurmela K.J. Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles // Experimental Mathematics. 2000. Vol. 9. Issue. 2. P. 241-250.
Stoyan Y.G., Patsuk V.M. Covering a compact polygonal set by identical circles // Computational Optimization and Applications. 2010. Vol. 46. C. 75-92.