擂台赛

给定n个点在直角坐标系下的坐标,(x_1,y_1),(x_2,y_2)…(x_n,y_n)。请编一程序求出包含所有n个点的最小圆。即所求的圆满足: (1)面积最小; (2)n个给定的点只能在圆上或圆内。 要求:n个点的坐标由键盘输入,程序输出所求圆的圆     

最小覆盖算法及正确性证明

本文中的最小覆盖问题是指用一个圆覆盖平面上的若干个点。本文给出了求近似最小覆盖圆的最大距离算法。估计了它与最小覆盖圆的误差上界为1/2(4-2 3~(1/2)m)~(1/2)(m表示最大距离),并运用谓词归约方法证明了算法的正确性。     

WSN中有效的最小单位圆集覆盖算法*

针对具有不同传输半径的无线传感器网络覆盖与广播数据转发问题,提出了一种以最小单位圆覆盖集作为广播数据转发集的算法。该算法能有效计算出覆盖范围的轮廓集,具有最优的时间复杂度O(n log n)。对每个节点,该算法以其最少数量的邻居节点子集实现所有邻居节点的覆盖,并证明了该算法找到的最小单位圆覆盖集与其轮廓集是相等的。详细的仿真实验及与现有算法的比较表明,提出的覆盖算法不仅以最少数量的节点实现了网络覆盖与广播数据转发,同时延长了网络生命期。     

双域单向水平倾角最小化圈绕凸壳新算法

本文依据同构化凸壳构造基本定理,提出了效率更高的双域单向水平倾角最小化圈绕二维点集凸壳新算法,实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是：1）“初始顶点与双域生成”处理：找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点（若有多个最小点,则只取最左的最小点）和Y轴坐标值最大点（若有多个最大点,则只取最右的最大点）,作为凸壳逆时针圈绕的初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左。2）进行单向“圈绕寻找下一新顶点”：A）在S右内,过逆向次新顶点作X轴正向射线,并找出当前子点集内对该逆向次新顶点正向射线（为始边的）倾角最小的点,此最小点即为S右逆向最新顶点;B）在S左内,过次新顶点作X轴负向射线,并找出当前子点集内对该逆向次新顶点负向射线（为终边的）倾角最小的点,此最小点即为S左逆向最新顶点。3）删除对已得各项点所构成的子凸壳各内点。4）仅当所剩当前点集非空时才从“2）”继续作逐边双域单向圈绕。     

高维空间球体的k-中心聚类问题

本文提出了高维空间球体的k-中心聚类问题。该问题是指对高维空间中多个球构成的集合B,构造是个球来共同覆盖B中所有已知的球,并使k个球中的最大半径最小。本文从B中有选择地取出一部分球构成集合s,称其为B的核心集,并利用该核心集,对给定ε给出了高维空间球体k-中心聚类问题关于球数n和维数d的多项式时间1-ε近似算法。而且,S中球的个数为O（1／ε^2）,与B中球的个数和空间维数无关。     

覆盖平面点集的最窄圆环

给出判断一个覆盖平面有限点集的圆环达到最窄的一组充分条件，同时指了对于一般的平面有限点集而言其中的一个条件是不可放弃的，这个结果对于解决所谓圆度问题不仅有理论价值，而且有实际实际意义。     

单域双向水平倾角最小化圈绕凸壳新算法

依据同构化凸壳构造基本定理,提出了效率更高的单域双向水平倾角最小化圈绕二维点集凸壳新算法,它实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新.本新算法的同构化特点是：1）找出给定二维点集的最低点,即Y轴坐标值最小点（若有多个最小点,则只取最左的最小点）,并作为凸壳逆向（即逆时针）圈绕、顺向（即顺时针）圈绕的共同初始顶点（即最低顶点）.2）双向圈绕寻找最新顶点（即凸壳的下一组逆向、顺向最新顶点,而该组最新顶点＂初始组必为一个,最末组方可一个,其余组总为一对＂ ）：A.过逆向次新顶点作X轴正向射线,并找出当前点集内对该逆向次新顶点正向射线（为始边的）倾角最小的点,此最小点即为当前逆向最新顶点;B.过顺向次新顶点作X轴负向射线,并找出当前点集内对该顺向次新顶点负向射线（为终边的）倾角最小的点,此最小点即为当前顺向最新顶点.3）删除对已得各顶点所构成的子凸壳各内点.4）仅当所剩当前点集非空时才从＂2）＂继续作逐边双向圈绕.     

