|
Итерационные алгоритмы построения наилучших покрытий выпуклых многогранников наборами различных шаров
П. Д. Лебедевa, А. Л. Казаковbc a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск
c Институт машиноведения УрО РАН, г. Екатеринбург
Аннотация:
В теории управления и в различных прикладных областях математики важно выполнять аппроксимацию множеств сложной геометрии наборами унифицированных простых тел. Один из самых распространенных методов — покрытие шарами. В классическом варианте все шары равны, однако интерес представляет и более общая постановка, когда они могут быть различны. В настоящей статье изучается задача о построении покрытия компактного множества $M$ в трехмерном евклидовом пространстве набором из заданного числа шаров, радиусы которых равны произведению общего для всех параметра $r$ на индивидуальный положительный коэффициент. Критерием оптимальности считается минимизация $r$. Предложены эвристические алгоритмы построения искомых покрытий, основу которых составляют процедуры разбиения $M$ на зоны влияния точек и вычисление их чебышевских центров. Доказаны утверждения о свойствах указанных алгоритмов, выполнена их программная реализация. Проведено численное решение задач о покрытии куба различными наборами шаров двух типов. Намечены возможные направления для проведения дальнейших исследований.
Ключевые слова:
оптимизация, покрытие шарами, эвристический алгоритм, чебышевский центр, вычислительный эксперимент.
Поступила в редакцию: 11.01.2021 Исправленный вариант: 20.02.2021 Принята в печать: 25.02.2021
Образец цитирования:
П. Д. Лебедев, А. Л. Казаков, “Итерационные алгоритмы построения наилучших покрытий выпуклых многогранников наборами различных шаров”, Тр. ИММ УрО РАН, 27, № 1, 2021, 116–129
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1797 https://www.mathnet.ru/rus/timm/v27/i1/p116
|
Статистика просмотров: |
Страница аннотации: | 144 | PDF полного текста: | 48 | Список литературы: | 24 | Первая страница: | 3 |
|