求解最小覆盖问题的快速近似算法的进一步研究

分析了已有求覆盖平面上给定的若干个点的尽可能小的圆的问题的算法。给出了一个新的求解最小覆盖问题的算法，其计算时间复杂度为平面上给定的点数量的线性函数，该算法已编程实现，通过几万例随机算例的实际计算比较，表明算法所得结果的平均精度比已有的各种快速近似算法所得的精度要高，而且具体每例所需的计算时间均比已有快速近似算法对应的计算时间要短。     

覆盖平面上给定点集的最小凸多边形的算法

研究求覆盖平面上给定的若干个点的最小凸多边形的算法．给出了两种算法，讨论了算法的基本思想，描述了算法步骤，得出了算法的时间复杂度．结果表明，算法的平均计算时间复杂度为平面上给定点的数量的线性函数，即为Ο（ｎｍ），在最坏情况下可为Ο（ｍ２）     

一种求解带权集合覆盖问题的近似算法

以优化形式描述的集合覆盖问题是一个NP难问题,设计快速有效的近似算法,具有重要的理论与现实意义.基于贪心算法思想,提出了一种求解带权集合覆盖问题的近似算法,并讨论了该算法的相对近似比.     

具有通用机的多组工件的Q//C_(max)问题的近似算法

研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。     

预算型最大覆盖问题的近似算法

研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.     

具有通用机的四组工件排序问题

为解决实践中对多组任务的优化排序问题，文中提出了一种改进的最长工作优先安排（LPT）的算法，利用“最大相对加工时间”准则和“首先空闲”准则，讨论了将四组工件安排在四台速度相同的专用机、一台同速度的通用机上的Gmax问题，得到了利用该近似算法所得的解丁与最优解T^＊的一个估计：T/T^＊≤5/4，结果表明，采用该近似算法对工件排序，在最差情况下要比最优排序多出1/4的时间。     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

基于时间满意的集覆盖问题及若干贪婪算法应用研究

传统的选址问题过于简单地考量时间这一对企业竞争力影响重大的因素。针对这一特点，对时间满意度函数进行了定义，从顾客角度考虑覆盖半径，从企业角度考虑覆盖比例，提出比传统集覆盖问题更一般的基于时间满意的覆盖选址问题。在给定的网络G（V，A）中，以最小化总的建站成本为目标建立这一问题的整数规划模型，并应用3种被证明为在覆盖选址问题中计算效果很好的贪婪算法对不同规模的问题进行求解计算。     

社交网络中求最小正影响支配集的改进算法

网络中求解最小正影响支配集的问题已经被证明是NP难问题,且已有性能较好的贪心求解算法．通过分析现有的贪心近似算法（Wang-Greedy）和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy)．理论分析表明,Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度．在一些较大规模的真实社交网络实例中的实验研究表明,Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高．     

利用旧井点的钻井布局模型

根据平移变换的性质，先将问题一转化为求单位网络[0，1]×[0，1]内的点集的最大覆盖问题，提出了算值计算方法并对此给出了数学证明．然后，利用问题一的数值算法，构造了问题二的近似算法.对本文提供的算例，结出了问题一的精确解．对于问题二，给出了近似解．     

基于局部搜索策略的车间作业调度问题的算法研究

为车间作业调度问题提供了一个快速、易于实现的近似算法．该算法基于局部搜索策略,采用特殊的邻域构造方法,即邻域的构造仅与关键路径上的工序相关．该算法找到了所测试的14个标准算例中12算例的最优解,而且在PⅡ233的计算机上每个算例的计算时间不超过1s。     

最优顶点覆盖的贪心边近似算法

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证（能得到最优覆盖点数）时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.     

染色的装箱问题及其近似算法

给出了染色装箱问题和染色覆盖问题的数学描述,得到了给定颜色限制的染色装箱问题和染色覆盖问题的两个近似算法.     

基于三维点云的工程结构平面分割及表面检测

为了实现对工程结构各平面更加全面、快速、准确的数字化检测,本文提出了一种基于三维点云的工程结构平面自动分割及表面检测方法。首先,通过无人机重建满足工程检测精度要求的高精度三维点云模型;其次,融合体素降采样方法、随机采样一致性(RANSAC)方法和基于密度的聚类算法(DBSCAN),快速、精准、自动地分割工程结构的特征平面,避免手动分割过程中存在的结果不确定及计算效率低的问题;第三,通过设计的精细分割算法有效剔除特征平面周围的噪点,准确提取结构特征平面点云,计算分析特征平面点云,数字化描述结构的表面形状;最后,通过一个在建地铁车站深基坑工程实例,系统地验证了该方法的有效性和准确性。研究结果表明：设计的三维点云平面自动分割算法能够实现工程结构各个平面快速准确的自动分割,自动分割与手动分割结果的交并比接近90%;针对工程结构平面的表面检测算法能够实现结构表面形状的准确测量,有效映射结构物理表面的状态。     

平面数据点集的整体B样条曲线逼近

讨论了给定平面数据点集的整体B样条逼近，给出了逼近算法和逼近精度的判别，并就不同约束条件下得到的逼近曲线进行了比较。所给算法生成的B样条曲线插值于首末两个数据点。     

奖励收集顶点覆盖问题的一个2-近似算法

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。     

利用二次曲线拟合和圆环点进行摄像机标定

为了提高摄像机标定的精度和实用性，提出一种新的标定算法．所用的标定模板由平面上两个相交的圆周组成，且两圆的圆心和半径均未知，通过对两圆的图像进行二次曲线拟合，再根据拟合的二次曲线来计算圆环点图像完成标定过程．与经典的平面标定算法相比，该算法无需进行角点检测和角点匹配，不需人工干预即可实现自动化标定，且在标定过程引入了更多的图像点信息．模拟实验结果表明，在实际的噪声水平下，该算法对焦距的相对标定误差比平面标定算法减小约0．1%，此时主点的相对标定误差也略小于平面标定算法．真实图像的实验结果也表明，所提算法具有较好的精度和实用性．     

管内声传播计算的一种差分方法

本文在［４］基础上改进了边界格点处理，得到了一个比［４］精度更好的差分格式，而不增加计算时间。等截面管道声传播问题的算例表明：达到同样精度时本文格式ＣＰＵ的时间只是［４］的到。本文还利用简单的坐标变换，引入声学速度势及本文格式计算了没有流动与具有流动的对称变截面管道声传播问题，算例表明与已有结果比较符合良好。     

基于贪心算法的离散单位圆盘覆盖问题研究

提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解.首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖.基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆.最小覆盖圆的中心视为选址位置.基于具体案例证明了算法的有效性.讨论了该算法的影响因素,分析了时间复杂度以及近似度比率.     

多时间尺度电力系统稳定域边界校正法

研究了多时间尺度电力系统稳定域边界的校正问题.将奇异摄动理论应用于多时间尺度动力系统,给出了精确慢流形的逐次近似算法,从而获得系统的有效近似慢流形;基于近似慢流形提出了稳定域局部边界的校正法,所给算法利用5阶双时间尺度电力系统模型进行仿真计算.仿真结果表明所得校正边界比简化局部边界更接近稳定域边界,较好地提高了稳定域局部边界的计算精度.