（计算机应用技术专业论文）基于约束程序的petri网可达问题的研究.pdf

墓于约束程序的p e t r i 网可达问题的研究 基于约束程序的p e t r i 网可达问题的研究 摘要 p e t r i 网是一种广泛应用于描述异步并发现象的图形化建模和分析工 具，p e t r i 网的可达性判定问题是进行p e t r i 网建模和分析的基础。判定p e t r i 网可达性的基本方法有可达树、可达图、状态方程和不变量分析等，由于 合爆炸问题的存在，使得这些基本p e t r i 网的分析方法随着问题规模的增大 而超出目前计算机的运算能力，严重限制着p e t r i 网建模机制在现实中的应 用。 本文采用逻辑抽象技术和约束程序的方法，主要对三种类型的可达问 题进行的研究。即： 问题l ：给定p e t r i 网e = ( p ，t ；f ，w ，研o ) 和任一标识班，判断该标识是 否由初始标识坍。可达。 问题2 ：给定p e t r i 网= ( 尸，t ；f ，w ，m 。) 和一组标识，求这组标识中的 元素从初始标识m 。可达的情况。 问题3 ：给定p e t r i 网= ( p ，t ；f ，w ，m 。) 和任一t - 向量u ，判断是否有 对应t _ 向量u 的实际变迁序列由初始标识发生。即在对应t - 向量u 的 实际变迁序列的作用下标识所，= m o + c u 是由初始标识m 。可达。 针对以上3 个问题，本文具体工作为： 首先，在分析逻辑抽象技术和序列深度参数算法的基础上，引入最大 步集、部分标识的关键标识、部分步关键变迁等概念，证明关键约束的可 | i 于约束程序的p e t r i 崩可碴问噩音奇研，0 用、完整和正确性。丰富了基于约束程序的p e t r i 网理论。 其次，提出了解决问题1 、问题2 的基于关键约束理论的可达集及序列 深度参数求解算法和可达判定算法。使得算法不但可以在并行度高、多 t o k e n 或存在家态情况下，使用更少约束和变量，避免搜索重复路径与产 生重复标识；而且对有界p e t r i 网判定时，不需要指定k 值，并可以一次 对一组标识完成可达判定。大大地提高了判定的效率和适用范围。 最后，在分析变迁约束可达问题的各种求解办法和缺陷的基础上，提 出了变迁约束可达问题的求解模型和判定算法。使用该约束模型的构造的 算法充分利用t 向量提供的信息，对可达图进行展望搜索，忽略了对不 相关分支的搜索；在约束搜索策略的指导下，使得变量( 解) 快速逼近于 t 向量。通过实例分析表明，算法在多t o k e n 、多并发、大最大步集的情 况下，将大大减少了问题搜索的分支。最坏情况下( 在不可达并且单t o k e n 的情况下) 算法才有可雒等同于关键约束的搜索量。另外，问题搜索所减 少搜索的分支的数量和网结构及其t o k e n 数有关。 关键词；p e t r i 网可达问题逻辑抽象技术关键约束变迁约束约束 程序约束满足求解 h 广西大省嘟士掌位论文 | i 于l t 由j i t 程序的p e t r i 网可选问噩的研究 r e s e a r c ho nc o n s t r a l n tp r o g r a m m i n gb a s e d p e t r in e t sr e a c h a b i l i t yp r o b l e m a b s t r a c t p e t r in e ti sag r a p h i c a la n dm a t h e m a t i c a lm o d e l i n gt o o la p p l i c a b l et om a n ys y s t e m s 。i ti s ap r o m i s i n gt o o lf o rt h es y s t e m st h a ta r ec h a r a c t e r i z e da sb e i n gc o n c u r r e n t ，a s y n c h r o n o u s ， d i s t r i b u t o d ，p a r a l l e l ，n o n d e t e r m i n i s t i e ，a n d o rs t o c h a s t i c t h er e a c h a b i l i t yp r o b l e mi so n e o f t h eb a s i cp r o b l e m si np e t r in e ta n a l y s i s t h e r ea r em a n yb a s i cm e t h o d st os o l v ei t ，i n c l u d i n g s t a t ee q u a t i o n , t _ i n v a r i a n ta n dr e a c h a b i l i t yg r a p h t h er e a c h a b i l i t yg r a p hc o r r e s p o n d st ot h e u s u a lf o r m a lr e p r e s e n t a t i o no ft h eb e h a v i o ro ft h ep e t r in e t h o w e v e r , d u et ot h ew e l l - k n o w n c o m b i n a t o r i a le x p l o s i o np r o b l e m ，i ti s i m p o s s i b l e t o e x p l o r i n gt h er e a e h a b i l i t yg r a p h e x h a u s t i v e l y f o r t u n a t e l y , i th a sb e e ns h o w nt h a tt h er e a c h a b i l i t yp r o b l e mi sd e c i d a b l e ， a l t h o u g hi ti se x p - t i m ea n de x p s p a c eh a r di nt h eg e n e r a lc a s e i nt h i st h e s i s ，w ef o c u so nt h r e et y p e so fr e a e h a b i l i t yp r o b l e m ，b a s e do nc o n s t r a i n t s p r o g r a m m i n ga n dt h el o g i c a la b s t r a c t i o nt e c h n i q u ep r e s e n t e db yb e n a s s e ra n dy i m t h e s e t h r e er e a e h a b i l i t yp r o b l e ma r ed e f i n e da sf o l l o w ： ( 1 ) p r o b l e ml ：“g i v e nap e t r in e t = ( p ，t ；f ，w ，m o ) a n daf i n a lm a r k i n gm f ， d e c i d ei f m f r e a c h a b l ef r o mt h ei n i t i a lm a r k i n gm 0 ” ( 2 ) p r o b l e m2 ：“g i v e nap e t r in e t = ( p ，r ；f ，w ，m o ) a n das e to f m a r k i n g s ，d e c i d ei f e a c ho ft h e mr e a c h a b l ef r o mt h ei n i t i a lm a r k i n gm 0 ” ( 3 ) p r o b l e m3 ：“g i v e nap e t r in e t = ( p ，t ；f ，w ，m o ) a n dat _ v e c t o ru ，d e c i d ei ft h e t r a n s i t i o ns e q u e n c e sc o r r e s p o n dt ot h et v e c t o rui sf r i a b l ef r o mt h ei n i t i a lm a r k i n gm 0 ；i n o t h e rw o r d s ，d e c i d ei ft h em a r k i n gm f = m o + c ug e n e r a t e db yt h e1j e c t o rur e a c h a b l e f r o mt h ei n i t i a lm a r k i n g m 0 ” t os o l v et h ep r o b l e m sg i v e na b o v e ，o u rw o r k sf a l li n t ot h ef o l l o w i n ga s p e c t s ： f i r s t l y , a f t e ra n a l y z i n gt h ec h a r a c t e r i s t i co f l o g i c a la b s t r a c t i o nt e c h n i q u e ，w ed e f i n et h e m a x i m u ms t e p ss e t ，t h ek e ym a r k i n g sa n dt h ek e yt r a n s i t i o n s t h e nw ep r o v et h a tu s i n gt h e k e ym a r k i n g sa n dt h ek e yt r a n s i t i o n sc a ne x a c t l yc a p t u r et h ec o n c r e t es t e p sa n dm a r k i n g s e x c l u d i n gt h ep o s s i b i l i t yo fi d e n t i c a lm a r k i n g sa p p e a r e di no t h e rp a r t i a ls t e p so rp a r t i a l m a r k i n g s i i i 广西大掣壤士掌位论文| i 于约束程序的p e t r i 用匐r 选问题的研究 ( 2 ) s e c o n d l y , b e i n gs u p p o r t e db yo u rp r o p o s i t i o n ，w ep r o p o s et h ek e yc o n s t r a i n t s a l g o r i t h m ，w h i c hn o to n l yc a l lr u ne f f i c i e n t l ya n de f f e c t i v e l yi nt h ep e t r in e tw i t hm u l t i t o k e n a n d o rr e p e t i t i v em a r k i n g s ( h a v i n gac y c l ei nt h er e a c h a b i l i t yg r a p ho rad i f f e r e n tt r a n s i t i o n s e q u e n c e si n a ni d e n t i c a lm a r k i n g ) ，b u ta l s oc o m p u t et h es e q u e n t i a ld e p t hp a r m n e t e ro f b o u n d e dp e t r in e tb yu s i n gl e s sa d d i t i o n a lv a r i a b l e sa n dc o n s t r a i n s w h a t sm o r e t h ek e y c o n s t r a i n t sa l g o r i t h mi sg o o da ts o l v i n gt h er e a c h a b i l i t yp r o b l e mo fas e to fm a r k i n g sd e f i n e d i np r o b l e m2 ( 3 ) f i n a l l y , a f t e ra n a l y z i n gs o m em e t h o d so fs o l v i n gt h er e a c h a b i l i t yp r o b l e md e f i n e di n p r o b l e m3 ，w er e c r e a t eo u rc o n s t r a i n t sm o d e la n dp r e s e n tan e wa l g o r i t h m ，t h en e w a l g o r i t h ml 珊st h ef o r w a r dc h e c k i n gm e t h o dt oa v o i ds e a r c h i n gt h ep a t h su n r e l a t e dt v e c t o r u w ea l s oc o n s i d e rt h ec o n s t r a i n t ss e a r c hs t r a t e g yt om a k eo u rv a r i a b l e sm p i d l ya p p r o a c h e s t h et a r g e t o u rr e s u l ts h o wt h a tt h ea l g o r i t h mi sg o o da tp r o b l e m3w i t ht h ep e t r in e th a v i n g m u l t i t o k e na n d o rr e p e t i t i v em a r k i n g s k e yw o r d s ：p e t r i n e t ；r e a c h a b i l i t yp r o b l e m ；l o g i c a l a b s t r a c t i o n t e c h n i q u e ；k e yc o n s t r a i n t s ；t r a n s i t i o nc o n s t r a i n s ；c o n s t r a i n t s a t i s f a c t i o n p r o b l e m i v 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位两使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名：熏辜乞乞 学位论文使用授权说明 2 p d 7 年莎月3 日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复割手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 凼p 时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：蚍导师签名：啤晦喳 2 。砗f 月3 只 、 | 盱约束程序的p e t r i 搠司r 这问题的研究 第一章绪论 p e 伍网是一种广泛应用于描述异步并发现象的跨越通讯科学、计算机科学、控制科 学和系统科学交叉研究领域的图形化建模和分析工具，它既有严格的数学定义，又有直 观的图形表示，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚 实的概念基础。实践证明，p e t r i 网比传统的系统建模、分析和控制方法更具有独特的 优越性，被广泛应用在人造系统模型、软件设计、工作流管理、数据分析、并行程序设 计和协议验证等。 p e 砸网的可达性判定问题是进行p e 们网建模和分析的基础。判定p e t r i 网可达性的 基本方法有可达树、可达图、状态方程和不变量分析等，由于合爆炸问题的存在，使得 这些基本p e 打i 网的分析方法随着问题规模的增大而超出目前计算机的运算能力，严重 限制着p e t r i 网建模机制在现实中的应用。本文在前人研究的基础上，采用逻辑抽象技 术和约束程序的方法，进行p e t r i 网可达问题算法及分析技术的研究。 本章概述p o d 网和约束程序的研究背景和现状、研究目的意义、论文的主要研究 内容及组织结构。 1 1 相关研究现状 1 1 1p e t ri 网论及其可达性的研究 1 9 6 2 年德国的c a p e 埘先生在其博士学位论文用自动机通信”中首次建立了p e 埘 网。经历四十多年的发展，p e t r i 网己经形成了较为颦实的理论基础和多种类型的应用体 系。 目前，p e t r i 网的研究主要有： ( 1 ) p e 仃i 网模型行为特性及其分析方法的研究。 ( 2 ) p c t r i 网的扩展研究。 ( 3 ) p e 埘网语言研究。 ( 4 ) p e 砸网应用研究与工具研制。 典型的p e 啊网有【l l ：抑制弧p e t f i 网模型( i i l l l i b i t o r a r e sp e t r in e tm o d e l ) 、高级p e t d 网 1 | l 于约束程序的p e t r i 网匐r 这问题的研究 ( h i 【g i i l e v e l p e t r i n e t ) 、时间时延p e t r i ( t i m e t i m e d p e t r i n e t ) 、随机p e t r i 网( s t o c h a s t i c p e t r in e t ) 、对象p e t r i 网( o b j e c tp e t r in e t ) 、时序p e t r i 网( t e m p o r a lp e t r in e t ) 、被控 p e t r i 网( c o n t r o l l e dp e l r in e t ) 和混合p e t r i 网( h y b d dp a dn e o 等。这些模型的主要分析 技术包括：代数分析计算技术、图分析技术和归纳分析技术。 p e t r i 网的具体应用主要表现在：通信网络的协议验证和分析【2 , 3 1 、操作系统的p e t r i 网描述【4 】、并发程序的描述与验i t 正1 5 , 6 1 、p e t r i 网在分布式数据库系统的应用【7 1 、p e t r i 网在 实时系统中的应用1 8 1 、自动制造系统的p e t r i 网建模与分析9 2 1 、对证券交易系统的模拟 与验证【1 3 1 、基于p e t r i 网的工作流研究i 悼1 6 1 、电网系统异常现象控制器综合过程与算法【1 7 1 等。 随着计算机科学家逐渐认识和重视并发现象，p e t r i 网也受到了广泛的关注，成为计 算机界、自动化界的热门研究课题，同时，问题规模和各类模型的递增使得p e t r i 网可 达问题成为研究的重点和热点。事实上，在p e t r i 网研究的初期，人们就发现基本p e t r i 网模型存在一些可判定问题，但是，有界p e t r i 网的性质却很好，应用起来没有遇到难 题。随后，人们发现广义p e t r i 网的可达标识数随着模型中的库所、变迁和托肯数量的 增长呈指数增长，导致所谓组合爆炸问题( c o m b i n a t o r i a le x p l o s i o n ) 。因此，在一个复 杂的网系统中尽管模型可能有界，但是使用可达树、关联矩阵与状态方程、不变量分析 等基本p e t r i 网的分析方法的分析已经超出目前计算机的运算能力，严重限制着此类建 模机制在现实中的应用。 目前，求解p e t i r 网的可达问题的主要方法包括： ( 1 ) 基于状态方程的方法。 典型的方法有：参数分析法( p a r a m e t e r i z e da n a l y s i s ) 【1 8 】、代数法( a l g e b r a i c m e t h o d s ) 1 9 1 满秩分解法【2 0 1 和综合判定法【2 ”等。 ( 2 ) 在不改变其组合空间的基础上，分析解决问题。 典型的方法有：图形压缩( g r a p hc o m p r e s s i o n ) 如：b d d 译码( b d de n c o d i n g ) 法田1 、正向检测法( f o r w a r dc h e c k i n g ) 1 2 3 1 、i r t l 2 4 j 法和决策变量的启发式选择 法【2 5 1 等 ( 3 ) 简化技术。简化技术主要采用“分而治之”的思想，将一个复杂的网系统在 保留原有某些性质不变的情况下，通过不同的技术构造或分解成若干较为简 单的网系统。 2 广西大掌硕士茸啦论文| 盱约束程序的p e t r i 网胃j 选问题的研究 典型的方法有：对称法( s y m m e t r i e s ) 1 2 6 ) 、缩变法( r e d u c t i o n s ) 1 2 7 1 、分步次 序法( p a r t i a lo r d e r ) ( 包括图分步法圆和s t u b b o r n 集法【2 9 】) 、e s p n 性能等价 化简分析方法 3 0 i 、同步变迁实施速率等价法( s t e r ) 1 3 1 l 和m i m 0 0 改进方法嘲 等。 值得一提的是简化技术，它是近几年p e t r i 网领域中的主流方向之一。但是大多数 工作都局限于保性研究上，而且条件过强，很难普适。因此，保持行为的化简，分解研 究，减弱条件，提高适应性将是进一步努力的目标。 p e 埘的自身优势使其成为众多学科的交叉研究领域，它的广泛应用和理论模型的不 断演进，给我们提供了很大的研究空问。 1 1 2 约束程序 约束程序口3 1 ( c o n s t r a i n tp r o g r a m m i n g ，c p ) 是围绕关系约束这一数学概念建立起来的 关于程序设计和问题求解的方法论，是研究基于约束的组合优化问题的推理和计算系 统。作为- - f 新兴的软件技术，约束程序具有说明特性而且特别适合高效地求解调度和 规划领域的大型组合搜索问趔3 4 1 。 目前，最常见的几种约束程序有： ( 1 ) 约束逻辑程序设计c l p ，如c l p ( r ) 1 3 5 1 等。 ( 2 ) 并发约束程序设计c c ，如a k l 、c o ( f d ) 1 3 6 1 和c o p s ( c o n s t r a i n t so b j e c t sp r o d u c t i o n s y s t e m ) 1 3 7 4 明。 ( 3 ) 嵌入过程性语言的约束程序，如i l o gs o l v e 4 0 1 和“明月”约束求解平台i 3 4 , 4 1 - 4 3 1 ， 它们共同的重要特征是说明性的问题建模、约束效应传播和可行解空问的有效搜索。 约束程序主要以约束满足问题的建模和求解为核心问题( 目前的主流说法) 。约束 满足问题的求解方法包括： ( 1 ) 系统化的搜索方法，如回溯方法。 ( 2 ) 相容性技术】，如节点和弧相容技术。 ( 3 ) 各种约束传播方法，比如f c + c b j i 删等。 从广义上讲，约束程序还包括约束求解1 4 5 1 。约束求解与约束满足的主要区别是约束 求解考虑的是无限论域的变量，并且单个的约束更加复杂，如非线性方程。通常，约束 求解算法使用梯度法、黄会分割法、牛顿法等代数和数值的方法，而不是组合搜索。 3 墓于约束程序的p e t r i 网胃b 毛问题的研究 目前，就算法方面而言主要包括：对系统化搜索回溯方法的各种改进研究，对节点 和弧相容等技术的扩展，探索求解算法的多种值和变量选择的启发式策略，对约束优化 问题探索遗传算法、人工神经元网络等随机搜索算法的使用，同时还出现了利用多种算 法联合求解问题的新趋势。 1 1 3p e t r i 网与约束程序 随着对并行机制要求的提高，p e t r i 网被誉为当今研究并发系统的主要工具之一。另 一方面，约束程序技术也已经渗透到众多研究领域，如：人工智能、运筹学、程序理论、 机器学习和决策支持等，成为多学科交叉的具有重大应用背景的研究方向，并被美国计 算机协会( a c m ) 评为1 9 个最具战略意义的计算机研究方向之一【拍】。美国著名计算 机学家e u g e n ec f r e u d e r 教授在i n t e r n a t i o n a lj o u r n a lo f c o n s t r a i n t s 创刊号对约束程序做 出了肯定评价：“计算机程序设计的最高境界是用户给出问题，而由计算机自动求解。显 然，约束程序是计算机科学中最接近这一终极目标的方法。”刚 事实上，p e t r i 网和约束程序具有互通之处，彼此在相互渗透着。一方面，逻辑程序 利用p e t d 网发展自我。文献【4 7 】利用高级p e t d 网的并行特性来表示函数自由 ( f u n c t i o n f r e e ) 的逻辑程序，文献【4 8 】利用对象p e t r i 网来表示约束满足问题。另一方 面，p e t r i 网也利用约束程序分析自身性质。首先b e n a s s e r 等人提出运用逻辑抽象技术 ( l o g i c a la b s t r a c t i o nt e c h n i q u e ，l a t ) 4 9 - 5 1 解决可达问题。随后，文献 5 2 1 通过定义 序列深度参数( s e q u e n t i a ld e p t hp a r a m e t e r ) 对l a t 方法进行改进。文献【5 3 】通过改进l a t 方法在时延p e t r i 网上解决循环问题等。 总的来说，目l j i 国外这方面的研究刚刚起步不久，而国内利用约束程序研究p e t r i 网或者利用p e t f i 网研究约束程序的都比较少。但p e t r i 网与约束程序的发展未来，将会 彼此相互渗透着。 1 2 选题的目的和意义 从上节的背景介绍中，我们了解了p e t r i 网和约束程序的重要性和研究价值。因此 利用约束程序丰富的算法思想和技术，结合p e t r i 网的具体模型和机制，进行p e t r i 网研 究，将有利于丰富p e t r i 网理论、促进p e t r i 网和约束程序的融合及应用。 此外，基于约束程序的p e t r i 网研究才刚刚起步不久，而p e t r i 网的可达性的研究是 4 基于约束程序的p e t r i 用可达问题的研，薯 p e t d 网理论研究的基础和重点；可达问题是研究所有p c t r i 网建模系统的动态特性的最 基本和最重要的问趔州；也就是说，p e t r i 网的其余各种性质，如有界性( b o 咖d n 髂s ) 、 活性( l i v e n e s s ) 、死锁( d e a d l o c k ) 等都要通过可达性来定义，也最终都可以归结为可达问 题。因此，本论文把基于约束程序的p e t r i 网可达问题作为研究课题。 1 3 研究的主要内容 本文工作主要在结合约束程序与p e 砸网研究的基础上，展开基于约束程序的p e t r i 网可达问题的研究。研究主要针对三种类型的可达问题进行的。即： 问题h 给定p e t r i 网= ( p ，t ；f ，缈，m o ) 和任一标识m ，判断标识珊，是否由初始 标m o 可达。 问题2 ：给定p e t r i 网= ( p ，t ；f ，m 。) 和一组标识，求这组标识中的元素从初始 标识肌。可达的情况。 问题3 ：给定p e t r i 网= ( 只乃，) 和t _ 向量u ，判断是否有对应t - 向量盯的 实际变迁序列由初始标识发生，即在对应t _ 向量u 的实际变迁序列的作用下标识 m ，= + c u 是由初始标识可达。 针对以上3 个问题，本文研究证明了关键约束相关理论；提出基于关键约束理论的 可达相关算法；提出变迁约束可达问题的求解模型和判定算法。具体内容如下： ( 1 ) 研究关键约束理论。在分析逻辑抽象技术和序列深度参数算法的基础上，引 入最大步集、部分标识的关键标识、部分步关键变迁等概念，证明关键约束的可用、完 整和乖确性。 ( 2 ) 提出了解决问题i 、问题2 的基于关键约束理论的可达集及序列深度参数求解 算法和可达判定算法。并通过对比分析、例子验证的办法，分析l a t 算法、序列深度 参数搜索算法的和关键约束算法的优劣。 ( 3 ) 针对问题3 ，提出了变迁约束可达问题的求解模型和判定算法。在分析了变迁 约束可达问题的各种求解办法和缺陷的基础上，对约束求解模型进行构造。通过具体算 法和实例求解过程分析算法的特性，并总结其优势所在。 1 4 论文的组织结构 本文各章节的安排如下： 5 广西大掣q 曩士掌位论文| 矛约束程序的p e t r i 网可迭问题的研究 第一章绪论 介绍p e t r i 网和约束程序的研究背景和现状、研究目的意义、论文的主要研究内容 及组织结构。 第二章p e t r i 网可达问题及分析基础 首先介绍p e t r i 网的基本概念，然后阐述p e t r i 可达问题、基本动态性质、结构特性， 最后概述p e t r i 网的几种基本分析方法。 第三章约束程序及约束满足求解技术 首先介绍约束及约束满足问题的概念，然后介绍相关约束满足问题的求解技术，最 后探讨搜索中的动态变量选择与变量值选择策略。 第四章基于关键约束的p e t f i 网可达算法研究 首先阐述和分析逻辑抽象技术研究的相关理论及算法，然后对提出的关键约束理论 进行证明，给出关键约束模型、算法和例子，最后比较分析算法的优劣。 第五章基于变迁约束的可达问题判定研究 首先对变迁约束问题进行阐述，并对其求解方法进分析，然后提出求解的约束模型 和算法，最后通过实例比较分析算法特性。 第六章总结与展望 对研究工作进行总结和对后续研究进行展望。 6 广曩f 大掣嘎i 士学位论文基于约束程序的p e t r i 阚可达问题的研3 电 第二章p e t ri 网可达问题及其分析基础 本章主要给出与本文相关的p e t r i 网基本知识，其内容主要参考文献 5 5 5 7 1 。 2 1p e t r i 网的基本定义 定义2 - 1 三元组n = ( p ，t ；f ) 称为有向网( 简称网) 的充分必要条件是： ( 1 ) p n t = ； ( 2 ) p u t ； ( 3 ) f ( p x t ) u ( r x p ) ，其中“”为笛卡儿积； ( 4 ) d o m ( f ) u c o d ( f ) = p u r ，其中f 的定义域和值域分别为： d o m ( f ) = x p u r p y j p u t ：( x ，y ) f ) c o d ( f ) = 抄p u r l 3 x p u t ：0 ，y ) f ) 。 其中户和r 分别称为的库所( p l a c e ) 集和变迁( t r a n s i t i o n ) 集，为流关系( f l o w r e l a t i o n1 。用图形来表示一个网时，把一个库所画成一个小圆圈，一个变迁画成一个小 矩形。对x ，y p u r ，若( x ，y ) f 则从x 到y 画一条有向边。 库所和变迁是两类不同的元素，所以尸n t = ；而p u t 矿表示网中至少有一个 元素。每个库所代表一种资源，资源的流动由流关系规定，所以，( p x 丁) u ( t p ) 表 示变迁只能与库所有直接的流关系；不参与任何变迁的资源表现为孤立的库所，不引起 资源流动的变迁表现为孤立的变迁，d o r a ( f ) u c o d ( n = p u f 规定网中不能有孤立的元 素。 定义2 - 2 设工p u t 为的任一元素， ( i ) j y 陟p v t ( j ，x ) f 称为工的前集( p r e - s e t ) 或输入集a ( 2 ) x 。纠z e p u t a ( x ，2 ) 毋称为x 的后集( p o s t s e t ) 或输出集。 ( 3 ) x 。= 、t j x 称为元素x 的外延。 显然，一个变迁的外延是由某些库所组成的集合，一个库所的外延是由某些变迁组 成的集合。 定义2 3 对于有向网n = ( p ，7 ；f ) ( 1 ) 若v x p u t ：x n ，毋，则称网为单纯网。 7 广西大掌硕士掌位美没 | 0 于约束程序的p e t r i 网可选问题音鲁研究 ( 2 ) 若v x ，y p u 丁：z = 7 x = j ，j x = y ，则称网为简单网。 定义2 4 对于有向网n = ( p ，r ；，) ( 1 ) k ：p j 1 , 2 ， u ) 称为的容量函数( c a p a c i t y f u n c t i o n ) ，其中国表示无穷。 ( 2 ) 对给定容量函数x ，m ：p 一 0 ，1 ，2 ) 称为的一个标识( m a r k i n g ) 的条件是： 坳e p ：m ( p ) x ( p ) 。 ( 3 ) w ：p 斗 1 , 2 ) 称为上的权函数，对( 膏，y ) f ，w ( x ，y ) = ( ( z ，y ) ) 称为 ( x ，y ) 上的权。 用图形来表示一个网时，对p ：m ( p ) s k ( p ) ，若m ( 力= k ，则在表示库所p 的小圆圈内加上k 个小黑点( 当数值k 很大时，也可以直接写上数字k ) ，并说库所p 中 有k 个托肯( t o k e n ) 或标记。 定义2 - 5 组= ( p ，t ；f ，k ，w ，m o ) 构成网系统的条件是： ( 1 ) n = ( p ，t ；f ) 构成有向网，称为的基网。 ( 2 ) k ，w ，m o 依次为上的容量函数、权函数和标识。肘。称为的初始标识( i n i t i a l m a r k i n g ) 。 设肘为网系统= ( p ，t ；f ，k ，w ，) 的基网n = ( p ，；，) 上的任一标识，t t 为任 一变迁。 定义2 - 6，在m 有发生权( f i r a b l e ) 的条件是： 、忉。t ： ，( p ) w ( p ，f ) 、咖t 。： f ( p ) + w ( p ，f ) k ( p ) f 在m 有发生权记作m t ，也说吖授权( e n a b l e s ) t 发生或t 在肘授权( e n a b l e d ) 下 发生。 定义2 7 若m t ，则f 在m 可以发生，将标识m 改变为m 的后继m 。，肘的定 义是：对坳p 。，、隗m ( p ) m - w ( f ，( p , 昌t 耘1 叫 州加懈家阮办w ( f ，力耘若p e ，n t - ，t 【m ( - s )若p 叠t 肘为m 的后继的事实记m t m 。 c a r l a d a mp e t r i1 9 6 2 年使用的系统模型实际上是k = 国和w ；1 的网系统。2 0 世纪 7 0 年代a h o l t 把这种系统称为p c t r i 网，p c t r i 网的名称由此而诞生。同时，把网和网系 统不加区分地称为p e t r i 网，直到2 0 世纪8 0 年代中期，人们彳。明确指出必须把网和网 系统分开。所以，历史的原因使“p e t r i ”网一词有三种不同的含义： 基于约束程序的p e t r i 用可琏问题的研究 ( 1 ) 指定义2 - 1 中的有向网n = ( p ，r ；f ) 。 ( 2 ) 指定义2 5 中的网系统，当k ；国，w ；l 。 ( 3 ) 泛指以有向网为基础的整个学科。 2 2p e t r i 网的性质 2 2 1 可达性 可达性( t e a c h a b i l i t y ) 是p e t r i 网的最基本的动态性质，其余各种性质都要通过可达性 来定义。 定义2 - 8 设= ( ，t ；f ，m ) 为一个p e 仃i 网。如果存在t t ，使m t m ，则称m 为从m 直接可达的。如果存在变迁序列f l t 2 ，和标识序列吖。m ：，惦使得 m t i m l 【f 2 m 2 帆一i i t , m ( 2 1 ) 则称 以为从m 可达的。从m 可达的一切标识的集合记为r ( m ) 。约定m r ( m ) 。 如果记变迁序列 t 2 ，t k 为盯，则( 2 1 ) 式也可以记为m a m k 。 用p e t r i 网模拟一个实际系统时，以网( p ，r ；，) 描述系统结构，初始标识m o 表示系 统的初始状态，r ( 厶) 给出系统运行过程中可能出现的全部状态的集合。 定义2 - 9 设= ( p ，t ；f ，m o ) 为一个p e t r i 网，其中帆是的初始标识。的可达 标识集尺( 如) 定义为满足下面两个条件的最小集合： ( 1 ) n ( m o ) ； ( 2 ) m r ( m o ) ，且存在t t ，使得m t m ，则m r ( m o ) 。 定理2 - 1 设= ( p ，t ；f ，帆) 为一个p e t r i 网，是的初始标识则 ( 1 ) 对任意m 矗( m o ) ，都有r ( m ) r ( m o ) ； ( 2 ) 对任意m l ，m 2 r ( m o ) ，r ( m i ) r ( m 2 ) 当且仅当m l r ( 鸩) 且 如r ( 毛) - 2 2 2 可逆性和可覆盖性 定义2 - 1 0 设= ( 尸，t ；f ，m o ) 为一个p e t r i 网，m r ( m o ) 。如果v m r ( 膨) ， 都有m r ( m ) ，则称肘为的一个可返回标识或一个家态( h o m es t a t e ) 。 定义2 - 1 1 设= ( p ，t ；f ，j j l 如) 为个p e t r i 网，如果的初始标识吖。是一个家态， 则称为可逆网系统( r e v e r s i b l e n e ts y s t e m ) ，或称可回复网系统。 p e 砸网的可逆性( r e v e r s i b i l i t y ) 反映系统的可回复性。易知，如果= ( p ，丁；f ，m o ) 是 o | i 于约束程月；的p e t r i 用可选问题的研究 不可逆网系统，但存在m r ( 帆) 是一个家态，那么把初始标识换成肼，得到的 - = ( 只t ；f ，膨) 则是个可逆网系统。 定义2 - 1 2 设n = ( p ，t ；f ) 为一个网，m 和鸠是的两个标识。如果v p p 都有 m l ( p ) = m 2 ( p ) ，则称m i 被肘2 覆盖，或者说m 2 覆盖 毛，记作m l m 2 。如果j j l 毛m 2 ， 而且存在p p ，使得m j ( p ) m 2 ( 力，记m 1 ，n r m 是的一个可 覆盖标识，则中3 m r ( 如) 使得m i t 。也就是说，中存在着一个变迁序列盯导致 变迁t 的发生。这就是研究p e t r i 网的可覆盖性( c o v e r a b i l i t y ) 的意义所在。 2 2 3 有界性和安全性 定义2 - 1 4 设= ( p ，t ；f ，m o ) 为一个p e t d 网，p 尸。若存在正整数曰，使得 v m 且( m o ) ：m ( p ) b ，则称库所p 为有界( b o u n d e d ) ，并称满足此条件得最小j 下整 数b 为库所p 的界，记为b ( p ) 。即 b ( p ) = m i n b v m r ( 毛) ：w ( p ) b ) 当b ( p ) = 1 时，称库所p 为安全的( s a f e ) 。 定义2 1 5 设z ( p ，t ；f ，m 。) 为一个p e t r i 网，如果每个p p 都是有界的，则称 为有界p e 伍网。称 b ( z ) = m a x b ( z ) | p p 为的界。当a ( p ) = 1 时，称为安全的。 定理2