三划分问题可多项式归约为唯一可达向量Petri网可达性问题

为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的三划分问题,三划分问题是扩展的三划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的三划分问题的Petri网模型;证明扩展的三划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明三划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.     

时间与空间局部性强弱的量化方法

为了解决虚拟内存空间的管理问题,基于现有工作集管理算法的参数,提出了时间与空间局部性强弱量化描述的定义、性质以及可行计算方法.该方法时间复杂度小,量化结果反映了程序运行期间工作集的时间与空间局部性的强弱变化.     

结合问题特征利用SE-Tree反向深度求解冲突集的方法

基于模型诊断是人工智能领域内的一个重要研究方向,求解极小冲突集在基于模型诊断中有着重要应用.在对结合CSISE-Tree求解冲突集方法深入研究的基础上,根据冲突集求解特征重构了结合枚举树的计算冲突集的过程,提出基于深度优先反向搜索求解冲突集的方法.针对CSISE-Tree方法求解时占用内存空间与元件总数指数级相关的缺点,构建反向深度搜索方法减小求解时所占用内存空间;针对CSISE-Tree方法不能对部分非极小的冲突集进行剪枝的问题,给出对非冲突集和更多非极小的冲突集进行剪枝的方法,有效减少了求解时调用SAT(Boolean SATisfiability problem)求解器的次数;实验结果表明,与CSISE-Tree方法相比,本文提出的方法求解效率有明显的提升,并避免了求解时的内存爆炸问题.     

基于遗传算法进化业务冲突检测规则的研究

完备和正确的检测规则是业务冲突管理器在线检测冲突时提高检测率的关键.该文借鉴遗传算法的随机搜索能力提出一种冲突检测规则进化算法,通过加入已知冲突信息的指导和以概率递减选择新业务参与变异的方式提高系统进化速度,对检测规则集进行优化降低系统时间和空间复杂度.实验证明此算法提高了系统检测率.     

利用冲突信息降维的进化高维目标优化算法

进化多目标优化算法求解高维目标优化问题面临收敛能力、计算复杂度、决策以及Pareto前沿的可视化等困难，其根本原因是目标空间维数高。目标降维通过丢弃冗余目标，为缓解高维目标优化求解困难提供一种新思路。本文提出利用冲突信息降维的分解进化高维目标优化算法（CIOR-MOEA/D）。该方法通过衡量目标在近似解集上体现的冲突性，构造问题的冲突信息矩阵，对该矩阵进行特征分析，确定目标的重要性程度，实现维数约简，并利用分解进化多目标优化算法（MOEA/D）对重要子目标集合进行分解进化,从而得到问题的近似解集。实验结果表明,本文提出的目标降维算法在降维的准确性与鲁棒性上均表现突出，能够有效地处理冗余高维目标优化问题。      

使用SAT求解器产生所有极小冲突部件集

 产生所有的极小冲突部件集为基于模型诊断中的一个重要步骤.本文将待诊断系统的行为模型及观测分别使用合取范式(CNF)形式的文件描述,从而提出将判定系统组件子集是否为冲突集的问题转化为:首先提取相关组件的CNF模型及观测,然后调用成熟的SAT求解器判定可满足性.随后,通过有效地结合CSISE-tree等方法来产生所有的极小冲突集.为进一步提高效率,给出了充分利用系统输入/输出结构信息的启发式策略.实验结果表明,使用结合SAT求解器及CSISE-tree等方法能够较快产生所有极小冲突集,并且启发式策略使得求解效率进一步提高(平均提高约21%,最高者甚至达到约48%).     

递归建立HS-树计算最小碰集

在基于模型的诊断中，广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS－树，HST－树，BHS－树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS－树（Recursive hitting set-树，简记为RHS－树）计算最小碰集的方法，在空间复杂性与时间复杂性上能够满足大多数诊断系统中的要求。     

OTN/ASON波长冲突与解决方案研究

分析了基于OTN的ASON（OTN/ASON）波长冲突产生的原因；以4网元OTN/ASON为例，对由于资源占用导致的波长冲突进行了详细阐述，并进行了实验验证；初步提出了一种基于GMPLS协议的波长自动转换算法，以解决OTN/ASON的波长冲突问题。     

SAT问题中隐蔽集求解的改进

隐蔽集(backdoor sets)作为隐藏结构的一种,能有效地提高难求解问题的求解效率,近年来成为人们研究的热点.隐蔽集中变量的赋值能有效减少SAT问题求解的搜索分支,从而减少问题求解的时间复杂度和空间复杂度.为提高SAT问题的求解效率,提出一种求解SAT问题隐蔽集的改进算法,并给出最小隐蔽集的定义.在该算法中加入启发式,使求解出的隐蔽集变量个数较少,最后给出隐蔽集问题的总结和展望.     

基于极小独立支配集的MANET虚拟骨干网算法

对规模较大、移动较频繁的MANET(Mobile Ad hoc Networks),用独立支配集构建虚拟骨干网,克服骨干节点之间必须维护连通性的问题,使得拓扑变化较快时骨干网的重构能快速实现;利用极大独立集的求解得到极小独立支配集,并给出基于该支配集的虚拟骨干网数学模型及算法;通过仿真验证算法的有效性、低复杂度和自恢复能力.     

