Алгоритм двовимірного пакування прямокутників з метаструктурою

Loading...
Thumbnail Image
Date
2021
Authors
Мусіяка, Олександр
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Алгоритми двовимірного пакування прямокутників у зону, обмежену прямокутником мають широке використання для вирішення найрізноманітніших практичних задач. Мотивація для створення нового алгоритму полягає у тому, що прямокутники це зазвичай абстракція якогось фізичного об’єкта, що має певний набір інших властивостей окрім власних розмірів. Це породжує додаткові обмеження та метрики, що досить часто потрібно оптимізувати. Метрики та обмеження є функцією взаємного положення та орієнтації об’єктів, проте при щільному пакуванні їх неможливо довільно переміщувати один відносно одного. Досить часто обчислення метрики вимагає значних витрат обчислювальних ресурсів що робить недоцільним або навіть неможливим обчислення метрики на кожному кроці процесу знаходження рішення задачі. Іншим аспектом, що утруднює оптимізацію метрики на етапі пошуку рішення з задовільною ефективністю є складність бізнес логіки програмного забезпечення, що визначає саму функцію, яка підлягає оптимізації. Інтеграція бізнес логіки, що може досить часто змінюватися з алгоритмічною частиною програми призводить до зниження якості коду у плані легкості внесення змін, обмежує можливості ефективного покриття тестами та унеможливлює розділення бізнес логіки та алгоритму на окремі модулі, що утруднює повторне використання коду. Через зазначені вище труднощі на практиці досить часто використовують підхід до оптимізації метрик чи задоволення обмежень шляхом простого перебору альтернативних результатів роботи двовимірного пакування, та вибору найкращого варіанту, що задовольняє обмеженням. Недоліком такого підходу є той факт, що алгоритм двовимірного пакування на етапі знаходження рішення керується лише геометричними розмірами, та можливо простими метриками та обмеженнями, що можуть бути легко обчислені. Через це унаслідок певних особливостей роботи алгоритму чи статистичного розподілу вхідних даних різноманіття кінцевих результатів може бути обмеженим у плані взаємного розміщення об’єктів, що призводить до зниження якості знайденого рішення. Метою розробки даного алгоритму є реалізація можливості зміни взаємного розташування об’єктів без повторного вирішення вихідної задачі. Такі властивості знайденого рішення отримуються завдяки накладанню додаткових обмежень на властивості пакування та використанню спеціальної структури даних, що відображає певну множину рішень та може бути легко перетворена будь-яке з них.
Description
Keywords
алгоритм двовимірного пакування, метаструктура, магістерська робота
Citation