Конструирование алгоритмов геометрического размещения на основе матричной и уровне-вой технологий

Аннотация

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