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

• 作者: 刘显明 杨勃 潘理 郑红
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: Petri网 冲突集问题 NP(Non-deterministicPolynomial)完全性 极大冲突集枚举算法
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 学术论文
• 页码范围: 1858-1863
• 页数: 6页
• 分类号: TP301
• 字数: 6283字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2016.08.013

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘理	湖南理工学院信息与通信工程学院	37	171	8.0	11.0
2	郑红	华东理工大学信息科学与工程学院	25	70	6.0	7.0
3	刘显明		8	54	4.0	7.0
4	杨勃	湖南理工学院信息与通信工程学院	27	63	4.0	6.0