机场噪声监测无线传感网络最小连通覆盖集研究

针对机场噪声监测无线传感网络中的最小连通覆盖集问题,设计了一种基于目标区域Voronoi划分的集中式近似算法,用于分析完全覆盖目标区域所需的最低要求的节点集;为了更好地调整噪声监测节点的感知半径Rs与通信半径Rc的比值关系,在通信半径小于两倍感知半径时,提出了一种基于最小生成树的连通算法用以确保CVT算法构造的覆盖集连通所需的辅助节点。理论分析与仿真实验表明,与现有常用的集中式贪婪算法和DVC算法相比,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小等两方面都较优。     

一类最短网络

为了提高计算机的运算速度和集成电路的集成度,对大规模集成电路芯片连线优化问题的一个重要数学模型-Steiner最小树结构的研究从60年代起便引起人们的关注.设X是平面任一有限点集内接于X的最小网络称为X上的Steiner最小树,记作SMT(X).其上不仅有属于X的结点,还有不属于X的结点(Steiner点).已知在一般平面点集X上构造Steiner最小树的问题是NP-完全问题.自1978年以来,仅有少数在特殊点集上构造Steiner最小树的工作.我们在一种分布在两条平行直线上的点集上构造出Steiner最小树的无穷类.     

布氏硬度自动测量中多圆检测方法

圆检测应用广泛,是布氏硬度自动测量的关键。针对圆检测中存在圆分裂、多个圆、不完整圆的情况,提出一种基于交叉圆合并、凸包点迭代纯化最小二乘拟合的圆检测方法。首先对图像进行纹理增强并二值化,其次提取有效区域的最小外接矩形,并得到圆弧与最小外接矩形的三个切点,得到初始圆,然后合并有交叉的圆。最后求合并圆的轮廓点与其凸包的交集,进行迭代纯化最小二乘拟合,最终得到亚像素级的圆半径值。最后通过实际应用测试,验证了论文方法的有效性。     

离散点集最小包围圆算法分析与改进

针对平面上的离散点集求取最小包围圆的问题,评述现有算法并给出一种 改进算法,称为较远点对定义初始包围圆的增量算法。首先概述了几条对算法理解和设计有 直接影响的最小包围圆性质或判定;然后对求取最小包围圆的随机增量算法、最远点优先渐 近算法、对偶决策算法等3 种典型算法进行概述和简要分析;再对随机增量算法和最远点优 先渐近算法进行改进;最后,以二维区域随机点集、一维共线随机点集和共线有序点集3 类数据进行实验对比。实验结果表明,最远点优先渐近算法是过去3 种算法中效率最高的; 论文提出的较远点对定义初始包围圆的增量算法大大提高了随机增量算法的时间效率,是该 文所列举的方法中最快的算法,并且是一种确定性算法。离散点集最小包围圆的快速计算有 助于碰撞检测和机器人等领域的广泛应用。     

无线网络干扰最小化问题的一种缩边贪心算法

无线传感器网络的最大干扰最小化问题可以被描述为已知平面上◢n◣个点的位置及发射半径的阈值,要求设置发射半径使得任意点被其他点发射范围覆盖的最大数量达到最小。为了有效求解该问题,提出了一种新的贪心算法——缩边算法。不同于已有算法的构图方式,该算法是通过采取缩边的方式构造网络通信拓扑图,并结合了操作系统中批量处理的思想对贪心算法进行了加速,缩短了算法的运行时间。通过实验验证,该算法相比于已有算法在随机产生的算例上能产生更优的解。     

无线传感器网络最小连通覆盖集问题求解算法

