Генерація випадкових карт прямокутного розкрою

  • I. V. Kozin
  • S. E. Batovskiy
Ключові слова: карта розкрою, безвідходний прямокутний розкрій, алгоритми генерації прямокутного розкрою, гільйотинний розкрій

Анотація

Досліджується проблема генерації безвідходних карт прямокутного розкрою. Для різних видів карт досліджуються відповідні моделі і алгоритми генерації. Запропоновано генератори для безвідходних карт розкрою на прямокутники обмежених розмірів, генератори карт гільйотинного розкрою. Відомо, що велика кількість прикладних оптимізаційних задач на сьогоднішній день не можуть бути точно розв’язані, оскільки їх обчислювальна складність відноситься до класу NP-важких. У багатьох випадках для пошуку наближених рішень використовуються метаеври-стики різних типів, але при виборі тієї чи іншої метаевристики залишається відк-ритим питання про якість обраного методу. Пропонується кілька можливих варіа-нтів розв'язання проблеми, одним з яких є перевірка метаевристичних алгоритмів на прикладах з відомих тестових бібліотек з відомими рекордами. Іншим підходом до вирішення проблеми оцінки якості алгоритмів, що розглядається, є порівняння «нового» алгоритму з іншими алгоритмами, робота яких вже детально вивчена. По-будова генератора випадкових завдань з відомим оптимальним рішенням, може ви-рішити проблему отримання «середніх» оцінок точності використовуваного алго-ритму в порівнянні з іншими методами. У роботі розглядається побудова генерато-рів випадкових повних карт прямокутного розкрою з урахуванням певних обме-жень на розміри складових їх елементарних прямокутників. Існування наборів та-ких карт формує базу тестових завдань для перевірки якості наближених алгорит-мів пошуку оптимального розкрою. Прямокутний розкрій, який розглядається в роботі, також є основою для побудови розкроїв з використанням більш складних фігур. В якості найпростішого методу генерації випадкових прямокутних карт розкрою наводиться метод, який використовує гільйотинний розкрій. Також, наводиться більш складний алгоритм генерації випадкового прямокутного розкрою, робота якого полягає в генерації випадкової точкової сітки і видалення деяких випадкових точок з цієї сітки. Велика увага приділяється саме реалізаціям наведених методів, оскільки основною метою статті є застосування генераторів на практиці. Всі наве-дені алгоритми вже використовуються в програмній системі тестування еволюцій-но-фрагментарних алгоритмів для різних класів оптимізаційних задач на графах

Переглядів анотації: 21
Завантажень PDF: 31
Опубліковано
2018-05-31