OFDM中继系统中能效优化的资源联合分配算法

在协作正交频分复用系统中,合理的资源分配对于提高系统性能具有重要的意义。针对中继、子载波和功率的联合分配,对最大化系统能效为目标的分配算法进行研究,提出了一个最低容量限制下的最大能效次优化资源联合分配算法(JRAA,joint resource allocation algorithm)。该算法使用冲突图表示系统资源冲突关系,根据冲突图的最大独立集结果进行资源分配。经过仿真验证,该资源分配算法实现了中继一子载波和功率的联合分配,在能效性能方面优于现有的算法。     

基于回溯的最大频繁项集挖掘算法

针对Apriori类算法多次扫描数据库和FP-tree类算法需要构建大量条件模式树的问题,文中提出了挖掘最大频繁项集的GBMFI算法。采用垂直格式存储事务数据库,以枚举树为基础,利用子集非频繁性质和父子节点支持度信息在搜索过程中对枚举树进行剪枝,最终得到最大频繁项集。通过实验对比,结果证明了算法的有效性,尤其适用于稀疏数据集。     

在线multicast数据传输网络中的一个优化问题

首先建立了数据传输网络选择的最小成本模型，给出了有效支撑树代表集的概念，并给出了一个时间复杂性为D(mlogen)的算法产生代表集。然后对静态数据传输问题和在线数据传输问题，分别给出了一个时间复杂性为D(mlogen)和O(m^2 mlogen)的多项式时间的算法。     

Stochastic Petri nets: Properties, applications and tools

This paper presents a survey on stochastic Petri nets. A stochastic Petri net is first and foremost a Petri net, whose places represent resources and transitions represent operations. Random time variables attached to transitions are associated with random operation durations. The stochastic behavior must be completely defined by a set of rules associated with the choice of the next transition to be fired in a given marking, the memory properties of the time already spent for a given operation. We introduce some of the main stochastic Petri nets classes, and we give theoretical results associated with conservation properties, ergodic properties and computational methods leading to exact and approximated solutions. From a practical point of view we present the modeling example of a bus allocation and existing software tools.     

平面凸多边形斜支撑线求解的最佳算法

平面凸多边形斜支撑求解是计算几何中诸多问题的一个核心算法。至今，求解该问题的最好算法的时间复杂度为Ｏ（ｎ＋ｍ）。本文在七妙利用凸多边形特殊性质的基础上，给出了一时间复杂度为Ｏ（ｏｌｇ（ｎ＋ｍ）的最佳算法，从而彻底解决了这一问题。     

基于活跃集的支持向量机切平面法

切平面法作为求解非光滑凸优化问题的典型方法,在支持向量机问题的求解中得到了广泛的应用.但是该算法在求解过程中往往会出现不稳定的情况.针对这一不稳定性,前人提出了优化切平面法,通过在切平面法中加入线搜索环节来确保目标函数单调下降.但是优化切平面法的运算复杂度比较高,不适合训练数据量大、对训练速度要求高的应用.本文提出了一种基于活跃集的优化切平面法,在计算目标函数和进行线搜索时,只单独处理活跃集内的样本,将其它样本当作一个整体来进行处理.相对于传统的优化切平面法,本文方法只需在一部分样本上计算目标函数和进行线搜索,从而可以在不损失求解精度的前提下节省求解时间.     

基于直觉模糊Petri网的知识表示和推理

针对模糊Petri网存在隶属度单一的问题,将直觉模糊集理论与Petri网理论相结合,构建直觉模糊Petri网(Intuitionistic Fuzzy Petri Nets,IFPN)模型,用于知识的表示和推理.首先构建了IFPN模型,并将其应用于知识的表示,通过在模型中引入抑止转移弧,解决了否命题的表示问题.其次提出了基于矩阵运算的IFPN推理算法,通过修改变迁触发后token值的传递规则,解决了推理过程中的事实的保留问题;通过修改变迁的触发规则,抑制了变迁的重复触发.最后对推理算法进行了分析,并举例验证了提出的IFPN模型及其推理算法的可行性,结果表明IFPN是对FPN的有效扩充和发展,其对推理结果的描述更加细腻、全面.     

A Divide-and-Conquer Strategy to Deadlock Prevention in Flexible Manufacturing Systems

Petri nets are a popular mathematical tool to investigate the deadlock problems in resource allocation systems. As an important problem solution paradigm in computer science, the divide-and-conquer strategy is used in this paper to investigate the deadlock prevention for flexible manufacturing systems (FMSs) that are modeled with Petri nets. Based on the concept of resource circuits, a plant net model is divided into an idle subnet, an autonomous subnet, and a number of small but independent subnets, called toparchies, from the viewpoint of deadlock control. A liveness-enforcing supervisor, called toparch, is designed for each toparchy. If a particular separation condition holds in a plant net model, the computational complexity of toparches is significantly reduced. This research shows that the resultant net, called monarch, by composing the toparches derived for the toparchies can serve as a liveness-enforcing Petri net supervisor for the whole plant model. FMS examples are given to illustrate the proposed method.