降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战.在传感器节点高密度部署的环境中,在保证网络性能的前提下,仅将最少量的节点投入活跃工作状态,而将其余节点投入低功耗的睡眠状态,是一种节约系统能量的有效方法.如何计算同时满足"覆盖要求"(工作节点必须能够完全覆盖目标区域)和"连通性要求"(工作节点组成的通信网络必须是连通的)的最小节点集合,是一个NP难问题.设计了一种基于目标区域Voronoi划分的集中式近似算法(centralized Voronoi tessellation,简称CVT),用于计算完全覆盖目标区域所需要的近似最小节点集.当节点通信半径大于等于2倍感知半径时,CVT算法构造的节点集是连通的;当节点通信半径小于2倍感知半径时,设计了一种基于最小生成树(minimum spanning tree,简称MST)的连通算法来计算确保CVT算法构造的覆盖集连通所需的辅助节点.理论分析和实验数据表明,CVT(+MST)算法的性能在时间复杂性和连通覆盖集大小方面都优于已有的贪婪算法.     

高维空间球集覆盖问题的改进1+ε近似算法

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。     

基于双域双向水平倾角最小化圈绕的凸壳新算法

本文依据同构化凸壳构造基本定理,提出效率更高的双域双向水平倾角最小化圈绕凸壳新算法.本新算法的同构化特点是:1)"初始顶点与双域生成"处理:找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点)和Y轴坐标值最大点(若有多个最大点,则只取最左的最大点),作为凸壳(逆时针围绕的)A向初始顶点、(顺时针圈绕的)B向初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左.2)在S右内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理:分别过自己的最近新顶点,作X轴正向射线,并A向或B向找出当前点集内对该顶点正向射线(为始边的)倾角最小的点;删除对已得各顶点所构成的子凸壳内点,当所剩当前点集非空时继续作"2)"逐边圈绕,直到为空.3)同理,在子点集S左内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理.     

高维空间球集覆盖问题的改进1+ε近似算法

高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/〖KF(〗3〖KF)〗近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε〖SX(〗3〖〗2〖SX)〗(1/ε+d)lg1/ε)。算法保证核心集中球的个数为 O(1/ε),与S中球的个数和空间维数无关。     

基于极坐标测量的圆度误差评定算法

提出一种利用极坐标测量数据求解圆度误差的网格搜索算法,其原理是在最小二乘圆心周围按一定规则布置一系列的极坐标网格点,依次以各网格点为理想圆心计算所有测点的半径值,通过比较这些半径值,实现最小区域法、最小外接圆法和最大内接圆法的圆度误差精确评定。详细叙述了算法求解圆度误差的过程和步骤,给出了数学计算公式及程序流程图。试验结果表明,该算法可有效、正确地评定圆度误差。     

关于覆盖广义粗集的一些基本结果

粗集理论是数据挖掘的一个重要工具,本文研究一类广义粗集,即覆盖广义粗集.主要的结果有:(1)与经典的Pawlak粗集理论相对应的覆盖广义粗集的基本性质;(2)一个论域上两个覆盖生成相同覆盖广义粗集的充分必要条件;(3)一个覆盖的约简,即一个覆盖能生成原覆盖广义粗集的最小部分;(4)覆盖广义粗集中上下近似运算的相互依赖性;(5)覆盖下近似运算的公理化.     

无线可充能传感器网络的锚点算法与移动设备调度研究

由于传感器的电池容量和存储容量有限,导致无法持续对传感器进行能量补充并收集传感器生成的感测数据。针对该问题,研究了周期性能量补充和数据收集问题,提出了一种用于充能和数据收集的方法,包括基于网格的算法(GBA)、基于支配集的算法(DSBA)和基于圆相交的算法(CIBA)。通过这三种方法或两两相结合的方法找到锚点集合,通过移动设备调度算法调度最小数量的移动设备来访问生成的锚点。仿真结果验证了所提方法的有效性。与联合能量数据采集(JEDA)算法、最小覆盖圆(SEC)算法相比,所提CIBA需要的移动设备数量最少,总移动距离也最短,具有良好的综合性能。     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。