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

grand

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

2021-3-22 09:03 上传

点击文件名下载附件
下载积分: 威望 -5

: x6 A* W/ h4 f5 Q! V6 K& \( T

dull

Petri网局部性的极大冲突集枚举算法，收藏了。