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

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

MBD在数字电路故障诊断中的应用研究

提出了一个将MBD(基于模型的诊断)方法用于数字电路故障诊断的应用方案,并对该方案所涉及的最小冲突集候选搜索算法、冲突识别策略以及最小碰集算法的选择等进行了讨论。最后,以一个经典的数字电路故障诊断为例,同时结合数字电路的一组故障观测数据,对该数字电路发生的故障做了故障诊断实验。     

最小代价多播生成树的快速算法

本文针对MPH（Minimum Path Cost Heuristic）等多播最小生成树算法存在的问题，通过改进最短路径节点的搜寻过程，以较小的存储空间为代价，获得了计算效率很高的快速最小代价多播生成树算法FMPH（Fast Minimum Path Cost Heuristic），且获得多播生成树与MPH算法完全相同，随机网络模型的仿真结果表明：FMPH算法快速、稳定，是一种值得推广使用的高效算法。     

求解多目标最小生成树的一种改进的非支配排序遗传算法

在改进的非支配排序遗传算法(NSGA-Ⅱ)的基础上,提出了一种基于生成树边集合编码求解多目标最小生成树问题的进化算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明:对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于边集合编码的进化算法在求解效率和解的质量方面都优于基于Pr(?)fer编码的进化算法。     

极小碰集求解算法的性能分析与比较

基于模型的诊断为人工智能领域中一个重要的研究分支,极小碰集即候选诊断的求解过程极大影响最终的诊断效率.本文关注当前主要的极小碰集求解算法,简要介绍了它们的基本思想,从算法描述和实例比较了它们的异同和复杂性,并设计实现了一个统一的实验平台,测试并比较了它们的实际执行效率,为实际选择合适的算法提供了重要参考依据.     

通信网络架设中最小生成树问题的一种新算法

本文在Prim算法的基础上,结合最优二叉树的思想,提出了一种新的计算方法,将最小生成树的生成过程划分为几个连通子图的最小生成树生成过程,从而显著的提高算法效率。     

VLSI总体布线算法研究与实现

总体布线是布图设计中一个极为重要的设计环节。本文提出了基于可分离最小生成树(SMST)的优化L形直角斯坦(Steiner)树(L_RST)和优化Z_RST的算法。该算法实现上绕开计算重合度问题，以新的角度计算代价。利用基于tile的结构，实现了伪管脚(pseudo pin)的分配，适用于现代多层布线需求。最后文章研究了同时考虑串扰和时延的综合性能驱动的总体布线算法改进。     

基于直角Steiner树的片上网络互连算法

提出了一种基于最小直角Steiner树,在Manhattan平面上避免障碍物的互连算法,以实现片上网络中各IP核的互连.该算法在定制NoC中将Steiner树的生成算法用于互连设计.算法首先在初始阶段对有障碍两点间的边权重重新赋值,然后调用最小生成树算法,使生成的直角Steiner树总长度最小.实验表明,该算法可以使片上网络的总连线缩短.     

N个城市间的最经济的网络建设

N个城市闾有多种的网络建设方案,本文使用最小支撑树的原理,运用算法中的普林算法进行运算。褥到的最小生成树使n个城市闻的连接是连通的,而且是最经济的在各种网络建设方案中。     

结合特征学习的粒子群求解极小碰集方法

基于模型诊断中的极小碰集问题是人工智能领域的一个重要课题,现实中很多实际问题都可以转化为极小碰集问题,如老师与课程问题,极小覆盖集问题等.通过对极小碰集问题特征的研究,本文结合粒子群优化求解极小碰集的算法提出了一个新的算法,来指导极小碰集的求解:引入学习机制,减少极小碰集求解中对无解空间的搜索;加入翻转策略,来加速极小碰集有解空间中的求解.实验结果表明本文提出的算法在求解极小碰集问题上的效率有明显提高.     

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

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

几何基元的提取方法

基元提取在基于模型的计算机视觉中起着重要的作用。基元抽取问题可以归结为优化问题,即寻找代价函数的全局最小值。利用统计方法对最小子集进行随机抽样,大大减少了对最小子集的评价。同时引入了参数向量列表,并提出了一种新的代价函数,用于对基元的参数向量进行评价,使计算量减少、抽取精度提高。该方法可以用于多个基元的提取。分析实验结果表明,该方法能快速、准确地提取集合基元。     

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

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

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

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

THE RANKS OF CYCLIC AND NEGACYCLIC CODES OVER THE FINITE RING R

The ranks of cyclic and negacyclic codes over the finite chain ring R as well as their minimal generating sets are defined, and then the expression forms we presented by studying the structures of cyclic and negacyclic codes over the finite chain ring R. Through the paper, it is assumed that the length of codes n can not be divided by the characteristic of R.     

CYCLIC CODES OVER THE RING Zp2 OF LENGTH pe

The study of cyclic codes over rings has generated a lot of public interest. In this paper,we study cyclic codes and their dual codes over the ring Zp2 of length pe,and find a set of generators for these codes. The ranks and minimal generator sets of these codes are studied as well,which play an important role in decoding and determining the distance distribution of codes.     

基于网络编码的无线网络多流问题研究

多流问题研究多对源、宿节点之间所能达到的最大吞吐。在无线网络中,解决该问题的关键在于量化无线干扰。由于网络编码能够在一定程度上克服无线干扰的影响,因此通过使用超边来描述编码发送,并构造关于超边的冲突图,可以实现对网络编码条件下无线干扰（以协议干扰模型为例）的量化,进而解决网络编码条件下的多流问题。此外,针对在超边冲突图中搜集所有极大独立集的NP难问题,提出了一种实用的搜集算法,并给出了相关的数字结果。     

网络端端可靠度的上下界计算研究

考虑精确计算较大规模网络的端端可靠度属于NP—hard问题,提出一种计算网络端端可靠度的近似方法,算法分别基于最小路集和不交最短路集来计算网络端端可靠度的上下界,并在此基础上给出了示例来阐明算法的有效性,该计算方法的算法实现简单,能快速计算出网络的端端相对可靠度。