《网的基本概念PPT课件》由会员分享，可在线阅读，更多相关《网的基本概念PPT课件（22页珍藏版）》请在金锄头文库上搜索。
1、第一部分 Petri网的基本概念提纲网与网系统网与网系统n库所库所/变迁系统与加权变迁系统与加权Petri网网n并发与冲突并发与冲突网与网系统nPetri网是一种网状信息流模型，包括库所和变迁两类节点，同时在网是一种网状信息流模型，包括库所和变迁两类节点，同时在库所集上添加表示状态信息的托肯分布（标识）库所集上添加表示状态信息的托肯分布（标识）库所表示条件、资源、等待队列和信道等库所表示条件、资源、等待队列和信道等变迁表示事件、动作、语句执行和消息发送变迁表示事件、动作、语句执行和消息发送/接受等接受等一个变迁（事件）有一定数量的输入和输出库所，分别代表事件的前置一个变迁（事件）有一定数量的输
2、入和输出库所，分别代表事件的前置条件和后置条件条件和后置条件库所中的托肯代表可以使用的资源数量或数据库所中的托肯代表可以使用的资源数量或数据nPetri网按引发规则使得事件驱动状态的演变，从而反映系统动态运网按引发规则使得事件驱动状态的演变，从而反映系统动态运行过程行过程网与网系统p1p2t1t2c1c2t3t4B例：例：网网N1=(P1,T1; F1)，其，其中中 P1 = p1, p2, c1, c2, B T1=t1, t2, t3, t4 F1=(p1, t1),(t1, p2), 网与网系统n定义定义1.1. 三元组三元组N=(P,T;F)称作称作网网当且仅当：当且仅当：（1） P
3、T, P T=;（2） F (P T) (T P);（3）dom(F) cod(F)=P T其中，其中， dom(F)=x P T | y P T: (x, y) F cod(F) =x P T | y P T: (y, x) F这里，里， P表示表示库所（所（Place）集合）集合 T表示表示变迁（迁（Transition）集合）集合 F是网的流关系（是网的流关系（Flow）网与网系统n定义定义1.2. 设设N=(P,T;F)为一个网，对为一个网，对 x P T，令，令 x = y | y P T (y, x) F x = y | y P T (x, y) F 称称x为x的的前集前集或或输入
4、集，入集， x为x的的后集后集或或输出集。称出集。称x x 为元素元素x的的外延外延。一个库所的外延是变迁集一个库所的外延是变迁集T T的一个子集的一个子集一个变迁的外延是库所集一个变迁的外延是库所集P P的一个子集的一个子集网与网系统例：例：网网N1=(P1,T1;F1)，其，其中中 t2 = p2 t2 = p1, Bp1p2t1t2c1c2t3t4B网与网系统n定义定义1.3. 设设N=(P,T;F)为一个网为一个网（1）若对）若对 x P T， x x =，则则称称N为为一个一个纯网网（pure net）。）。（2）若）若对对 x, y P T，(x= y) (x =y ) x=y，则
5、称称N为一个一个简单网网（simple net）。）。（3）若）若 p P，|p|=|p|=1，则称称N为一个一个T-图（T-Graph）或）或标识图（marked graph）。）。（4）若）若 t T，|t|=|t|=1，则称称N为一个一个S-图（S-Graph）或）或状状态机机（state machine）。）。（5）若）若 t1,t2 T (t1 t2), t1 t2 |t1|=|t2|=1，则称称N为一个一个自由自由选择网网（free-choice net）。）。（6）若）若 t1,t2 T (t1 t2), t1 t2 t1=t2，则称称N为一个一个扩充充的自由的自由选择网网（ex
6、tended free-choice net）。）。网与网系统n定义定义1.4. 四元组四元组PN=(P,T;F,M0)称作称作Petri网（网系网（网系统）当且仅当当且仅当（1） N=(P,T;F)为一个网；为一个网；（2）映射）映射M:P 0,1,2,(非非负整数集整数集)称称为网网N的一个的一个标识，其中，其中，M0是是初始初始标识；（3）引发规则：）引发规则：（）变迁（）变迁t T称称为使能的使能的当且当且仅当：当： p t：M(p) 1，记作作Mt;（）在（）在M下使能的变迁下使能的变迁t可以引发，引发后得到一个新的标识可以引发，引发后得到一个新的标识M，记作，记作MtM,对p P，
7、有有网与网系统p1p2t1t2c1c2t3t4Bp1p2t1t2p3p1p2t1t2p3一个网系统的全部可能的运行情况由它的基网一个网系统的全部可能的运行情况由它的基网N N和初始标识和初始标识M M0 0完全确定。完全确定。因此，给出了基网和初始标识，也就唯一确定了一个网系统因此，给出了基网和初始标识，也就唯一确定了一个网系统M M0101=1,0,0=1,0,0M M0202=0,1,0=0,1,0提纲n网与网系统网与网系统库所库所/变迁系统与加权变迁系统与加权Petri网网n并发与冲突并发与冲突库所/变迁系统与加权Petri网n库所库所/变迁系统（简称变迁系统（简称P/T系统）是在定义系
8、统）是在定义的的Petri网基础上增加两个函数得到的网基础上增加两个函数得到的库所集上的容量函数库所集上的容量函数有向边上的权函数有向边上的权函数n增加这两个函数的目的是使得对某些实际增加这两个函数的目的是使得对某些实际系统建模显得方便系统建模显得方便库所/变迁系统与加权Petri网n定义定义1.5. 六元组六元组=(P,T;F,K,W,M0)称作称作一个一个库所所/变迁网系迁网系统，其中，其中（1） N=(P,T;F)为一个网；为一个网；（2） W: F 1,2,(正整数集正整数集)称称为权函数；函数；（3） K: P 1,2,(正整数集正整数集)称称为容量函数；容量函数；（4） M: P
9、0,1,2,是一个是一个标识，满足足p P：M(p) K(p)其中，其中，M0是初始是初始标识；（5）引发规则：）引发规则：（）对于（）对于t T，Mt的引的引发条件条件（）若（）若MtM,对p P，有，有tH2O222例：化学反应的例：化学反应的P/TP/T系统系统H2O 库所/变迁系统与加权Petri网p1p2t1t2c1c2t3t4B定义的定义的PetriPetri网网P/TP/T系统系统p1p2t1t2c1c2t3t4B1t t2 2无法引发无法引发库所/变迁系统与加权Petri网n对于一个库所对于一个库所/变迁系统变迁系统=(P,T;F,K,W,M0)，若规定，若规定 p P：K(p
10、)= f F：W(f)=1那么，就变成形如定义给出的网系统（那么，就变成形如定义给出的网系统（原型原型Petri网网）n对于一个对于一个P/T系统，如果规定各个库所的容量都为无穷大，即取消库所集上系统，如果规定各个库所的容量都为无穷大，即取消库所集上的容量函数而保留有向边集上的权函数，就得到一种介于原型的容量函数而保留有向边集上的权函数，就得到一种介于原型Petri网和网和P/T系统之间的网系统模型系统之间的网系统模型=(P,T;F,W,M0)，称这种模型为，称这种模型为加权加权Petri网网（weighted Petri net）nP/T系统并不比原型系统并不比原型Petri网具有更强的模拟
11、能力，凡是可以用网具有更强的模拟能力，凡是可以用P/T系统对系统对其建模的实际系统，也可以用原型其建模的实际系统，也可以用原型Petri网对其建模。每一个网对其建模。每一个P/T系统都可系统都可以转换为一个行为等效的以转换为一个行为等效的Petri网网库所/变迁系统与加权Petri网K(p)=2p容量限制容量限制ptt权函数权函数p2pt2ptp等价的原型等价的原型PetriPetri网网提纲n网与网系统网与网系统n库所库所/变迁系统与加权变迁系统与加权Petri网网并发与冲突并发与冲突并发与冲突n定义定义1.6. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是
12、PN中的两中的两个变迁。如果个变迁。如果PN的一个标识的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2 且且 Mt2M2 M2 t1 则称称t1和和t2在在M并并发，记为Mt1 , t2 。u如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生如果两个事件（变迁）在某状态下都有发生权，而且其中任何一个的发生 都不会使另一个失去发生权，则称这两个事件在该状态下处于并发都不会使另一个失去发生权，则称这两个事件在该状态下处于并发u并发不能简单地理解为并发不能简单地理解为“同时发生同时发生”，而是指事件之间因果上的无依赖性。，而是指事件之间因果上的无依赖性。u按
13、网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关按网论的观点，事件的发生只依赖于它们的外延，而与全局情况无关并发与冲突n定义定义1.7. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两个变迁。中的两个变迁。如果如果PN的一个标识的一个标识M使得使得 （1）Mt1 但但 Mt2 ； （2）Mt1M1 M1 t2 则称称t1和和t2存在存在顺序关系序关系。p1p2t1t2p4p6p5t3t4p3p0t0t5并发与冲突n定义定义1.8. 设设PN=(P,T;F,M0)是一个是一个Petri网，网， t1和和t2是是PN中的两中的两个变迁。如果个变迁
14、。如果PN的一个标识的一个标识M使得使得Mt1且且Mt2，那么若，那么若 Mt1M1 M1 t2 且且 Mt2M2 M2 t1 则称称t1和和t2在在M冲突冲突。冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权冲突关系描述了系统的非确定性：在某情况下有两个（或多个）事件都有权发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正发生，但在实际运行过程中，只有一个能真正发生。系统存在冲突之处，正是外界环境可以对其施加控制（加以选择）之处。是外界环境可以对其施加控制（加以选择）之处。并发与冲突t2t1t3t4p1p2p3t3和和t4并发并发t2t1t3t4p1p2p3
15、t1 1和和t t2 2冲突冲突并发和冲突的示例并发和冲突的示例t2t1t3t4p1p2p3控制装置控制装置t2t1p1p2p3p4p5t1 1和和t t2 2不是冲突，而是并发关系不是冲突，而是并发关系并发与冲突混惑的示例混惑的示例t2t1t3p1p2p3p4p5t2t1t3p1p2p3p4p5存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便存在混惑的网系统不是好的系统模型，因为在这种网系统的运行中，冲突是否出现无法确定，不便于对系统施加外部控制，在建立实际系统的于对系统施加外部控制，在建立实际系统的PetriPetri网模型时，应尽量避免出现混惑。网模型时，应尽量避免出现混惑。n混惑混惑 同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（同时存在并发和冲突，但由于并发事件中的某些事件的发生，会使冲突自动消失，如（1）所）所示。示。 系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能系统在某些状态下存在并发，并发事件中不同事件的发生，使得系统可能存在冲突，也可能不出现冲突，如（不出现冲突，如（2）所示。）所示。
