Парадигма развития науки (стр. 14 )

Сети Петри будем использовать в основном как формальный аппарат при моделировании систем научных исследований, которым присущ параллелизм в реализации исследовательского процесса.

Рис. 19.10 Рис. 19.11

Если рассматри­вать систему научных исследований в целом, то возможны два принципиаль­но различных подхода к использованию сетей Петри. В первом система научных исследований моделируется сетью Петри, которая преобразуется по определенным правилам к некоторому «оптимальному» виду. Полученная сеть Петри преобразуется в проект системы научных исследований. Предполагается, что он также опти­мальный. Здесь сети Петри применяют непосредственно при проекти­ровании системы научных исследований. Этот подход, однако, имеет трудности, связанные с неодно­значностью обратного преобразования сети Петри в проект системы научных исследований,— что подвергает сомнению оптимальность получаемого проекта системы научных исследований. Во втором, более общепринятом, подходе сначала с помощью обыч­ных средств создается проект системы научных исследований и по нему строится модель в виде сети Петри. Затем исследуются свойства полученной сети и делаются выводы о свойствах и характеристиках проекта системы научных исследований. Если они неудовлетворительны, то полученные в результате исследования сети Петри данные используют для модификация проекта системы научных исследований. Модифицирован­ный проект системы научных исследований снова преобразуют в сеть Петри, и цикл повторяется. Этот процесс заканчивается, когда сеть Петри будет обладать необ­ходимыми свойствами.

Рассмотрим, какие свойства сети Петри как модели системы научных исследований могут интересовать исследователя. Одно из важнейших свойств — эффективность.

Позиция сети Петри называется эффективной, если число фишек в ней никогда не превышает 1.

Маркированная сеть Петри эффективна, если эффективны все ее позиции.

Это свойство очень важно при интерпретации позиций как простых условий: если в позиции есть фишка, то условие выполняется, если нет, то не выполняется. Если интерпретация фишек более сложная, например количество фишек показывает число информационных единиц, то может быть интересен вопрос, ограничено ли число фишек в данной позиции, и если да, то какова граница. Так приходим к свойству ограниченности. Позиция называется k-ограниченной, если число фишек в ней в любой дости­жимой маркировке не превышает целого k. Маркированная сеть Петри называется k-ограниченной, если ее позиции являются k - ограниченными. В сети Петри, приведенной на рис. 19.12, позиции р1, р2 явля­ются эффективными, позиция р3 –

2-ограниченная, вся сеть - 2-ограниченная.

Рис. 19.12

В случае когда фишки интерпретируются как некоторые ресурсы, они не должны ни создаваться, ни уничтожаться. Иначе говоря, в сети должен действовать закон сохранения. Маркированная сеть Петри на­зывается строго сохраняющей, если мощность маркировки (как комп­лекта позиций) постоянна. В общем случае фишка может интерпрети­роваться как некоторое число элементарных ресурсов, причем это число меняется от позиции к позиции. Введем понятие взвешивания позиций: вектор W = (w1, w2, ..., wп), где wi — вес позиции pi. Сеть Петри называется сохраняющей по отношению к вектору взвешивания W, если скалярное произведение вектора W и маркировки (рассматриваемой как вектор) постоянно; сеть Петри — сохраняющая, если она является сохраняющей по отношению к вектору взвешивания W, все элементы которого положительны.

Рассмотренные до сих пор свойства относятся как к последователь­ным, так и к параллельным системам научных исследований. Но при переходе от последова­тельных систем научных исследований к параллельным возникают принципиально новые трудности: возможность тупиковых ситуаций. Тупиком в сети Петри называется множество переходов, которые в некоторой достижимой маркировке μ' и в последующих достижимых из μ' маркировках не разрешены. Свойство возможности возникновения тупиков в системе научных исследований моделируется свойством активности в сетях Петри. Переход tj назы­вается активным, если он не входит ни в какой тупик. Переход называется пассивным, если он не разрешен ни в какой достижимой маркировке. При детальном исследовании активности сети Петри ис­пользуют также понятие уровней активности.

Переход tj обладает активностью:

- уровня 0, если он не может быть запущен (пассивный);

- уровня 1, если он потенциально запустим, т. е. существует достижимая маркировка, в которой он разрешен;

- уровня 2, если для любого целого k существует последовательность запусков переходов, в которой он присутствует не менее k раз;

