Аннотация:
Статья посвящена проблеме декомпозиции сложных систем, представленных в виде сетей Петри, с целью оптимизации процедуры синтеза новых параллельных систем. Предлагается улучшенный подход, объединяющий алгоритм Джонсона и метод поиска в глубину. Алгоритм Джонсона применяется для эффективного поиска элементарных циклов, что позволяет преодолеть ограничения традиционного матричного метода, характеризующегося высокой вычислительной и пространственной сложностью, а также невозможностью гарантировать выделение элементарных циклов заданной длины. Для нахождения линейных фрагментов ацикличных сетей Петри используется адаптированный алгоритм поиска в глубину. Проведено аналитическое и экспериментальное сравнение предложенных алгоритмов с известными аналогами на полных и разряженных сетях Петри. Экспериментальные данные показывают значительное преимущество алгоритма Джонсона при работе с разряженными структурами сетей Петри, выражающееся в увеличении скорости выполнения и в полноте обнаружения элементарных циклов. Предлагаемый подход демонстрирует существенное сокращение временных затрат на этапе декомпозиции и способствует созданию условий (базы знаний), ограничивающих множество синтезируемых структур и упрощающих последующие этапы проектирования параллельных систем. Полученные результаты подтверждают практическую эффективность и применимость предложенных методов декомпозиции сетей Петри в задачах синтеза структур сложных систем.
