第3章Petri网.ppt

* （2） 可达树、覆盖树 对于无界Petri网，由于可达标识将无限制地增长，故可达树结构的结点也将无限制地增长。为了使所得到的树保持有限，可引入一个被认为是“无限”的特殊符号“?”。该?具有如下特性：?k ? Z（整数集）：? k，?±k = ? 且??? 。 对于结点M，如果从M0到M的路径上存在结点M? 满足：?p?P，M(p)?M? (p)，且M?M? ，即，M′是可覆盖的，此时，可对M中满足M(p)M? (p) 的p用?重置M(p)，这样得到的树就称为Petri网的覆盖树。 （2） 可达树、覆盖树 覆盖树的构造算法如下： step 1：将初始标识M0作为树根，并标记为new； step 2：若不存在标记为new的标识，停机； step 3：选择一个标记为new的标识M，重复以下各步： ① 若从根节点M0到M的路径上有与M相同的标识，将M标记为old，并转step 2； ② 若标识M下没有迁移可以引发，则将M记为dead-end，并转step 2； ③ 若标识M下存在可以引发的迁移，则对每个使能迁移t进行如下各步： （a）计算在t引发后M的后继标识M? （注：若M(p)=?，则M?(p)=?）； （b）若从根节点M0到M? 的路径中存在结点M?? 满足：?p?P，M? (p)? M?? (p)，且M? ≠M??，则对M? 中的每个满足M? (p) M??（p）的p，用?重置M? (p)； （c） 将M? 作为树的一个标志为new节点，并从M到M? 画用t标注的弧； step 4：将M标记为old，并转step 2。 * （2） 可达树、覆盖树 利用覆盖树，可以分析Petri网PN =（N，M0）的如下性质： ① 当且仅当覆盖树中不出现含有?的标识时，PN有界，且因此R(M0)是有限的； ② 当且仅当覆盖树中每个标识的元素都为0或1时，PN是安全的； ③ 当且仅当迁移t?T不出现在覆盖树中时，t为死的，即存在死锁。 由于?的存在，于覆盖树一般不能用来分析可达性和活性。 p1 t4 t2 p3 p2 t3 （1,0,0） （0,0,1） (dead-end) （1,?,0） （0,?,1） （1,?,0） (old) （0,?,1） (old) t2 t4 t4 t2 t3 t2 * （3） 状态方程、不变量 Petri网的网结构可以用一个矩阵来表示，对于PN=（N，M0），令P={p1，p2，p3，…，pm}，T={t1，t2，t3，…，tn}。 关联矩阵：Petri网PN=（N，M0）的关联矩阵为一个以P?T作序标的矩阵C：P×T→Z（整数集合），其矩阵元素C(pi，tj)= W(tj，pi)? W(pi，tj)。也可以写作： [Cij] m×n =[Cij+] m×n? [Cij-] m×n 或者 C = C+?C? 其中， Cij+ = W（tj，pi）是从迁移tj到它的输出位置pi的弧的权， Cij- = W（pi，tj）是从迁移tj的输入位置pi到迁移tj的弧的权，并称C+为Petri网的输入关联矩阵，C?为Petri网的输出关联矩阵。 * 如果Petri网PN =（N，M0）是一个纯网，即满足?x?P∪T：?x∩x?=?，则对任何pi、tj， Cij+和Cij- 中必至少有一个为0，所以关联矩阵是对Petri网结构的准确描述。 如果PN不是纯网，那么Cij+和Cij-就可能全不为0，于是Cij+-Cij-就是t引发时输入输出的最终效果，而不是对输入和输出的准确描述。 * （3） 状态方程、不变量 S-向量、T-向量：以位置集P为序标集的列向量V：P→Z叫做PN的S-向量。以迁移集T为序标集的列向量U：T→Z叫做Petri网的T-向量。 对于关联矩阵为C= C+ ? C?的Petri网，如果M1[tjM2，则标识向量M2和M1之间的关系，可用下述等式描述：M2 = M1+ C...j。 C...j表示矩阵C的第j列向量。 状态方程：若M0[?＞M，则标识向量M0和M之间的关系为： M = M0+C·U --- Petri网的状态方程 其中，U是PN的T-向量，对于ti?T，U（ti）对应于ti在?中出现的次数（称为迁移的引发向量）。 * （3） 状态方程、不变量 p1 p2 3 4 6 4 p3 p4 p5 p6 t1 2