- уровня 3, если существует бесконечная последовательность запусков, в которой он присутствует неограничен­но часто;

- уровня 4, если он потенциально запустим из всякой достижимой маркировки (т. е. акти­вен).

В сети Петри, изобра­женной на рис. 19.13, а, переход t3 активен, переходы t1, t2, t4, t6 имеют уровень активности 3; переход t6 пассивен. В сети Пет­ри, приведенной на рис. 19.13, б, переход t4 пассивен, переход t3 обладает активностью уровня 1, переход t2 — активностью уровня 2, a t1 — активностью уровня 3.

Одной из наиболее важных задач анализа сетей Петри является задача достижи­мости: достижима ли маркировка μ' из начальной маркиров­ки μ данной сети Петри? Важность этой задачи обусловлена тем, что маркировка служит интерпретацией состояния системы научных исследований. Решение задачи достижимости позволит определить, достижимо ли определенное состояние системы научных исследований, будь оно «хорошим» или «плохим» для системы научных исследований. Описанные свойства и соответствующие задачи анализа сетей Петри — наиболее общие, хотя и не охватывают все множество вопро­сов, которые могут возникнуть при анализе сетей Петри.

Pис. 19.13

Для решения задач анализа имеется два основных подхода.

Первый основан на построении дерева достижимости.

Дерево достижимости — это ориенти­рованное корневое дерево, вершинам которого соответствуют возмож­ные маркировки, дугам — переходы.

Корневой вершине соответствует начальная маркировка. Из каждой вершины исходят дуги, соответ­ствующие разрешенным переходам. Построение дерева осуществляется последовательно начиная с корневой вершины; на каждом шаге строится очередной ярус дерева. Например, дерево достижимости для сети Петри, изображенной на рис. 19.13, а, после трех шагов имеет вид, приведенный на рис. 19.14, а (маркировки представлены векторами).

Рис. 19.14

Очевидно, что если не использовать при построении дерева опреде­ленные соглашения, то активные (даже ограниченные) сети Петри будут иметь бесконечное дерево достижимости.

Назовем вершины (и соответствующие маркировки), построенные на очередном шаге алгоритма, граничными. Если в какой-либо гранич­ной маркировке нет разрешенных переходов, то будем называть такую маркировку терминальной. Если какая-либо граничная вершина имеет маркировку, уже существующую в дереве, то назовем ее дублирующей. Для терминальных и дублирующих вершин не будем строить исходя­щих из них дуг. Это обеспечивает конечность дерева достижимости для ограниченной сети Петри (например, рис. 19.13, а, 19.14, а). Для не­ограниченных сетей требуется как-то обозначить неограниченное число фишек в позиции. Пусть ω обозначает такое число, причем

ω+а=ω, ω — а=ω, а<ω, ω≤ω,

где а — произвольное целое положительное число.

Будем использовать при построении дерева достижимости сле­дующее правило.

Пусть граничная вершина μ не является терминальной или дублирующей. Для каждого разрешенного перехода tj в мар­кировке μ построим дугу, исходящую из μ. Дугу будем помечать переходом tj. Маркировка μ' новой вершины определяется следующим образом. Если μ(рi)=ω, то μ'(рi)=ω. Если на пути от корневой вер­шины к μ существует вершина μ" такая, что в результате запуска в μ перехода tj число фишек в каждой позиции не меньше чем в μ", а в позиции pi строго больше, то μ'(pi) = ω. В противном случае μ'(pi) - число фишек в позиции pi, получающееся после запуска tj из μ (рис. 19.14, б).

Теорема. Дерево достижимости любой сети Петри конечно.

Доказательство этого утверждения основано на свойствах ω и на правилах введения этого символа в маркировку граничных вершин.

Метод анализа систем научных исследований, основанный на дереве достижимости, позволяет определить свойства эффективности, ограниченности, сохранения, иссле­довать свойства активности и достижимости.

Сеть Петри ограниченна тогда и только тогда, когда символ ω отсутствует в дереве достижимости. Кроме того, положение символа ω показывает, какие позиции неограниченны. Если символ ω отсут­ствует в дереве, то число достижимых маркировок конечно и все вопросы анализа можно решить простым перебором. В частности, для нахождения границы маркировки данной позиции pi нужно найти наибольшее значение i-й компоненты среди всех вершин дерева. Если эта граница не превышает 1, то позиция эффективна.