Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Проблема достижимостиДана СП и начальная маркировка (разметка) М: Дана другая разметка . Достижима ли ,т.е. верно ли. что R (С, М)? Чтобы R (С, М) должно быть: = М + R => задача достижимости сводится к определению целочисленного неотрицательного вектора из уравнения: R = - М (61), однако это уравнение даст лишь необходимое условие достижимости: из (57) M1 = M0 + (j) R, т.е. если есть начальная разметка M0 и есть, имеющая матричную форму R, то следующая строится так: - строка у которой все нули, кроме 1 единицы, которая стоит на месте перехода, который сработает. · если достижимо, то (61) имеет требуемое решение(формулировка не удачна, т.к. достижимо, то что искать?). · (тоже самое) если уравнение (61) не имеет решения, то недостижима.
Однако, даже если уравнение имеет решение Z0m, все равно требуется дополнительное исследование, т.к. в векторе = (j1) + (j2) +…+ (jk) не фиксирована последовательность срабатывания переходов (т.е. их можно менять местами). В простых случаях достаточно выполнить проверку полученного решения. Пример 11: R= Возьмем М=[0100] (=М´´´) желаемая =[1110] - размрность определяемая числом переходов => из (59) и (61)
пусть 2 перехода (у нас) [ 1, 2] = [1 1 1 0] - [0 1 0 0] = [1 0 1 0] Если система неразрешима => end если разрешима – продолжать исследование
Система 4-х уравнений с 2-мя неизвестными => несовместна не может быть (-1) или (0.5) => система уравнений несовместна, недостижима.
Проверим на достижимость = [0 0 1 1]
[ 1, 2] = [0 0 1 1] - [0 1 0 0] = [0 -1 1 0] => 2=1, 1=0 => = (2)=[0 1], что означает: 1 переход – Ø, второй =1 => разрешен
В данном примере разметка называется тупиковой для данной СП (см. правило (а)). (т.е. из [0 0 1 1] мы некуда выйти не можем). 5. Проблема сохранения.
СП С с разметкой М называется сохраняющей относительно весового вектора W=(w1,…,wn) є Zon (число координат по числу позиций у этого вектора), если для любой достижимой разметки є R(c,m) выполняется соотношение
(62) (для всех последующих разметок весовая функция не должна изменяться)
Краткая запись:
MW= W (63)
т.к. =M+μR, то умножив скалярно все члены этого выражения на W получим: W=MW+μRW, но по условию (63) => μRW= Ø. Т.к. это должно выполняться при любом μ, то проверка сохранности и отыскания сохраняющих весов полностью решается уравнением
RW= Ø (64) (Если дана СП, то матрица R дана, система однородна, т.е. всегда имеет тривиальное решение, все веса ≠0, иначе нет смысла проверять условие)
В случае W=(1,1,1,…,1) (все веса единичны), СП называется строго сохраняющей. Она характеризуется тем, что для любого перехода tjчисло выходных и входных позиций одинаково: |O(tj)|=|I(tj)| Vtj (вектор W имеет столько координат, сколько в сети позиций)
Пример 12: (уравнений 2,известных 4 => имеет, как правило, множество решений). (не строго сохраняющая, т.к. если представить все Wi =1, то -1+1-1=0, что неверно). Система имеет множество решений: пусть W3 = a, W4 = b => W2 = a + b => W1 = b W = (b, a + b, a, b) если b = 0, a = 1, то W = (0110) (данная СП является сохраняющей) b = 1, a = 0, то W = (1101) В заключение выполняется проверка (веса с начальной маркировкой, каждая следующая маркировка вычисляется …). С помощью матричного представления СП рассматриваются и другие проблемы (проблема живости (живая СП), проблемы тупиков и ограниченности, и т.д.).
|