ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 1, с. 88-97
== КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 512.5+519.1(075.8)
ПОСЛЕДОВАТЕЛЬНОСТИ ЦЕПЕЙ С УПОРЯДОЧЕННЫМ ОХВАТЫВАНИЕМ
© 2007 г. Т. А. Паншкова
Челябинск, Южно-Уральский государственный ун-т Поступила в редакцию 12.04.06 г.
С целью повышения эффективности использования станков с числовым программным управлением для раскроя листового материала предлагается формализовать задачу поиска траектории режущего инструмента в виде маршрута с упорядоченным охватыванием в соответствующем раскройному плану плоском графе О = (V, Е). Показано, что такой маршрут можно представить в виде последовательности не более п/2 + 1 цепей с упорядоченным охватыванием, где п число вершин нечетной степени в графе О. В работе построен алгоритм нахождения искомой последовательности цепей, имеющий вычислительную сложность 0(|Е|).
Введение. Многие задачи нахождения маршрутов, удовлетворяющих, определенным ограничениям, появились из конкретных практических ситуаций. В частности, для повышения эффективности работы графопостроителей траектория пера должна содержать как можно меньше холостых проходов. Если изображению соответствует плоский эйлеров граф О, то оно может быть нарисовано без холостых проходов. Если же граф О не является эйлеровым и содержит т = 2к вершин нечетной степени, то с помощью алгоритма Листинга-Люка [1, 2] возможно покрытие графа к цепями. При этом необходимые к - 1 холостых проходов минимальной длины можно найти с помощью решения задачи о назначении для соответствующего полного к-дольного графа.
В задачах раскроя листового материала на станках плазменной резки с числовым программным управлением (ЧПУ) появляется дополнительное ограничение: отрезанная от листа часть не должна требовать последующих разрезаний.
Из-за отсутствия подходящей формальной постановки задачи и соответствующих алгоритмов в сложившейся практике на раскройном плане детали размещают неплотно, чтобы обеспечить возможность вырезания детали за деталью. Это приводит к нерациональному использованию, как материала, так и оборудования.
Если моделью траектории резца считать цепь в плоском графе, то требование исключения необходимости разрезаний отделенной от листа части можно формализовать как условие отсутствия пересечения внутренних граней любой начальной части данной цепи с ребрами графа. В [3-5] поставлена и решена задача построения в плоском эйлеровом графе эйлеровых циклов, удовлетворяющих данному условию. Формально такие
циклы определены как циклы с у-упорядочен-ным охватыванием, где V - вершина, инцидентная внешней (бесконечной) грани графа. Сформулирована и доказана теорема существования цикла с упорядоченным охватыванием. Доказательство теоремы конструктивно и фактически сводится к описанию и доказательству результативности рекурсивного алгоритма построения искомого цикла. Анализ сложности алгоритма дает оценку 0(|Е|2), где Е - множество ребер графа. Показано [5], что построить маршрут с упорядоченным охватыванием в плоском неэйлеровом графе О можно за счет модификации алгоритма построения эйлерова цикла с упорядоченным охватыванием. Маршрут, построенный в плоском графе с помощью модифицированного алгоритма, является маршрутом с упорядоченным охватыванием. Вычислительная сложность алгоритма также не превосходит величины 0(|Е|2).
В данной работе рассматриваются вопросы, связанные с повышением эффективности алгоритмов построения в плоском графе маршрутов с упорядоченным охватыванием. Резервом для повышения эффективности является отказ от использования рекурсии и формирование алгоритма, не содержащего рекурсию в чистом виде. Вычислительная сложность построенного алгоритма не превосходит величины 0(|Е|). На его основе разработан алгоритм построения в плоском графе, не содержащем висячих вершин, такой последовательности цепей, покрывающих все его ребра и имеющих упорядоченное охватывание, что выполнено условие отсутствия пересечения внутренних граней любой начальной части последовательности цепей с ребрами графа. Вычислительная сложность алгоритма не более 0(|Е|).
1. Формальная постановка задачи. Если И3 -топологическое представление графа И в плоско-
сти S, то в соответствии с [6] компоненты связности множества $\И$ называются гранями плоского графа И3, а множество граничных точек грани - ее краем; теоретико-множественное объединение краев всех граней равно И3, поэтому каждые ребро и вершина принадлежат краю хотя бы одной грани, и ясно также, что никакое ребро (в отличие от вершины) не может принадлежать краям более чем двух граней. Ровно одна из граней плоского графа И3 является внешней (бесконечной).
Таким образом, с формальной точки зрения сформулированное во Введении ограничение требует отсутствия пересечения внутренних граней любой начальной части маршрута заданного плоского графа О с ребрами его оставшейся части [7].
Поскольку станки с ЧПУ имеют программы вырезания множества примитивов, из которых состоят кривые, представляющие контуры деталей, то нас будет интересовать не конкретный вид ребер графа О, а лишь порядок их обхода. С точностью до гомеоморфизма представление любого плоского графа О = (V, Е) возможно с помощью задания для каждого ребра е е Е следующих функций [2]: v1(e), v2(e) - вершины, инцидентные ребру е;/(е),/2(е) - грани, находящиеся слева при движении по ребру е от вершины ^(е) к вершине V _к(е), к = 1, 2; 11(е), 12(е) - ребра, принадлежащие граням /(е), к = 1, 2, инцидентные вершинам ^(е).
Иллюстрация введенных функций дана на рис. 1. Их построение не составляет проблем. Фактически они определяются и используются еще на этапе проектирования раскройного плана, т.е. графа О. Пространственная сложность такого представления будет 0(|Е|).
Пусть на плоскости $ задан плоский граф О = = (V, Е), а/ - внешняя (бесконечная) грань графа О. Для любого подмножества /с О обозначим через 1п1;(/) подмножество являющееся объединением всех связных компонент множества $/, не содержащих внешней грани /0.
Определение. Будем говорить, что цикл С = ^е1 ^е2... в эйлеровом графе О имеет упорядоченное охватывание, если для любой его начальной части С = ^1е1^2е2.еь I < |Е| выполнено условие 1п1;(С) п Е = 0.
Например, для плоского эйлерова графа, приведенного на рис. 2, цикл ^е1 ^3е3^2е2у1е4^3е5^2е6у1 удовлетворяет условию упорядоченного охваты-вания, а цикл ^1е4^3е5^2е6^1е1^3е3^2е2^1 - не отве-чаяет, так как М^е^е^е^) з {еь е2, е3}.
В терминах задачи раскроя используемые определения интерпретируются следующим образом: $ - раскраиваемый лист, О - раскройный план, С - траектория движения режущего инструмента, ЫС) - отделенная от листа часть при прохождении режущим инструментом части траектории, тогда условие упорядоченности охваты-вания означает, что отрезанная от листа часть не
Рис. 2. Пример эйлерова графа.
требует дополнительных разрезаний. Существование эйлеровых циклов с упорядоченным охва-тыванием в плоских эйлеровых графах доказано в [3, 7]. Рекурсивные алгоритмы построения таких циклов представлены в [4, 7].
Проблеме построения маршрута с упорядоченным охватыванием в плоском графе произвольного вида посвящена работа [5], в которой разработан алгоритм построения таких маршрутов, имеющий вычислительную сложность не более 0(|Е|2).
Разработка эффективных алгоритмов построения циклов с упорядоченным охватыванием в плоских эйлеровых графах исследуется в [3]. Однако, предложенный в ней алгоритм строит циклы с квазиупорядоченным охватыванием. Результаты о возможности покрытия графа последовательностью цепей с упорядоченным охватыванием анонсировались в докладах [8, 9].
2. Эффективный алгоритм построения эйлерова цикла с упорядоченным охватыванием.
Текст алгоритма А для построения цикла с упорядоченным охватыванием в плоском графе О, представленном списком ребер с заданными на нем функциями ^(е), 1к(е),/(е), к = 1, 2, приведен на рис. 3.
Выполнение алгоритма состоит из трех процедур: "Инициализация" (рис. 4); "Упорядочение" (рис. 5); "Формирование" (рис. 6).
АЛГОРИТМ А Функция "Инициализация"
Входные данные: G = (V, E) - плоский эйлеров граф. (V v е V) do Stack(v) = 0 od;
Выходные данные: firste E, laste E, mark1(e): E ^ E (V e e E) do
Инициализация(); mark1(e) = mark2(e) = prev1(e) = prev2(e) = 0;
Упорядочение(); od
Формирование(); first = last = e0; v0 = v = v1(e0); ne = l1(e0); /* k = 1;
end. kmark(e0) = 1*/
end.
Рис. 3. Эффективный алгоритм построения цикла с
упорядоченным охватыванием. Рис. 4. Процедура "Инициализация".
Функция "Упорядочение" while (first Ф го) do while (mark1(ne)) = ^ and last Ф ne) do M1: /* kmark(ne) = k */ mark1(last) = ne; if (v2(ne) Ф v) REPLACE (ne); v = vx(ne); last = ne; ne = l1(ne);
od
e = first; first = mark1(first); v = v2(e); ne = l2(e); M2: /* k = kmark(e) + 1 */ mark1(e) = Stack(v1(e)); mark2(e) = Stack(v) if (mark1(e) Ф 0) do
if (v1(e) = v1(mark1(e))) prev1(mark1(e)) = e; else prev2(mark1(e)) = e;
od
if (mark2(e) Ф 0) do /* Помещение ребра в стеки вершин v1(e) и v2(e) */ if (v = v1(mark2(e))) prev1(mark2(e)) = e; else prev2(mark2(e)) = e;
od
Stack(v) = e; Stack(v1(e)) = e;
od end.
Рис. 5. Процедура "Упорядочение".
Функция "Формирование"
v = v0; e = Stack(v); first = last = e;
do
if (v1(e) = v) REPLACE (e);
Stack(v) = mark2(e); /* Извлечение ребра из стека вершины v2(e) */
if (v = v1(mark2(e))) prev1(mark2(e)) = 0; else prev2(mark2(e)) = 0;
v = v1(e) if (prev1(e) Ф 0)
if (e = mark1(prev1(e))) mark1(prev1(e)) = mark1(e) else mark2(prev1(e)) = mark1(e); else do
Stack(v) = mark1(e);
if (v = v1(mark1(e))) prev1(mark1(e)) = 0; else prev2(mark1(e)) = 0; e = Stack(v); /* Извлечение ребра из стека вершины v1(e) */ M3: mark1(last) = е; last = е; od while (last Ф 0); end.
Рис. 6. Процедура "Формирование".
Процедуры "Инициализация" и "Упорядочение" используют функцию REPLACE(), которая переопределяет введенные функции vk(e), lk(e), fk(e), k = 1, 2, таким образом, чтобы движение по ребру e е E в построенном алгоритмом цикле происходило от вершины v2(e), к вершине vx(e). Легко заметить, что данное переопределение, если оно необходимо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.