Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Кокорев Д. С. 1
  • 1 Институт проблем передачи информации им. А.А. Харкевича РАН , 127051, г. Москва, Большой Каретный пер., д. 19 стр. 1

Алгоритм поиска оптимального варианта огранки драгоценного камня максимальной массы с заданными отклонениями от симметричности

2017. № 2 (40). С. 40–46 [содержание номера]

Д.С. Кокорев - аспирант лаборатории распределенных вычислительных систем, Институт проблем передачи информации им. А.А. Харкевича РАН     
Адрес: 127051, г. Москва, Большой Каретный пер., д. 19 стр. 1
E-mail: korvin-d@yandex.ru

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

Работа выполнена при поддержке Российского научного фонда (проект 16-11-10352). 

Библиографическое описание: Kokorev D.S. An algorithm for determining the optimal variant of a cut gem with maximal mass and specified symmetry deviations // Business Informatics. 2017. No. 2 (40). P. 40–46. DOI: 10.17323/1998-0663.2017.2.40.46
BiBTeX
RIS
 
 
Rambler's Top100 rss