АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ ДЕКОМПОЗИЦИИ МНОГОСВЯЗНОГО ОРТОГОНАЛЬНОГО ПОЛИГОНА

Т. И. Григорчук, Ю. И. Валиахметова, Л. И. Васильева

Аннотация


Рассматривается задача декомпозиции много- связного ортогонального полигона на прямоугольные участки. Актуальность этой задачи обусловлена ее широким практическим толкованием, а также ее принадлежностью к классу NP-трудных. Ввиду того, что точные методы теряют свою эффективность при решении NP-трудных задач, поскольку временные затраты возрастают до недопустимых значений, для решения задач деком- позиции многосвязных ортогональных полигонов разрабатыва- ются различные эвристические алгоритмы. Задача декомпозиции многосвязного ортогонального полигона является подзадачей ряда задач, конечной целью которых является получение рацио- нальной карты геометрического покрытия или ортогонального раскроя. На первоначальном же этапе требуется «разбить» исход- ный ортогональный полигон на прямоугольные участки, которые впоследствии раскраиваются из прямоугольного ресурса, либо подлежат геометрическому покрытию ресурсом. От качества полученного на первом этапе решения задачи декомпозиции орто- гонального многосвязного полигона во многом зависит эффектив- ность решения задачи в целом. В настоящей статье описана содержательная постановка зада- чи, приводится ее математическая модель. Проведен обзор описан- ных в литературе и разработанных ранее авторами алгоритмов, позволяющих получать рациональные карты декомпозиции много- связных ортогональных полигонов на прямоугольные участки. Описанные в статье алгоритмы и методы декомпозиции основаны на различных эвристических идеях, каждый из них разработан для решения некоторой прикладной задачи и учитывает ряд техноло- гических ограничений, присущих именно той области, для которой был создан. Применение эвристических подходов позволяет полу- чать разнообразные алгоритмы, способные за приемлемое вычис- лительное время находить рациональные планы декомпозиции многосвязных ортогональных полигонов.

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


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

Полный текст:

PDF

Литература


Мухачева Э. А., Валиахметова Ю.И., Хасанова Э. И., и др. Проектирование размещения ортогональных объектов на полигонах с препятствиями. М.: Новые технологии.Информационные технологии. 2010. №10.С. 16-22.

Телицкий С. В., Валиахметова Ю. И., Хасанова Э. И. Гибридный алгоритм на основе последовательного уточнения оценок для задач максимального ортогонального покрытия. Уфа: РИЦ БашГУ. Вестник Башкирского университета. 2012. Т. 17. №1 (I). С. 421-425.

Валиахметова Ю. И .,Филиппова А. С., Ураков А. Р., Телицкий С. В. Критерии эффективности многокритериальной комплексной задачи геометрического покрытия и раскроя ортогонального ресурса. Информационные технологии и системы: труды второй международной научной конференции. Научное электронное издание. Челябинск: Изд-во Челябинского государственного университета, 2013. С. 26-28.

Мухачева Э. А., Валиахметова Ю. И., Хасанова Э. И., Телицкий С.В. Проектирование размещения ортогональных объектов на полигонах с препятствиями. М.: Новые технологии. Информационные технологии. 2010. № 10. С. 16-22.

Валиахметова Ю. И. Мультиметодная технология моделирования ортогональной упаковки. Монография. LAP LAMBERT Academic Publishing GmbH&Co. KG Dudweiler Landstr. 99,66123 Saarbrucken, Germany. ISBN: 978-3-8465-1420-7.

Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem. Management Science. 1997. 35. P. 64-68.

Филиппова А. С., Дяминова Э.И., Валиахметова Ю. И. Метод ограниченной декомпозиции для решения комплексной задачи геометрического покрытия и раскроя. М.: Новые технологии. Информационные технологии, препринт.

Хасанова Э. И. Проектирование размещения геометрических объектов на многосвязном ортогональном полигоне. Диссертационная работа на соискание ученой степени кандидата технических наук. Уфа: УГАТУ, 2011.

Валиахметова Ю. И., Григорчук Т. И., Васильева Л. И., Карамова Л. М. Технологии моделирования алгоритмов ортогонального раскроя-упаковки и геометрического покрытия: сравнение эффективности. Электронный научный журнал «Нефтегазовое дело», №5, 2015. с.424-445

Валиахметова Ю. И., Ермак А. С., Чернова А. А. Алгоритмы решения комплексной задачи геометрического покрытия и раскроя. Математическое моделирование процессов и систем:Материалы IV Всерос. науч.-практ. конф.,посвященной 75-летию физико-математического факультета, 16-19 декабря 2015г.,г. Стерлитамак: В 2-х частях. - Ч. 2.Стерлитамак: Стерлитамакский филиал БашГУ, 2015. с. 97-102.


Ссылки

  • На текущий момент ссылки отсутствуют.