На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

В Институте проблем передачи информации им. А.А. Харкевича РАН исследовалась задача нахождения многогранников заданной формы внутри других многогранников.

24.05.2016

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

Частным случаем этой проблемы является задача нахождения в выпуклом многограннике произвольной формы объекта заданной формы с наибольшим объемом. Она имеет широкую область применения: компьютерное моделирование трехмерных объектов, программные тренажеры, компьютерные игры, приложения, решающие задачи упаковки и раскроя, программы, отвечающие за передвижение роботов, ювелирная промышленность, обработка дорогостоящих материалов. Описанный в статье алгоритм используется в коммерческих целях для нахождения оптимального плана бриллианта на разных стадиях огранки драгоценного камня.

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

Для реализации алгоритма были использованы сторонние программные ресурсы, организованные с помощью RESTful-веб-сервисов. Такой подход позволяет не тратить время на разработку сложных математических алгоритмов, а использовать уже готовые решения и тем самым сконцентрироваться на поставленной задаче.

Подробное описание дается в статье «Оптимизационный алгоритм поиска вписанного многогранника максимального объема», автор Кокорев Д.С. (Институт проблем передачи информации им. А.А. Харкевича РАН, Москва).