共查询到18条相似文献,搜索用时 98 毫秒
1.
2.
分析了已有求覆盖平面上给定的若干个点的尽可能小的圆的问题的算法。给出了一个新的求解最小覆盖问题的算法,其计算时间复杂度为平面上给定的点数量的线性函数,该算法已编程实现,通过几万例随机算例的实际计算比较,表明算法所得结果的平均精度比已有的各种快速近似算法所得的精度要高,而且具体每例所需的计算时间均比已有快速近似算法对应的计算时间要短。 相似文献
3.
求一般图的最小顶点覆盖集问题的混合贪婪算法 总被引:1,自引:0,他引:1
现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充. 相似文献
4.
本文详细研究了模板依赖的公理系统,完成了有效性和完备性证明,提出了模板依赖集的闭包计算、求最小覆盖集的算法。 相似文献
5.
最小基数箱子覆盖问题及其启发式算法 总被引:2,自引:0,他引:2
研究了一个新颖的装箱问题,即最小基数箱子覆盖问题(Minimum Cardinality Bin Covering Problem),证明了该问题是强NP-完备的;在物件大小满足一定的条件下,给出了一个时间复杂度为O(n)的启发式算。 相似文献
6.
降低能耗以延长网络生存时间是无线传感器网络设计中的一个研究热点.提出一种利用遗传算法实现的"密度控制"策略.该策略利用无线传感器工作节点的最小节点子集(最小覆盖集),达到覆盖整个传感器网络区域的目的.所提出的算法能够较好地调和无线传感器网络寿命和网络覆盖率之间的矛盾,仿真实验证明了算法的有效性. 相似文献
7.
提出一种基于神经网络求解逻辑综合中最小造价覆盖问题的优化算法。首先给出了最小造价覆盖问题与能量函数的映射关系,并以此构造了改进的两级Hopfield网络模型。然后利用该网络的动态特性,求出最小造价覆盖问题的最优解。最后对算法进行了分析和小结。 相似文献
8.
给出了利用命题逻辑公式的析取范式和主析取范式求图的全部极小覆盖和最小覆盖以及全部极小边覆盖和最小边覆盖的一般算法. 相似文献
9.
在有限域上多元非线性方程的解集可以是任意向量集,在该向量集所属的空间上如果找到最小数量的陪集,并覆盖该向量集,那么用这组陪集来线性化该方程成为了可能。文章提出了在多元非线性方程的解集中算出陪集的算法以及最小陪集覆盖的算法,并给出了独立试验的结果。 相似文献
10.
点覆盖问题是一个著名的NP完全问题.本文对广义Petersen图P(n,2)的精确最小点覆盖数进行研究,讨论并证明了广义Petersen图P(n,2)的最小点覆盖数,给出了最小点覆盖集的构造方法. 相似文献
11.
周培德 《北京理工大学学报》2005,25(4):332-336
提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2). 相似文献
12.
低维复射影空间中的全实极小子流形 总被引:3,自引:0,他引:3
孟君 《徐州师范大学学报(自然科学版)》2005,23(3):41-44
研究了复射影空间CP^6中6维全实极小子流形,利用6维紧致黎曼流形的Euler数及Green定理,计算曲率张量R和Ricci张量Rij的模的平方,得到了数量曲率的拼挤常数,讨论了其局部结构. 相似文献
13.
14.
寻求多边形链顶点凸壳的算法 总被引:6,自引:0,他引:6
提出一种计算简单多边形链顶点凸壳的算法,基本思想是分段计算,在每段的计算中,先分4种不同情况计算出边链L1,然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列,构成边链L2,最后对L2进行倒查,删去非凸壳顶点,剩下的点即凸壳顶点,该算法不仅易于实现,而且其时间复杂性是线性的。 相似文献
15.
16.
定义了网络连结矩阵的两个变换,引入了L满秩矩阵与L非满秩矩阵的概念·证明了这两类特殊矩阵与网络连通性的关系·利用这一关系和定义的两个变换,给出了求网络极小割集以及与极小割集对应的结点集合的递推公式;建立了一个求网络所有极小割集及与之对应的结点划分集合的有效算法·算法只需对网络的连结矩阵进行处理,在计算机上实现起来很方便·最后通过实例说明了算法的有效性· 相似文献
17.
几种快速排序算法实现的比较 总被引:3,自引:0,他引:3
胡云 《安庆师范学院学报(自然科学版)》2008,14(3)
快速排序是一种基本的排序思想,但实现方法有多种。通过对几种实现方法的比较,发现在一般情况下,它们执行的时间复杂度都为O(nlog2n),但它们的实现方法有一些不同,这也决定了它们在具体的执行时间上存在一些差别。了解这些差异,有利于在解决问题时选择最佳的方法。 相似文献
18.
周培德 《北京理工大学学报》2003,23(5):576-580
提出求解3-中心问题、4-中心问题、5-中心问题及k(<10)-中心问题的算法.设计该算法的依据是覆盖点集的凸壳必覆盖点集.算法首先判定点集凸壳的形状,然后确定k个圆的排列方式,最后以确定方式计算圆心位置.证明了算法的正确性并且分析了算法的复杂性. 相似文献