|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Программирование
Constructing of $OE$-postman path for a planar graph
[Построение $OE$-маршрута китайского почтальона в плоском графе]
T. A. Panyukova South Ural State University, Chelyabinsk, Russian Federation
Аннотация:
При автоматизированной подготовке процесса раскроя раскройный план можно представить в качестве плоского графа. Целью такого моделирования является определение кратчайшего пути режущего инструмента, при условии, что отрезанная от листа часть не требовала бы дополнительных разрезаний. В статье рассматривается задача построения пути китайского почтальона в плоском графе, являющемуся моделью раскройного плана. На этот путь наложено условие упорядоченного охватывания (т.е. цикл из пройденных ребер не охватывает еще не пройденных). Такой путь еще будем называть $OE$-путем. Данное ограничение и означает отсутствие дополнительных разрезаний для деталей. В статье рассматривается рекурсивный алгоритм построения таких цепей. Доказано, что алгоритм имеет полиномиальную сложность. Разработанное программное обеспечение позволяет решить задачу для произвольного плоского графа. Программа протестирована для различных типов плоских графов.
Ключевые слова:
плоский граф; задача китайского почтальона; маршрут; упорядоченное охватывание; алгоритм; программная реализация.
Поступила в редакцию: 15.08.2014
Образец цитирования:
T. A. Panyukova, “Constructing of $OE$-postman path for a planar graph”, Вестн. ЮУрГУ. Сер. Матем. моделирование и программирование, 7:4 (2014), 90–101
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyuru240 https://www.mathnet.ru/rus/vyuru/v7/i4/p90
|
Статистика просмотров: |
Страница аннотации: | 131 | PDF полного текста: | 60 | Список литературы: | 40 |
|