Проблема достижимости

Дана СП и начальная маркировка (разметка) М:

Дана другая разметка . Достижима ли ,т.е. верно ли. что R (С, М)?

Чтобы R (С, М) должно быть:

= М + R =>

задача достижимости сводится к определению целочисленного неотрицательного вектора из уравнения: R = - М (61), однако это уравнение даст лишь необходимое условие достижимости:

из (57) M₁ = M₀ + (j) R, т.е. если есть начальная разметка M₀ и есть, имеющая матричную форму R, то следующая строится так: - строка у которой все нули, кроме 1 единицы, которая стоит на месте перехода, который сработает.

· если достижимо, то (61) имеет требуемое решение(формулировка не удачна, т.к. достижимо, то что искать?).

· (тоже самое) если уравнение (61) не имеет решения, то недостижима.

Однако, даже если уравнение имеет решение Z₀^m, все равно требуется дополнительное исследование, т.к. в векторе = (j₁) + (j₂) +…+ (j_k) не фиксирована последовательность срабатывания переходов (т.е. их можно менять местами). В простых случаях достаточно выполнить проверку полученного решения.

Пример 11: R=

Возьмем М=[0100] (=М´´´) желаемая =[1110]

- размрность определяемая числом переходов => из (59) и (61)

пусть 2 перехода (у нас)

[ ₁, ₂] = [1 1 1 0] - [0 1 0 0] = [1 0 1 0]

Если система неразрешима => end

если разрешима – продолжать исследование

Система 4-х уравнений с 2-мя неизвестными => несовместна

не может быть (-1) или (0.5) => система уравнений несовместна, недостижима.

Проверим на достижимость = [0 0 1 1]

[ ₁, ₂] = [0 0 1 1] - [0 1 0 0] = [0 -1 1 0]

=> ₂=1, ₁=0 => = (2)=[0 1], что означает: 1 переход – Ø, второй =1 => разрешен

В данном примере разметка называется тупиковой для данной СП (см. правило (а)). (т.е. из [0 0 1 1] мы некуда выйти не можем).

5. Проблема сохранения.

СП С с разметкой М называется сохраняющей относительно весового вектора W=(w₁,…,w_n) є Z_oⁿ (число координат по числу позиций у этого вектора),

если для любой достижимой разметки є R(c,m) выполняется соотношение

(62) (для всех последующих разметок весовая функция не должна изменяться)

Краткая запись:

MW= W (63)

т.к. =M+μR, то умножив скалярно все члены этого выражения на W получим:

W=MW+μRW, но по условию (63) => μRW= Ø. Т.к. это должно выполняться при любом μ, то проверка сохранности и отыскания сохраняющих весов полностью решается уравнением

RW= Ø (64)

(Если дана СП, то матрица R дана, система однородна, т.е. всегда имеет тривиальное решение, все веса ≠0, иначе нет смысла проверять условие)

В случае W=(1,1,1,…,1) (все веса единичны), СП называется строго сохраняющей.

Она характеризуется тем, что для любого перехода t_jчисло выходных и входных позиций одинаково:

|O(t_j)|=|I(t_j)| Vt_j

(вектор W имеет столько координат, сколько в сети позиций)

Пример 12:

(уравнений 2,известных 4 => имеет, как правило, множество решений).

(не строго сохраняющая, т.к. если представить все

W_i =1, то -1+1-1=0, что неверно).

Система имеет множество решений:

пусть W₃ = a, W₄ = b => W₂ = a + b => W₁ = b

W = (b, a + b, a, b)

если b = 0, a = 1, то W = (0110) (данная СП является сохраняющей)

b = 1, a = 0, то W = (1101)

В заключение выполняется проверка (веса с начальной маркировкой, каждая следующая маркировка вычисляется …).

С помощью матричного представления СП рассматриваются и другие проблемы (проблема живости (живая СП), проблемы тупиков и ограниченности, и т.д.).

Date: 2015-09-02; view: 314; Нарушение авторских прав