文献类型：期刊文章

作　　者：潘理[1] 郑红[2] 刘显明[3] 杨勃[1]

机构地区：[1]湖南理工学院信息与通信工程学院,湖南岳阳414006 [2]华东理工大学信息科学与工程学院,上海200237 [3]江西省电力公司信息通信分公司,江西南昌330077

出　　处：《电子学报》

基　　金：国家自然科学基金(No.61473118);湖南省教育厅科学研究重点项目(No.15A079);湖南省科技计划项目(No.2014GK3026);江西省电力公司科技项目(No.5218351400A1)

年　　份：2016

卷　　号：44

期　　号：8

起止页码：1858-1863

语　　种：中文

收录情况：BDHX、BDHX2014、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2015_2016、EI(收录号：20163402737331)、IC、JST、RCCSE、RSC、SCOPUS、ZGKJHX、核心刊

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

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

分 类 号：TP301]