电子学报 ›› 2016, Vol. 44 ›› Issue (8): 1858-1863.DOI: 10.3969/j.issn.0372-2112.2016.08.013

• 学术论文 • 上一篇    下一篇

基于Petri网局部性的极大冲突集枚举算法

潘理1, 郑红2, 刘显明3, 杨勃1   

  1. 1. 湖南理工学院信息与通信工程学院, 湖南岳阳 414006;
    2. 华东理工大学信息科学与工程学院, 上海 200237;
    3. 江西省电力公司信息通信分公司, 江西南昌 330077
  • 收稿日期:2015-05-12 修回日期:2015-11-09 出版日期:2016-08-25 发布日期:2016-08-25
  • 通讯作者: 郑红
  • 作者简介:潘理 男,1975年出生,湖南平江人.博士,湖南理工学院副教授.研究方向为Petri网、形式化建模与优化.E-mail:panli.hnist@gmail.com
  • 基金资助:
    国家自然科学基金(No.61473118);湖南省教育厅科学研究重点项目(No.15A079);湖南省科技计划项目(No.2014GK3026);江西省电力公司科技项目(No.5218351400A1)

Maximal Conflict Set Enumeration Algorithm Based on Locality of Petri Nets

PAN Li1, ZHENG Hong2, LIU Xian-ming3, YANG Bo1   

  1. 1. School of Information and Communication Engineering, Hunan Institute of Science and Technology, Yueyang, Hunan 414006, China;
    2. Information Science and Engineering College, East China University of Science and Technology, Shanghai, 200237 China;
    3. Information and Communication Branch, Jiangxi Electric Power Company, Nanchang, Jiangxi 330077, China
  • Received:2015-05-12 Revised:2015-11-09 Online:2016-08-25 Published:2016-08-25

摘要: 冲突是Petri网研究的重要主题.目前Petri网冲突研究主要集中于冲突建模和冲突消解策略,而对冲突问题本身的计算复杂性却很少关注.提出Petri网的冲突集问题,并证明冲突集问题是NP(Non-deterministic Polynomial)完全的.提出极大冲突集动态枚举算法,该算法基于当前标识的所有极大冲突集,利用Petri网实施局部性,仅计算下一标识中受局部性影响的极大冲突集,从而避免重新枚举所有极大冲突集.该算法时间复杂度为Om2n),m是当前标识的极大冲突集数目,n是变迁数.最后证明自由选择网、非对称选择网的极大冲突集枚举算法复杂度可降至On2).极大冲突集枚举算法研究将为Petri网冲突问题的算法求解提供理论参考.

关键词: Petri网, 冲突集问题, NP(Non-deterministic Polynomial)完全性, 极大冲突集枚举算法

Abstract: Conflict is an essential concept in Petri net theory.The existing research focuses on the modelling and resolution strategies of conflict problems,but less on the computational complexity of the problems theirselves.In this paper,we propose the conflict set problem for Petri nets,and prove that the conflict set problem is NP-complete.Furthermore,we present a dynamic algorithm for the maximal conflict set enumeration.Our algorithm only computes those conflict sets that are affected by local firing,which avoids enumerating all maximal conflict sets at each marking.The algorithm needs time O(m2n) where m is the number of maximal conflict sets at the current marking and n is the number of transitions.Finally,we show that the maximal conflict set enumeration problem can be solved in O(n2) for free-choice nets and asymmetric choice nets.The results on complexity of thel conflict set problem provide a theoretical reference for solving conflict problems of Petri nets.

Key words: Petri nets, conflict set problem, NP completeness, maximal conflict set enumeration algorithm

中图分类号: