共查询到20条相似文献,搜索用时 187 毫秒
1.
传感器网络中基于Voronoi网格的快速覆盖判定算法 总被引:1,自引:0,他引:1
覆盖问题是传感器网络研究中的一个基础课题,判定感兴趣的区域是否被一组给定的传感器节点完全覆盖,在监控等传感器网络的许多应用领域中具有重要意义。提出了一种传感器网络中基于Voronoi网格的快速覆盖判定算法VT-RCDA(Voronoi Tessellation based Rapid Coverage Decision Algorithm)。算法首先将感兴趣的区域进行正方形网格剖分,然后采用Voronoi网格模型将复杂的区域覆盖问题转化为简单的顶点覆盖问题。理论分析与仿真实验表明,与已有算法相比,新算法具有较好的覆盖判定正确率,较低的计算复杂度,且针对具有n个节点的传感器网络,能在O(nlogn)的时间开销内快速判断出任意给定感兴趣区域能否被这n个传感器节点覆盖。 相似文献
2.
覆盖问题是传感器网络研究中的一个基础课题,如何判定某个感兴趣的区域是否被一组给定的传感器节点覆盖,在传感器网络的许多监控应用领域中具有重要意义。提出了一种传感器网络中基于正三角形剖分的快速κ-覆盖判定算法和最大κ-覆盖问题的求解算法,新算法首先把感兴趣区域剖分为正三角形区域,从而将复杂的区域覆盖问题转化为简单的正三角形区域覆盖问题。理论分析与仿真实验表明,针对具有n个节点的传感器网络,新算法的计算时间复杂度为O(n),低于已有算法O(nlogn)的计算时间复杂度。 相似文献
3.
并行加工经济批量问题的最优算法 总被引:1,自引:0,他引:1
考察了 n - period经济加工批量问题并给出一种复杂度 O(mnlogn )的优化算法 .对于无能力约束的动态经济加工批量问题 (Wagner- Whitin问题 ) ,最早由 Wagner和 Whitin(195 8)提出 ,并给出一个基于动态规划 ,复杂度为 O(n2 )的算法 .最近 ,有许多人重新对该问题进行了研究 ,并以多种方式给出了复杂度为 O(nlogn )的算法 .本文在以上研究的基础上 ,针对柔性加工多机并行加工情况 ,给出了一种复杂度为 O(mnlogn )的 Wagner- Whitin问题的解法 . 相似文献
4.
针对具有大型解空间的多目标决策问题,为进一步提高多目标决策的效率,快速且有效的非支配解集构造方法值得探究.给出非支配关系性质、初始非支配解集(简称初集)及非支配解集构造的有关定义与定理.在此基础上,依据有序集理论与运算规则,提出基于初集排序方法的Pareto非支配解集构造算法.该算法应用集合排序的方法,对有序的可行解集与有序的非支配解集进行比较,获得多目标决策问题的最优解.构建不包含初始非支配解的有序可行解集,设计非支配解排序规则、查找规则与插入规则.分析提出的算法及常见的非支配排序方法的时间复杂度.通过ZDT1~ZDT3、DTLZ1与DTLZ3测试函数的非支配解集构造实验,与王芳等(2016)提出的NTCM等方法相比,证明提出的非支配解集构造算法是有效的,时间复杂度更低,非支配解集构造时间具有显著的优势. 相似文献
5.
6.
7.
支持矢量机(SVM)是一种两类分类器,而支持矢量数据描述(SVDD)是一种单类数据分类方法,通过在特征空间寻找包含某类样本的最小超球体来对样本分类,该方法只需已知某类数据即可构造分类器.但是在SVDD方法中,直接根据超球体构造的分类器对样本数据正确识别能力不高.针对这个问题,根据样本在特征空间中到各个超球体球心的距离构造了样本属于各-个类别的模糊隶属度函数,提出了FSVDD多目标识别方法.在FSVDD的训练过程中采用了乘性迭代规则的快速优化算法,该快速算法降低了优化的复杂度和缩短了优化时间.在针对不同类型数据集的识别实验中,证明了提出的FSVDD多目标识别算法具有训练速度快、识别率高的优点,有很强的实用性. 相似文献
8.
在硬实时系统中,由于任务超时完成将会导致灾难性后果,因此硬实时系统必须具有实时性和可靠性保障。为了提高硬实时系统的容错能力,基于回卷恢复模型提出了允许容错优先级提升的分配策略。为了获得系统中容错优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的容错优先级配置搜索算法(fault tolerant priority configuration search algorithm, FTPCSA)。该算法能够将搜索空间由O(n!)减少到O(n2)。最后给出了该算法的最优性证明。经过深入分析和实验证明,允许容错优先级提升的分配策略能够在容错优先级继承策略的基础上,进一步提高系统的容错能力 相似文献
9.
10.
针对基于压缩型扩展卡尔曼滤波(CEKF)的SLAM算法在状态增广和地图管理两方面的不足,提出了一种改进算法(ICEKF算法).读算法通过增广辅助系数矩阵即可快速完成状态增广,计算复杂度由O(N2)降低为O(NA),其中N和NA分别为全局和局部地图中的路标数.在地图管理上,ICEKF算法采用一种基于欧氏距离的局部地图动态选择方法,避免了CEKF算法对全局地图进行预先划分带来的路标分配等问题.仿真表明ICEKF算法在估计结果上与EKF算法具有一致的最优性,与CEKF算法相比计算量大大降低. 相似文献
11.
并行广义预测自校正控制器(GPC) 总被引:1,自引:1,他引:0
本文旨在讨论GPC算法[1,2]的并行化问题,通过对原串行算法的数据流及数据相关性的分析,得到了一种三角阵列的并行算法。该算法自然导致Systolic结构,并具有良好的数值稳定性。对于一个 n阶系统而言,本算法采用O(n2)阶的处理器单元互连成三角阵列,可以把计算时间由原来的O(n3)阶(内积运算)时间提高到 O(n)阶,因而具有 O(n2)的加速比,其处理器的利用效率得到了很大提高。 相似文献
12.
提出了一种易于脉动阵列实现的平方根椭球状态定界算法。算法将椭球形状矩阵的平方根进行递推计算,使得计算的数值稳定性得以提高。由于平方根算法具有矩阵与矩阵以及矩阵与向量的运算形式,因而适合在并行处理器上执行。为了并行计算,给出了实现此平方根算法的脉动阵列结构。计算复杂性分析显示,若系统状态维数为n,串行计算的计算复杂度至少为O(n3),而并行计算的计算复杂度降为O(n)。仿真结果验证了本方法的有效性。 相似文献
13.
HOU Sixiang 《系统科学与复杂性》1997,(2)
1.IntroductionTheF3Cm..canbestatedasfOllows.Eachofthenjobs1,2,'')nistobeprocessedonthreemachinesA,B,Cinthesameorder.Giventheprocessingtimesal?hiandciofjobionmachinesA,BandC,findtheorderinwhicheachmachineshouldprocessethejobssoastominimizingthetotaltimesp… 相似文献
14.
Mobius立方体是超立方体的一种变形结构。Mobius立方体除了具有超立方体本身的可扩展性和路由简单等优点外,它与含有相同数目的点和边的超立方体相比具有更好的性能。文中提出一种新的用于Mobius立方体网络的最短路径路由算法,避免了递归调用。分析和实验证明,相对于Cull P提出的最短路径算法有更高的效率,并易于硬件实现,且时间复杂度为O(n)。 相似文献
15.
旅行售货员位置问题在组合优化中是非常困难的问题之一,由于它的困难(它涉及到族行售货员问题和位置问题双重问题)这个问题一直引起人们极大关注,然而多于一人的旅行售货员问题还没有去探讨。本文提出一个复杂度为O(n4)的算法解决直线上的双旅行售货员位置问题 相似文献
16.
New Mehrotra's second order predictor-corrector algorithm for P_*(κ) linear complementarity problems
It has been shown in various papers that most interior-point algorithms for linear optimization and their analysis can be generalized to P*(κ)- linear complementarity problems. This paper presents an extension of the recent variant of Mehrotra’s second order algorithm for linear optimijation. It is shown that the iteration-complexity bound of the algorithm is O(4κ + 3)√14κ + 5 n log (x0)Ts0 ε , which is similar to that of the corresponding algorithm for linear optimization. 相似文献
17.
An optimal scheduling algorithm based on task duplication 总被引:1,自引:0,他引:1
Ruan Youlin Liu Gan Zhu Guangxi & Lu XiaofengNational Laboratory of Optoelectronics Huazhong University of Science Technology Wuhan P. R. China 《系统工程与电子技术(英文版)》2005,16(2)
1.INTRODUCTION Anefficientschedulingofaparallelprogramontothe processorsisvitalforachievingahighperformance fromaparallelcomputersystem.Thetaskduplication basedschedulingisanewapproachtothescheduling problems.Sincethecommunicationtimeamongtasks assignedtothesameprocessorisconsideredtobe negligible,taskduplicationisonewayofreducingthe interprocessorcommunicationoverhead.Usingthis approach,someofthemorecriticaltasksofaparallel programareduplicatedonmorethanoneprocessor.Thiscanpotentiallyred… 相似文献
18.
19.
将多平台分布式的IMM_Kalman(DIMM_Kalman)算法和IMM_JPDA(DIMM_JPDA)算法相结合,得到改进的DIMM_JPDA(DIIMM_JPDA)算法。在DIIMM_JPDA算法中,每个平台都有自己独立的IMM算法跟踪系统,每个IMM算法中都采用Kalman/JPDA滤波器,全局的滤波值由各平台的滤波值融合而成。然而在全局融合中,由于协方差矩阵可能出现奇异,导致计算的不稳定性或出现严重异常。为了克服上述问题的缺点,引入了特征值扰动方法,使该协方差矩阵变成非奇异矩阵。仿真实验表明改进的DIIMM_JPDA算法比DIMM_JPDA算法有更小的误差。 相似文献
20.