Разработка алгоритма построения дерева достижимости

Основными методами анализа достижимости являются: метод построения дерева достижимости и матричный метод исследования достижимости.

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

В процессе указанного движения по дереву могут достигаться такие граничные вершины, которым соответствует маркировка, тупиковая по отношению ко всем переходам (при этой маркировке не существует разрешенных переходов). Данные вершины называются терминальными вершинами. Очевидно, терминальные вершины являются концевыми (висячими) вершинами дерева.

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

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

Общий алгоритм построения дерева достижимости (для ограниченных и неограниченных сетей Петри).

Шаг 0. Внести в список нерассмотренных (граничных) вершин вершину с начальной маркировкой , перейти к шагу 1.

Шаг 1. Извлечь из списка нерассмотренных вершин некоторую вершину с маркировкой и выполнить следующие операции:

а) если для не один переход не разрешен, объявить терминальной вершиной;

б) если среди рассмотренных вершин дерева находится такая вершина , для которой , объявить дублирующей вершиной;

в) если пункты "а" или "б" выполнены, перейти к шагу 3, в противном случае объявить внутренней вершиной и перейти к шагу 2.

Шаг 2. Определить для каждого разрешенного при перехода новую вершину с маркировкой , руководствуясь следующим правилом для каждой позиции :

а) если , то ;

б) если для внутренней вершины имеет место , то для тех позиций , для которых это неравенство строгое, принимается ;

в) во всех остальных случаях принимается .

Каждую такую вершину с маркировкой вносим в список нерассмотренных вершин и переходим к шагу 1.

Шаг 3. Если список нерассмотренных вершин не пуст, перейти к шагу 1; если он пуст, остановить алгоритм. В последнем случае каждая вершина оказывается внутренней, терминальной или дублирующей.

Дата добавления: 2014-11-29