基本信标计算的一种快速算法  

Effective algorithm for obtaining a set of elementary siphons

作　　者：王安荣[1] 李志武[1] 

机构地区：[1]西安电子科技大学机电工程学院,陕西西安710071

出　　处：《西安电子科技大学学报》2008年第4期632-638,共7页Journal of Xidian University

基　　金：国家自然科学基金资助(60474018;60773001);教育部归国留学人员科研基金资助(2004-527);教育部归国留学人员实验室基金资助(030401);国家高科技发展规划863计划资助(2008AA04Z109)

摘　　要：提出一种基于二分法搜索原理计算基本信标的高效算法.如果网的特征T-向量矩阵非行满秩,则将其按行一分为二.以同样的方法处理新得到的子矩阵,直至得到的子矩阵行满秩,则该矩阵对应的信标全为基本信标.以这些基本信标为基础,递归搜索其余子矩阵,最终得到全部基本信标.该算法与顺序搜索法相比较,矩阵求秩的次数大为减少.对Petri的一个子类——一个拥有资源的简单加工进程的线性系统(LS3PR)网系统来说,该算法是一个多项式算法,并通过一系列算例验证了该算法的效率.Elementary siphons are computationally expensive when the size of a Petri net is large. Based on binary search, this paper proposes an efficient algorithm for finding a set of elementary siphons. If the characteristic T-vector matrix of a net is not of row full rank, the matrix is divided into two sub- matrices. This step is repeated until a row full rank sub-matrix is found. The siphons corresponding to the sub-matrix are elementary. Based on these elementary siphons, other elementary siphons can be accordingly found by recursive search in the sub-matrices. This algorithm ensures that the number of times of calculating the ranks of matrices is greatly reduced compared with the traditional sequential search method. For the linear simple sequential process with resources （LS^3PR）, it is polynomial. Finally, the efficiency is demonstrated by case study.

关 键 词：PETRI网 一个拥有资源的简单加工进程的线性系统 二分法搜索 基本信标 

分 类 号：TP271.8[自动化与计算机技术—检测技术与自动化装置]