Построение OE-маршрута китайского почтальона в плоском графе

Abstract

При автоматизированной подготовке процесса раскроя раскройный план можно представить в качестве плоского графа. Целью такого моделирования является определение кратчайшего пути режущего инструмента, при условии, что отрезанная от листа часть не требовала бы дополнительных разрезаний. В статье рассматривается задача построения пути китайского почтальона в плоском графе, являющемуся моделью раскройного плана. На этот путь наложено условие упорядоченного охватывания (т.е. цикл из пройденных ребер не охватывает еще не пройденных). Такой путь еще будем называть $OE$-путем. Данное ограничение и означает отсутствие дополнительных разрезаний для деталей. В статье рассматривается рекурсивный алгоритм построения таких цепей. Доказано, что алгоритм имеет полиномиальную сложность. Разработанное программное обеспечение позволяет решить задачу для произвольного плоского графа. Программа протестирована для различных типов плоских графов.